IO Cost Model: Algorithmic Complexity for Big Data
Concept. For data larger than RAM, total runtime is dominated by IO. Model cost as C_r × pages_read + C_w × pages_written and ignore CPU.
Intuition. With Listens at a billion rows, a full table scan reads thousands of 64 MB pages and takes minutes on disk. The CPU work to compare 4.5 > 4.0 takes negligible time. Total runtime is C_r × pages_read + C_w × pages_written.
Small Data vs Big Data: Where the Cost Sits
-
Small data (< 10 GB): count CPU operations. Everything fits in RAM, so we measure CPU costs.
-
Big data (> 100 GB): count IOs, pages read and written. IO costs dominate; CPU costs are trivial by comparison.
Key Notation for IO Costs
Figure: IO cost notationThe IO cost formula and the symbols it uses. IO cost equals C_r times the pages read plus C_w times the pages written. C_r is the time to read one page and C_w the time to write one page, both shown in orange. P(R) is the number of pages in table R and T(R) = n is the number of rows (tuples) in R. Color key: orange marks the two per-page costs C_r and C_w.
Figure 1. Cost counts page I/Os, not CPU work. Cr and Cw are the time to read or write one page; P(R) is the pages in table R and T(R) = n its row count. Every algorithm's cost is Cr × pages read + Cw × pages written.
Three Examples: Building Your Intuition
Figure: Three algorithms: count the pagesThree algorithms and their IO cost, revealed one at a time. Example 1, basic: read and write every page once, cost C_r times P(R) plus C_w times P(R). Example 2, multi-pass: read every page seven times and write three times, cost C_r times seven P(R) plus C_w times three P(R). Example 3, logarithmic: read log P(R) passes and write a tenth of the pages per row, cost C_r times log P(R) times P(R) plus C_w times 0.1 P(R) times T(R). Color key: orange is the cost formula.
Figure 2. Three algorithms, each costed by the pages it touches. Example 1 reads and writes every page once; Example 2 makes seven read passes and three write passes; Example 3 reads log P(R) passes and writes a tenth of the pages per row. The cost is the page count; the CPU work is negligible.
The Big Picture
-
** Sorting at O(n log n)** - That's for CPU complexity in RAM. Paging big data is much more expensive.
-
Count IOs: N, 2N, 3N - Paging data is what really determines runtime.
-
Smart algorithms minimize disk access. Save one IO, and you've saved 10 million CPU/GPU operations.
Calculating Read and Write Costs
The cost of reading one page, and of an algorithm:
$$ C_r = \text{access time} + \frac{\text{page size}}{\text{scan speed}} $$
$$ \text{IO cost} = C_r \times \text{pages read} + C_w \times \text{pages written} $$
| Device (2025+) | Access time | Scan speed | Cr, one 64 MB page |
|---|---|---|---|
| RAM | 100 ns | 100 GB/s | 0.00064 s |
| SSD | 10 μs | 5 GB/s | 0.01281 s |
| HDD | 10 ms | 100 MB/s | 0.65 s |
| Network | 1 μs | 10 GB/s | 0.00640 s |
Page size is 64 MB unless a problem says otherwise; units are decimal (1 MB = 1,000,000 bytes, 1 GB = 1,000,000,000 bytes). In practice a write can cost more than a read; unless a problem says otherwise, CS145 uses Cw = Cr.
CS145 Equations (v1.3)
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) |