5.2Execution plans & the optimizer

For an application developer or DBA, when a SQL statement is correct but slow to execute, the cause lies in which procedure (execution plan) the DBMS uses to process the query. This section covers the thinking behind the optimizer, the mechanism by which a DBMS estimates "which execution plan will be fastest," and the judgment needed to read an execution plan and improve a slow query.

5.2.1Cost-based optimization and statistics

• Cost-based optimization (CBO) estimates the I/O and CPU cost of each of several candidate execution plans that would yield the same result (which index to use, which join method, etc.) and chooses the plan with the lowest estimated cost. This is the approach adopted by all major modern RDBMSs.
• The accuracy of the cost estimate depends heavily on the freshness of statistics (metadata the DBMS collects, such as the distribution of values per column, row counts, NULL ratios, and index selectivity). If statistics go stale—for example, right after a large bulk update or delete—there is a risk of estimating a row count wildly different from reality and choosing an inappropriate execution plan (e.g., a full table scan where an index should have been used). Building periodic statistics recollection (e.g., ANALYZE) into operations is important.

5.2.2Join methods (nested loop / sort-merge / hash join)

• Nested loop join repeatedly searches the inner table for a matching row, once for each row of the outer table. It is very fast if the inner table's join column has an index, but without one it repeats a full table scan of the inner table once per outer row, becoming extremely slow when both tables are large. It suits cases where the outer table has few rows.
• Sort-merge join first sorts both tables on the join column, then scans the two sorted columns simultaneously from the start, matching them up. Sorting itself has a cost, but if the data is already sorted (e.g., via an index), it is efficient. Hash join builds a hash table from the join column of the smaller table, then probes that hash table for each row of the larger table to find matches. It excels at equality joins (=) and is relatively fast even for large-to-large joins where an index cannot be used, but building the hash table requires memory.

Suppose a DBA receives a report that a nightly batch query, SELECT * FROM orders o JOIN customers c ON o.customer_id = c.customer_id WHERE o.order_date >= '2026-07-01', finished in a few seconds through last month but now takes several minutes. Checking the execution plan reveals that the join method on the orders side switched from a nested loop join to a nested loop involving a full table scan, running far slower than expected. To isolate the cause, the DBA first suspected the freshness of statistics. Sure enough, a large historical-data migration (an INSERT of several million rows) had recently run against the orders table, and statistics had not been refreshed since. The optimizer, working from stale statistics (the much smaller pre-migration row count), mistakenly estimated that "the orders side has few rows, so repeated lookups into the inner table are still fast enough," and ended up choosing a nested loop against a row count that had actually grown enormously. As a remedy, the DBA first ran ANALYZE (statistics recollection) so the optimizer would recognize the current row count and distribution. As a result, the optimizer switched its plan to a hash join (since orders now has many rows and the join is a customer_id equality join), and execution time returned to a few seconds. What this case shows is that an execution plan can degrade and performance can suffer purely from stale statistics, without any change to the SQL statement or join condition itself—so a DBA should not jump to "it got slower, so we must be missing an index," but instead first check the execution plan and the freshness of statistics before choosing a remedy (statistics recollection, adding an index, hinting a join method, etc.).

5.2.3Section summary

• Cost-based optimization chooses the execution plan with the lowest I/O/CPU cost. If the underlying statistics go stale, it can choose a poor plan
• Choose among nested loop join (suits an indexed inner side), sort-merge join (suits pre-sorted data), and hash join (suits equality joins on large data)
• A full table scan is not always disadvantageous—when matching rows make up a large proportion (low selectivity), it can be faster than an index scan