Query Cost Estimation Formulas: Scan vs. Seek
In this lesson, you will learn how the query optimizer decides between a Full Table Scan and an Index Seek by calculating the estimated cost of each operation.
The Decision Math
The database engine’s optimizer uses statistical data (which we covered in our recent look at histograms and density) to assign a numerical "cost" to every possible execution plan. When you run a query, the optimizer compares the cost of reading the entire table against the cost of using an index.
The core formula for this decision involves Table Density. Density is essentially a measure of how "unique" or "distributed" the data is.
- Table Scan Cost: Roughly proportional to the total number of pages in the table. The engine must read every single block from disk into memory.
- Index Seek Cost: Roughly proportional to the height of the B-Tree index plus the number of leaf pages required to retrieve the requested rows.
Illustrating the "Tipping Point"
If you have a table with 1,000,000 rows, an index seek is incredibly cheap—perhaps 3 or 4 I/O operations to traverse the tree. However, if your query returns 600,000 of those rows, the index seek becomes more expensive than a full table scan. Why? Because the engine would have to perform a "Bookmarking Lookup" for every single row to grab the extra columns not included in the index.
Consider this simplified logic:
-- Query: Get user details for a specific status
SELECT Name, Email, Phone
FROM Users
WHERE Status = 'Active';
If the optimizer sees that 80% of your users are 'Active', it realizes that "seeking" the index is actually slower because it will be jumping back and forth between the index and the data pages too many times. It will mathematically determine that a Full Table Scan is cheaper than performing 800,000 individual index lookups.
The "Tipping Point" is the exact percentage of rows retrieved where the cost of the index seek (plus lookups) crosses the threshold of the cost of a full table scan. The optimizer uses the density of the Status column to determine exactly where that point lies for your specific dataset.
Key Takeaway: The optimizer chooses a scan over a seek when the estimated cost of repetitive data page lookups exceeds the cost of simply reading the entire table sequentially.