IM Engineer Study Notes
← Back to list
Database
#조인알고리즘#NestedLoop#HashJoin#SortMerge#옵티마이저
Last updated · 2026-10-30

Database Join Algorithms (Nested Loop · Sort-Merge · Hash Join)

1. Overview

A. Definition

A join algorithm refers to the processing method that physically combines two or more relations (tables) according to a join condition to produce a result set in a relational database. When a user declares only 'what to combine' in SQL, such as FROM A, B WHERE A.k = B.k, which physical procedure to use to find the matching pairs of the two sets is decided by the optimizer, which selects a join algorithm.

The key to understanding join algorithms lies in the fact that 'there are several ways to produce the same join result, and depending on data volume·distribution·sort state·presence of indexes, one method can be tens to thousands of times faster'. In the relational model, the join is the most expensive yet most frequent operation. Combining two tables is essentially a search (matching) problem of finding, for each row of one set, the matching row in the other set, and how that search is organized is precisely what differentiates the algorithms. Comparing every row pair with no strategy costs in proportion to the product of the two tables (Cartesian product), but using sorting or a hash table can lower that cost close to linear.

Why a join is intrinsically an expensive operation is also clear set-theoretically. Joining two relations is conceptually equivalent to producing the Cartesian product (all combinations of rows) and then keeping only the rows that satisfy the join condition. If A has 1 million rows and B has 1 million rows, the Cartesian product becomes 1 trillion (10^12) combinations, so no matter how efficiently the condition filters, the naive way of 'actually producing the product and then filtering' is practically impossible. All three join algorithms are methods that 'directly find only the pairs satisfying the condition without actually producing the product', and their means are respectively index search·sort order·hash addressing. Studying join algorithms ultimately means understanding 'three engineering tricks that reduce an exponential search space close to linear'.

The reason a relational DBMS chooses the join algorithm automatically is that SQL is a declarative language. The user writes only the 'meaning' of the combination, not the 'procedure' of it, so the optimal procedure changes every time data volume and distribution change. The join algorithms that commercial·open-source DBMSs commonly implement fall into three broad kinds — Nested Loop Join, Sort-Merge Join, and Hash Join — and the Cost-Based Optimizer (CBO) selects the cheapest of these for each query based on statistics.

B. Need and Position

The choice of join algorithm is a decisive variable governing query performance. For example, in a query combining an order table (10 million rows) and a customer table (1 million rows), when the condition filters out only a tiny few, a Nested Loop going through an index finishes in milliseconds; but in a batch-type query that must combine most of the two tables, using the same Nested Loop causes hundreds of millions of random I/Os and takes tens of minutes. Conversely, using a Hash Join for this batch query scans each table only once and finishes in a few seconds. In other words, a single algorithm choice changes service responsiveness and resource consumption nonlinearly.

A join algorithm is a core component of the execution plan that the optimizer builds within the SQL-processing pipeline (parsing → optimization → execution). The optimizer combines three axes — ① access path (index vs full scan), ② join order (which table to read first), and ③ join method (algorithm) — to produce candidate plans and compare their cost. Therefore, understanding each algorithm's operating principle·cost structure·preconditions is a core capability that forms the foundation of DB tuning, hint design, execution-plan interpretation, and capacity planning.

2. Overall Structure of Join Algorithms

The three algorithms solve the common goal of 'how to find the pairs' with different strategies. The overall structure diagram below shows how a join request branches, via the optimizer, into three physical algorithms.

flowchart TB
  SQL["Join query(FROM A JOIN B ON ...)"] --> OPT["Optimizer(CBO)"]
  STAT["Statistics(cardinality·distribution·index)"] --> OPT
  OPT --> NL["Nested Loop Join"]
  OPT --> SM["Sort-Merge Join"]
  OPT --> HJ["Hash Join"]
  NL --> NLU["Favorable for small set·index present"]
  SM --> SMU["Favorable when pre-sorted·inequality join"]
  HJ --> HJU["Favorable for large equi-join·unsorted"]
  style OPT fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
  style STAT fill:#fef3e8,stroke:#ed8f2f,stroke-width:2px

What must be distinguished here is join order and join method. Join order is the question of 'which table to read first to reduce the result (driving table)', while join method is the question of 'which algorithm to combine the two chosen sets with'. If there are three or more tables, the optimizer performs joins two at a time in stages (left-deep or bushy tree), deciding the order and method together at each stage. Because the size of the intermediate result set governs the cost of the next stage, finding 'the order that filters small first' is as important as the method choice. As the number of joined tables grows, the possible combinations of order explode factorially, so the optimizer limits the search space with dynamic programming·heuristics.

The essential difference among the three algorithms lies in 'where the pair-finding cost is reduced'. Nested Loop searches the other table one row at a time but accelerates the search with an index — that is, it relies on 'locality of search'. Sort-Merge pre-sorts both sides and finds pairs in a single simultaneous traversal (merge) — that is, it relies on 'the order that sorting creates'. Hash Join builds a hash table from one side and finds pairs with constant-time lookup — that is, it relies on 'the direct addressing that hashing creates'. Because these three strategies each have different preconditions (index·sort·memory), their superiority flips depending on the data situation. This is why the optimizer re-chooses per query rather than fixing one.

3. Nested Loop Join

Nested Loop Join is the most intuitive method, finding pairs satisfying the join condition by repeatedly searching the inner table for each row of the outer (driving) table. As its name suggests, it has a double-loop structure, where the outer loop takes the leading set one row at a time and the inner loop scans the trailing set with that row's join key.

In this structure the outer table is called the 'driving table', and because the size of the leading set determines the total number of iterations, the join order of 'placing the small set on the outside' governs half the performance. The optimizer looks at statistics and chooses the side that produces fewer results as the leading one, but if statistics are distorted, it may wrongly choose the large set as leading, causing an accident where iterations explode.

The key is 'whether the inner table has an index on the join key'. If there is an index, the inner search changes from a full scan to an index search (random access), finding a pair with just a few block reads per outer row. In this case the total cost is roughly proportional to 'outer count × (index search + table random access)'. Therefore it is overwhelmingly favorable when the outer set is small and the inner has an appropriate index. For example, a query attaching each person's order history (inner, with a customer-ID index) to '50 customers who signed up today' (outer) finishes with just 50 index searches.

Conversely, a large outer set is fatal. If the outer is 1 million rows, the inner index search is repeated 1 million times, and this random I/O entails disk head movement (or random access on SSD), making it far slower than sequential I/O. Also, if the inner has no index, the inner is fully scanned for each outer row, so the cost explodes in proportion to the product of the two table counts (Cartesian product). To mitigate this, modern DBMSs use variants such as block Nested Loop (bundling several outer rows and processing in buffer units), inner block caching, and access after sorting outer keys (prefetch).

Nested Loop also has the practical advantage of being favorable for partial range processing. Because it produces the result one row at a time from the start, it can take just as many as needed and stop without processing the whole, in OLTP queries that need only the top few, such as ROWNUM <= 10 or LIMIT 10. That is why it is used by default for OLTP transactions·screen paging·small-result lookups.

Another variable that determines Nested Loop's performance is the clustering factor, that is, the degree of alignment between index order and actual table storage order. If the rows found via the inner index are scattered across table blocks (bad clustering factor), each outer row must randomly access a different block, so perceived performance drops even with an index. Conversely, if the join-key order matches the storage order, the probability of revisiting the same block rises, buffer-cache hit rate increases, and random I/O decreases. So Nested Loop tuning must look beyond 'whether an index was created' to 'whether the rows the index points to are physically clustered'. In this respect, join algorithm choice also touches table design·load order.

flowchart LR
  O["Outer table(small·leading)"] --> R1["Row 1 → search Inner by join key"]
  O --> R2["Row 2 → search Inner by join key"]
  O --> R3["Row N → search Inner by join key"]
  R1 --> IDX["Inner join-key index"]
  R2 --> IDX
  R3 --> IDX
  IDX --> RES["Return matched row"]
  style IDX fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px

4. Sort-Merge Join

Sort-Merge Join is a method that sorts each of the two tables by the join key, then matches pairs by scanning the two sorted streams simultaneously (merge). Picture placing two phone books side by side and going down looking for the same name. If both sets are sorted in the same order, pairs can be found by reading each set sequentially just once while advancing pointers.

The basis for Sort-Merge holding is the property that 'to find common elements in two sorted sequences, it suffices to scan each side just once'. Because both are sorted in the same key order, if one side's key is smaller than the other's, only the smaller side needs to advance, with no need to go back. However, when the join key has duplicates (one-to-many·many-to-many), one pointer must be rewound in the matching segment to output all combinations, so if duplication is high, the merge stage too incurs a light backtracking.

This algorithm is broadly divided into a Sort stage and a Merge stage. In the sort stage the two sets are sorted in join-key order, and this cost of roughly N log N dominates the total cost. The merge stage is a linear traversal (O(N + M)) that compares both pointers, advances the smaller, and outputs to the result when keys are equal. Therefore how much the sort cost can be reduced is the crux, and if already sorted (when sort order is guaranteed by an index full scan, or when a previous operation's output is sorted), the sort stage can be skipped, making it very efficient.

The decisive strength of Sort-Merge Join is that it can process inequality (non-equi) joins. Because Hash Join judges only equality of hash values, it works only on = (equi) conditions; but Sort-Merge uses the sorted order, so it can also apply to conditions such as >=, BETWEEN, and range overlap. For example, a range join that 'maps discount policies whose product price falls in a certain interval' is a typical domain of Sort-Merge. Also, the sort result can be reused directly for ORDER BY or GROUP BY, giving an extra benefit when a subsequent operation requires sorting.

The limit is the sort cost. If both sets are large and not sorted, two large-scale sorts (external sort using disk if needed) precede, which can be slower than Hash Join. In the past, before Hash Join became standard, it was the default for large joins, but today the seat of large-volume equi-join processing has mostly been taken by Hash Join, and Sort-Merge is selected under the conditions of 'already sorted' or 'inequality join'.

If memory is insufficient in the sort stage, it switches to external sort, writing intermediate results to temporary disk in several runs and merging again. When this disk writing·reading is added, the sort cost grows further, so even when using Sort-Merge, the size of the sort work area (e.g., Oracle's SORT_AREA/PGA) governs performance. Conversely, if the join key already has a B+Tree index so that sort order is guaranteed by an index full scan alone, the sort stage can be omitted entirely and finished with just the merge traversal. Thus 'whether sorting can be obtained for free' becomes the practical criterion for adopting Sort-Merge.

Category Nested Loop Sort-Merge Hash Join
Basic strategy Search inner per outer row Sort both, then merge-traverse Build hash table + probe
Favorable situation Small set·index present Already sorted·inequality join Large equi-join·unsorted
Join condition Both equi·inequality Both equi·inequality Equi (=) only
Index dependence High (inner index near-essential) Low (sort substitutes) None (hash substitutes)
Memory sensitivity Low Medium (sort area) High (hash area)
Partial range processing Excellent (early return) Unfavorable (needs sort complete) Unfavorable (needs build complete)
Representative cost Outer count × inner search N log N + M log M N + M (when memory sufficient)

5. Hash Join

Hash Join is a method that builds a hash table of the join key in memory from the smaller table (build input), then reads the larger table (probe input) one row at a time and looks up the same hash bucket to find pairs. The key is that hash-table lookup is average constant time (O(1)), which allows finding each row's pair immediately while sequentially scanning the large table just once. The total cost, if memory is sufficient, converges to roughly O(N + M), reading the two tables once each.

As an actual industry case, consider a large e-commerce daily sales aggregation batch. In a typical star-schema query that aggregates tens of millions of daily order logs (fact) combined with product·member·region dimension tables (dimension), because the dimension tables are small and the fact is huge, a Hash Join that builds a hash table from each dimension and scans the fact once finishes processing within tens of seconds. Doing the same work with Nested Loop can take hours by repeating dimension index searches for tens of millions of rows. This is why it is no exaggeration to say that data-warehouse·BI aggregation stands on Hash Join.

The operation is divided into two stages, Build and Probe. In the build stage the optimizer looks at statistics, chooses the smaller set, applies a hash function to its join key, and builds a hash table loaded per bucket. In the probe stage it applies the same hash function to each row of the large set to find the corresponding bucket, confirms the actual key match within the bucket, and outputs the result. The smaller the build set, the more the hash table fits entirely in memory and the fastest it is, so the choice of 'making the small table the build' governs performance.

The decisive strength of Hash Join is that it is fast even without an index in large-data equi-joins. Unlike Nested Loop, which repeats random I/O as many times as the outer count, Hash Join does only sequential scans (sequential I/O) of both sides, so it is overwhelmingly favorable in large-volume batch·DW aggregation·ETL. For example, an analytic query combining 100 million sales rows and 100 thousand products by product code builds a hash table from the 100 thousand products and scans the 100 million sales once to finish — no index at all is needed.

The weakness is the constraint of being memory- and equi-join-only. If the build set is larger than available memory (hash area), the hash table does not all fit in memory, so it switches to Grace Hash Join / hybrid hash, which splits data into several partitions, writes them to disk, and reads them back. Since disk I/O increases and performance drops at this point, setting the hash-area size (e.g., Oracle PGA, PostgreSQL work_mem) is important. Also, because hash judges only value equality, it can be used only on = conditions and cannot apply to inequality joins such as >·BETWEEN, in which case it falls back to Sort-Merge or Nested Loop. One must also note that if data skew is severe and values concentrate in a specific bucket, hash collisions increase and performance degrades.

To unpack Grace Hash Join's operation a bit more, it splits both build·probe sides into N partitions with the same hash function, stores them on disk, and then re-reads and joins only the partition pairs of the same number. Because rows that could be pairs necessarily go into the same hash partition, even a large volume that cannot all be loaded into memory at once can be handled by repeating 'in-memory join split per partition'. Hybrid hash additionally keeps the first partition in memory without writing it to disk, a compromise that reduces disk round-trips within the possible range. Thanks to such mechanisms, Hash Join has stable scalability of 'very fast when memory is sufficient, and gently slower even when insufficient' — this is why large-volume DWs adopt Hash Join as the default weapon for joins.

6. Comparison and Selection Criteria: Why the Difference Arises

The fundamental reason the superiority of the three algorithms flips depending on the situation is that 'what the dominant cost of pair-finding is' changes with data volume·sort·index·memory. In OLTP queries that extract a small result, 'how little you touch' matters, so Nested Loop, which processes only the small outer set and returns early, wins. Conversely, in OLAP·batch queries that combine everything at large volume, 'how many times you read the whole' matters, so Hash Join, which scans the two tables sequentially just once each, wins. Sort-Merge fills the niche in between of 'already sorted so no sort cost, or inequality so hash cannot be used'.

From this viewpoint, the question of 'which algorithm is better' itself does not hold. The three algorithms are not in a superiority relationship but in a complementary relationship with different application domains, and each is best only in the range where its preconditions (index·sort·memory) are met. That the optimizer does not permanently adopt one but re-chooses per query·per statistics change, and that adaptive execution even switches at runtime, is precisely because of this complementarity. The engineer's role is not 'choosing the best algorithm' but 'arranging data and statistics so that each query is placed in the correct algorithm range'.

The practical implications are clear. First, index strategy and join algorithm are one body. If you intend Nested Loop, an inner join-key index is essential; if you intend Hash Join, sequential-scan efficiency (partitioning·compression) matters more than an index. Second, statistics freshness changes algorithm choice. If statistics are stale and a large set is misjudged as small, the optimizer picks Nested Loop instead of Hash Join, causing the typical failure where a few-second query becomes tens of minutes — so when an execution plan suddenly slows, check statistics and join method first. Third, optimizer hints (USE_NL, USE_HASH, USE_MERGE, etc.) can force the algorithm, but one must not forget that this is only a temporary remedy for distorted statistics, and the fundamental solution is correcting statistics·indexes·query structure.

Adding a concrete sense of numbers: in a 10 million ⨝ 1 million equi-join where the result occupies most of the whole, Hash Join finishes with two sequential scans (a few seconds); but forcing the same query to Nested Loop takes tens of minutes with 10 million index-search random I/Os. Conversely, in a query finding 'the orders of 10 customers who just signed up', Nested Loop finishes with 10 index searches (milliseconds); but forcing it to Hash Join wastes a few seconds scanning all 10 million orders to build a hash table. For the same two tables, the 'selectivity of the result' completely flips the superiority of the algorithm.

Summarizing the selection guidance in one sentence: "If selectivity is low (small result) so the leading set can be made small and the trailing side has an index, Nested Loop; if selectivity is high (large result) requiring both sides to be read and it is an equi-join, Hash Join; if one side is already sorted or the join condition is an inequality, Sort-Merge." In practical tuning this guidance is used in reverse — that is, 'designing indexes·statistics·query structure so that the desired algorithm comes out'. For example, if a small-result OLTP query is oddly resolved as Hash Join, reinforce the condition that narrows the leading set and the trailing join-key index to induce the optimizer to choose Nested Loop. Conversely, if a large batch is resolved as Nested Loop and is slow, refresh statistics or induce Hash Join with a USE_HASH hint. Thus, knowing the algorithms' principles lets you diagnose 'why it is slow' and design 'how to induce it'.

7. Advanced: Evolution of Join Processing in Modern DBMSs and Practical Application

The basic three join algorithms have not changed for decades, but the optimization techniques built on top of them have steadily advanced. The latest trends encountered in practice are organized into three.

These three flows all attack different points under the common goal of 'reducing join cost further'. Adaptive join targets the accuracy of the choice, parallel·distributed join the scalability of processing, and join elimination·pre-aggregation the reduction of the workload itself. In both the professional-engineer exam and practice, one must be able to weave these three axes together and design 'why it is slow → at which level (choice·scaling·elimination) to intervene'.

First is the Adaptive Join. Like Oracle 12c's Adaptive Plan and SQL Server's Adaptive Join, the optimizer does not fix on one method before execution but dynamically switches between Nested Loop and Hash Join by observing the actual processed row count during execution. This is an attempt to correct at runtime the problem of 'divergence between estimated cardinality and reality' caused by statistics error, serving as a safeguard that prevents serious misjudgment even when statistics are somewhat inaccurate. In the same vein, PostgreSQL has broadened the direction of improving the next execution with statistics collected during execution.

Second is parallel join and distributed join. In large-volume analytic environments (MPP DW, Spark, Presto/Trino, etc.), a hash join is split across multiple nodes and performed in parallel. Here the choice between the shuffle (repartition) join that redistributes both sides by join key and the broadcast join that replicates the small table to all nodes to eliminate shuffling governs distributed performance. If one side is small enough, broadcast eliminates network-shuffle cost and is overwhelmingly fast, which is a form of the single-node Hash Join 'make the small side the build' principle extended to a distributed environment. On join keys with severe data skew, a 'skew join' problem arises where work concentrates on a specific node, so skew optimization that handles hot keys separately is applied.

In addition, dedicated handling by the kind of join operation (semi/anti/outer join) is also important. EXISTS·IN are semi joins that need only one match, stopping the search at the first match to reduce cost. NOT EXISTS is an anti join using the inverse logic, and OUTER JOIN must preserve rows with no match by filling with NULL, so the algorithm implementation differs slightly. The optimizer changes these into ordinary joins via subquery unnesting to reuse the three algorithms, but additionally optimizes by exploiting the 'early termination' characteristic of semi/anti. Even the same Hash Join, if it is a semi join, marks only whether the build side matched and stops.

Third is join elimination and pre-aggregation. The optimizer eliminates joins that do not affect the result when foreign-key–primary-key integrity is guaranteed (join elimination), and the strategy of pre-computing frequently used join results into a Materialized View is standard in DWs. Also, combined with columnar storage·vectorized execution engines, hardware-friendly implementations that process hash joins in SIMD units to raise CPU efficiency have become common. In practice, confirming in the execution plan (EXPLAIN, EXPLAIN ANALYZE, Oracle DBMS_XPLAN) which join method was chosen and the difference between estimated and actual row counts is the starting point of tuning.

8. Considerations and Implications

Because join algorithms are not mere theory but a practical core that divides performance·resources·operational stability, from a professional-engineer viewpoint the following must be considered comprehensively. In particular, keeping in mind that a join is a relationship where 'indexes·partitions·statistics decided at design time' and 'the algorithm chosen at execution time' constrain each other, it is desirable to pre-reflect a join strategy matched to expected query patterns from the physical design stage.

  • Application strategy — inducing the algorithm matched to query nature: For OLTP (small·high-concurrency), optimize for Nested Loop and index design; for OLAP·batch (large·aggregation), optimize for Hash Join and sequential-scan efficiency (partitioning·compression·degree of parallelism). When using one DBMS for a workload where OLTP/OLAP are mixed, the characteristics of each query group must be separated and index·statistics·memory strategies applied differentially.

  • Trade-off — memory vs I/O, responsiveness vs throughput: Hash Join is an exchange of using memory to reduce I/O, and if the hash area is insufficient it falls to disk-based and the benefit vanishes. Nested Loop is insensitive to memory but random I/O explodes at large volume. Also, Nested Loop gives the first result quickly (responsiveness) whereas Hash/Sort-Merge must process everything (throughput), so the choice differs depending on whether the SLA is 'first-response time' or 'total completion time'.

  • Operational stability — statistics management and plan stabilization: Since 90% of join-method misjudgment stems from 'stale or inaccurate statistics', regular·automatic statistics collection and histograms (representing skewed distribution) must precede. For important queries, place 'plan stability' devices such as SQL Plan Baseline·plan fixing, hints, and result cache to prevent failures from plans suddenly changing.

  • Diagnostic capability — reading execution plans: The starting point of failure response is reading via EXPLAIN/EXPLAIN ANALYZE 'which join method the optimizer chose, and how far estimated rows and actual rows diverged'. If the divergence of the two is large, suspect statistics·cardinality estimation error, and identify whether the slow stage is Nested Loop's excessive iteration, Hash Join's disk spill, or Sort-Merge's external sort, prescribing by cause.

  • Outlook and related technologies: With the spread of adaptive execution, vectorization·GPU acceleration, and distributed query engines, join processing is moving from 'static choice' to 'runtime adaptation'. Join-algorithm knowledge is tightly linked with [[db-optimizer]](Optimizer RBO·CBO), [[btree-bplus-index]](index structures), [[db-tuning]](DB tuning), [[materialized-view]](Materialized View), and [[columnar-storage]](columnar storage), and integrating these into one performance system to understand·design is the capability required of a professional engineer.

References

In one line: A join algorithm is a physical strategy for finding the pairs of two tables — Nested Loop for small·indexed, Sort-Merge for already-sorted·inequality, and Hash Join for large equi-joins — and the quality of that choice ultimately depends on accurate statistics and appropriate index·memory design.