Selection Implementation

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

-- Cost Formula for Each Access Method
 
-- Sequential Scan:
-- I/O: B pages × seq_page_cost (all pages read sequentially)
-- CPU: T tuples × cpu_tuple_cost + T × cpu_operator_cost (predicate)
-- Total_seq = B × 1.0 + T × (0.01 + 0.0025)
 
-- Index Scan (standard):
-- I/O: H pages (tree traversal) × random_page_cost
--    + L pages (leaf scan) × seq_page_cost  
--    + M pages (heap access) × random_page_cost
-- CPU: Matching entries × (cpu_index_tuple_cost + cpu_tuple_cost)
-- Total_idx = H × 4.0 + L × 1.0 + M × 4.0 + ...
 
-- Index-Only Scan:
-- I/O: H pages × random_page_cost + L pages × seq_page_cost
-- CPU: Matching entries × cpu_index_tuple_cost
-- (No heap access!)
-- Total_idx_only = H × 4.0 + L × 1.0 + ...
 
-- Bitmap Index Scan:
-- I/O: (Index pages × random_page_cost) + (Heap pages × seq_page_cost)
-- CPU: Building bitmap + recheck operations
-- Total_bitmap = Index_IO + Heap_IO + bitmap_overhead
 
-- Example calculation for 10,000 page table, 100 matching rows:
-- Sequential: 10,000 × 1.0 = 10,000
-- Index: 4 × 4.0 + 100 × 4.0 = 16 + 400 = 416
-- Ratio: 10,000 / 416 = 24× cheaper to use index
 
SHOW seq_page_cost;
SHOW random_page_cost;
SHOW cpu_tuple_cost;

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

-- Break-Even Selectivity Analysis
 
-- For index scan to be cheaper than sequential scan:
-- Index_Cost < Sequential_Cost
 
-- Sequential: B × seq_page_cost = B × 1.0 = B
-- Index: H × random_page_cost + s×T × random_page_cost
--      = 4H + 4×s×T (assuming each tuple on different page)
 
-- For index to win: 4H + 4×s×T < B
 
-- Simplified (ignoring tree traversal, H ≈ 4):
-- 4×s×T < B
-- s < B / (4×T)
 
-- For table with T = 1,000,000 tuples, B = 10,000 pages:
-- s < 10,000 / (4 × 1,000,000) = 0.0025 = 0.25%
 
-- Interpretation: Index scan wins only if < 0.25% of rows match
-- This is quite selective! (2,500 rows out of 1 million)
 
-- With clustered data (correlation = 0.9):
-- Heap access approaches sequential, reducing random I/O penalty
-- Effective random_page_cost closer to 1.5
-- s < 10,000 / (1.5 × 1,000,000) = 0.0067 = 0.67%
 
-- With SSD (random_page_cost = 1.1):
-- s < 10,000 / (1.1 × 1,000,000) = 0.0091 = 0.91%
 
-- Real-world break-even typically 5-15% depending on:
-- - Correlation (clustering factor)
-- - Hardware (SSD vs HDD)
-- - Index type (B-tree depth, covering potential)

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
42

-- Viewing Selectivity Statistics in PostgreSQL
 
-- Table-level statistics:
SELECT 
    relname,
    reltuples AS estimated_rows,
    relpages AS pages,
    reltuples / NULLIF(relpages, 0) AS rows_per_page
FROM pg_class
WHERE relname = 'orders';
 
-- Column-level statistics:
SELECT 
    attname AS column_name,
    n_distinct,  -- Distinct values (negative = fraction)
    null_frac,   -- NULL fraction
    avg_width,   -- Average bytes per value
    correlation  -- Physical ordering correlation
FROM pg_stats
WHERE tablename = 'orders' AND attname = 'customer_id';
 
-- MCV (Most Common Values):
SELECT 
    attname,
    most_common_vals,   -- The values
    most_common_freqs   -- Their frequencies
FROM pg_stats
WHERE tablename = 'orders' AND attname = 'status';
 
-- Histogram buckets:
SELECT 
    attname,
    histogram_bounds
FROM pg_stats
WHERE tablename = 'orders' AND attname = 'order_date';
 
-- Force statistics refresh:
ANALYZE orders;
 
-- Increase statistics precision (1-10000):
ALTER TABLE orders ALTER COLUMN customer_id SET STATISTICS 1000;
ANALYZE 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

-- Access Path Enumeration Example
 
-- Query:
SELECT * FROM orders WHERE customer_id = 100 AND order_date > '2024-01-01';
 
-- Available indexes on orders:
-- idx_customer (customer_id)
-- idx_date (order_date)
-- idx_cust_date (customer_id, order_date)
 
-- Optimizer enumerates viable paths:
 
-- Path 1: Sequential Scan
-- + Applicable to any query
-- Cost: B × seq_page_cost + T × predicate_cost
 
-- Path 2: Index Scan on idx_customer
-- + Predicate includes customer_id equality
-- Cost: Index_traversal + Matching_entries × heap_access
--       + Filter(order_date) CPU cost
 
-- Path 3: Index Scan on idx_date
-- + Predicate includes order_date range
-- Cost: Index_traversal + Matching_entries × heap_access
--       + Filter(customer_id) CPU cost
 
-- Path 4: Index Scan on idx_cust_date
-- + Both predicates covered by composite index
-- Cost: Index_traversal + Matching_entries × heap_access
--       (no additional filter needed)
 
-- Path 5: Bitmap AND (idx_customer AND idx_date)
-- + Combine bitmaps from both indexes
-- Cost: Two index scans + bitmap ops + intersection heap scan
 
-- Optimizer calculates cost for each and picks minimum

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

-- Cardinality Estimation
 
-- Given:
-- Total rows: 10,000,000
-- customer_id = 100: n_distinct = 100,000 → s1 = 1/100,000 = 0.001%
-- order_date > '2024-01-01': histogram → s2 = 15%
 
-- Path 2 (Index on customer_id):
-- Index entries matching: 10M × 0.001% = 100 rows
-- After filter (order_date): 100 × 15% = 15 rows
-- Heap pages accessed: ~100 (each customer order on different page)
 
-- Path 3 (Index on order_date):
-- Index entries matching: 10M × 15% = 1,500,000 rows
-- After filter (customer_id): 1.5M × 0.001% = 15 rows
-- Heap pages accessed: ~500,000 (range matches many pages)
 
-- Path 4 (Composite index):
-- Index entries fully matching: 10M × 0.001% × 15% = 15 rows
-- Heap pages accessed: ~15
-- → CLEARLY THE WINNER
 
-- Path 5 (Bitmap AND):
-- Bitmap1: 100 rows → ~50 pages
-- Bitmap2: 1.5M rows → ~300,000 pages
-- Intersection: ~10 pages
-- Heap pages accessed: ~10
-- High overhead for small gain vs Path 4

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

-- EXPLAIN Output Analysis
 
-- Basic EXPLAIN (estimates only):
EXPLAIN SELECT * FROM orders WHERE customer_id = 100;
 
-- Output:
-- Index Scan using idx_customer on orders  (cost=0.43..8.45 rows=1 width=164)
--   Index Cond: (customer_id = 100)
 
-- Breaking down the output:
-- "Index Scan using idx_customer" → Access method chosen
-- "cost=0.43..8.45" → Startup cost..Total cost (arbitrary units)
-- "rows=1" → Estimated output rows
-- "width=164" → Estimated bytes per output row
-- "Index Cond" → Predicate applied via index
 
-- EXPLAIN ANALYZE (actual execution):
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM orders WHERE customer_id = 100;
 
-- Output:
-- Index Scan using idx_customer on orders
--   (cost=0.43..8.45 rows=1 width=164)
--   (actual time=0.025..0.027 rows=1 loops=1)
--   Index Cond: (customer_id = 100)
--   Buffers: shared hit=4
 
-- Additional fields:
-- "actual time=0.025..0.027" → Time to first row..Time to all rows (ms)
-- "rows=1" → ACTUAL rows returned (compare to estimated!)
-- "loops=1" → Number of times this node executed
-- "Buffers: shared hit=4" → Pages read from buffer pool
 
-- Comparing estimated vs actual:
-- Estimated rows: 1, Actual rows: 1 → Good estimate!
-- Cost: 8.45, Actual time: 0.027ms → Very fast

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

-- Common EXPLAIN Patterns and Interpretation
 
-- Pattern 1: Filter with high removal (inefficient index use)
-- Index Scan using idx_status on orders  (cost=0.42..1542.00 rows=10 width=164)
--                                         (actual time=0.025..156.234 rows=10 loops=1)
--   Index Cond: (status = 'active')
--   Filter: (amount > 1000)
--   Rows Removed by Filter: 49990
-- 
-- Problem: Index returns 50,000 rows, but only 10 match the full predicate.
-- Consider: Composite index on (status, amount) or different index.
 
-- Pattern 2: Sequential scan on large table (missing index)
-- Seq Scan on customers  (cost=0.00..458236.00 rows=5 width=87)
--                         (actual time=5234.123..5234.789 rows=5 loops=1)
--   Filter: (email = 'user@example.com')
--   Rows Removed by Filter: 9999995
--
-- Problem: Scanning 10M rows to find 5. 
-- Solution: CREATE INDEX idx_email ON customers(email);
 
-- Pattern 3: Bitmap becoming lossy (memory pressure)
-- Bitmap Heap Scan on orders  (cost=456.78..12345.00 rows=50000 width=164)
--   Heap Blocks: exact=1234 lossy=5678
--   Recheck Cond: (region = 'US')
--
-- Observation: 5678 lossy blocks = bitmaps too large for work_mem
-- Consider: Increase work_mem or accept lossy scan overhead
 
-- Pattern 4: Parallel scan efficiency
-- Gather  (cost=1000.00..15000.00 rows=100000 width=164)
--   Workers Planned: 4
--   Workers Launched: 4
--   -> Parallel Seq Scan on large_table  (...)
--      Actual time=123..456 rows=25000 loops=4 (each worker)
--
-- Good: 4 workers, each processing ~25% of work
-- Check: (time × loops) should be less than single-threaded time

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

-- Mistake 1: Stale Statistics
 
-- Symptom: Estimated rows wildly differ from actual
EXPLAIN ANALYZE SELECT * FROM orders WHERE status = 'pending';
-- Estimated rows: 100, Actual rows: 50,000
-- 500× error!
 
-- Cause: Table was bulk-loaded since last ANALYZE
 
-- Fix: Update statistics
ANALYZE orders;
 
-- For critical tables, increase statistics target:
ALTER TABLE orders ALTER COLUMN status SET STATISTICS 1000;
ANALYZE orders;
 
-- PostgreSQL: Track autovacuum statistics freshness
SELECT 
    schemaname, relname,
    last_analyze, last_autoanalyze,
    n_live_tup, n_dead_tup,
    n_mod_since_analyze
FROM pg_stat_user_tables
WHERE n_mod_since_analyze > 0.1 * n_live_tup;  -- >10% changed

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

-- Mistake 2: Wrong Cost Parameters (HDD settings on SSD)
 
-- Symptom: Optimizer avoids indexes that would be beneficial
-- Default random_page_cost = 4.0 is for spinning disk
-- On SSD, random I/O is only ~1.1-1.5× slower than sequential
 
-- Check current settings:
SHOW random_page_cost;
SHOW seq_page_cost;
 
-- For SSD storage, reduce random_page_cost:
SET random_page_cost = 1.1;
 
-- Verify the change affects plan selection:
EXPLAIN SELECT * FROM orders WHERE customer_id = 100;
-- Should now prefer index scan more often
 
-- Make permanent in postgresql.conf:
-- random_page_cost = 1.1
 
-- For in-memory tables (buffer pool can hold entire table):
-- Consider even lower values:
-- effective_cache_size = <large value matching RAM>

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

-- Mistake 3: Correlated Predicates
 
-- Query:
SELECT * FROM addresses WHERE city = 'San Francisco' AND state = 'CA';
 
-- Estimated: city selectivity × state selectivity = 0.001 × 0.05 = 0.00005
-- Actual: All San Francisco addresses ARE in CA, so actual = 0.001
 
-- The independence assumption fails because city determines state
 
-- Fix: Create extended statistics for correlated columns
-- PostgreSQL 10+:
CREATE STATISTICS addr_city_state (dependencies) 
    ON city, state FROM addresses;
ANALYZE addresses;
 
-- Now optimizer knows: P(state='CA' | city='San Francisco') = 1.0
-- Estimate becomes accurate
 
-- Check extended statistics:
SELECT * FROM pg_statistic_ext WHERE stxname = 'addr_city_state';

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

-- Hardware-Aware Cost Parameter Tuning
 
-- For NVMe SSD storage:
SET random_page_cost = 1.1;
SET seq_page_cost = 1.0;
 
-- For large RAM (data mostly cached):
SET effective_cache_size = '32GB';  -- Or your actual RAM
SET random_page_cost = 1.0;  -- Buffer pool hits are ~equal speed
 
-- For parallel processing capability:
SET max_parallel_workers_per_gather = 4;
SET parallel_tuple_cost = 0.01;
 
-- Force re-evaluation after tuning:
EXPLAIN ANALYZE <your_query>;
-- Compare old vs new execution time
 
-- Example: Query benefiting from SSD tuning
-- Before (random_page_cost = 4.0):
-- Seq Scan (prefers sequential due to high random cost)
 
-- After (random_page_cost = 1.1):
-- Index Scan (now recognizes random I/O is cheap)

                    ┌─────────────────────┐
                    │ Selection Query    │
                    │ with Predicate(s)  │
                    └──────────┬─────────┘
                               │
                    ┌──────────▼─────────┐
                    │ Estimate Combined  │
                    │ Selectivity        │
                    └──────────┬─────────┘
                               │
              ┌────────────────┼────────────────┐
              │                │                │
    ┌─────────▼──────┐ ┌──────▼──────┐ ┌───────▼───────┐
    │ Selectivity    │ │ Selectivity │ │ Selectivity   │
    │ > 30-50%       │ │ 5-30%       │ │ < 5%          │
    └───────┬────────┘ └──────┬──────┘ └───────┬───────┘
            │                 │                │
    ┌───────▼────────┐       │        ┌───────▼───────┐
    │ Sequential     │       │        │ Index Exists  │
    │ Scan Likely    │       │        │ Covering      │
    │ Best Choice    │       │        │ Predicate?    │
    └────────────────┘       │        └───────┬───────┘
                             │          Yes ─┬─ No
                             │               │
                    ┌────────▼───────┐ ┌─────▼─────┐
                    │ Multi-Predicate│ │ Sequential│
                    │ Bitmap OR/AND  │ │ Scan or   │
                    │ May Be Best    │ │Create Idx │
                    └────────────────┘ └───────────┘
                    
Legend:
- High selectivity (>30%): Sequential scan (read everything anyway)
- Medium selectivity (5-30%): Bitmap may win (sorted heap access)
- Low selectivity (<5%): Index scan wins (surgical access)
- Always consider: correlation, covering indexes, hardware