Query Processing & Optimization

-- SQL QUERY:
SELECT c.name, o.total_amount
FROM customers c
JOIN orders o ON c.customer_id = o.customer_id
WHERE c.city = 'Bengaluru'
  AND o.status = 'delivered'
ORDER BY o.total_amount DESC;

-- NAIVE RELATIONAL ALGEBRA TRANSLATION (what a simple parser produces):
π_{c.name, o.total_amount} (
  σ_{order_by: total_amount DESC} (
    σ_{c.city='Bengaluru' AND o.status='delivered'} (
      customers ⋈_{c.customer_id=o.customer_id} orders
    )
  )
)

-- This reads:
-- 1. Form the join of customers and orders (EXPENSIVE — all rows combined first)
-- 2. Filter by city AND status (filter happens AFTER the expensive join)
-- 3. Project to name and total_amount
-- 4. Sort by total_amount DESC

-- OPTIMISED RELATIONAL ALGEBRA (what the optimiser produces):
π_{c.name, o.total_amount} (
  sort_{total_amount DESC} (
    σ_{city='Bengaluru'}(customers)
    ⋈_{customer_id=customer_id}
    σ_{status='delivered'}(orders)
  )
)

-- This reads:
-- 1. Filter customers to only Bengaluru customers FIRST (reduces rows from 10M to 50K)
-- 2. Filter orders to only delivered FIRST (reduces rows from 50M to 20M)
-- 3. Join the two reduced relations (much smaller input to the join)
-- 4. Project to name and total_amount
-- 5. Sort the result

-- The key optimisation: PREDICATE PUSHDOWN
-- Push filters (σ) as close to the data source as possible.
-- Reduces the size of intermediate results at every step.

-- COST MODEL INPUTS (what PostgreSQL tracks in pg_class and pg_statistic):

-- 1. TABLE STATISTICS (updated by ANALYZE):
SELECT relname, reltuples, relpages
FROM pg_class
WHERE relname IN ('customers', 'orders');
-- reltuples: estimated row count (cardinality)
-- relpages: number of 8KB pages the table occupies

-- 2. COLUMN STATISTICS (updated by ANALYZE):
SELECT attname, n_distinct, correlation, most_common_vals, histogram_bounds
FROM pg_stats
WHERE tablename = 'orders';
-- n_distinct: number of distinct values (positive = exact, negative = fraction of rows)
-- correlation: how well column order matches physical storage order (1.0 = perfectly correlated)
-- most_common_vals: array of most frequent values and their frequencies
-- histogram_bounds: bucket boundaries for estimating range predicates

-- 3. COST PARAMETERS (in postgresql.conf):
SHOW seq_page_cost;       -- cost of reading a page in a sequential scan (default: 1.0)
SHOW random_page_cost;    -- cost of reading a page via random access (default: 4.0)
-- random_page_cost > seq_page_cost because sequential disk reads are faster
-- For SSDs: set random_page_cost = 1.1 (almost same as sequential)
SHOW cpu_tuple_cost;      -- cost of processing one row (default: 0.01)
SHOW cpu_index_tuple_cost; -- cost of processing one index entry (default: 0.005)
SHOW cpu_operator_cost;   -- cost of a comparison or function call (default: 0.0025)

-- COST FORMULA for sequential scan:
-- cost = relpages * seq_page_cost + reltuples * cpu_tuple_cost
-- For orders table: 6250 pages * 1.0 + 50000 rows * 0.01 = 6250 + 500 = 6750

-- COST FORMULA for index scan:
-- cost = (index pages read) * random_page_cost + (matching rows) * cpu_index_tuple_cost
--        + (matching rows) * random_page_cost (heap fetches)
-- For highly selective index (1% selectivity): far cheaper than full scan
-- For low-selectivity index (50% of table): more expensive than full scan!

-- SELECTIVITY: fraction of rows that satisfy a condition
-- = (estimated output rows) / (total input rows)

-- EQUALITY CONDITION: col = value
-- selectivity = 1 / n_distinct(col)
-- Example: city = 'Bengaluru', n_distinct(city) = 10 cities
-- selectivity = 1/10 = 0.1 = 10% of rows
-- If customers has 1M rows: estimated output = 1M * 0.1 = 100,000 rows

-- RANGE CONDITION: col BETWEEN a AND b
-- Uses histogram: count buckets that fall within [a,b] / total buckets
-- Example: salary BETWEEN 50000 AND 80000
-- Histogram: [20K, 40K, 60K, 80K, 100K, 150K] — 2 of 5 buckets → selectivity ≈ 0.4

-- CONJUNCTION (AND): multiply selectivities (assumes independence)
-- P(A AND B) ≈ P(A) * P(B)
-- WHERE city='Bengaluru' AND status='delivered'
-- selectivity = 0.1 * 0.2 = 0.02 = 2% of rows
-- PROBLEM: if city and status are correlated (Bengaluru users place more delivered orders),
-- the independence assumption underestimates the true selectivity → wrong plan

-- DISJUNCTION (OR): 1 - (1-P(A)) * (1-P(B))
-- WHERE city='Bengaluru' OR status='delivered'
-- selectivity = 1 - (1-0.1) * (1-0.2) = 1 - 0.9*0.8 = 1 - 0.72 = 0.28

-- JOIN CARDINALITY ESTIMATE:
-- |R ⋈_{R.A=S.B} S| ≈ |R| * |S| / max(n_distinct(R.A), n_distinct(S.B))
-- Assumes uniform distribution of join attribute values
-- customers ⋈ orders on customer_id:
-- |customers| = 100K, |orders| = 5M, n_distinct(customer_id) = 100K (same)
-- Estimated join output: 100K * 5M / 100K = 5M rows
-- (Each customer has ~50 orders on average → total 5M order rows, correct)

-- STALE STATISTICS = BAD PLANS:
-- If ANALYZE hasn't been run recently:
-- The optimiser thinks the table has the OLD row count
-- Might choose a full scan instead of an index scan (or vice versa)
-- Always run: VACUUM ANALYZE table_name; after large data loads

-- CHECK if statistics are stale:
SELECT relname, n_live_tup, n_dead_tup, last_analyze, last_autoanalyze
FROM pg_stat_user_tables
ORDER BY last_analyze NULLS FIRST;

-- PROBLEM: city and state are correlated (city='Mumbai' always means state='Maharashtra')
-- Bad estimate: P(city='Mumbai' AND state='Maharashtra') = P(city) * P(state)
--              = 0.05 * 0.1 = 0.005  (only 0.5% of rows)
-- Actual:       30% of all rows (Mumbai is a major city in Maharashtra — high correlation)
-- Optimiser makes wrong plan based on the bad estimate

-- SOLUTION: Create extended statistics for correlated columns
CREATE STATISTICS stat_city_state ON city, state FROM customers;
ANALYZE customers;
-- PostgreSQL now tracks the joint distribution of city and state together
-- Selectivity estimates for conditions on both columns are far more accurate

-- VIEW extended statistics:
SELECT stxname, stxkeys, stxkind
FROM pg_statistic_ext
WHERE stxrelid = 'customers'::regclass;
-- stxkind: d = n_distinct, f = functional dependencies, m = MCV (most common values)

-- Extended statistics types:
-- DEPENDENCIES: one column functionally determines another (zip → city)
-- MCV: track most common combinations of values
-- NDISTINCT: track distinct combinations

CREATE STATISTICS stat_zip_city (dependencies)
ON zip_code, city FROM addresses;
-- Now optimiser knows: given zip_code='400001', city is always 'Mumbai'

-- QUERY:
EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT)
SELECT c.name, r.name AS restaurant, COUNT(o.order_id) AS order_count,
       SUM(o.total_amount) AS total_spent
FROM customers c
JOIN orders o        ON c.customer_id   = o.customer_id
JOIN restaurants r   ON o.restaurant_id = r.restaurant_id
WHERE c.city = 'Bengaluru'
  AND o.status = 'delivered'
GROUP BY c.customer_id, c.name, r.restaurant_id, r.name
HAVING COUNT(o.order_id) >= 3
ORDER BY total_spent DESC
LIMIT 10;

-- EXAMPLE OUTPUT (annotated):
Sort  (cost=8234.56..8234.59 rows=10 width=68)
      (actual time=45.123..45.127 rows=10 loops=1)
  Sort Key: (sum(o.total_amount)) DESC
  Sort Method: top-N heapsort  Memory: 25kB
  Buffers: shared hit=3240, read=127
  ->  HashAggregate  (cost=8100.00..8200.00 rows=847 width=68)
                     (actual time=44.001..44.890 rows=847 loops=1)
        Group Key: c.customer_id, c.name, r.restaurant_id, r.name
        Filter: (count(o.order_id) >= 3)
        Rows Removed by Filter: 12341
        Buffers: shared hit=3240, read=127
        ->  Hash Join  (cost=312.00..7500.00 rows=24000 width=52)
                       (actual time=5.456..38.234 rows=23188 loops=1)
              Hash Cond: (o.restaurant_id = r.restaurant_id)
              Buffers: shared hit=3240, read=127
              ->  Hash Join  (cost=145.00..6800.00 rows=24000 width=32)
                             (actual time=2.123..31.456 rows=23188 loops=1)
                    Hash Cond: (o.customer_id = c.customer_id)
                    ->  Seq Scan on orders o
                              (cost=0.00..6200.00 rows=48000 width=20)
                              (actual time=0.025..24.678 rows=47921 loops=1)
                          Filter: ((status)::text = 'delivered')
                          Rows Removed by Filter: 2079
                    ->  Hash  (cost=120.00..120.00 rows=2000 width=16)
                               (actual time=1.987..1.987 rows=1952 loops=1)
                          Buckets: 2048  Batches: 1  Memory Usage: 112kB
                          ->  Seq Scan on customers c
                                    (cost=0.00..120.00 rows=2000 width=16)
                                    (actual time=0.013..1.456 rows=1952 loops=1)
                                Filter: ((city)::text = 'Bengaluru')
                                Rows Removed by Filter: 8048
              ->  Hash  (cost=80.00..80.00 rows=500 width=24)
                         (actual time=1.234..1.234 rows=500 loops=1)
                    Buffers: shared hit=5
                    ->  Seq Scan on restaurants r
                              (cost=0.00..80.00 rows=500 width=24)
                              (actual time=0.009..0.789 rows=500 loops=1)
Planning Time: 2.456 ms
Execution Time: 45.234 ms

-- ─────────────────────────────────────────────────────────────────
-- DECODING EVERY ELEMENT:
-- ─────────────────────────────────────────────────────────────────

-- cost=X..Y: X = startup cost (first row), Y = total cost (all rows)
-- cost units are arbitrary but relative: higher = more expensive
-- estimated vs actual: if they differ greatly → stale statistics

-- actual time=X..Y rows=Z loops=N:
-- X = milliseconds to first row, Y = milliseconds total
-- Z = actual rows output by this node
-- N = how many times this node was executed (inner side of NLJ runs many times)

-- Buffers: shared hit=X read=Y:
-- hit = pages found in buffer pool (fast, RAM)
-- read = pages read from disk (slow)
-- A high read count on a leaf node = candidate for an index

-- "Rows Removed by Filter: 12341" on HashAggregate → HAVING filtered 12K groups
-- "Rows Removed by Filter: 2079" on Seq Scan → WHERE filtered some rows
-- Large numbers here = predicate pushdown didn't fire or no index available

-- The PLAN TREE reads bottom-up:
-- Deepest indented nodes run FIRST (leaf nodes)
-- Root node (Sort) runs LAST and produces the final output

-- 3-TABLE JOIN: customers, orders, restaurants
-- Possible join orderings:
-- (customers ⋈ orders) ⋈ restaurants
-- (customers ⋈ restaurants) ⋈ orders   ← cross join! no direct predicate between these two
-- (orders ⋈ restaurants) ⋈ customers

-- DYNAMIC PROGRAMMING APPROACH:
-- Step 1: Cost of single-table access (scan or index):
--   cost(customers) = 120 pages * 1.0 = 120
--   cost(orders)    = 6250 pages * 1.0 = 6250
--   cost(restaurants) = 5 pages * 1.0 = 5

-- Step 2: Cost of all 2-table joins:
--   cost(customers ⋈ orders) via hash join = 120 + 6250 + 120(build) = ~6490
--     output: 5M rows (each customer has ~50 orders)
--   cost(orders ⋈ restaurants) via hash join = 6250 + 5 + 5(build) = ~6260
--     output: 5M rows (each order has one restaurant)
--   cost(customers ⋈ restaurants) = cross join: not applicable (no join predicate)

-- Step 3: Best 3-table join options:
--   Option A: (customers ⋈ orders) ⋈ restaurants
--     = cost 6490 + join 5M rows with 500 rows via hash = 6490 + 5000 = ~11490
--   Option B: (orders ⋈ restaurants) ⋈ customers
--     = cost 6260 + join 5M rows with 10K customers via hash = 6260 + 5000 = ~11260
--   Option B is slightly cheaper → CHOSEN

-- With predicate pushdown applied first:
--   After filtering customers WHERE city='Bengaluru': 1952 rows (not 100K)
--   After filtering orders WHERE status='delivered': 48K rows (not 5M)
-- Option B revisited: (filtered_orders ⋈ restaurants) ⋈ filtered_customers
--   = 6260(scan+filter) + small hash join = much cheaper
-- This is why predicate pushdown is applied before join ordering decisions.

-- GEQO (Genetic Query Optimization): for queries > join_collapse_limit tables
-- Uses genetic algorithm instead of exhaustive DP
-- Finds near-optimal but not guaranteed optimal solution
-- Faster than exhaustive search for very large join counts
SHOW geqo_threshold;  -- default 12: use GEQO for joins with > 12 tables
SHOW join_collapse_limit;  -- default 8: use DP for ≤ 8 tables

-- DISABLE specific join types (force the optimiser away from bad choices):
SET enable_nestloop = off;    -- disable NLJ (force hash or merge join)
SET enable_hashjoin = off;    -- disable hash join
SET enable_mergejoin = off;   -- disable sort-merge join
SET enable_seqscan = off;     -- disable sequential scans (force index scans)
-- WARNING: these are session-level settings. Restore after debugging.
-- Also: disabling an operator doesn't mean it's never used —
-- if no alternative exists, the disabled operator is used anyway.

-- FORCE a specific index:
-- PostgreSQL doesn't have direct index hints.
-- Workaround: use SET enable_seqscan = off temporarily,
-- OR rewrite the query to be more index-friendly.

-- UPDATE STATISTICS when the optimiser is using stale estimates:
ANALYZE customers;          -- update stats for one table
ANALYZE;                    -- update stats for all tables
VACUUM ANALYZE orders;      -- clean dead tuples AND update stats

-- CHECK why the optimiser chose a plan:
EXPLAIN (ANALYZE, BUFFERS, VERBOSE)
SELECT ...;
-- VERBOSE: shows which index was considered and rejected, output column lists

-- pg_hint_plan extension: provides Oracle-style hints for PostgreSQL
-- After installing: /*+ IndexScan(orders idx_orders_customer) */ in query
-- Not built-in — requires extension installation

-- SET STATISTICS: increase histogram precision for problem columns
ALTER TABLE orders ALTER COLUMN total_amount SET STATISTICS 500;
-- Default: 100 histogram buckets
-- For columns with complex distributions: increase to 500
ANALYZE orders (total_amount);
-- Now the histogram for total_amount has 500 buckets → better range estimates

-- Business requirement: monthly restaurant performance report for operations team
SELECT
    r.name                              AS restaurant_name,
    r.city,
    r.cuisine_type,
    COUNT(DISTINCT o.customer_id)       AS unique_customers,
    COUNT(o.order_id)                   AS total_orders,
    SUM(o.total_amount)                 AS gross_revenue,
    AVG(o.total_amount)                 AS avg_order_value,
    COUNT(rev.review_id)                AS review_count,
    AVG(rev.rating)                     AS avg_rating
FROM restaurants r
LEFT JOIN orders o
       ON r.restaurant_id = o.restaurant_id
      AND o.order_date >= '2024-01-01'
      AND o.order_date <  '2024-02-01'
      AND o.status = 'delivered'
LEFT JOIN reviews rev
       ON o.order_id = rev.order_id
GROUP BY r.restaurant_id, r.name, r.city, r.cuisine_type
ORDER BY gross_revenue DESC NULLS LAST;
-- Runtime: 45 seconds on a 50M row orders table

EXPLAIN (ANALYZE, BUFFERS)
-- [query above]

-- RELEVANT PARTS OF OUTPUT:
Sort  (actual time=44823.456..44825.234 rows=843 loops=1)
  ->  HashAggregate  (actual time=44820.123..44822.456 rows=843 loops=1)
        ->  Hash Left Join (actual time=312.456..44810.234 rows=48234567 loops=1)
              Hash Cond: (o.order_id = rev.order_id)
              ->  Hash Left Join (actual time=5.234..38452.123 rows=48234567 loops=1)
                    Hash Cond: (r.restaurant_id = o.restaurant_id)
                    ->  Seq Scan on restaurants r (rows=843 loops=1)
                    ->  Hash (actual time=4.123..4.123 rows=847 loops=1)
                          ->  Seq Scan on orders o
                                (actual time=0.025..34521.234 rows=48234567 loops=1)
                                Filter: (order_date >= '2024-01-01' AND order_date < '2024-02-01'
                                         AND status = 'delivered')
                                Rows Removed by Filter: 1765432
-- KEY OBSERVATIONS:
-- 1. Seq Scan on orders reading 48M+ rows in 34 seconds → MASSIVE bottleneck
-- 2. No index on order_date + status → full scan every time
-- 3. Hash Left Join on reviews producing 48M intermediate rows → too many rows in join

-- FIX 1: Add composite index matching the filter (date range + status)
CREATE INDEX CONCURRENTLY idx_orders_date_status
ON orders(order_date, status)
WHERE status = 'delivered';
-- Partial index: only delivered orders (most relevant for reporting)
-- order_date is the range column — leftmost in composite for range scans

-- FIX 2: Add index on reviews for the join
CREATE INDEX CONCURRENTLY idx_reviews_order
ON reviews(order_id)
INCLUDE (rating);
-- INCLUDE rating → covering index for the LEFT JOIN + AVG(rating) operation

-- FIX 3: Rewrite to use CTE for clarity and optimiser hints
WITH delivered_jan AS (
    SELECT
        restaurant_id,
        order_id,
        customer_id,
        total_amount
    FROM orders
    WHERE order_date >= '2024-01-01'
      AND order_date <  '2024-02-01'
      AND status = 'delivered'  -- uses new partial index
)
SELECT
    r.name, r.city, r.cuisine_type,
    COUNT(DISTINCT d.customer_id) AS unique_customers,
    COUNT(d.order_id) AS total_orders,
    SUM(d.total_amount) AS gross_revenue,
    AVG(d.total_amount) AS avg_order_value,
    COUNT(rev.review_id) AS review_count,
    AVG(rev.rating) AS avg_rating
FROM restaurants r
LEFT JOIN delivered_jan d ON r.restaurant_id = d.restaurant_id
LEFT JOIN reviews rev ON d.order_id = rev.order_id
GROUP BY r.restaurant_id, r.name, r.city, r.cuisine_type
ORDER BY gross_revenue DESC NULLS LAST;

-- AFTER FIXES — EXPLAIN output:
-- Index Scan on orders using idx_orders_date_status
--   (actual time=0.123..234.567 rows=48234 loops=1)   ← 48K not 48M rows!
-- Hash Left Join (actual time=...)  rows=48234 loops=1  ← 1000x fewer rows
-- Total Execution Time: 82.456 ms   ← from 45,000ms to 82ms = 548x faster

The optimisation process was: identify the bottleneck (sequential scan on orders), understand why (missing index on date + status), add the right index (partial composite covering the filter), and verify with EXPLAIN that the plan changed. The result is a 548× improvement — from a query that times out API requests to one that completes in 82 milliseconds. This exact workflow applies to every slow query in production.