Nested loop, merge, and hash join strategies
A nested loop join iterates the outer table and for each row, scans the inner table for matches. It is slow (O(n*m) with n and m as table sizes) but requires no sorted data or extra memory. A merge join assumes both tables are sorted by the join key, then scans both in lockstep, advancing pointers to find matches in O(n + m). A hash join builds a hash table on the inner table, then probes it once per outer row, also O(n + m).
Hash joins are fastest for unsorted data; merge joins excel when data is already sorted or when joins are cascaded (multiple joins in one query). Nested loops are used only when one table is tiny or when specific row orderings must be preserved.
Query optimizer selection and memory considerations
The query optimizer estimates table sizes, selectivity, and available memory, then picks the best algorithm. Hash joins spill to disk if the hash table exceeds memory, degrading to slower I/O. Merge joins avoid this by streaming sorted data and requiring only a small buffer. In-memory databases favor hash joins; disk-based systems with limited memory may prefer merge joins.
For production queries, understanding the chosen algorithm is critical for tuning. Forcing an index (to enable merge join) or increasing memory (to prevent spill in hash join) can transform a slow query into a fast one. EXPLAIN output reveals the chosen algorithm; deviations from expectation suggest stale statistics or suboptimal index design.