Must the inputs already be stored in sorted order?

No. A suitable ordering can be produced as part of execution.

Does each matching key produce one output row?

Not necessarily. Multiple rows with that key on both sides produce multiple combinations.

Is merge-scan always the fastest join?

No. The complete workload, input properties and alternative plans matter.

AI Glossary / Data engineering and architecture / Advanced

Merge-scan

Definition

Merge-scan is a way of joining two ordered collections by moving through their join-key values together and combining matching rows. In database query processing, it is commonly discussed as merge join or sort-merge join. Sorting may be performed first or supplied by a suitable existing access path. The method joins records; it does not refer to the SQL MERGE statement used to change stored data.

What it means

A join asks which records belong together under a specified condition. If both inputs are already arranged by that condition's key, a processor can compare their current positions instead of searching the entire second collection for every first-side record. PostgreSQL describes this ordered traversal as one of its join strategies. In an original learning-platform example, a roster and an attendance list could be matched by offering ID. The meaning of the output still depends on the chosen key: matching two lists by offering alone does not establish that the same learner appears in both.

How it works

For a simple equality join, compare the current key on each sorted input. Advance past a smaller key until a match becomes possible; when keys match, produce the required combinations. Repeated keys require handling whole matching groups, rather than assuming one row matches only one other row. PostgreSQL documents explicit sorting and appropriately ordered index scans as ways to obtain the required order. Its EXPLAIN output can show the join and its input operations. Costs must include obtaining the order and producing the output; an efficient traversal cannot make a very large requested result disappear.

Three practical examples

A reporting query joins ordered equipment records with ordered inspection records, using an agreed equipment identifier.
A data engineer inspects whether a large reconciliation query spends substantial time sorting its inputs before combining them.
An AI analytics team checks a join's repeated-key behavior before allowing a generated summary to treat joined rows as distinct learners.

Think of it this way

Imagine two alphabetized stacks of appointment cards. You move through both stacks, advancing the stack with the earlier name until matching names appear. If several cards in each stack share a name, you must decide which combinations the task requires. Alphabetical order helps locate the group; it does not prove that every person with the same name is the same individual. Database identifiers and join conditions address that separate question.

Worked example

Consider an original equality inner join with left rows A1 carrying key 1, A2 carrying key 2 and A3 carrying key 2. The right rows are B1 carrying key 2, B2 carrying key 2 and B3 carrying key 3. Both inputs are sorted by key. Key 1 has no right-side match, so A1 contributes nothing. At key 2, two left rows meet two right rows, producing four pairs: A2-B1, A2-B2, A3-B1 and A3-B2. Key 3 has no left-side match. The result therefore contains four rows. If someone expected only two, the algorithm has not necessarily duplicated records incorrectly: the stated equality condition requires all four combinations. This example assumes no additional filters and no null keys. It illustrates result cardinality, not a measured runtime or a particular database's internal buffering strategy.

Illustrative case study

In a fictional AI course-reporting service, a query combines registrations and feedback using offering ID alone. The report overstates the number of learners with feedback. An engineer notices a merge join in the plan, but changing the physical join method would not repair the underlying matching condition. Reviewers use a miniature dataset like the worked example to expose the multiple combinations. They then define whether the business question requires matching by learner and offering, aggregating first, or counting distinct eligible learners. The scenario illustrates separating a query's meaning from its execution strategy. It does not claim that merge joins uniquely cause inflated counts or that adding DISTINCT always repairs a wrongly specified join.

Common misconceptions and mistakes

A merge-scan is not a general instruction to combine two files line by line. The keys and join condition determine the matches. Ordered input also does not imply unique input: repeated values can produce many output rows. Another mistake is ignoring the cost of sorting when comparing strategies. A plan that benefits from an existing ordering may behave differently after that ordering is unavailable. Finally, the word merge in an execution plan should not be interpreted as an update to stored records. A read-only join and a data-modification statement serve different purposes.

Business use

When an AI feature repeatedly combines large datasets, ask whether the chosen keys express the business relationship before investigating speed. In the fictional course report, verify the expected counts using a small, hand-checkable sample. Then examine the actual execution plan and measure the complete query with representative data, including unevenly frequent keys. Record whether time is spent preparing inputs, producing matches or returning results. This makes a performance decision more useful than choosing a join strategy because its name sounds efficient. Changes should preserve the intended result while addressing the observed bottleneck.

Check your understanding

Why does the toy key 2 produce four rows?

Answer: Two left matches combine with two right matches.

Does switching to another correct join method remove those combinations?

Answer: No; the stated query still requires them.

Which part of the problem should be reviewed if those pairs are inappropriate?

Answer: The join condition and business definition.

What additional work might be needed before ordered traversal begins?

Answer: Sorting the inputs.

Related terms

Hash join
Sort-merge join
nested-loop join
query plan
join cardinality
sort order

Learn next

Create two short lists containing repeated keys and enumerate their equality-join pairs by hand. Then change the matching condition to include a second identifier. Explain why the result changes even if the database uses the same physical join strategy.

Sources

PostgreSQL documentation, Planner/Optimizer: https://www.postgresql.org/docs/current/planner-optimizer.html PostgreSQL documentation, Using EXPLAIN: https://www.postgresql.org/docs/current/using-explain.html The row-pair example, appointment-card analogy and course-reporting scenario are original educational illustrations. Performance conclusions require measurements of the actual workload.

Previous: Mercer's theorem Next: Merit function