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

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

Log-scale chart of join IO cost vs buffer B for Songs3 100 GB joined with Listens3 1 TB at C_r=C_w=1: solid BNLJ falls steeply from 2.6M to 18K as B grows, dashed SMJ-best eases from 159K to 54K, dotted HPJ-best is flat at ~54K, a green divider marks the crossover where HPJ stops being cheapest and BNLJ takes over.

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

  1. Cloud Environments: With variable RAM allocation per query, HPJ often wins due to its consistent performance

  2. SSDs vs HDDs: SSDs have C_r ≈ C_w, while HDDs often have C_w > C_r

  3. Memory-Rich Systems: BNLJ becomes optimal when B is large enough to hold significant chunks

  4. Multi-Query Workloads: Conservative B estimates favor HPJ's predictable performance

Key Takeaways

  1. Just 5 algorithms power most database operations.

  2. Memory (B) determines which algorithm is best.

  3. No memorization needed. Formulas follow intuition.