Query Processing, Join Algorithms and EXPLAIN

From SQL text to results

A query passes through stages: parsing checks syntax and builds a tree; rewriting expands views and simplifies expressions; the optimiser generates alternative execution plans (which indexes, which join order, which algorithms) and estimates their cost from statistics such as table sizes, value distributions and histograms; the executor runs the chosen plan. The main join algorithms: nested loop join (for each outer row, look up matching inner rows, efficient when the outer side is small and the inner side has an index); hash join (build a hash table on the smaller input, probe it with the larger one, good for large equality joins); and sort-merge join (sort both inputs on the join key and merge, useful when inputs are already sorted or for range-like joins). Use EXPLAIN to see the plan and EXPLAIN ANALYZE (in PostgreSQL) to run it and compare estimated with actual rows. Large mismatches between estimates and reality point to stale statistics, so run ANALYZE; sequential scans on large tables for selective queries suggest a missing index.

Reading a plan

Run it, then check the plan for the points listed in the comments.

EXPLAIN ANALYZE
SELECT s.name, m.score
FROM students s
JOIN marks m ON m.roll_no = s.roll_no
WHERE m.subject = 'DBMS' AND m.score >= 90;

-- what to look for in the plan:
--   Hash Join / Nested Loop / Merge Join   -> which join algorithm was chosen
--   Seq Scan on marks                      -> whole table read: index on (subject, score)?
--   Index Scan using idx_...               -> index used
--   rows=... (estimated) vs actual rows=... -> big gaps mean stale statistics (run ANALYZE)
--   actual time=...                        -> where the time is really spent

Measure, then index

Do not guess which index to add. Run EXPLAIN ANALYZE on the slow query, find the expensive node, and design an index for that access path. Then confirm the plan and timing improved.

त्वरित जाँच: Which join algorithm builds an in-memory table on the smaller input and probes it with rows from the larger input?

• Nested loop join
• Sort-merge join
• Hash join
• Cartesian product