IO Algorithms: Cost Analysis & Intuition
Concept. The IO cost of every algorithm in this module (BigSort, HashPartition, BNLJ, SMJ, HPJ) is a function of table size, buffer size, and the read/write cost ratio.
Intuition. Each algorithm minimizes IO in a different range of buffer sizes and input properties. Small B favors HPJ. Large B favors BNLJ. Pre-sorted input favors SMJ.
CS145 Equations Sheet
CS 145 Equations Reference - v1.3
Source: CS 145 Equations PDF (Updated 9/1/25)
Many CS algorithms assume data fits in RAM and focus on a CPU cost model (e.g., O(n log n) for Sorting). "Big" data does not fit in RAM.
Our Goal: Model IO Costs for working with data in (slow) SSD/HDDs and RAM (versus fast CPUs)
[1] Basic IO Cost Model for RAM, SSD, HDD
Assumption: 1 (disk) Block = 1 (RAM) Page
Core Formulas
-
Number of Pages:
numPages = ⌈numMBs / pageSize⌉ -
IO Costs:
- Read Cost per page: \(C_r = 1\) IO
-
Write Cost per page: \(C_w = k\) IOs (where \(1 \leq k \leq 10\) based on hardware, default: \(k = 1\))
-
Time per IO (seconds):
Time = accessLatency + (pageSize / scanSpeed)
Example
- Given: pageSize = 64 MBs, numMBs = 630 MBs, SSD: accessTime = 10 μs, scanSpeed = 5 GBps
- numPages = \(\lceil \frac{630 \text{ MB}}{64 \text{ MBs}} \rceil = 10\)
- \(C_r\) = \(1 \text{ IO} = 10 \text{ μs} + \frac{64 \text{ MB}}{5 \text{ GBps}}\) secs
- Time to read 10 pages = \(10 \times C_r\)
- Time to read 100 pages on 20 machines = \(5 \times C_r\)
[2] HP and BigSort 'R' on Column X
Variables:
- T(R) = # of rows in R
- P(R) = # of pages in R
- B = # of RAM pages (buffer)
Core Formulas
-
HashPartition(R):
IOCost = (Cr + Cw) × P(R) -
BigSort(R):
Let N = P(R) IOCost = (Cr + Cw) × N × (1 + ⌈log_B(N/2B)⌉)
Special Case for BigSort(R) when \(C_r = C_w = 1\):
- (Small data) \(N \leq 2B\)? IOcost = \(2N\)
- If \(2B < N \leq 2B^2\)? IOcost = \(4N\)
- If \(2B^2 < N \leq 2B^3\)? IOcost = \(6N\)
Example (\(C_r = C_w = 1\))
- Given: P(R) = 1000, B = 100
- HP(R) = \(2 \times 1000 = 2000\) IOs
- BigSort(R) = \(2 \times 1000 \times (1 + \lceil \log_{100} \frac{1000}{2 \times 100} \rceil) = 4000\) IOs
[3] Basic JOIN(R, S) on Column X
Variable: - OUT = number of output pages for a JOIN (depends on number of matching tuples and row size of JOIN result)
Core Formula
- BNLJ(R, S) - Block Nested Loop Join:
IOCost = Cr × (P(R) + P(S) × ⌈P(R)/B⌉) + Cw × OUT
Note: Pick BNLJ(S, R) if cheaper
Example (\(C_r = C_w = 1\))
- Given: P(R) = 1000, P(S) = 2000, B = 100
- BNLJ(R, S) = \(1000 + 2000 \times \lceil \frac{1000}{100} \rceil + OUT\)
- BNLJ(S, R) = \(2000 + 1000 \times \lceil \frac{2000}{100} \rceil + OUT\)
[4] HPJ(R, S) on Column X
Core Formulas
-
HPJ(R, S) - Hash Partition Join:
IOCost = HP(R) + HP(S) + PJ(R, S) + Cw × OUT -
Hash Partition cost:
HP(R) = (Cr + Cw) × P(R) // Same for HP(S) -
Partition Join cost PJ(R, S):
- ("Ideal"-case): \(C_r \times (P(R) + P(S))\)
- Skew? Try different hash
-
Many duplicates? Try different algorithm!
-
HPJ(R, R) - Self-join:
HPJ(R, R) = HP(R) + Cr × P(R) + Cw × OUT
Special Case (\(C_r = C_w = 1\))
- HPJ(R, S) = \(3(P(R) + P(S)) + OUT\)
Example (\(C_r = C_w = 1\))
- Given: P(R) = 1000, P(S) = 2000, B = 100
- HPJ(R, S) = \(3 \times (1000 + 2000) + OUT\)
- HPJ(R, R) = \(3 \times 1000 + OUT\)
[5] SMJ(R, S) with JOIN on Column X
Core Formulas
-
SMJ(R,S) - Sort-Merge Join:
IOCost = BigSort(R) + BigSort(S) + MergeJoin(R, S) + Cw × OUT -
MergeJoin(R, S) with JOIN on column X:
- (Best-case: No Backup): \(C_r \times (P(R) + P(S))\)
-
(Worst-case: All Backup): \(C_r \times P(R) \times P(S)\)
-
SMJ(R, R) - Self-join:
- (Best-case: No Backup): \(BigSort(R) + C_r \times P(R) + C_w \times OUT\)
-
(Worst-case: All Backup): \(BigSort(R) + C_r \times P(R) \times P(R) + C_w \times OUT\)
-
Pre-sorted optimization: If R is pre-sorted, BigSort(R) = 0. (Same for S.)
Example (\(C_r = C_w = 1\))
- Given: P(R) = 1000, P(S) = 2000, B = 100
- SMJ(R, S) = 4000 + 8000 + 3000 + OUT IOs
- BigSort(R) = \(2 \times 1000 \times (1 + \lceil \log_{100} \frac{1000}{2 \times 100} \rceil) = 4000\)
- BigSort(S) = \(2 \times 2000 \times (1 + \lceil \log_{100} \frac{2000}{2 \times 100} \rceil) = 8000\)
- MergeJoin(R, S) = 3000 IOs (no backup)
- MergeJoin(R, S) = 1000 × 2000 IOs (full backup)
[6] Indexing: Hash Index and B+ Trees
Variables
- n: Number of data rows
- N: Number of data pages
- d: Data row size
- k: Key size
- p: Pointer size
- M: Page size
- h: Index height
Core Formulas
-
Data Pages:
N = ⌈(n × d) / M⌉ -
Index Fanout:
f = ⌊M / (k + p)⌋ -
Hash Index (Unsorted):
P(index) = ⌈n / f⌉ -
Hash Index (Sorted):
P(index) = ⌈N / f⌉ -
B+ Tree Height (Unsorted):
h ≈ ⌈log_f(n)⌉ -
B+ Tree Height (Sorted):
h ≈ ⌈log_f(N)⌉ -
Query IOs:
IOCost ≈ h + 1 (index IO + data IO)
Example Values
- Given: M = 64MB, k = 8 bytes, p = 8 bytes, n = 10¹², d = 1024 bytes
- f = \(\lfloor \frac{64 \times 1024 \times 1024}{8 + 8} \rfloor = 4,194,304\)
- N = \(\lceil \frac{10^{12} \times 1024}{64 \times 1024 \times 1024} \rceil = 15,258,790\)
- B+ Tree height (unsorted): \(\lceil \log_{4,194,304}(10^9) \rceil = 2\)
- B+ Tree height (sorted): \(\lceil \log_{4,194,304}(15,258,790) \rceil = 2\)
Summary of Notation
| Symbol | Meaning |
|---|---|
| \(C_r\) | Read cost per page (1 IO) |
| \(C_w\) | Write cost per page (k IOs, typically k=1) |
| \(P(R)\) | Number of pages in table R |
| \(T(R)\) | Number of rows in table R |
| \(B\) | Buffer size (number of RAM pages) |
| \(OUT\) | Number of output pages from JOIN |
| \(\lceil x \rceil\) | Ceiling function (round up) |
| \(\lfloor x \rfloor\) | Floor function (round down) |
Real-World Examples: Choosing the Right Join Algorithm
Assume C_r = C_w = 1. For the JOINs below, we always add OUT (for the size of the output result). Always use the Equation Sheet for the full formulae.
Test Setup: B = 100 pages (≈ 6.4 GB RAM), Page Size = 64 MB
These examples use realistic table sizes from actual database workloads. Costs shown are simplified for clarity; real optimizer costs include additional factors.
Scenario Overview
| Example | Description | Table R | Table S | Special Conditions | Key Insight |
|---|---|---|---|---|---|
| Ex1 | Small Tables | Songs 10 GB |
Listens 10 GB |
none | Tables fit mostly in RAM |
| Ex2 | Large Tables | Songs 100 GB |
Listens 2 TB |
none | Tables >> buffer size |
| Ex3 | Pre-sorted Tables | Songs ↑ 100 GB sorted |
Listens ↑ 2 TB sorted |
Pre-sorted | SMJ skips sorting phase |
| Ex4 | Self-Join | Listens 2 TB |
Listens 2 TB (same) |
Self-join | Can't optimize table order |
| Ex5 | Song Similarity | Listens 100B rows |
Listens 100B rows |
Massive | Real-world similarity query |
Algorithm performance vs buffer size
Figure: Join IO cost versus buffer size, log scaleA log-scale line chart of IO cost against buffer size B for the same join, Songs3 100 GB by Listens3 1 TB, at C_r = C_w = 1. Buffer grows left to right: 10, 100, 1000, 10000 pages. BNLJ, the solid ink line, starts highest at 2.6M IOs and drops steeply to 18K as the buffer grows. SMJ-best, the dashed line, falls gently from 159K to 54K. HPJ-best, the dotted line, is flat at about 54K. A green crossover divider marks where the cheapest algorithm switches: HPJ is cheapest at small buffers, BNLJ at large buffers. Numbers are verified from the Module 3 NanoDB colab. Color key: green is the crossover and the winning regions; ink and grey are the cost lines and axes.
Figure 1. HPJ-best stays near 54K because partitioning does one read and one write independent of B. BNLJ drops from 2.6M to 18K because larger B reduces rescans of the inner table. SMJ-best drops as larger initial runs reduce merge passes. The crossover marks the point where BNLJ becomes cheaper than HPJ at this scale. SMJ with many duplicates can rescan during merge. HPJ with heavy skew can create oversized partitions, each up to 2 to 10x worse.
Exercise 2: Impact of Machine Configuration on IO Costs
Scenario: Songs3 (100GB) × Listens3 (1TB)
-
Songs3: 100GB = 1,600 pages
-
Listens3: 1TB = 16,384 pages
-
Row size: 1024 bytes
Key insight. Different machines have varying RAM (32 GB to 640 GB) and IO devices with different C_r and C_w costs. Query optimizers may allocate only 20 to 60% of RAM per query when running parallel workloads, which changes which algorithm wins.
Cost Analysis Across Different Configurations
| Buffer Size (B) |
C_r | C_w | BNLJ | BNLJ-rev | SMJ-best | HPJ-best | Winner |
|---|---|---|---|---|---|---|---|
| 10 (tiny) |
1 | 1 | 2.6M | 2.6M | 159K | 54K | HPJ |
| 1 | 10 | 2.6M | 2.6M | 792K | 216K | HPJ | |
| 10 | 1 | 26M | 26M | 954K | 378K | HPJ | |
| 10 | 10 | 26M | 26M | 1.6M | 540K | HPJ | |
| 100 (small) |
1 | 1 | 264K | 279K | 90K | 54K | HPJ |
| 1 | 10 | 264K | 279K | 414K | 216K | HPJ | |
| 10 | 1 | 2.6M | 2.8M | 575K | 378K | HPJ | |
| 10 | 10 | 2.6M | 2.8M | 899K | 540K | HPJ | |
| 1,000 (medium) |
1 | 1 | 34K | 44K | 87K | 54K | BNLJ |
| 1 | 10 | 34K | 44K | 396K | 216K | BNLJ | |
| 10 | 1 | 344K | 436K | 558K | 378K | BNLJ | |
| 10 | 10 | 344K | 436K | 867K | 540K | BNLJ | |
| 10,000 (large) |
1 | 1 | 18K | 20K | 54K | 54K | BNLJ |
| 1 | 10 | 18K | 20K | 216K | 216K | BNLJ | |
| 10 | 1 | 180K | 196K | 378K | 378K | BNLJ | |
| 10 | 10 | 180K | 196K | 540K | 540K | BNLJ |
Key Observations
Buffer Size Impact
- Small B (10-100): HPJ dominates
- Medium B (1,000): BNLJ becomes competitive
- Large B (10,000): BNLJ wins.
Read/Write Cost Impact
- High C_w: inflates the algorithms that write intermediate data (SMJ's sort, HPJ's partition). BNLJ only reads, so it is untouched.
- High C_r: all costs scale up together; the winner is unchanged.
- At fixed B the winner here never flips on C_r or C_w. Expensive writes just widen BNLJ's lead once B is large.
Practical Implications
-
Cloud Environments: With variable RAM allocation per query, HPJ often wins due to its consistent performance
-
SSDs vs HDDs: SSDs have C_r ≈ C_w, while HDDs often have C_w > C_r
-
Memory-Rich Systems: BNLJ becomes optimal when B is large enough to hold significant chunks
-
Multi-Query Workloads: Conservative B estimates favor HPJ's predictable performance
Key Takeaways
-
Just 5 algorithms power most database operations.
-
Memory (B) determines which algorithm is best.