Index Selection by Optimizer

Simplified Cost Model Example
=============================
 
Query: SELECT * FROM orders WHERE customer_id = 12345;
 
Plan A: Full Table Scan
-----------------------
- Table size: 500,000 pages
- Sequential read cost: 1.0 per page
- Total cost: 500,000 × 1.0 = 500,000 units
 
Plan B: Index Scan on customer_id
---------------------------------
- Index traversal: 4 pages × 4.0 (random I/O) = 16 units
- Estimated matching rows: 50
- Data page fetches: 50 pages × 4.0 = 200 units
- Total cost: 216 units
 
Plan B (216) << Plan A (500,000) → Optimizer chooses index scan
 
Key insight: Random I/O (index access) costs more per page than 
sequential I/O (table scan), but the total I/O volume matters more.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

-- Example: Order status distribution
-- Value        | Count   | Percentage
-- -------------|---------|----------
-- 'pending'    | 5,000   | 5%
-- 'processing' | 10,000  | 10%
-- 'shipped'    | 25,000  | 25%
-- 'delivered'  | 55,000  | 55%
-- 'cancelled'  | 5,000   | 5%
 
-- Without histogram (assuming uniform distribution):
SELECT * FROM orders WHERE status = 'delivered';
-- Optimizer estimates: 100,000 / 5 distinct = 20,000 rows (20%)
-- Actual result: 55,000 rows (55%)
-- Estimation error: 2.75x underestimate!
 
-- With accurate histogram:
-- Optimizer knows 'delivered' = 55% → estimates 55,000 rows
-- This changes whether index is beneficial!
 
-- If only 5,000 rows (5%), index is very efficient
-- If 55,000 rows (55%), full scan might be better

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

-- PostgreSQL: Analyze table to update statistics
ANALYZE orders;
ANALYZE orders(customer_id, status);  -- Specific columns
 
-- MySQL: Analyze table
ANALYZE TABLE orders;
 
-- SQL Server: Update statistics
UPDATE STATISTICS orders;
UPDATE STATISTICS orders WITH FULLSCAN;  -- Complete analysis
 
-- Oracle: Gather table statistics
EXEC DBMS_STATS.GATHER_TABLE_STATS('schema_name', 'orders');
 
-- Check when statistics were last updated (PostgreSQL)
SELECT schemaname, relname, last_analyze, last_autoanalyze
FROM pg_stat_user_tables
WHERE relname = 'orders';

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

-- Table: products (2,000,000 rows)
-- Available indexes:
--   1. idx_category (category_id)
--   2. idx_price (price)
--   3. idx_cat_price (category_id, price)
--   4. idx_name (product_name)
 
SELECT product_id, product_name, price
FROM products
WHERE category_id = 15 
  AND price > 100
ORDER BY price;
 
-- Optimizer evaluation:
 
-- Candidate 1: idx_category
-- Pro: Can filter category_id = 15
-- Con: Must then filter price > 100 from results
-- Con: Requires sort for ORDER BY price
-- Estimated: 40,000 index entries, 35,000 after price filter, sort needed
 
-- Candidate 2: idx_price  
-- Pro: Already sorted by price (no sort needed)
-- Con: Must scan all price > 100 entries and filter category
-- Estimated: 800,000 index entries scanned, 35,000 match both
 
-- Candidate 3: idx_cat_price (BEST CHOICE)
-- Pro: Filters category_id first (leftmost)
-- Pro: Then uses price for range scan (second column)
-- Pro: Already sorted by price within category!
-- Estimated: Navigate to category=15, range scan price>100
-- Result: 35,000 entries, no additional sort needed
 
-- Candidate 4: idx_name
-- Not usable: product_name not in WHERE clause with searchable condition
 
-- Full scan comparison:
-- 2,000,000 rows × 0.0175 selectivity = 35,000 rows expected
-- But requires reading all 2,000,000 rows + sort
 
-- Winner: idx_cat_price with estimated cost ~35,000 vs others 100,000+

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

-- PostgreSQL: Check correlation (clustering)
SELECT tablename, attname, correlation
FROM pg_stats
WHERE tablename = 'orders';
 
-- correlation close to 1.0 or -1.0 = good clustering
-- correlation close to 0 = poor clustering
 
-- attname    | correlation
-- -----------|------------
-- order_id   | 0.98        -- Well clustered (likely inserted in order)
-- order_date | 0.95        -- Well clustered (dates correlate with insert order)
-- customer_id| 0.02        -- Poorly clustered (customers are random)
 
-- Implication: Range scans on order_date are efficient
-- Range scans on customer_id cause lots of random I/O

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

-- Example 1: Low selectivity
SELECT * FROM orders WHERE status = 'delivered';
-- If 60% of orders are 'delivered', full scan is likely chosen
-- Index would read 60% of index + 60% of table = more work than full scan
 
-- Example 2: Function on column
SELECT * FROM customers WHERE UPPER(email) = 'USER@EXAMPLE.COM';
-- Index on email column CANNOT be used
-- UPPER() transforms values; B-tree doesn't know transformed order
-- Fix: CREATE INDEX idx_email_upper ON customers(UPPER(email));
 
-- Example 3: Implicit type conversion
-- Table has: customer_id INTEGER
SELECT * FROM orders WHERE customer_id = '12345';  -- String literal
-- Some databases convert column to string, breaking index usage
-- Fix: Use correct type: customer_id = 12345
 
-- Example 4: OR with different columns
SELECT * FROM products 
WHERE category_id = 5 OR brand_id = 10;
-- Neither single-column index covers both conditions efficiently
-- Options:
--   a) Accept full scan if both are low selectivity
--   b) Use UNION:
      SELECT * FROM products WHERE category_id = 5
      UNION
      SELECT * FROM products WHERE brand_id = 10;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

-- PostgreSQL: EXPLAIN ANALYZE with index information
EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT)
SELECT * FROM orders WHERE customer_id = 12345;
 
-- Look for these indicators:
 
-- Index being used:
-- Index Scan using idx_customer_id on orders  (cost=0.43..12.50 rows=50 width=120)
--                 ^^^^^^^^^^^^^^^                      ^^^^^ ^^^^^
--                 Index name used                      Cost estimates
 
-- Index NOT used (full scan):
-- Seq Scan on orders  (cost=0.00..15000.00 rows=50 width=120)
--   Filter: (customer_id = 12345)
--   Rows Removed by Filter: 999950  <- Had to examine many rows
 
-- MySQL: EXPLAIN with type column
EXPLAIN SELECT * FROM orders WHERE customer_id = 12345;
 
-- Key columns to check:
-- type: 'ref' or 'range' = index used, 'ALL' = full scan
-- possible_keys: indexes optimizer considered
-- key: index actually chosen (NULL = no index)
-- rows: estimated rows to examine
 
-- SQL Server: Actual execution plan
SET STATISTICS IO ON;
SELECT * FROM orders WHERE customer_id = 12345;
-- Shows logical reads, index seeks vs scans