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.

IO Complexity Fundamentals

Small Data vs Big Data: Where the Cost Sits

On small data the cost is CPU. Everything fits in RAM, so the bottleneck is arithmetic: sorting n values costs O(n log n), and the work is choosing that over O(n²). This holds for datasets under 1GB.

Above 100GB the bottleneck moves to IO. Moving data costs about a million times what the CPU work on it costs, so the target stops being instructions and becomes how often you touch the disk.

Three Examples: Building Your Intuition

Key Notation for IO Costs

The IO Reference Sheet has the full formulas and device specs. The shorthand:

  • C_r, C_w: Time cost to read/write a page (access + transfer time)

  • T(R) = n: Number of tuples (rows) in table R

  • P(R): Number of pages in table R

  • IO Cost: Total cost = numPages × C_r (or C_w)

Example Algorithms

Example 1: Basic Read/Write

Algorithm A1 reads and writes P(R) pages. The cost? Simple:

$$ C_r \times P(R) + C_w \times P(R) $$

Example 2: Multi-Pass

Algorithm A2 reads P(R) pages seven times and writes them three times. CPU operations? 20 times T(R), but they're too fast to matter:

$$ C_r \times 7 \times P(R) + C_w \times 3 \times P(R) $$

Example 3: Logarithmic

Algorithm A3 reads P(R) pages log P(R) times and writes 0.1×P(R) pages T(R) times. It's akin to binary search iterations:

$$ C_r \times \log(P(R)) \times P(R) + C_w \times 0.1 \times P(R) \times T(R) $$

The Big Picture

  1. Forget O(n log n) - That's for CPU complexity, not big data.

  2. Count IOs: N, 2N, 3N - This is what really determines runtime.

  3. Smart algorithms minimize disk access. Save one IO, and you've saved 10 million CPU/GPU operations.