I/O Cost Calculation for Query Plans

Why Cost a Plan?

A query optimizer's primary job is to choose the cheapest physical plan from a vast number of alternatives. To do this, it needs a quantitative way to compare them. It can't actually run every possible plan—that would defeat the purpose of optimization. Instead, it uses a cost model to estimate the cost of each plan without executing it.

While a true cost model might include CPU, memory, and network usage, the dominant factor for large, disk-resident datasets is almost always the number of disk I/Os. For this reason, we will follow the standard practice of defining cost as the total number of page I/Os required to execute the plan.

From Logical Plan to Costed Physical Plan

Let's watch a segment from the CMU "Query Planning & Optimization" lecture. It provides an excellent high-level overview of how an optimizer takes a simple SQL query, constructs a physical plan, and starts attaching cost estimates to each operator in the plan tree, working its way from the bottom up.

As you saw, costing a plan is a bottom-up process. The estimated output of a lower operator (in terms of pages) becomes the input for the operator above it. This makes our previous work on cardinality estimation absolutely critical.

The Cost of Individual Operators

The total cost of a plan is the sum of the costs of its constituent physical operators. Let's briefly revisit the I/O cost formulas for the main operators we've studied. These formulas are the building blocks of our overall cost calculation.

We'll use the following notation:

• B(R): Number of pages in relation R.
• T(R): Number of tuples (records) in relation R.
• M: Number of available buffer pool pages.

These are simplified formulas. A real optimizer's cost model is more complex, but this captures the core logic.

A Worked Example: Comparing Physical Plans

Now, let's put it all together. We will analyze a single SQL query and calculate the cost for three different physical plans that could execute it. This will demonstrate how different choices of join algorithms and access paths lead to vastly different costs.

The example comes from the University of Washington's database course.

Query and Statistics:

SELECT sname 
FROM Supplier x, Supply y 
WHERE x.sno = y.sno 
  AND y.pno = 2 
  AND x.scity = 'Seattle' 
  AND x.sstate = 'WA';

Catalog Statistics:

• Supplier: T(Supplier) = 1000 records, B(Supplier) = 100 pages.
• Supply: T(Supply) = 10,000 records, B(Supply) = 100 pages.
• V(Supplier, scity) = 20 (20 unique cities)
• V(Supply, pno) = 2500 (2500 unique part numbers)
• We have M = 11 buffer pages available for our operations.

Physical Plan 1: Naive Block Nested Loop Join

This plan does the join first and then applies all the selections "on the fly" as it processes the joined tuples.

Let's calculate the cost. The selections and projection are on-the-fly, so their cost is 0 I/O. The entire cost comes from the join.

• Join Algorithm: Block Nested Loop Join (BNLJ)
• Outer Relation: Supplier (B(Supplier) = 100)
• Inner Relation: Supply (B(Supply) = 100)
• Memory: M = 11

The BNLJ cost formula is B(Outer) + (⌈B(Outer) / (M-2)⌉ * B(Inner)).

Plugging in the numbers:

• Cost = 100 + (⌈100 / (11-2)⌉ * 100)
• Cost = 100 + (⌈100 / 9⌉ * 100)
• Cost = 100 + (12 * 100)
• Cost = 100 + 1200 = 1300 I/Os
  (Note: The value in the image is slightly different due to a different M-1 vs M-2 assumption, but the principle is the same).

This is our baseline cost.

Pipelining vs. Materialization: A Critical Distinction

In Plan 1, we assumed the selections were pipelined. But what if we pushed the selections down and materialized the results?

• Materialization: An operator writes its entire output to a temporary relation on disk. The next operator then reads from that temporary relation. This incurs I/O for both the write and the subsequent read.
• Pipelining: An operator passes its output tuples directly to the next operator in memory, one-by-one or in small batches. This avoids the intermediate I/O.

Most optimizers, including the classic System R optimizer, strongly prefer pipelining and assume intermediate results are not materialized unless an operator is "blocking" (like a sort, which needs to see all its input before producing any output).

This next resource provides an excellent, detailed explanation of how materialization decisions affect the final I/O cost calculation.

Physical Plan 2: Pushing Selections Down (with Materialization)

Let's apply the concept from the reading. We'll create a plan that filters Supplier and Supply first, writes the small, filtered results to temporary tables, and then joins them.

Step 1: Filter Supplier

• Scan Supplier (100 I/Os).
• Apply scity='Seattle'. Selectivity = 1/V(scity) = 1/20.
• Estimated output size = 1/20 * B(Supplier) = 1/20 * 100 = 5 pages.
• Cost: 100 (read) + 5 (write temp T1) = 105 I/Os.

Step 2: Filter Supply

• Scan Supply (100 I/Os).
• Apply pno=2. Selectivity = 1/V(pno) = 1/2500.
• Estimated output size = 1/2500 * T(Supply) = 1/2500 * 10000 = 4 tuples. This is much less than a page, so we'll say it's 1 page.
• Cost: 100 (read) + 1 (write temp T2) = 101 I/Os.

Step 3: Join Filtered Results (T1 and T2)

• We use BNLJ to join T1 (5 pages) and T2 (1 page). Let's make T2 the outer relation to be efficient.
• Cost = B(T2) + (⌈B(T2) / (M-2)⌉ * B(T1))
• Cost = 1 + (⌈1 / 9⌉ * 5) = 1 + (1 * 5) = 6 I/Os.

Total Cost = 105 (Filter S) + 101 (Filter R) + 6 (Join) = 212 I/Os.

By filtering first, even with the cost of materialization, we've dramatically reduced the cost from 1300 to 212 I/Os!

Physical Plan 3: Using an Index

Now, what if we have indexes? Assume we have an unclustered hash index on Supply.pno.

Step 1: Filter Supply using Index

• We want to find y.pno = 2. An index lookup is perfect for this.
• Cost: 1-2 I/Os to traverse the index + 1 I/O per matching tuple. We estimated 4 matching tuples. Since the index is unclustered, this could be up to 4 I/Os for the data pages.
• Total cost is very low, let's say 5 I/Os. The output is just 4 tuples.

Step 2: Join with Supplier using Index Nested Loop

• We can now stream these 4 tuples into an Index Nested Loop Join. For each of the 4 tuples from Supply, we do an index lookup on Supplier.sno to find the match.
• Assume we also have an index on Supplier.sno. The cost would be 4 * (cost of one index probe on Supplier), which would be very small.

The total cost would be in the single digits, demonstrating the immense power of using indexes to avoid full table scans.

Conclusion

You can now see how an optimizer puts all the pieces together. It combines its knowledge of physical operators, statistics from the catalog, and cardinality estimates to produce a concrete I/O cost for a given plan.

Key Takeaways:

• The cost of a query plan is estimated as the sum of the I/O costs of its physical operators.
• The calculation is done bottom-up: the estimated output size (cardinality) of one operator determines the input size and cost of the next.
• Pipelining (streaming results in memory) is much cheaper than materialization (writing intermediate results to disk), as it avoids write and read I/Os.
• Pushing down selections is highly effective, as it reduces the size of data handled by expensive operators like joins.
• The choice of physical operators (e.g., Index Scan vs. File Scan, Hash Join vs. BNLJ) has a massive impact on the final cost.

Preview of the Next Lesson

We can now cost a single plan. But how does the optimizer explore the exponentially large search space of all possible plans to find a good one? In our next lesson, we will dive into the classic System R dynamic programming algorithm, which systematically builds and costs plans to find an optimal join order.