2 of 35

Architecture of a DBMS

Completed

And We’ll Visit

You are Here

Database Management

System

Database

Query Parsing�& Optimization

Relational Operators

Files and Index Management

Buffer Management

Disk Space Management

SQL Client

3 of 35

Recall: Heap Files

Unordered collection of records
Recall API for higher layers of the DBMS. �Today we’ll ask: “How? At what cost?”

Insert/delete/modify record
Fetch a particular record by record id …

Record id is a pointer encoding pair of (pageID, location on page)

Scan all records

Possibly with some conditions on the records to be retrieved

4 of 35

Recall: Multiple File Organizations

Many alternatives exist, each good in some situations and less so in others.

This is a theme in DB systems work!

Heap Files: Suitable when typical access is a full scan of all records
Sorted Files: Best for retrieval in order, or when a range of records is needed
Clustered Files & Indexes: Group data into blocks to enable fast lookup and efficient modifications.

More on this soon …

5 of 35

Bigger Questions

What is the “best” file organization?

Depends on access patterns …
How? What are common access patterns anyway?

Can we be quantitative about tradeoffs?

If one is better … by how much?

6 of 35

Goals

Big picture overheads for data access

We’ll (overly) simplify performance models to provide insight, not to get perfect performance
Still, a bit of discipline:

Clearly identify assumptions up front
Then estimate cost in a principled way

Foundation for query optimization

Can’t choose the fastest scheme without an estimate of speed!

7 of 35

COST MODEL AND ANALYSIS

8 of 35

Cost Model for Analysis

B: The number of data blocks in the file
R: Number of records per block
D: (Average) time to read/write disk block
Focus: Average case analysis for uniform random workloads
For now, we will ignore

Sequential vs Random I/O
Pre-fetching
Any in-memory costs

Good enough to show the overall trends

Block 1

Block 2

…

Block B

Record 1

Record 2

…

Record R

9 of 35

More Assumptions

Single record insert and delete
Equality selection – exactly one match
For Heap Files:

Insert always appends to end of file.

For Sorted Files:

Packed: Files compacted after deletions.
Sorted according to search key

10 of 35

Extra Challenge

After understanding these slides …

You should question all these assumptions and rework
Good exercise to study for tests, and generate ideas

11 of 35

Heap Files & Sorted Files

B: The number of data blocks = 5
R: Number of records per block = 2
D: (Average) time to read/write disk block = 5ms

2, 5

1, 6

4, 7

3, 10

8, 9

Heap File

1, 2

3, 4

5, 6

7, 8

9, 10

For illustration, records are just integers

Sorted File

12 of 35

Cost of Operations: Scan?

B: The number of data blocks = 5
R: Number of records per block = 2
D: (Average) time to read/write disk block = 5ms

	Heap File	Sorted File
Scan all records
Equality Search
Range Search
Insert
Delete

13 of 35

Scan All Records

B: The number of data blocks
R: Number of records per block
D: Average time to read/write disk block
Pages touched: ?
Time to read the record: ?

2, 5

1, 6

4, 7

3, 10

8, 9

Heap File

1, 2

3, 4

5, 6

7, 8

9, 10

Sorted File

14 of 35

Cost of Operations: Scan Cost

B: The number of data blocks
R: Number of records per block
D: Average time to read/write disk bloc

	Heap File	Sorted File
Scan all records	B*D	B*D
Equality Search
Range Search
Insert
Delete

15 of 35

Cost of Operations: Equality Search?

B: The number of data blocks
R: Number of records per block
D: Average time to read/write disk block

	Heap File	Sorted File
Scan all records	B*D	B*D
Equality Search
Range Search
Insert
Delete

16 of 35

Find Key 8: Heap File

P(i): Probability that key is on page i is 1/B
T(i): Number of pages touched if key on page i is i
Therefore the expected number of pages touched
Pages touched on average?

Heap File

2, 5

1, 6

4, 7

3, 10

8, 9

17 of 35

Find Key 8: Sorted File

Worst-case: Pages touched in binary search

log₂B

Average-case: Pages touched in binary search

log₂B?

Sorted File

1, 2

3, 4

5, 6

7, 8

9, 10

18 of 35

Average Case Binary Search

Expected Number of Reads: 1 (1 / B) + 2 ( 2 / B) + 3 (4 / B) + 4 (8 / B)

19 of 35

Average Case Binary Search cont

Expected Number of Reads: 1 (1 / B) + 2 ( 2 / B) + 3 (4 / B) + 4 (8 / B)

1 IO

2 IOs

3 IOs

4 IOs

20 of 35

Cost of Operations: Equation Search Cost

B: The number of data blocks
R: Number of records per block
D: Average time to read/write disk block

	Heap File	Sorted File
Scan all records	B*D	B*D
Equality Search	0.5BD	(log₂B)*D
Range Search
Insert
Delete

21 of 35

Cost of Operations: Range Search?

B: The number of data blocks
R: Number of records per block
D: Average time to read/write disk block

	Heap File	Sorted File
Scan all records	B*D	B*D
Equality Search	0.5BD	(log₂B)*D
Range Search
Insert
Delete

22 of 35

Find Keys Between 7 and 9: Heap File

Always touch all blocks. Why?

Heap File

2, 5

1, 6

4, 7

3, 10

8, 9

23 of 35

Find Keys Between 7 and 9: Comparison

Find beginning of range
Search for start of range
Scan right

Heap File

2, 5

1, 6

4, 7

3, 10

8, 9

Sorted File

1, 2

3, 4

5, 6

7, 8

9, 10

24 of 35

Cost of Operations: Range Search Cost

B: The number of data blocks
R: Number of records per block
D: Average time to read/write disk block

	Heap File	Sorted File
Scan all records	B*D	B*D
Equality Search	0.5BD	(log₂B)*D
Range Search	B*D	((log₂B)+pages)*D
Insert
Delete

25 of 35

Cost of Operations: Insert?

B: The number of data blocks
R: Number of records per block
D: Average time to read/write disk block

	Heap File	Sorted File
Scan all records	B*D	B*D
Equality Search	0.5BD	(log₂B)*D
Range Search	B*D	((log₂B)+pages)*D
Insert
Delete

26 of 35

Insert 4.5: Heap File

Stick at end of file
Cost = 2*D
Why 2?

Heap File

2, 5

1, 6

4, 7

3, 10

8, 9

4.5,_

27 of 35

Insert 4.5: Heap VS Sorted File

Read last page, append, write. Cost = 2*D
Find location for record. Cost = log₂BD

Heap File

2, 5

1, 6

4, 7

3, 10

8, 9

4.5,

Sorted File

1, 2

3, 4

5, 6

7, 8

9, _

28 of 35

Insert 4.5: Heap Vs Sorted Pt 2

Read last page, append, write. Cost = 2*D
Find location for record. Cost = log₂BD
Insert and shift rest of file

1, 2

3, 4

5, 6

7, 8

9, 10

2, 5

1, 6

4, 7

3, 10

8, 9

4.5,

10, _

Heap File

Sorted File

4.5, 5

6, 7

8, 9

29 of 35

Cost of Operations: Insert Cost

B: The number of data blocks
R: Number of records per block
D: Average time to read/write disk block

	Heap File	Sorted File
Scan all records	B*D	B*D
Equality Search	0.5BD	(log₂B)*D
Range Search	B*D	((log₂B)+pages)*D
Insert	2*D	((log₂B)+B)*D
Delete

30 of 35

Cost of Operations: Delete?

B: The number of data blocks
R: Number of records per block
D: Average time to read/write disk block

	Heap File	Sorted File
Scan all records	B*D	B*D
Equality Search	0.5BD	(log₂B)*D
Range Search	B*D	((log₂B)+pages)*D
Insert	2*D	((log₂B)+B)*D
Delete

31 of 35

Delete 4.5: Heap File

Average case to find the record: B/2 reads
Delete record from page
Cost = (B/2 + 1) * D

Why + 1?

Heap File

2, 5

1, 6

4, 7

3, 10

8, 9

4.5,

32 of 35

Delete 4.5: Heap File Vs Sorted File

Average case runtime: (B/2+1) * D
Find location for record: log₂B
Delete record in page 🡪 Gap

Heap File

2, 5

1, 6

4, 7

3, 10

8, 9

Sorted File

1, 2

3, 4

4.5, 5

6, 7

8, 9

10, _

33 of 35

Delete 4.5: Heap File Vs Sorted File Pt 2

Average case runtime: (B/2+1) * D
Find location for record: log2B
Shift the rest by 1 record 2 * (B/2)

Heap File

2, 5

1, 6

4, 7

3, 10

8, 9

Sorted File

1, 2

3, 4

__, 5

6, 7

8, 9

10, _

7, 8

9, 10

34 of 35

Cost of Operations Complete

B: The number of data blocks
R: Number of records per block
D: Average time to read/write disk block

	Heap File	Sorted File
Scan all records	B*D	B*D
Equality Search	0.5BD	(log₂B)*D
Range Search	B*D	((log₂B)+pages)*D
Insert	2*D	((log₂B)+B)*D
Delete	(0.5B+1)D	((log₂B)+B)*D

35 of 35

Cost of Operations Complete Pt 2

B: The number of data blocks
R: Number of records per block
D: Average time to read/write disk block
Can we do better?

Indexes!

	Heap File	Sorted File
Scan all records	B*D	B*D
Equality Search	0.5BD	(log₂B)*D
Range Search	B*D	((log₂B)+pages)*D
Insert	2*D	((log₂B)+B)*D
Delete	(0.5B+1)D	((log₂B)+B)*D