Merge Join

Description

Joins ordered input streams using merge clauses.

Core node tag

T_MergeJoin

Structured EXPLAIN Node Type

Merge Join

Inputs

Ordered outer and inner child plans

Output

Joined tuples according to the selected join type

Executor initializer

ExecInitMergeJoin

Memory mechanism

unclassified

EXPLAIN names and attributes

Structured formats use the Node Type above. Text-format spellings can also include operation, strategy, join type, scan direction or aggregation-stage attributes.

Text names recorded by this source: Merge.

Parallel-aware and parallel-safe are different plan properties. A node running inside a parallel worker is not necessarily a parallel-aware node.

Memory and temporary storage

This extraction does not assign a universal memory limit or spill policy to this node. Inspect the same-build implementation and its expressions or provider.

Parallel execution and instrumentation

The source callbacks below can coordinate execution or collect worker instrumentation. Their presence is not a blanket claim that this node supports a shared parallel scan or shared state.

Callbacks in this build: none extracted from this node implementation.

Same-version manual discussion

Merge join requires its input data to be sorted on the join keys. In this example each input is sorted by using an index scan to visit the rows in the correct order; but a sequential scan and sort could also be used. (Sequential-scan-and-sort frequently beats an index scan for sorting many rows, because of the nonsequential disk access required by the index scan.)

One way to look at variant plans is to force the planner to disregard whatever strategy it thought was the cheapest, using the enable/disable flags described in Section 19.7.1 . (This is a crude tool, but useful. See also Section 14.3 .) For example, if we're unconvinced that merge join is the best join type for the previous example, we could try

which shows that the planner thinks that hash join would be nearly 50% more expensive than merge join for this case. Of course, the next question is whether it's right about that. We can investigate that using EXPLAIN ANALYZE , as discussed below .

As seen in this example, when the query is an INSERT , UPDATE , DELETE , or MERGE command, the actual work of applying the table changes is done by a top-level Insert, Update, Delete, or Merge plan node. The plan nodes underneath this node perform the work of locating the old rows and/or computing the new data. So above, we see the same sort of bitmap table scan we've seen already, and its output is fed to an Update node that stores the updated rows. It's worth noting that although the data-modifying node can take a considerable amount of run time (here, it's consuming the lion's share of the time), the planner does not currently add anything to the cost estimates to account for that work. That's because the work to be done is the same for every correct query plan, so it doesn't affect planning decisions.

When an UPDATE , DELETE , or MERGE command affects a partitioned table or inheritance hierarchy, the output might look like this:

Merge joins also have measurement artifacts that can confuse the unwary. A merge join will stop reading one input if it's exhausted the other input and the next key value in the one input is greater than the last key value of the other input; in such a case there can be no more matches and so no need to scan the rest of the first input. This results in not reading all of one child, with results like those mentioned for LIMIT . Also, if the outer (first) child contains rows with duplicate key values, the inner (second) child is backed up and rescanned for the portion of its rows matching that key value. EXPLAIN ANALYZE counts these repeated emissions of the same inner rows as if they were real additional rows. When there are many outer duplicates, the reported actual row count for the inner child plan node can be significantly larger than the number of rows that are actually in the inner relation.

Examples from this manual build

Example copied from the PostgreSQL 18.6 manual; it was not executed for this collection.

Another possible type of join is a merge join, illustrated here:

EXPLAIN SELECT *
FROM tenk1 t1, onek t2
WHERE t1.unique1 < 100 AND t1.unique2 = t2.unique2;

                                        QUERY PLAN
------------------------------------------------------------------------------------------
 Merge Join  (cost=0.56..233.49 rows=10 width=488)
   Merge Cond: (t1.unique2 = t2.unique2)
   ->  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..643.28 rows=100 width=244)
         Filter: (unique1 < 100)
   ->  Index Scan using onek_unique2 on onek t2  (cost=0.28..166.28 rows=1000 width=244)

Executor implementation notes

Merge-join is done by joining the inner and outer tuples satisfying join clauses of the form ((= outerKey innerKey) ...). The join clause list is provided by the query planner and may contain more than one (= outerKey innerKey) clause (for composite sort key).

However, the query executor needs to know whether an outer tuple is "greater/smaller" than an inner tuple so that it can "synchronize" the two relations. For example, consider the following relations:

outer: (0 ^1 1 2 5 5 5 6 6 7) current tuple: 1 inner: (1 ^3 5 5 5 5 6) current tuple: 3

To continue the merge-join, the executor needs to scan both inner and outer relations till the matching tuples 5. It needs to know that currently inner tuple 3 is "greater" than outer tuple 1 and therefore it should scan the outer relation first to find a matching tuple and so on.

Therefore, rather than directly executing the merge join clauses, we evaluate the left and right key expressions separately and then compare the columns one at a time (see MJCompare). The planner passes us enough information about the sort ordering of the inputs to allow us to determine how to make the comparison. We may use the appropriate btree comparison function, since Postgres' only notion of ordering is specified by btree opfamilies.

EXPLAIN identity in core source

case T_MergeJoin:
			pname = "Merge";	/* "Join" gets added by jointype switch */
			sname = "Merge Join";
			break;

Related entries

• EXPLAIN
• Using EXPLAIN
• Parallel plans
• enable_mergejoin

Documentation and source

• src/backend/commands/explain.c:1424
• src/backend/executor/execProcnode.c:302
• src/backend/executor/nodeMergejoin.c
• src/include/nodes/plannodes.h
• PostgreSQL 18.6 · using-explain
• PostgreSQL 18.6 · using-explain
• PostgreSQL 18.6 · using-explain

Compare versions

PostgreSQL 17 → 18: unchanged.

Compares recorded interfaces and attributes. Source fingerprints and build metadata are excluded; an absent sample is not proof of the introduction or removal release.

Related entries

• HashHash
• Hash JoinHashJoin
• Nested LoopNestLoop