https://sqlmaster.mssqlplanner.com

Tag: Join Algorithms

  • SQL Server Join Algorithms: Nested Loop, Hash Match, and Merge Join Explained

    SQL Server Join Algorithms: Nested Loop, Hash Match, and Merge Join Explained

    Every JOIN you write compiles down to one of three physical algorithms. The optimizer picks based on table sizes, available indexes, and sort order — not the JOIN keyword you typed.

    Join Algorithms, sketched out(the optimizer picks — not your JOIN keyword)Nested Loopoutersmall sideseek indexper rowrepeat × each outer rowO(N × seek cost)Hash Matchbuild (small)probe (large)hash tablespills to tempdb if too bigO(N + M), memory-hungryMerge Joinwalk both sorted inputs, onceO(N + M), needs sort orderfree when sort comes from a clustered index

    The Three Algorithms

    Algorithm Best when Cost profile
    Nested Loop One side is small, other side is indexed on the join key Cheap for small × large with a good index; terrible for large × large
    Hash Match Both sides large, no useful sort order Builds an in-memory hash table on the smaller side; can spill to tempdb if too big
    Merge Join Both sides already sorted on the join key Very cheap when sort order is free (e.g. from a clustered index)

    Visualizing the Decision

    Nested Loop For each outer row, seek the inner index O(N × seek cost) Hash Match Build hash table on smaller input, probe with larger O(N + M), memory-hungry Merge Join Walk both sorted inputs in lockstep, once O(N + M), needs sort order

    Reading It in the Plan

    This is exactly the Chapter 3 execution-plan-reading skill (Developers & DBAs course) applied to a new operator family — the same right-to-left reading order, now watching for which JOIN algorithm appears rather than Seek vs Scan.

    When you see Hash Match on a query you expected to be a quick lookup, that’s a strong signal one side of the join is much larger than expected, or a useful index is missing. When you see Nested Loop with a huge outer row count, that’s the opposite problem — an algorithm suited for small inputs being forced onto a large one.

    Enjoyed this?

    Subscribe to get every new lesson as soon as it’s published, and share it with a developer who’d find it useful.

    📡 Subscribe via RSS  | 
    Share on X  | 
    Share on LinkedIn  | 
    Share on Facebook

    Want the full structured course with quizzes and hands-on labs? Check out SQL Server Performance Tuning, coming soon on this site.