Query Optimizer & Statistics
Concept. The optimizer estimates the cost of alternative plans and chooses the cheapest.
The Journey: SQL to a Plan
Figure: Choose a cheaper plan for the same answerOne left-to-right pipeline of five stages. Stage 1: SQL is declarative, it states the result, not the procedure. Stage 2: parse and bind turn the text into a validated tree, resolving names and types against the catalog. Stage 3: the logical plan applies equivalence-preserving relational-algebra rewrites (predicate pushdown, projection pruning, subquery flattening); this defines the result, every rewrite returns the same rows. Stage 4, the focal stage: the physical-plan search picks a join order, join algorithm, and access path, using dynamic programming that computes the best sub-plan for each subset of tables once and reuses it, so it never enumerates all n factorial orders, and costs each from table statistics; this is where speed is decided. Stage 5: the chosen operator tree executes, routinely about 100 times faster than the naive ordering. Because the logical plan and every plan the search considers are result-equivalent, only speed varies, never the answer. Color key: mint is the physical-plan cost search where speed is decided; grey is the parse, rewrite, and execute scaffolding.
Figure 1. Preserve the query’s result; choose how to compute it using estimated costs.
Algorithm Lego Blocks
The optimizer picks from a catalog of algorithm "blocks" and assembles them into a physical plan. Four families:
Figure: Combine operators into a planRead, join, group, and sort the recommendation query. Choose alternatives for each operation; partitioning and sorting support operators when needed.
Figure 2. For the recommendation query, choose access methods, a join, an aggregation method, and a final sort by count. Partition or sort only where an operator needs it. Compare the complete plans using estimated rows, pages, memory, and existing order.
Statistics: estimating the work
-
Sample: inspect a sample of the table (example: 1% of its rows).
-
Summarize: keep row and page counts, distinct-value counts, common-value frequencies, and histograms of value ranges.
-
Store and use: save these compact summaries in the database’s system catalog, organized by table and column. The optimizer uses them to estimate output rows and compare plan costs.
Example: for WHERE user_id BETWEEN 1 AND 100, suppose the statistics estimate that 1% of rows match. That is the selectivity. With 1 million input rows, the estimated output cardinality is 1,000,000 × 1% = 10,000 rows.
For our recommendation query, distinct counts and common-value frequencies help estimate join matches and the number of song groups. These row estimates determine the page counts used in the cost formulas.
When statistics go stale
As data changes, old summaries can lead to poor plan choices. Run ANALYZE to refresh them; PostgreSQL can also do this automatically. Statistics are estimates, so even fresh statistics can be wrong.
Compare plans: add up their I/O costs and choose the smaller total.