{"kind": "plan", "major": "18", "item": {"slug": "merge-join", "name": "Merge Join", "name_zh": "MergeJoin", "category": "Join", "summary": "Joins ordered input streams using merge clauses.", "aliases": ["Merge", "MergeJoin", "T_MergeJoin"], "content_hash": "fc2274bf13780cd868a3c75ea485339a90f50f739c2df501be1d6ee5c65b27c8", "versions": {"10": {"facts": [{"label": "Core node tag", "value": "T_MergeJoin"}, {"label": "Structured EXPLAIN Node Type", "value": "Merge Join"}, {"label": "Inputs", "value": "Ordered outer and inner child plans"}, {"label": "Output", "value": "Joined tuples according to the selected join type"}, {"label": "Executor initializer", "value": "ExecInitMergeJoin"}, {"label": "Memory mechanism", "value": "unclassified"}], "memory": {"evidence": [{"url": "https://ftp.postgresql.org/pub/source/v10.23/postgresql-10.23.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "6243569c57308f37d4ee23e2a477cc19928bc6cce4511c556d66cbc39e0d7ef4", "archive_sha256": "94a4b2528372458e5662c18d406629266667c437198160a18cdfd2c4a4d6eee9"}], "mechanism": "unclassified", "description": "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.", "source_notes": []}, "tables": [{"key": "explain-labels", "rows": [{"label": "Merge", "identity": "Merge Join"}], "title": "EXPLAIN labels in this source build", "columns": [{"key": "label", "label": "Text-format label"}, {"key": "identity", "label": "Structured node identity"}]}], "related": [{"url": "/wiki/sql/explain/?v=10", "label": "EXPLAIN"}, {"url": "/docs/10/using-explain.html", "label": "Using EXPLAIN"}, {"url": "/docs/10/parallel-plans.html", "label": "Parallel plans"}, {"url": "/wiki/guc/enable_mergejoin/?v=10", "label": "enable_mergejoin"}], "release": {"ref": "PostgreSQL 10.23 source archive", "label": "10.23", "major": "10", "channel": "historical", "revision": "94a4b2528372458e5662c18d406629266667c437198160a18cdfd2c4a4d6eee9", "source_url": "https://ftp.postgresql.org/pub/source/v10.23/postgresql-10.23.tar.bz2", "source_snapshot_utc": ""}, "sources": [{"url": "https://ftp.postgresql.org/pub/source/v10.23/postgresql-10.23.tar.bz2", "line": 924, "path": "src/backend/commands/explain.c", "label": "src/backend/commands/explain.c:924", "sha256": "a785298532047cfeda969e78c3597a343dc1c56d61ba85830b0f16a02a14b5a1", "archive_sha256": "94a4b2528372458e5662c18d406629266667c437198160a18cdfd2c4a4d6eee9"}, {"url": "https://ftp.postgresql.org/pub/source/v10.23/postgresql-10.23.tar.bz2", "line": 295, "path": "src/backend/executor/execProcnode.c", "label": "src/backend/executor/execProcnode.c:295", "sha256": "cea76648bb38ae55f18f989768bee1a4ee025691ceea0f86bccb29dcdc166acc", "archive_sha256": "94a4b2528372458e5662c18d406629266667c437198160a18cdfd2c4a4d6eee9"}, {"url": "https://ftp.postgresql.org/pub/source/v10.23/postgresql-10.23.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "6243569c57308f37d4ee23e2a477cc19928bc6cce4511c556d66cbc39e0d7ef4", "archive_sha256": "94a4b2528372458e5662c18d406629266667c437198160a18cdfd2c4a4d6eee9"}, {"url": "https://ftp.postgresql.org/pub/source/v10.23/postgresql-10.23.tar.bz2", "path": "src/include/nodes/plannodes.h", "label": "src/include/nodes/plannodes.h", "sha256": "d562c321108844798cd234303fffb618f13d4ee3f3a5ac79bfd963b077e47c22", "archive_sha256": "94a4b2528372458e5662c18d406629266667c437198160a18cdfd2c4a4d6eee9"}, {"url": "/docs/10/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 10.23 \u00b7 using-explain", "sha256": "a4b4304aedb0a2da0145cc7c35b03b319a5c7ee3df35a8ef84ab6d3a610f98f3"}, {"url": "/docs/10/using-explain.html#USING-EXPLAIN-CAVEATS", "path": "using-explain.html", "label": "PostgreSQL 10.23 \u00b7 using-explain", "sha256": "a4b4304aedb0a2da0145cc7c35b03b319a5c7ee3df35a8ef84ab6d3a610f98f3"}, {"url": "/docs/10/parallel-plans.html#PARALLEL-JOINS", "path": "parallel-plans.html", "label": "PostgreSQL 10.23 \u00b7 parallel-plans", "sha256": "cd37ed0ef7e2cf177707f50d9a7258574b4cefdcc087e6ee99a3bf377d960fcb"}, {"url": "/docs/10/parallel-plans.html#PARALLEL-AGGREGATION", "path": "parallel-plans.html", "label": "PostgreSQL 10.23 \u00b7 parallel-plans", "sha256": "cd37ed0ef7e2cf177707f50d9a7258574b4cefdcc087e6ee99a3bf377d960fcb"}], "node_tag": "T_MergeJoin", "sections": [{"title": "EXPLAIN names and attributes", "paragraphs": ["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."]}, {"title": "Memory and temporary storage", "paragraphs": ["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."]}, {"title": "Parallel execution and instrumentation", "paragraphs": ["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."]}, {"title": "Same-version manual discussion", "paragraphs": ["Merge join requires its input data to be sorted on the join keys. In this plan the tenk1 data is sorted by using an index scan to visit the rows in the correct order, but a sequential scan and sort is preferred for onek , because there are many more rows to be visited in that table. (Sequential-scan-and-sort frequently beats an index scan for sorting many rows, because of the nonsequential disk access required by the index scan.)", "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.", "Just as in a non-parallel plan, the driving table may be joined to one or more other tables using a nested loop, hash join, or merge join. The inner side of the join may be any kind of non-parallel plan that is otherwise supported by the planner provided that it is safe to run within a parallel worker. For example, if a nested loop join is chosen, the inner plan may be an index scan which looks up a value taken from the outer side of the join.", "Each worker will execute the inner side of the join in full. This is typically not a problem for nested loops, but may be inefficient for cases involving hash or merge joins. For example, for a hash join, this restriction means that an identical hash table is built in each worker process, which works fine for joins against small tables but may not be efficient when the inner table is large. For a merge join, it might mean that each worker performs a separate sort of the inner relation, which could be slow. Of course, in cases where a parallel plan of this type would be inefficient, the query planner will normally choose some other plan (possibly one which does not use parallelism) instead.", "PostgreSQL supports parallel aggregation by aggregating in two stages. First, each process participating in the parallel portion of the query performs an aggregation step, producing a partial result for each group of which that process is aware. This is reflected in the plan as a Partial Aggregate node. Second, the partial results are transferred to the leader via Gather or Gather Merge . Finally, the leader re-aggregates the results across all workers in order to produce the final result. This is reflected in the plan as a Finalize Aggregate node."]}, {"title": "Examples from this manual build", "blocks": [{"code": "EXPLAIN SELECT *\nFROM tenk1 t1, onek t2\nWHERE t1.unique1 < 100 AND t1.unique2 = t2.unique2;\n\n                                        QUERY PLAN\n------------------------------------------------------------------------------------------\n Merge Join  (cost=198.11..268.19 rows=10 width=488)\n   Merge Cond: (t1.unique2 = t2.unique2)\n   ->  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..656.28 rows=101 width=244)\n         Filter: (unique1 < 100)\n   ->  Sort  (cost=197.83..200.33 rows=1000 width=244)\n         Sort Key: t2.unique2\n         ->  Seq Scan on onek t2  (cost=0.00..148.00 rows=1000 width=244)", "source": {"url": "/docs/10/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 10.23 \u00b7 using-explain", "sha256": "a4b4304aedb0a2da0145cc7c35b03b319a5c7ee3df35a8ef84ab6d3a610f98f3"}, "paragraphs": ["Example copied from the PostgreSQL 10.23 manual; it was not executed for this collection.", "Another possible type of join is a merge join, illustrated here:"]}, {"code": "SET enable_sort = off;\n\nEXPLAIN SELECT *\nFROM tenk1 t1, onek t2\nWHERE t1.unique1 < 100 AND t1.unique2 = t2.unique2;\n\n                                        QUERY PLAN\n------------------------------------------------------------------------------------------\n Merge Join  (cost=0.56..292.65 rows=10 width=488)\n   Merge Cond: (t1.unique2 = t2.unique2)\n   ->  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..656.28 rows=101 width=244)\n         Filter: (unique1 < 100)\n   ->  Index Scan using onek_unique2 on onek t2  (cost=0.28..224.79 rows=1000 width=244)", "source": {"url": "/docs/10/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 10.23 \u00b7 using-explain", "sha256": "a4b4304aedb0a2da0145cc7c35b03b319a5c7ee3df35a8ef84ab6d3a610f98f3"}, "paragraphs": ["Example copied from the PostgreSQL 10.23 manual; it was not executed for this collection.", "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 sequential-scan-and-sort is the best way to deal with table onek in the previous example, we could try"]}]}, {"title": "Executor implementation notes", "paragraphs": ["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."]}, {"code": "case T_MergeJoin:\n\t\t\tpname = \"Merge\";\t/* \"Join\" gets added by jointype switch */\n\t\t\tsname = \"Merge Join\";\n\t\t\tbreak;", "title": "EXPLAIN identity in core source"}], "strategies": [], "description": ["Joins ordered input streams using merge clauses."], "evidence_kind": "source and documentation", "explain_names": ["Merge"], "partial_modes": [], "comparison_data": {"node_tag": "T_MergeJoin", "strategies": [], "text_names": ["Merge"], "initializer": "ExecInitMergeJoin", "partial_modes": [], "memory_mechanism": "unclassified", "parallel_callbacks": []}, "comparison_hash": "b17771ee4d48585afbaba91552e5eb00f05a4b6784aa491387217937a4a30511", "explain_prefixes": ["Parallel"], "runtime_verified": false, "source_inventory": {"explain": "src/backend/commands/explain.c", "executor": "src/backend/executor/execProcnode.c", "implementation": "src/backend/executor/nodeMergejoin.c"}, "parallel_callbacks": []}, "11": {"facts": [{"label": "Core node tag", "value": "T_MergeJoin"}, {"label": "Structured EXPLAIN Node Type", "value": "Merge Join"}, {"label": "Inputs", "value": "Ordered outer and inner child plans"}, {"label": "Output", "value": "Joined tuples according to the selected join type"}, {"label": "Executor initializer", "value": "ExecInitMergeJoin"}, {"label": "Memory mechanism", "value": "unclassified"}], "memory": {"evidence": [{"url": "https://ftp.postgresql.org/pub/source/v11.22/postgresql-11.22.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "43151ca42279b11ec4428fb349dd66ee12a7a114376ff44ac1b0031fa2c5213a", "archive_sha256": "2cb7c97d7a0d7278851bbc9c61f467b69c094c72b81740b751108e7892ebe1f0"}], "mechanism": "unclassified", "description": "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.", "source_notes": []}, "tables": [{"key": "explain-labels", "rows": [{"label": "Merge", "identity": "Merge Join"}], "title": "EXPLAIN labels in this source build", "columns": [{"key": "label", "label": "Text-format label"}, {"key": "identity", "label": "Structured node identity"}]}], "related": [{"url": "/wiki/sql/explain/?v=11", "label": "EXPLAIN"}, {"url": "/docs/11/using-explain.html", "label": "Using EXPLAIN"}, {"url": "/docs/11/parallel-plans.html", "label": "Parallel plans"}, {"url": "/wiki/guc/enable_mergejoin/?v=11", "label": "enable_mergejoin"}], "release": {"ref": "PostgreSQL 11.22 source archive", "label": "11.22", "major": "11", "channel": "historical", "revision": "2cb7c97d7a0d7278851bbc9c61f467b69c094c72b81740b751108e7892ebe1f0", "source_url": "https://ftp.postgresql.org/pub/source/v11.22/postgresql-11.22.tar.bz2", "source_snapshot_utc": ""}, "sources": [{"url": "https://ftp.postgresql.org/pub/source/v11.22/postgresql-11.22.tar.bz2", "line": 1049, "path": "src/backend/commands/explain.c", "label": "src/backend/commands/explain.c:1049", "sha256": "9df8400c1a4377179572ceb916d6020fca4e2760f74bf416d77ed97476523bbd", "archive_sha256": "2cb7c97d7a0d7278851bbc9c61f467b69c094c72b81740b751108e7892ebe1f0"}, {"url": "https://ftp.postgresql.org/pub/source/v11.22/postgresql-11.22.tar.bz2", "line": 295, "path": "src/backend/executor/execProcnode.c", "label": "src/backend/executor/execProcnode.c:295", "sha256": "95ef4d4a5df4c29f14af9763fae2c530449bdacdf3853d9ff297adf1fed6153b", "archive_sha256": "2cb7c97d7a0d7278851bbc9c61f467b69c094c72b81740b751108e7892ebe1f0"}, {"url": "https://ftp.postgresql.org/pub/source/v11.22/postgresql-11.22.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "43151ca42279b11ec4428fb349dd66ee12a7a114376ff44ac1b0031fa2c5213a", "archive_sha256": "2cb7c97d7a0d7278851bbc9c61f467b69c094c72b81740b751108e7892ebe1f0"}, {"url": "https://ftp.postgresql.org/pub/source/v11.22/postgresql-11.22.tar.bz2", "path": "src/include/nodes/plannodes.h", "label": "src/include/nodes/plannodes.h", "sha256": "5e0511194183800e8d6eb293fd4b40639c7d3118e2d199c8e7865ba4fa4cf67f", "archive_sha256": "2cb7c97d7a0d7278851bbc9c61f467b69c094c72b81740b751108e7892ebe1f0"}, {"url": "/docs/11/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 11.22 \u00b7 using-explain", "sha256": "8411bc78085d4737e32d7cca103d859da6c6539e33ec5e2fba46e74c6f199d8a"}, {"url": "/docs/11/using-explain.html#USING-EXPLAIN-CAVEATS", "path": "using-explain.html", "label": "PostgreSQL 11.22 \u00b7 using-explain", "sha256": "8411bc78085d4737e32d7cca103d859da6c6539e33ec5e2fba46e74c6f199d8a"}, {"url": "/docs/11/parallel-plans.html#PARALLEL-JOINS", "path": "parallel-plans.html", "label": "PostgreSQL 11.22 \u00b7 parallel-plans", "sha256": "353df5869034b7665159a74037d9cf3e1800d15efcea3390daaa99aae89fa288"}, {"url": "/docs/11/parallel-plans.html#PARALLEL-AGGREGATION", "path": "parallel-plans.html", "label": "PostgreSQL 11.22 \u00b7 parallel-plans", "sha256": "353df5869034b7665159a74037d9cf3e1800d15efcea3390daaa99aae89fa288"}], "node_tag": "T_MergeJoin", "sections": [{"title": "EXPLAIN names and attributes", "paragraphs": ["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."]}, {"title": "Memory and temporary storage", "paragraphs": ["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."]}, {"title": "Parallel execution and instrumentation", "paragraphs": ["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."]}, {"title": "Same-version manual discussion", "paragraphs": ["Merge join requires its input data to be sorted on the join keys. In this plan the tenk1 data is sorted by using an index scan to visit the rows in the correct order, but a sequential scan and sort is preferred for onek , because there are many more rows to be visited in that table. (Sequential-scan-and-sort frequently beats an index scan for sorting many rows, because of the nonsequential disk access required by the index scan.)", "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.", "Just as in a non-parallel plan, the driving table may be joined to one or more other tables using a nested loop, hash join, or merge join. The inner side of the join may be any kind of non-parallel plan that is otherwise supported by the planner provided that it is safe to run within a parallel worker. Depending on the join type, the inner side may also be a parallel plan.", "In a merge join , the inner side is always a non-parallel plan and therefore executed in full. This may be inefficient, especially if a sort must be performed, because the work and resulting data are duplicated in every cooperating process.", "PostgreSQL supports parallel aggregation by aggregating in two stages. First, each process participating in the parallel portion of the query performs an aggregation step, producing a partial result for each group of which that process is aware. This is reflected in the plan as a Partial Aggregate node. Second, the partial results are transferred to the leader via Gather or Gather Merge . Finally, the leader re-aggregates the results across all workers in order to produce the final result. This is reflected in the plan as a Finalize Aggregate node."]}, {"title": "Examples from this manual build", "blocks": [{"code": "EXPLAIN SELECT *\nFROM tenk1 t1, onek t2\nWHERE t1.unique1 < 100 AND t1.unique2 = t2.unique2;\n\n                                        QUERY PLAN\n------------------------------------------------------------------------------------------\n Merge Join  (cost=198.11..268.19 rows=10 width=488)\n   Merge Cond: (t1.unique2 = t2.unique2)\n   ->  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..656.28 rows=101 width=244)\n         Filter: (unique1 < 100)\n   ->  Sort  (cost=197.83..200.33 rows=1000 width=244)\n         Sort Key: t2.unique2\n         ->  Seq Scan on onek t2  (cost=0.00..148.00 rows=1000 width=244)", "source": {"url": "/docs/11/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 11.22 \u00b7 using-explain", "sha256": "8411bc78085d4737e32d7cca103d859da6c6539e33ec5e2fba46e74c6f199d8a"}, "paragraphs": ["Example copied from the PostgreSQL 11.22 manual; it was not executed for this collection.", "Another possible type of join is a merge join, illustrated here:"]}, {"code": "SET enable_sort = off;\n\nEXPLAIN SELECT *\nFROM tenk1 t1, onek t2\nWHERE t1.unique1 < 100 AND t1.unique2 = t2.unique2;\n\n                                        QUERY PLAN\n------------------------------------------------------------------------------------------\n Merge Join  (cost=0.56..292.65 rows=10 width=488)\n   Merge Cond: (t1.unique2 = t2.unique2)\n   ->  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..656.28 rows=101 width=244)\n         Filter: (unique1 < 100)\n   ->  Index Scan using onek_unique2 on onek t2  (cost=0.28..224.79 rows=1000 width=244)", "source": {"url": "/docs/11/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 11.22 \u00b7 using-explain", "sha256": "8411bc78085d4737e32d7cca103d859da6c6539e33ec5e2fba46e74c6f199d8a"}, "paragraphs": ["Example copied from the PostgreSQL 11.22 manual; it was not executed for this collection.", "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 sequential-scan-and-sort is the best way to deal with table onek in the previous example, we could try"]}]}, {"title": "Executor implementation notes", "paragraphs": ["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."]}, {"code": "case T_MergeJoin:\n\t\t\tpname = \"Merge\";\t/* \"Join\" gets added by jointype switch */\n\t\t\tsname = \"Merge Join\";\n\t\t\tbreak;", "title": "EXPLAIN identity in core source"}], "strategies": [], "description": ["Joins ordered input streams using merge clauses."], "evidence_kind": "source and documentation", "explain_names": ["Merge"], "partial_modes": [], "comparison_data": {"node_tag": "T_MergeJoin", "strategies": [], "text_names": ["Merge"], "initializer": "ExecInitMergeJoin", "partial_modes": [], "memory_mechanism": "unclassified", "parallel_callbacks": []}, "comparison_hash": "b17771ee4d48585afbaba91552e5eb00f05a4b6784aa491387217937a4a30511", "explain_prefixes": ["Parallel"], "runtime_verified": false, "source_inventory": {"explain": "src/backend/commands/explain.c", "executor": "src/backend/executor/execProcnode.c", "implementation": "src/backend/executor/nodeMergejoin.c"}, "parallel_callbacks": []}, "12": {"facts": [{"label": "Core node tag", "value": "T_MergeJoin"}, {"label": "Structured EXPLAIN Node Type", "value": "Merge Join"}, {"label": "Inputs", "value": "Ordered outer and inner child plans"}, {"label": "Output", "value": "Joined tuples according to the selected join type"}, {"label": "Executor initializer", "value": "ExecInitMergeJoin"}, {"label": "Memory mechanism", "value": "unclassified"}], "memory": {"evidence": [{"url": "https://ftp.postgresql.org/pub/source/v12.22/postgresql-12.22.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "f849259598dabde3817453142090df89d7286452a516d4a45e22597a7cd450ca", "archive_sha256": "8df3c0474782589d3c6f374b5133b1bd14d168086edbc13c6e72e67dd4527a3b"}], "mechanism": "unclassified", "description": "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.", "source_notes": []}, "tables": [{"key": "explain-labels", "rows": [{"label": "Merge", "identity": "Merge Join"}], "title": "EXPLAIN labels in this source build", "columns": [{"key": "label", "label": "Text-format label"}, {"key": "identity", "label": "Structured node identity"}]}], "related": [{"url": "/wiki/sql/explain/?v=12", "label": "EXPLAIN"}, {"url": "/docs/12/using-explain.html", "label": "Using EXPLAIN"}, {"url": "/docs/12/parallel-plans.html", "label": "Parallel plans"}, {"url": "/wiki/guc/enable_mergejoin/?v=12", "label": "enable_mergejoin"}], "release": {"ref": "PostgreSQL 12.22 source archive", "label": "12.22", "major": "12", "channel": "historical", "revision": "8df3c0474782589d3c6f374b5133b1bd14d168086edbc13c6e72e67dd4527a3b", "source_url": "https://ftp.postgresql.org/pub/source/v12.22/postgresql-12.22.tar.bz2", "source_snapshot_utc": ""}, "sources": [{"url": "https://ftp.postgresql.org/pub/source/v12.22/postgresql-12.22.tar.bz2", "line": 1120, "path": "src/backend/commands/explain.c", "label": "src/backend/commands/explain.c:1120", "sha256": "d02ea84fdaa201de5d9360645a9f24bfbd2c31f7d45a639e09560ac0e6b6471d", "archive_sha256": "8df3c0474782589d3c6f374b5133b1bd14d168086edbc13c6e72e67dd4527a3b"}, {"url": "https://ftp.postgresql.org/pub/source/v12.22/postgresql-12.22.tar.bz2", "line": 295, "path": "src/backend/executor/execProcnode.c", "label": "src/backend/executor/execProcnode.c:295", "sha256": "311b17379fe54e3f342fe5ad41c43afbdfa1b844978db2bb2eb22b82520d3256", "archive_sha256": "8df3c0474782589d3c6f374b5133b1bd14d168086edbc13c6e72e67dd4527a3b"}, {"url": "https://ftp.postgresql.org/pub/source/v12.22/postgresql-12.22.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "f849259598dabde3817453142090df89d7286452a516d4a45e22597a7cd450ca", "archive_sha256": "8df3c0474782589d3c6f374b5133b1bd14d168086edbc13c6e72e67dd4527a3b"}, {"url": "https://ftp.postgresql.org/pub/source/v12.22/postgresql-12.22.tar.bz2", "path": "src/include/nodes/plannodes.h", "label": "src/include/nodes/plannodes.h", "sha256": "b0c4a0aeb48660ce06e5e700d5529ca9066fd16682bd15783d6e71b5420b07b0", "archive_sha256": "8df3c0474782589d3c6f374b5133b1bd14d168086edbc13c6e72e67dd4527a3b"}, {"url": "/docs/12/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 12.22 \u00b7 using-explain", "sha256": "06297525f2180b07e752837a3351be9c871b56559f535bcd0a67dec9baac10c0"}, {"url": "/docs/12/using-explain.html#USING-EXPLAIN-CAVEATS", "path": "using-explain.html", "label": "PostgreSQL 12.22 \u00b7 using-explain", "sha256": "06297525f2180b07e752837a3351be9c871b56559f535bcd0a67dec9baac10c0"}, {"url": "/docs/12/parallel-plans.html#PARALLEL-JOINS", "path": "parallel-plans.html", "label": "PostgreSQL 12.22 \u00b7 parallel-plans", "sha256": "fa33380814ee65998f524524f8681d70cf3b1198d54b39847b00462b01517ffb"}, {"url": "/docs/12/parallel-plans.html#PARALLEL-AGGREGATION", "path": "parallel-plans.html", "label": "PostgreSQL 12.22 \u00b7 parallel-plans", "sha256": "fa33380814ee65998f524524f8681d70cf3b1198d54b39847b00462b01517ffb"}], "node_tag": "T_MergeJoin", "sections": [{"title": "EXPLAIN names and attributes", "paragraphs": ["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."]}, {"title": "Memory and temporary storage", "paragraphs": ["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."]}, {"title": "Parallel execution and instrumentation", "paragraphs": ["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."]}, {"title": "Same-version manual discussion", "paragraphs": ["Merge join requires its input data to be sorted on the join keys. In this plan the tenk1 data is sorted by using an index scan to visit the rows in the correct order, but a sequential scan and sort is preferred for onek , because there are many more rows to be visited in that table. (Sequential-scan-and-sort frequently beats an index scan for sorting many rows, because of the nonsequential disk access required by the index scan.)", "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.", "Just as in a non-parallel plan, the driving table may be joined to one or more other tables using a nested loop, hash join, or merge join. The inner side of the join may be any kind of non-parallel plan that is otherwise supported by the planner provided that it is safe to run within a parallel worker. Depending on the join type, the inner side may also be a parallel plan.", "In a merge join , the inner side is always a non-parallel plan and therefore executed in full. This may be inefficient, especially if a sort must be performed, because the work and resulting data are duplicated in every cooperating process.", "PostgreSQL supports parallel aggregation by aggregating in two stages. First, each process participating in the parallel portion of the query performs an aggregation step, producing a partial result for each group of which that process is aware. This is reflected in the plan as a Partial Aggregate node. Second, the partial results are transferred to the leader via Gather or Gather Merge . Finally, the leader re-aggregates the results across all workers in order to produce the final result. This is reflected in the plan as a Finalize Aggregate node."]}, {"title": "Examples from this manual build", "blocks": [{"code": "EXPLAIN SELECT *\nFROM tenk1 t1, onek t2\nWHERE t1.unique1 < 100 AND t1.unique2 = t2.unique2;\n\n                                        QUERY PLAN\n------------------------------------------------------------------------------------------\n Merge Join  (cost=198.11..268.19 rows=10 width=488)\n   Merge Cond: (t1.unique2 = t2.unique2)\n   ->  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..656.28 rows=101 width=244)\n         Filter: (unique1 < 100)\n   ->  Sort  (cost=197.83..200.33 rows=1000 width=244)\n         Sort Key: t2.unique2\n         ->  Seq Scan on onek t2  (cost=0.00..148.00 rows=1000 width=244)", "source": {"url": "/docs/12/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 12.22 \u00b7 using-explain", "sha256": "06297525f2180b07e752837a3351be9c871b56559f535bcd0a67dec9baac10c0"}, "paragraphs": ["Example copied from the PostgreSQL 12.22 manual; it was not executed for this collection.", "Another possible type of join is a merge join, illustrated here:"]}, {"code": "SET enable_sort = off;\n\nEXPLAIN SELECT *\nFROM tenk1 t1, onek t2\nWHERE t1.unique1 < 100 AND t1.unique2 = t2.unique2;\n\n                                        QUERY PLAN\n------------------------------------------------------------------------------------------\n Merge Join  (cost=0.56..292.65 rows=10 width=488)\n   Merge Cond: (t1.unique2 = t2.unique2)\n   ->  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..656.28 rows=101 width=244)\n         Filter: (unique1 < 100)\n   ->  Index Scan using onek_unique2 on onek t2  (cost=0.28..224.79 rows=1000 width=244)", "source": {"url": "/docs/12/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 12.22 \u00b7 using-explain", "sha256": "06297525f2180b07e752837a3351be9c871b56559f535bcd0a67dec9baac10c0"}, "paragraphs": ["Example copied from the PostgreSQL 12.22 manual; it was not executed for this collection.", "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 sequential-scan-and-sort is the best way to deal with table onek in the previous example, we could try"]}]}, {"title": "Executor implementation notes", "paragraphs": ["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."]}, {"code": "case T_MergeJoin:\n\t\t\tpname = \"Merge\";\t/* \"Join\" gets added by jointype switch */\n\t\t\tsname = \"Merge Join\";\n\t\t\tbreak;", "title": "EXPLAIN identity in core source"}], "strategies": [], "description": ["Joins ordered input streams using merge clauses."], "evidence_kind": "source and documentation", "explain_names": ["Merge"], "partial_modes": [], "comparison_data": {"node_tag": "T_MergeJoin", "strategies": [], "text_names": ["Merge"], "initializer": "ExecInitMergeJoin", "partial_modes": [], "memory_mechanism": "unclassified", "parallel_callbacks": []}, "comparison_hash": "b17771ee4d48585afbaba91552e5eb00f05a4b6784aa491387217937a4a30511", "explain_prefixes": ["Parallel"], "runtime_verified": false, "source_inventory": {"explain": "src/backend/commands/explain.c", "executor": "src/backend/executor/execProcnode.c", "implementation": "src/backend/executor/nodeMergejoin.c"}, "parallel_callbacks": []}, "13": {"facts": [{"label": "Core node tag", "value": "T_MergeJoin"}, {"label": "Structured EXPLAIN Node Type", "value": "Merge Join"}, {"label": "Inputs", "value": "Ordered outer and inner child plans"}, {"label": "Output", "value": "Joined tuples according to the selected join type"}, {"label": "Executor initializer", "value": "ExecInitMergeJoin"}, {"label": "Memory mechanism", "value": "unclassified"}], "memory": {"evidence": [{"url": "https://ftp.postgresql.org/pub/source/v13.23/postgresql-13.23.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "18848e4bb13e8b2c3eb54cdb75a9e9bbb2f058051e1ad9476873d4c60a0f1a7f", "archive_sha256": "6ec3c82726af92b7dec873fa1cdf881eca92a4219787dfad05acb6b10e041fd6"}], "mechanism": "unclassified", "description": "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.", "source_notes": []}, "tables": [{"key": "explain-labels", "rows": [{"label": "Merge", "identity": "Merge Join"}], "title": "EXPLAIN labels in this source build", "columns": [{"key": "label", "label": "Text-format label"}, {"key": "identity", "label": "Structured node identity"}]}], "related": [{"url": "/wiki/sql/explain/?v=13", "label": "EXPLAIN"}, {"url": "/docs/13/using-explain.html", "label": "Using EXPLAIN"}, {"url": "/docs/13/parallel-plans.html", "label": "Parallel plans"}, {"url": "/wiki/guc/enable_mergejoin/?v=13", "label": "enable_mergejoin"}], "release": {"ref": "PostgreSQL 13.23 source archive", "label": "13.23", "major": "13", "channel": "historical", "revision": "6ec3c82726af92b7dec873fa1cdf881eca92a4219787dfad05acb6b10e041fd6", "source_url": "https://ftp.postgresql.org/pub/source/v13.23/postgresql-13.23.tar.bz2", "source_snapshot_utc": ""}, "sources": [{"url": "https://ftp.postgresql.org/pub/source/v13.23/postgresql-13.23.tar.bz2", "line": 1178, "path": "src/backend/commands/explain.c", "label": "src/backend/commands/explain.c:1178", "sha256": "541713e0e7f1c9cc352c2b6028964d440c19d2678a4463000094c24a88c1e730", "archive_sha256": "6ec3c82726af92b7dec873fa1cdf881eca92a4219787dfad05acb6b10e041fd6"}, {"url": "https://ftp.postgresql.org/pub/source/v13.23/postgresql-13.23.tar.bz2", "line": 295, "path": "src/backend/executor/execProcnode.c", "label": "src/backend/executor/execProcnode.c:295", "sha256": "d085ee99acfa00587e6ade3a1d9f8108a0566beedbbee3f54a50c9fc0cc2e875", "archive_sha256": "6ec3c82726af92b7dec873fa1cdf881eca92a4219787dfad05acb6b10e041fd6"}, {"url": "https://ftp.postgresql.org/pub/source/v13.23/postgresql-13.23.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "18848e4bb13e8b2c3eb54cdb75a9e9bbb2f058051e1ad9476873d4c60a0f1a7f", "archive_sha256": "6ec3c82726af92b7dec873fa1cdf881eca92a4219787dfad05acb6b10e041fd6"}, {"url": "https://ftp.postgresql.org/pub/source/v13.23/postgresql-13.23.tar.bz2", "path": "src/include/nodes/plannodes.h", "label": "src/include/nodes/plannodes.h", "sha256": "dcb296833777b02008c4b6bae8e8f7c6423b7ffba21f36702597c9d596d039ab", "archive_sha256": "6ec3c82726af92b7dec873fa1cdf881eca92a4219787dfad05acb6b10e041fd6"}, {"url": "/docs/13/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 13.23 \u00b7 using-explain", "sha256": "650fd8629382d5dc8f9f8412c50ec5f32442a9ad2f98ca88e5348a7c2bd0ac7a"}, {"url": "/docs/13/using-explain.html#USING-EXPLAIN-CAVEATS", "path": "using-explain.html", "label": "PostgreSQL 13.23 \u00b7 using-explain", "sha256": "650fd8629382d5dc8f9f8412c50ec5f32442a9ad2f98ca88e5348a7c2bd0ac7a"}, {"url": "/docs/13/parallel-plans.html#PARALLEL-JOINS", "path": "parallel-plans.html", "label": "PostgreSQL 13.23 \u00b7 parallel-plans", "sha256": "025ad8564a8461b676c9153f9e084429cca0ef86c968090689b082120060f3d0"}, {"url": "/docs/13/parallel-plans.html#PARALLEL-AGGREGATION", "path": "parallel-plans.html", "label": "PostgreSQL 13.23 \u00b7 parallel-plans", "sha256": "025ad8564a8461b676c9153f9e084429cca0ef86c968090689b082120060f3d0"}], "node_tag": "T_MergeJoin", "sections": [{"title": "EXPLAIN names and attributes", "paragraphs": ["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."]}, {"title": "Memory and temporary storage", "paragraphs": ["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."]}, {"title": "Parallel execution and instrumentation", "paragraphs": ["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."]}, {"title": "Same-version manual discussion", "paragraphs": ["Merge join requires its input data to be sorted on the join keys. In this plan the tenk1 data is sorted by using an index scan to visit the rows in the correct order, but a sequential scan and sort is preferred for onek , because there are many more rows to be visited in that table. (Sequential-scan-and-sort frequently beats an index scan for sorting many rows, because of the nonsequential disk access required by the index scan.)", "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.", "Just as in a non-parallel plan, the driving table may be joined to one or more other tables using a nested loop, hash join, or merge join. The inner side of the join may be any kind of non-parallel plan that is otherwise supported by the planner provided that it is safe to run within a parallel worker. Depending on the join type, the inner side may also be a parallel plan.", "In a merge join , the inner side is always a non-parallel plan and therefore executed in full. This may be inefficient, especially if a sort must be performed, because the work and resulting data are duplicated in every cooperating process.", "PostgreSQL supports parallel aggregation by aggregating in two stages. First, each process participating in the parallel portion of the query performs an aggregation step, producing a partial result for each group of which that process is aware. This is reflected in the plan as a Partial Aggregate node. Second, the partial results are transferred to the leader via Gather or Gather Merge . Finally, the leader re-aggregates the results across all workers in order to produce the final result. This is reflected in the plan as a Finalize Aggregate node."]}, {"title": "Examples from this manual build", "blocks": [{"code": "EXPLAIN SELECT *\nFROM tenk1 t1, onek t2\nWHERE t1.unique1 < 100 AND t1.unique2 = t2.unique2;\n\n                                        QUERY PLAN\n------------------------------------------------------------------------------------------\n Merge Join  (cost=198.11..268.19 rows=10 width=488)\n   Merge Cond: (t1.unique2 = t2.unique2)\n   ->  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..656.28 rows=101 width=244)\n         Filter: (unique1 < 100)\n   ->  Sort  (cost=197.83..200.33 rows=1000 width=244)\n         Sort Key: t2.unique2\n         ->  Seq Scan on onek t2  (cost=0.00..148.00 rows=1000 width=244)", "source": {"url": "/docs/13/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 13.23 \u00b7 using-explain", "sha256": "650fd8629382d5dc8f9f8412c50ec5f32442a9ad2f98ca88e5348a7c2bd0ac7a"}, "paragraphs": ["Example copied from the PostgreSQL 13.23 manual; it was not executed for this collection.", "Another possible type of join is a merge join, illustrated here:"]}, {"code": "SET enable_sort = off;\n\nEXPLAIN SELECT *\nFROM tenk1 t1, onek t2\nWHERE t1.unique1 < 100 AND t1.unique2 = t2.unique2;\n\n                                        QUERY PLAN\n------------------------------------------------------------------------------------------\n Merge Join  (cost=0.56..292.65 rows=10 width=488)\n   Merge Cond: (t1.unique2 = t2.unique2)\n   ->  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..656.28 rows=101 width=244)\n         Filter: (unique1 < 100)\n   ->  Index Scan using onek_unique2 on onek t2  (cost=0.28..224.79 rows=1000 width=244)", "source": {"url": "/docs/13/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 13.23 \u00b7 using-explain", "sha256": "650fd8629382d5dc8f9f8412c50ec5f32442a9ad2f98ca88e5348a7c2bd0ac7a"}, "paragraphs": ["Example copied from the PostgreSQL 13.23 manual; it was not executed for this collection.", "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 sequential-scan-and-sort is the best way to deal with table onek in the previous example, we could try"]}]}, {"title": "Executor implementation notes", "paragraphs": ["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."]}, {"code": "case T_MergeJoin:\n\t\t\tpname = \"Merge\";\t/* \"Join\" gets added by jointype switch */\n\t\t\tsname = \"Merge Join\";\n\t\t\tbreak;", "title": "EXPLAIN identity in core source"}], "strategies": [], "description": ["Joins ordered input streams using merge clauses."], "evidence_kind": "source and documentation", "explain_names": ["Merge"], "partial_modes": [], "comparison_data": {"node_tag": "T_MergeJoin", "strategies": [], "text_names": ["Merge"], "initializer": "ExecInitMergeJoin", "partial_modes": [], "memory_mechanism": "unclassified", "parallel_callbacks": []}, "comparison_hash": "b17771ee4d48585afbaba91552e5eb00f05a4b6784aa491387217937a4a30511", "explain_prefixes": ["Parallel"], "runtime_verified": false, "source_inventory": {"explain": "src/backend/commands/explain.c", "executor": "src/backend/executor/execProcnode.c", "implementation": "src/backend/executor/nodeMergejoin.c"}, "parallel_callbacks": []}, "14": {"facts": [{"label": "Core node tag", "value": "T_MergeJoin"}, {"label": "Structured EXPLAIN Node Type", "value": "Merge Join"}, {"label": "Inputs", "value": "Ordered outer and inner child plans"}, {"label": "Output", "value": "Joined tuples according to the selected join type"}, {"label": "Executor initializer", "value": "ExecInitMergeJoin"}, {"label": "Memory mechanism", "value": "unclassified"}], "memory": {"evidence": [{"url": "https://ftp.postgresql.org/pub/source/v14.24/postgresql-14.24.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "9efa6c854338ab3f9b1df5eae3e06cb9c4fa9ede0f6ef7ed39048c13803e5350", "archive_sha256": "a7fa7ed3d558172355f51406097a7bd4f6b473be80f311ef7cda96bf383d8897"}], "mechanism": "unclassified", "description": "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.", "source_notes": []}, "tables": [{"key": "explain-labels", "rows": [{"label": "Merge", "identity": "Merge Join"}], "title": "EXPLAIN labels in this source build", "columns": [{"key": "label", "label": "Text-format label"}, {"key": "identity", "label": "Structured node identity"}]}], "related": [{"url": "/wiki/sql/explain/?v=14", "label": "EXPLAIN"}, {"url": "/docs/14/using-explain.html", "label": "Using EXPLAIN"}, {"url": "/docs/14/parallel-plans.html", "label": "Parallel plans"}, {"url": "/wiki/guc/enable_mergejoin/?v=14", "label": "enable_mergejoin"}], "release": {"ref": "PostgreSQL 14.24 source archive", "label": "14.24", "major": "14", "channel": "stable", "revision": "a7fa7ed3d558172355f51406097a7bd4f6b473be80f311ef7cda96bf383d8897", "source_url": "https://ftp.postgresql.org/pub/source/v14.24/postgresql-14.24.tar.bz2", "source_snapshot_utc": ""}, "sources": [{"url": "https://ftp.postgresql.org/pub/source/v14.24/postgresql-14.24.tar.bz2", "line": 1214, "path": "src/backend/commands/explain.c", "label": "src/backend/commands/explain.c:1214", "sha256": "e091be4e2a083b8dea39ccd09beedede22c1716ef974da66c214a44f48be8c41", "archive_sha256": "a7fa7ed3d558172355f51406097a7bd4f6b473be80f311ef7cda96bf383d8897"}, {"url": "https://ftp.postgresql.org/pub/source/v14.24/postgresql-14.24.tar.bz2", "line": 302, "path": "src/backend/executor/execProcnode.c", "label": "src/backend/executor/execProcnode.c:302", "sha256": "72da1c5ad457f1d92a39ab73531701794df858419e3b89d6e6cb7079634e68fa", "archive_sha256": "a7fa7ed3d558172355f51406097a7bd4f6b473be80f311ef7cda96bf383d8897"}, {"url": "https://ftp.postgresql.org/pub/source/v14.24/postgresql-14.24.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "9efa6c854338ab3f9b1df5eae3e06cb9c4fa9ede0f6ef7ed39048c13803e5350", "archive_sha256": "a7fa7ed3d558172355f51406097a7bd4f6b473be80f311ef7cda96bf383d8897"}, {"url": "https://ftp.postgresql.org/pub/source/v14.24/postgresql-14.24.tar.bz2", "path": "src/include/nodes/plannodes.h", "label": "src/include/nodes/plannodes.h", "sha256": "302f51a16b570dba7ec4e7bc045f7df5800d21630280354d1a24025f3baec75d", "archive_sha256": "a7fa7ed3d558172355f51406097a7bd4f6b473be80f311ef7cda96bf383d8897"}, {"url": "/docs/14/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 14.24 \u00b7 using-explain", "sha256": "7f5ab59cb21a035ada45ea3426c5d1cca3f781273483677f73fdd76753555206"}, {"url": "/docs/14/using-explain.html#USING-EXPLAIN-CAVEATS", "path": "using-explain.html", "label": "PostgreSQL 14.24 \u00b7 using-explain", "sha256": "7f5ab59cb21a035ada45ea3426c5d1cca3f781273483677f73fdd76753555206"}, {"url": "/docs/14/parallel-plans.html#PARALLEL-JOINS", "path": "parallel-plans.html", "label": "PostgreSQL 14.24 \u00b7 parallel-plans", "sha256": "71fc3525781b74150364925e123cd8598fdebe0e05326706f2bc2e1ffa0b88a4"}, {"url": "/docs/14/parallel-plans.html#PARALLEL-AGGREGATION", "path": "parallel-plans.html", "label": "PostgreSQL 14.24 \u00b7 parallel-plans", "sha256": "71fc3525781b74150364925e123cd8598fdebe0e05326706f2bc2e1ffa0b88a4"}], "node_tag": "T_MergeJoin", "sections": [{"title": "EXPLAIN names and attributes", "paragraphs": ["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."]}, {"title": "Memory and temporary storage", "paragraphs": ["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."]}, {"title": "Parallel execution and instrumentation", "paragraphs": ["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."]}, {"title": "Same-version manual discussion", "paragraphs": ["Merge join requires its input data to be sorted on the join keys. In this plan the tenk1 data is sorted by using an index scan to visit the rows in the correct order, but a sequential scan and sort is preferred for onek , because there are many more rows to be visited in that table. (Sequential-scan-and-sort frequently beats an index scan for sorting many rows, because of the nonsequential disk access required by the index scan.)", "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.", "Just as in a non-parallel plan, the driving table may be joined to one or more other tables using a nested loop, hash join, or merge join. The inner side of the join may be any kind of non-parallel plan that is otherwise supported by the planner provided that it is safe to run within a parallel worker. Depending on the join type, the inner side may also be a parallel plan.", "In a merge join , the inner side is always a non-parallel plan and therefore executed in full. This may be inefficient, especially if a sort must be performed, because the work and resulting data are duplicated in every cooperating process.", "PostgreSQL supports parallel aggregation by aggregating in two stages. First, each process participating in the parallel portion of the query performs an aggregation step, producing a partial result for each group of which that process is aware. This is reflected in the plan as a Partial Aggregate node. Second, the partial results are transferred to the leader via Gather or Gather Merge . Finally, the leader re-aggregates the results across all workers in order to produce the final result. This is reflected in the plan as a Finalize Aggregate node."]}, {"title": "Examples from this manual build", "blocks": [{"code": "EXPLAIN SELECT *\nFROM tenk1 t1, onek t2\nWHERE t1.unique1 < 100 AND t1.unique2 = t2.unique2;\n\n                                        QUERY PLAN\n------------------------------------------------------------------------------------------\n Merge Join  (cost=198.11..268.19 rows=10 width=488)\n   Merge Cond: (t1.unique2 = t2.unique2)\n   ->  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..656.28 rows=101 width=244)\n         Filter: (unique1 < 100)\n   ->  Sort  (cost=197.83..200.33 rows=1000 width=244)\n         Sort Key: t2.unique2\n         ->  Seq Scan on onek t2  (cost=0.00..148.00 rows=1000 width=244)", "source": {"url": "/docs/14/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 14.24 \u00b7 using-explain", "sha256": "7f5ab59cb21a035ada45ea3426c5d1cca3f781273483677f73fdd76753555206"}, "paragraphs": ["Example copied from the PostgreSQL 14.24 manual; it was not executed for this collection.", "Another possible type of join is a merge join, illustrated here:"]}, {"code": "SET enable_sort = off;\n\nEXPLAIN SELECT *\nFROM tenk1 t1, onek t2\nWHERE t1.unique1 < 100 AND t1.unique2 = t2.unique2;\n\n                                        QUERY PLAN\n------------------------------------------------------------------------------------------\n Merge Join  (cost=0.56..292.65 rows=10 width=488)\n   Merge Cond: (t1.unique2 = t2.unique2)\n   ->  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..656.28 rows=101 width=244)\n         Filter: (unique1 < 100)\n   ->  Index Scan using onek_unique2 on onek t2  (cost=0.28..224.79 rows=1000 width=244)", "source": {"url": "/docs/14/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 14.24 \u00b7 using-explain", "sha256": "7f5ab59cb21a035ada45ea3426c5d1cca3f781273483677f73fdd76753555206"}, "paragraphs": ["Example copied from the PostgreSQL 14.24 manual; it was not executed for this collection.", "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 20.7.1 . (This is a crude tool, but useful. See also Section 14.3 .) For example, if we're unconvinced that sequential-scan-and-sort is the best way to deal with table onek in the previous example, we could try"]}]}, {"title": "Executor implementation notes", "paragraphs": ["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."]}, {"code": "case T_MergeJoin:\n\t\t\tpname = \"Merge\";\t/* \"Join\" gets added by jointype switch */\n\t\t\tsname = \"Merge Join\";\n\t\t\tbreak;", "title": "EXPLAIN identity in core source"}], "strategies": [], "description": ["Joins ordered input streams using merge clauses."], "evidence_kind": "source and documentation", "explain_names": ["Merge"], "partial_modes": [], "comparison_data": {"node_tag": "T_MergeJoin", "strategies": [], "text_names": ["Merge"], "initializer": "ExecInitMergeJoin", "partial_modes": [], "memory_mechanism": "unclassified", "parallel_callbacks": []}, "comparison_hash": "b17771ee4d48585afbaba91552e5eb00f05a4b6784aa491387217937a4a30511", "explain_prefixes": ["Parallel", "Async"], "runtime_verified": false, "source_inventory": {"explain": "src/backend/commands/explain.c", "executor": "src/backend/executor/execProcnode.c", "implementation": "src/backend/executor/nodeMergejoin.c"}, "parallel_callbacks": []}, "15": {"facts": [{"label": "Core node tag", "value": "T_MergeJoin"}, {"label": "Structured EXPLAIN Node Type", "value": "Merge Join"}, {"label": "Inputs", "value": "Ordered outer and inner child plans"}, {"label": "Output", "value": "Joined tuples according to the selected join type"}, {"label": "Executor initializer", "value": "ExecInitMergeJoin"}, {"label": "Memory mechanism", "value": "unclassified"}], "memory": {"evidence": [{"url": "https://ftp.postgresql.org/pub/source/v15.19/postgresql-15.19.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "b91f72bd62b5a1d293aa18560ce7c5c2c01edb9731dc1285fbcf7270fc866ddd", "archive_sha256": "e1a64a87a46b825b88c082e4518161a47aab53c45694964f8ba1df28f7859f89"}], "mechanism": "unclassified", "description": "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.", "source_notes": []}, "tables": [{"key": "explain-labels", "rows": [{"label": "Merge", "identity": "Merge Join"}], "title": "EXPLAIN labels in this source build", "columns": [{"key": "label", "label": "Text-format label"}, {"key": "identity", "label": "Structured node identity"}]}], "related": [{"url": "/wiki/sql/explain/?v=15", "label": "EXPLAIN"}, {"url": "/docs/15/using-explain.html", "label": "Using EXPLAIN"}, {"url": "/docs/15/parallel-plans.html", "label": "Parallel plans"}, {"url": "/wiki/guc/enable_mergejoin/?v=15", "label": "enable_mergejoin"}], "release": {"ref": "PostgreSQL 15.19 source archive", "label": "15.19", "major": "15", "channel": "stable", "revision": "e1a64a87a46b825b88c082e4518161a47aab53c45694964f8ba1df28f7859f89", "source_url": "https://ftp.postgresql.org/pub/source/v15.19/postgresql-15.19.tar.bz2", "source_snapshot_utc": ""}, "sources": [{"url": "https://ftp.postgresql.org/pub/source/v15.19/postgresql-15.19.tar.bz2", "line": 1217, "path": "src/backend/commands/explain.c", "label": "src/backend/commands/explain.c:1217", "sha256": "bb3b442d0f1b098aa8707335250102f027a596cd94117308bd16d1d36b258f5c", "archive_sha256": "e1a64a87a46b825b88c082e4518161a47aab53c45694964f8ba1df28f7859f89"}, {"url": "https://ftp.postgresql.org/pub/source/v15.19/postgresql-15.19.tar.bz2", "line": 302, "path": "src/backend/executor/execProcnode.c", "label": "src/backend/executor/execProcnode.c:302", "sha256": "19836c50a272741a4eac653541e655437c2e00710a541e5348d6a277d0669d7c", "archive_sha256": "e1a64a87a46b825b88c082e4518161a47aab53c45694964f8ba1df28f7859f89"}, {"url": "https://ftp.postgresql.org/pub/source/v15.19/postgresql-15.19.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "b91f72bd62b5a1d293aa18560ce7c5c2c01edb9731dc1285fbcf7270fc866ddd", "archive_sha256": "e1a64a87a46b825b88c082e4518161a47aab53c45694964f8ba1df28f7859f89"}, {"url": "https://ftp.postgresql.org/pub/source/v15.19/postgresql-15.19.tar.bz2", "path": "src/include/nodes/plannodes.h", "label": "src/include/nodes/plannodes.h", "sha256": "fb4a4c8165495299131173680bc02a950d88e1ff610231fd97997bc0c9afc1d7", "archive_sha256": "e1a64a87a46b825b88c082e4518161a47aab53c45694964f8ba1df28f7859f89"}, {"url": "/docs/15/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 15.19 \u00b7 using-explain", "sha256": "d1f509457c647da453d2575c772d91022a0f115dd84f9a3b20f5ff25a243648f"}, {"url": "/docs/15/using-explain.html#USING-EXPLAIN-ANALYZE", "path": "using-explain.html", "label": "PostgreSQL 15.19 \u00b7 using-explain", "sha256": "d1f509457c647da453d2575c772d91022a0f115dd84f9a3b20f5ff25a243648f"}, {"url": "/docs/15/using-explain.html#USING-EXPLAIN-CAVEATS", "path": "using-explain.html", "label": "PostgreSQL 15.19 \u00b7 using-explain", "sha256": "d1f509457c647da453d2575c772d91022a0f115dd84f9a3b20f5ff25a243648f"}, {"url": "/docs/15/parallel-plans.html#PARALLEL-JOINS", "path": "parallel-plans.html", "label": "PostgreSQL 15.19 \u00b7 parallel-plans", "sha256": "ec9345488a15cdc05d3e0b0849763e2bf0b864ad17de786c5f023db5dab1ea96"}], "node_tag": "T_MergeJoin", "sections": [{"title": "EXPLAIN names and attributes", "paragraphs": ["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."]}, {"title": "Memory and temporary storage", "paragraphs": ["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."]}, {"title": "Parallel execution and instrumentation", "paragraphs": ["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."]}, {"title": "Same-version manual discussion", "paragraphs": ["Merge join requires its input data to be sorted on the join keys. In this plan the tenk1 data is sorted by using an index scan to visit the rows in the correct order, but a sequential scan and sort is preferred for onek , because there are many more rows to be visited in that table. (Sequential-scan-and-sort frequently beats an index scan for sorting many rows, because of the nonsequential disk access required by the index scan.)", "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 an 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.", "Just as in a non-parallel plan, the driving table may be joined to one or more other tables using a nested loop, hash join, or merge join. The inner side of the join may be any kind of non-parallel plan that is otherwise supported by the planner provided that it is safe to run within a parallel worker. Depending on the join type, the inner side may also be a parallel plan.", "In a merge join , the inner side is always a non-parallel plan and therefore executed in full. This may be inefficient, especially if a sort must be performed, because the work and resulting data are duplicated in every cooperating process."]}, {"title": "Examples from this manual build", "blocks": [{"code": "EXPLAIN SELECT *\nFROM tenk1 t1, onek t2\nWHERE t1.unique1 < 100 AND t1.unique2 = t2.unique2;\n\n                                        QUERY PLAN\n------------------------------------------------------------------------------------------\n Merge Join  (cost=198.11..268.19 rows=10 width=488)\n   Merge Cond: (t1.unique2 = t2.unique2)\n   ->  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..656.28 rows=101 width=244)\n         Filter: (unique1 < 100)\n   ->  Sort  (cost=197.83..200.33 rows=1000 width=244)\n         Sort Key: t2.unique2\n         ->  Seq Scan on onek t2  (cost=0.00..148.00 rows=1000 width=244)", "source": {"url": "/docs/15/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 15.19 \u00b7 using-explain", "sha256": "d1f509457c647da453d2575c772d91022a0f115dd84f9a3b20f5ff25a243648f"}, "paragraphs": ["Example copied from the PostgreSQL 15.19 manual; it was not executed for this collection.", "Another possible type of join is a merge join, illustrated here:"]}, {"code": "SET enable_sort = off;\n\nEXPLAIN SELECT *\nFROM tenk1 t1, onek t2\nWHERE t1.unique1 < 100 AND t1.unique2 = t2.unique2;\n\n                                        QUERY PLAN\n------------------------------------------------------------------------------------------\n Merge Join  (cost=0.56..292.65 rows=10 width=488)\n   Merge Cond: (t1.unique2 = t2.unique2)\n   ->  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..656.28 rows=101 width=244)\n         Filter: (unique1 < 100)\n   ->  Index Scan using onek_unique2 on onek t2  (cost=0.28..224.79 rows=1000 width=244)", "source": {"url": "/docs/15/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 15.19 \u00b7 using-explain", "sha256": "d1f509457c647da453d2575c772d91022a0f115dd84f9a3b20f5ff25a243648f"}, "paragraphs": ["Example copied from the PostgreSQL 15.19 manual; it was not executed for this collection.", "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 20.7.1 . (This is a crude tool, but useful. See also Section 14.3 .) For example, if we're unconvinced that sequential-scan-and-sort is the best way to deal with table onek in the previous example, we could try"]}]}, {"title": "Executor implementation notes", "paragraphs": ["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."]}, {"code": "case T_MergeJoin:\n\t\t\tpname = \"Merge\";\t/* \"Join\" gets added by jointype switch */\n\t\t\tsname = \"Merge Join\";\n\t\t\tbreak;", "title": "EXPLAIN identity in core source"}], "strategies": [], "description": ["Joins ordered input streams using merge clauses."], "evidence_kind": "source and documentation", "explain_names": ["Merge"], "partial_modes": [], "comparison_data": {"node_tag": "T_MergeJoin", "strategies": [], "text_names": ["Merge"], "initializer": "ExecInitMergeJoin", "partial_modes": [], "memory_mechanism": "unclassified", "parallel_callbacks": []}, "comparison_hash": "b17771ee4d48585afbaba91552e5eb00f05a4b6784aa491387217937a4a30511", "explain_prefixes": ["Parallel", "Async"], "runtime_verified": false, "source_inventory": {"explain": "src/backend/commands/explain.c", "executor": "src/backend/executor/execProcnode.c", "implementation": "src/backend/executor/nodeMergejoin.c"}, "parallel_callbacks": []}, "16": {"facts": [{"label": "Core node tag", "value": "T_MergeJoin"}, {"label": "Structured EXPLAIN Node Type", "value": "Merge Join"}, {"label": "Inputs", "value": "Ordered outer and inner child plans"}, {"label": "Output", "value": "Joined tuples according to the selected join type"}, {"label": "Executor initializer", "value": "ExecInitMergeJoin"}, {"label": "Memory mechanism", "value": "unclassified"}], "memory": {"evidence": [{"url": "https://ftp.postgresql.org/pub/source/v16.15/postgresql-16.15.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "8426514ac454d9e1feb343aff03cab36b27995ebbc313fccfb373f323716138e", "archive_sha256": "c1575341fa7bd40f5274ea465b34390f4dc64cdd0770af327005caaeb9f6b7ed"}], "mechanism": "unclassified", "description": "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.", "source_notes": []}, "tables": [{"key": "explain-labels", "rows": [{"label": "Merge", "identity": "Merge Join"}], "title": "EXPLAIN labels in this source build", "columns": [{"key": "label", "label": "Text-format label"}, {"key": "identity", "label": "Structured node identity"}]}], "related": [{"url": "/wiki/sql/explain/?v=16", "label": "EXPLAIN"}, {"url": "/docs/16/using-explain.html", "label": "Using EXPLAIN"}, {"url": "/docs/16/parallel-plans.html", "label": "Parallel plans"}, {"url": "/wiki/guc/enable_mergejoin/?v=16", "label": "enable_mergejoin"}], "release": {"ref": "PostgreSQL 16.15 source archive", "label": "16.15", "major": "16", "channel": "stable", "revision": "c1575341fa7bd40f5274ea465b34390f4dc64cdd0770af327005caaeb9f6b7ed", "source_url": "https://ftp.postgresql.org/pub/source/v16.15/postgresql-16.15.tar.bz2", "source_snapshot_utc": ""}, "sources": [{"url": "https://ftp.postgresql.org/pub/source/v16.15/postgresql-16.15.tar.bz2", "line": 1250, "path": "src/backend/commands/explain.c", "label": "src/backend/commands/explain.c:1250", "sha256": "8e017f0116dbea471339b40c37a667cc9f95039e7e0329c783e5e8ce194de7e1", "archive_sha256": "c1575341fa7bd40f5274ea465b34390f4dc64cdd0770af327005caaeb9f6b7ed"}, {"url": "https://ftp.postgresql.org/pub/source/v16.15/postgresql-16.15.tar.bz2", "line": 302, "path": "src/backend/executor/execProcnode.c", "label": "src/backend/executor/execProcnode.c:302", "sha256": "e48c08e555f8cb4e4bb43df516c4b8906ce9bc374b2a745d98a1fc8c22cc5099", "archive_sha256": "c1575341fa7bd40f5274ea465b34390f4dc64cdd0770af327005caaeb9f6b7ed"}, {"url": "https://ftp.postgresql.org/pub/source/v16.15/postgresql-16.15.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "8426514ac454d9e1feb343aff03cab36b27995ebbc313fccfb373f323716138e", "archive_sha256": "c1575341fa7bd40f5274ea465b34390f4dc64cdd0770af327005caaeb9f6b7ed"}, {"url": "https://ftp.postgresql.org/pub/source/v16.15/postgresql-16.15.tar.bz2", "path": "src/include/nodes/plannodes.h", "label": "src/include/nodes/plannodes.h", "sha256": "97db47353db76326b874589a5ad0a04501cc74cd72e237e7bd956e7472c41f1f", "archive_sha256": "c1575341fa7bd40f5274ea465b34390f4dc64cdd0770af327005caaeb9f6b7ed"}, {"url": "/docs/16/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 16.15 \u00b7 using-explain", "sha256": "bd8b86e5281cf0e52ad6e0e4bb8b6ff6510dac61982b44f0c1dd07d54012db3c"}, {"url": "/docs/16/using-explain.html#USING-EXPLAIN-ANALYZE", "path": "using-explain.html", "label": "PostgreSQL 16.15 \u00b7 using-explain", "sha256": "bd8b86e5281cf0e52ad6e0e4bb8b6ff6510dac61982b44f0c1dd07d54012db3c"}, {"url": "/docs/16/using-explain.html#USING-EXPLAIN-CAVEATS", "path": "using-explain.html", "label": "PostgreSQL 16.15 \u00b7 using-explain", "sha256": "bd8b86e5281cf0e52ad6e0e4bb8b6ff6510dac61982b44f0c1dd07d54012db3c"}, {"url": "/docs/16/parallel-plans.html#PARALLEL-JOINS", "path": "parallel-plans.html", "label": "PostgreSQL 16.15 \u00b7 parallel-plans", "sha256": "53d83f63f97381fe1e4c0cfe5ceb81d30c1542b03e35a144684afd8fb3b9686c"}], "node_tag": "T_MergeJoin", "sections": [{"title": "EXPLAIN names and attributes", "paragraphs": ["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."]}, {"title": "Memory and temporary storage", "paragraphs": ["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."]}, {"title": "Parallel execution and instrumentation", "paragraphs": ["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."]}, {"title": "Same-version manual discussion", "paragraphs": ["Merge join requires its input data to be sorted on the join keys. In this plan the tenk1 data is sorted by using an index scan to visit the rows in the correct order, but a sequential scan and sort is preferred for onek , because there are many more rows to be visited in that table. (Sequential-scan-and-sort frequently beats an index scan for sorting many rows, because of the nonsequential disk access required by the index scan.)", "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 an 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.", "Just as in a non-parallel plan, the driving table may be joined to one or more other tables using a nested loop, hash join, or merge join. The inner side of the join may be any kind of non-parallel plan that is otherwise supported by the planner provided that it is safe to run within a parallel worker. Depending on the join type, the inner side may also be a parallel plan.", "In a merge join , the inner side is always a non-parallel plan and therefore executed in full. This may be inefficient, especially if a sort must be performed, because the work and resulting data are duplicated in every cooperating process."]}, {"title": "Examples from this manual build", "blocks": [{"code": "EXPLAIN SELECT *\nFROM tenk1 t1, onek t2\nWHERE t1.unique1 < 100 AND t1.unique2 = t2.unique2;\n\n                                        QUERY PLAN\n------------------------------------------------------------------------------------------\n Merge Join  (cost=198.11..268.19 rows=10 width=488)\n   Merge Cond: (t1.unique2 = t2.unique2)\n   ->  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..656.28 rows=101 width=244)\n         Filter: (unique1 < 100)\n   ->  Sort  (cost=197.83..200.33 rows=1000 width=244)\n         Sort Key: t2.unique2\n         ->  Seq Scan on onek t2  (cost=0.00..148.00 rows=1000 width=244)", "source": {"url": "/docs/16/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 16.15 \u00b7 using-explain", "sha256": "bd8b86e5281cf0e52ad6e0e4bb8b6ff6510dac61982b44f0c1dd07d54012db3c"}, "paragraphs": ["Example copied from the PostgreSQL 16.15 manual; it was not executed for this collection.", "Another possible type of join is a merge join, illustrated here:"]}, {"code": "SET enable_sort = off;\n\nEXPLAIN SELECT *\nFROM tenk1 t1, onek t2\nWHERE t1.unique1 < 100 AND t1.unique2 = t2.unique2;\n\n                                        QUERY PLAN\n------------------------------------------------------------------------------------------\n Merge Join  (cost=0.56..292.65 rows=10 width=488)\n   Merge Cond: (t1.unique2 = t2.unique2)\n   ->  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..656.28 rows=101 width=244)\n         Filter: (unique1 < 100)\n   ->  Index Scan using onek_unique2 on onek t2  (cost=0.28..224.79 rows=1000 width=244)", "source": {"url": "/docs/16/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 16.15 \u00b7 using-explain", "sha256": "bd8b86e5281cf0e52ad6e0e4bb8b6ff6510dac61982b44f0c1dd07d54012db3c"}, "paragraphs": ["Example copied from the PostgreSQL 16.15 manual; it was not executed for this collection.", "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 20.7.1 . (This is a crude tool, but useful. See also Section 14.3 .) For example, if we're unconvinced that sequential-scan-and-sort is the best way to deal with table onek in the previous example, we could try"]}]}, {"title": "Executor implementation notes", "paragraphs": ["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."]}, {"code": "case T_MergeJoin:\n\t\t\tpname = \"Merge\";\t/* \"Join\" gets added by jointype switch */\n\t\t\tsname = \"Merge Join\";\n\t\t\tbreak;", "title": "EXPLAIN identity in core source"}], "strategies": [], "description": ["Joins ordered input streams using merge clauses."], "evidence_kind": "source and documentation", "explain_names": ["Merge"], "partial_modes": [], "comparison_data": {"node_tag": "T_MergeJoin", "strategies": [], "text_names": ["Merge"], "initializer": "ExecInitMergeJoin", "partial_modes": [], "memory_mechanism": "unclassified", "parallel_callbacks": []}, "comparison_hash": "b17771ee4d48585afbaba91552e5eb00f05a4b6784aa491387217937a4a30511", "explain_prefixes": ["Parallel", "Async"], "runtime_verified": false, "source_inventory": {"explain": "src/backend/commands/explain.c", "executor": "src/backend/executor/execProcnode.c", "implementation": "src/backend/executor/nodeMergejoin.c"}, "parallel_callbacks": []}, "17": {"facts": [{"label": "Core node tag", "value": "T_MergeJoin"}, {"label": "Structured EXPLAIN Node Type", "value": "Merge Join"}, {"label": "Inputs", "value": "Ordered outer and inner child plans"}, {"label": "Output", "value": "Joined tuples according to the selected join type"}, {"label": "Executor initializer", "value": "ExecInitMergeJoin"}, {"label": "Memory mechanism", "value": "unclassified"}], "memory": {"evidence": [{"url": "https://ftp.postgresql.org/pub/source/v17.11/postgresql-17.11.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "31a47888da5b9d6a99193a92808c6e6d3d04d8ec0af049b28a10888b73503bc0", "archive_sha256": "dd27f2b3c59e73ed14aa3324901242bf69a032a6347805f274e6260322d42979"}], "mechanism": "unclassified", "description": "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.", "source_notes": []}, "tables": [{"key": "explain-labels", "rows": [{"label": "Merge", "identity": "Merge Join"}], "title": "EXPLAIN labels in this source build", "columns": [{"key": "label", "label": "Text-format label"}, {"key": "identity", "label": "Structured node identity"}]}], "related": [{"url": "/wiki/sql/explain/?v=17", "label": "EXPLAIN"}, {"url": "/docs/17/using-explain.html", "label": "Using EXPLAIN"}, {"url": "/docs/17/parallel-plans.html", "label": "Parallel plans"}, {"url": "/wiki/guc/enable_mergejoin/?v=17", "label": "enable_mergejoin"}], "release": {"ref": "PostgreSQL 17.11 source archive", "label": "17.11", "major": "17", "channel": "stable", "revision": "dd27f2b3c59e73ed14aa3324901242bf69a032a6347805f274e6260322d42979", "source_url": "https://ftp.postgresql.org/pub/source/v17.11/postgresql-17.11.tar.bz2", "source_snapshot_utc": ""}, "sources": [{"url": "https://ftp.postgresql.org/pub/source/v17.11/postgresql-17.11.tar.bz2", "line": 1439, "path": "src/backend/commands/explain.c", "label": "src/backend/commands/explain.c:1439", "sha256": "741251b1a3b6d269a52a673d42eb63b02e13a5872db7b359b137086ab21b63c8", "archive_sha256": "dd27f2b3c59e73ed14aa3324901242bf69a032a6347805f274e6260322d42979"}, {"url": "https://ftp.postgresql.org/pub/source/v17.11/postgresql-17.11.tar.bz2", "line": 302, "path": "src/backend/executor/execProcnode.c", "label": "src/backend/executor/execProcnode.c:302", "sha256": "a77576e158b94cb01fa8c5174ba133004eabdd727660323f8afc66c8d2e757b8", "archive_sha256": "dd27f2b3c59e73ed14aa3324901242bf69a032a6347805f274e6260322d42979"}, {"url": "https://ftp.postgresql.org/pub/source/v17.11/postgresql-17.11.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "31a47888da5b9d6a99193a92808c6e6d3d04d8ec0af049b28a10888b73503bc0", "archive_sha256": "dd27f2b3c59e73ed14aa3324901242bf69a032a6347805f274e6260322d42979"}, {"url": "https://ftp.postgresql.org/pub/source/v17.11/postgresql-17.11.tar.bz2", "path": "src/include/nodes/plannodes.h", "label": "src/include/nodes/plannodes.h", "sha256": "d390dd69e2d3f5085beb42b33e46ff0676a2959b916a12b82118a7e545f8e562", "archive_sha256": "dd27f2b3c59e73ed14aa3324901242bf69a032a6347805f274e6260322d42979"}, {"url": "/docs/17/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 17.11 \u00b7 using-explain", "sha256": "8e3422c77496cc53bfc225ccadda3e82eb23c8c362b8eb95e7fb02cdb315ea78"}, {"url": "/docs/17/using-explain.html#USING-EXPLAIN-ANALYZE", "path": "using-explain.html", "label": "PostgreSQL 17.11 \u00b7 using-explain", "sha256": "8e3422c77496cc53bfc225ccadda3e82eb23c8c362b8eb95e7fb02cdb315ea78"}, {"url": "/docs/17/using-explain.html#USING-EXPLAIN-CAVEATS", "path": "using-explain.html", "label": "PostgreSQL 17.11 \u00b7 using-explain", "sha256": "8e3422c77496cc53bfc225ccadda3e82eb23c8c362b8eb95e7fb02cdb315ea78"}], "node_tag": "T_MergeJoin", "sections": [{"title": "EXPLAIN names and attributes", "paragraphs": ["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."]}, {"title": "Memory and temporary storage", "paragraphs": ["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."]}, {"title": "Parallel execution and instrumentation", "paragraphs": ["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."]}, {"title": "Same-version manual discussion", "paragraphs": ["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."]}, {"title": "Examples from this manual build", "blocks": [{"code": "EXPLAIN SELECT *\nFROM tenk1 t1, onek t2\nWHERE t1.unique1 < 100 AND t1.unique2 = t2.unique2;\n\n                                        QUERY PLAN\n------------------------------------------------------------------------------------------\n Merge Join  (cost=0.56..233.49 rows=10 width=488)\n   Merge Cond: (t1.unique2 = t2.unique2)\n   ->  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..643.28 rows=100 width=244)\n         Filter: (unique1 < 100)\n   ->  Index Scan using onek_unique2 on onek t2  (cost=0.28..166.28 rows=1000 width=244)", "source": {"url": "/docs/17/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 17.11 \u00b7 using-explain", "sha256": "8e3422c77496cc53bfc225ccadda3e82eb23c8c362b8eb95e7fb02cdb315ea78"}, "paragraphs": ["Example copied from the PostgreSQL 17.11 manual; it was not executed for this collection.", "Another possible type of join is a merge join, illustrated here:"]}]}, {"title": "Executor implementation notes", "paragraphs": ["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."]}, {"code": "case T_MergeJoin:\n\t\t\tpname = \"Merge\";\t/* \"Join\" gets added by jointype switch */\n\t\t\tsname = \"Merge Join\";\n\t\t\tbreak;", "title": "EXPLAIN identity in core source"}], "strategies": [], "description": ["Joins ordered input streams using merge clauses."], "evidence_kind": "source and documentation", "explain_names": ["Merge"], "partial_modes": [], "comparison_data": {"node_tag": "T_MergeJoin", "strategies": [], "text_names": ["Merge"], "initializer": "ExecInitMergeJoin", "partial_modes": [], "memory_mechanism": "unclassified", "parallel_callbacks": []}, "comparison_hash": "b17771ee4d48585afbaba91552e5eb00f05a4b6784aa491387217937a4a30511", "explain_prefixes": ["Parallel", "Async"], "runtime_verified": false, "source_inventory": {"explain": "src/backend/commands/explain.c", "executor": "src/backend/executor/execProcnode.c", "implementation": "src/backend/executor/nodeMergejoin.c"}, "parallel_callbacks": []}, "18": {"facts": [{"label": "Core node tag", "value": "T_MergeJoin"}, {"label": "Structured EXPLAIN Node Type", "value": "Merge Join"}, {"label": "Inputs", "value": "Ordered outer and inner child plans"}, {"label": "Output", "value": "Joined tuples according to the selected join type"}, {"label": "Executor initializer", "value": "ExecInitMergeJoin"}, {"label": "Memory mechanism", "value": "unclassified"}], "memory": {"evidence": [{"url": "https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "df6726b291493e06be7c43e5664bfb4251267eff66481eaf8e04969c39612b25", "archive_sha256": "555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f"}], "mechanism": "unclassified", "description": "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.", "source_notes": []}, "tables": [{"key": "explain-labels", "rows": [{"label": "Merge", "identity": "Merge Join"}], "title": "EXPLAIN labels in this source build", "columns": [{"key": "label", "label": "Text-format label"}, {"key": "identity", "label": "Structured node identity"}]}], "related": [{"url": "/wiki/sql/explain/?v=18", "label": "EXPLAIN"}, {"url": "/docs/18/using-explain.html", "label": "Using EXPLAIN"}, {"url": "/docs/18/parallel-plans.html", "label": "Parallel plans"}, {"url": "/wiki/guc/enable_mergejoin/?v=18", "label": "enable_mergejoin"}], "release": {"ref": "PostgreSQL 18.6 source archive", "label": "18.6", "major": "18", "channel": "stable", "revision": "555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f", "source_url": "https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2", "source_snapshot_utc": ""}, "sources": [{"url": "https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2", "line": 1424, "path": "src/backend/commands/explain.c", "label": "src/backend/commands/explain.c:1424", "sha256": "34c86d6070224a0e981efef51f79101d6d505e5874f1684ace183034bab14bb4", "archive_sha256": "555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f"}, {"url": "https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2", "line": 302, "path": "src/backend/executor/execProcnode.c", "label": "src/backend/executor/execProcnode.c:302", "sha256": "f8a06a3f539077249b20664b2812433db6d7bd12b2c0ca633525db43d06f112a", "archive_sha256": "555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f"}, {"url": "https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "df6726b291493e06be7c43e5664bfb4251267eff66481eaf8e04969c39612b25", "archive_sha256": "555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f"}, {"url": "https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2", "path": "src/include/nodes/plannodes.h", "label": "src/include/nodes/plannodes.h", "sha256": "52422b327a8049fbbb20d8b96008a0fc0a6fafa60f7eff3c695d5b2e83830120", "archive_sha256": "555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f"}, {"url": "/docs/18/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 18.6 \u00b7 using-explain", "sha256": "60040c30180093418a0affe56dd27dff9df2504b705b38039589e458bf5c31ed"}, {"url": "/docs/18/using-explain.html#USING-EXPLAIN-ANALYZE", "path": "using-explain.html", "label": "PostgreSQL 18.6 \u00b7 using-explain", "sha256": "60040c30180093418a0affe56dd27dff9df2504b705b38039589e458bf5c31ed"}, {"url": "/docs/18/using-explain.html#USING-EXPLAIN-CAVEATS", "path": "using-explain.html", "label": "PostgreSQL 18.6 \u00b7 using-explain", "sha256": "60040c30180093418a0affe56dd27dff9df2504b705b38039589e458bf5c31ed"}], "node_tag": "T_MergeJoin", "sections": [{"title": "EXPLAIN names and attributes", "paragraphs": ["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."]}, {"title": "Memory and temporary storage", "paragraphs": ["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."]}, {"title": "Parallel execution and instrumentation", "paragraphs": ["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."]}, {"title": "Same-version manual discussion", "paragraphs": ["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."]}, {"title": "Examples from this manual build", "blocks": [{"code": "EXPLAIN SELECT *\nFROM tenk1 t1, onek t2\nWHERE t1.unique1 < 100 AND t1.unique2 = t2.unique2;\n\n                                        QUERY PLAN\n------------------------------------------------------------------------------------------\n Merge Join  (cost=0.56..233.49 rows=10 width=488)\n   Merge Cond: (t1.unique2 = t2.unique2)\n   ->  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..643.28 rows=100 width=244)\n         Filter: (unique1 < 100)\n   ->  Index Scan using onek_unique2 on onek t2  (cost=0.28..166.28 rows=1000 width=244)", "source": {"url": "/docs/18/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 18.6 \u00b7 using-explain", "sha256": "60040c30180093418a0affe56dd27dff9df2504b705b38039589e458bf5c31ed"}, "paragraphs": ["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:"]}]}, {"title": "Executor implementation notes", "paragraphs": ["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."]}, {"code": "case T_MergeJoin:\n\t\t\tpname = \"Merge\";\t/* \"Join\" gets added by jointype switch */\n\t\t\tsname = \"Merge Join\";\n\t\t\tbreak;", "title": "EXPLAIN identity in core source"}], "strategies": [], "description": ["Joins ordered input streams using merge clauses."], "evidence_kind": "source and documentation", "explain_names": ["Merge"], "partial_modes": [], "comparison_data": {"node_tag": "T_MergeJoin", "strategies": [], "text_names": ["Merge"], "initializer": "ExecInitMergeJoin", "partial_modes": [], "memory_mechanism": "unclassified", "parallel_callbacks": []}, "comparison_hash": "b17771ee4d48585afbaba91552e5eb00f05a4b6784aa491387217937a4a30511", "explain_prefixes": ["Parallel", "Async"], "runtime_verified": false, "source_inventory": {"explain": "src/backend/commands/explain.c", "executor": "src/backend/executor/execProcnode.c", "implementation": "src/backend/executor/nodeMergejoin.c"}, "parallel_callbacks": []}, "19": {"facts": [{"label": "Core node tag", "value": "T_MergeJoin"}, {"label": "Structured EXPLAIN Node Type", "value": "Merge Join"}, {"label": "Inputs", "value": "Ordered outer and inner child plans"}, {"label": "Output", "value": "Joined tuples according to the selected join type"}, {"label": "Executor initializer", "value": "ExecInitMergeJoin"}, {"label": "Memory mechanism", "value": "unclassified"}], "memory": {"evidence": [{"url": "https://ftp.postgresql.org/pub/source/v19beta4/postgresql-19beta4.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "65c9b61454ef3ed8dae2f6fefbbcb56578829ea6256e00816bd0cd6c72536dc7", "archive_sha256": "83157ee9c599d03b2f7a3d73ef3a56ec24e0e79cc2b3501a64d1364f56398c86"}], "mechanism": "unclassified", "description": "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.", "source_notes": []}, "tables": [{"key": "explain-labels", "rows": [{"label": "Merge", "identity": "Merge Join"}], "title": "EXPLAIN labels in this source build", "columns": [{"key": "label", "label": "Text-format label"}, {"key": "identity", "label": "Structured node identity"}]}], "related": [{"url": "/wiki/sql/explain/?v=19", "label": "EXPLAIN"}, {"url": "/docs/19/using-explain.html", "label": "Using EXPLAIN"}, {"url": "/docs/19/parallel-plans.html", "label": "Parallel plans"}, {"url": "/wiki/guc/enable_mergejoin/?v=19", "label": "enable_mergejoin"}], "release": {"ref": "PostgreSQL 19beta4 source archive", "label": "19beta4", "major": "19", "channel": "preview", "revision": "83157ee9c599d03b2f7a3d73ef3a56ec24e0e79cc2b3501a64d1364f56398c86", "source_url": "https://ftp.postgresql.org/pub/source/v19beta4/postgresql-19beta4.tar.bz2", "source_snapshot_utc": ""}, "sources": [{"url": "https://ftp.postgresql.org/pub/source/v19beta4/postgresql-19beta4.tar.bz2", "line": 1436, "path": "src/backend/commands/explain.c", "label": "src/backend/commands/explain.c:1436", "sha256": "8b115b1c194a4b54ae630209a741e293b1df49a9052f10b2de9ca092a48998e3", "archive_sha256": "83157ee9c599d03b2f7a3d73ef3a56ec24e0e79cc2b3501a64d1364f56398c86"}, {"url": "https://ftp.postgresql.org/pub/source/v19beta4/postgresql-19beta4.tar.bz2", "line": 302, "path": "src/backend/executor/execProcnode.c", "label": "src/backend/executor/execProcnode.c:302", "sha256": "5e39b2037bed672da55104229ecc32da5abde44c26bcad01479edcfa044d09ed", "archive_sha256": "83157ee9c599d03b2f7a3d73ef3a56ec24e0e79cc2b3501a64d1364f56398c86"}, {"url": "https://ftp.postgresql.org/pub/source/v19beta4/postgresql-19beta4.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "65c9b61454ef3ed8dae2f6fefbbcb56578829ea6256e00816bd0cd6c72536dc7", "archive_sha256": "83157ee9c599d03b2f7a3d73ef3a56ec24e0e79cc2b3501a64d1364f56398c86"}, {"url": "https://ftp.postgresql.org/pub/source/v19beta4/postgresql-19beta4.tar.bz2", "path": "src/include/nodes/plannodes.h", "label": "src/include/nodes/plannodes.h", "sha256": "1c65d5d6b6c81c71531685843647869bcae630779d815a5036b06e070c6c06c7", "archive_sha256": "83157ee9c599d03b2f7a3d73ef3a56ec24e0e79cc2b3501a64d1364f56398c86"}, {"url": "/docs/19/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 19beta4 \u00b7 using-explain", "sha256": "52f111fbd213e2200146319d01a9dcc2ea90001617d2a28edc52f7954c2dd70b"}, {"url": "/docs/19/using-explain.html#USING-EXPLAIN-ANALYZE", "path": "using-explain.html", "label": "PostgreSQL 19beta4 \u00b7 using-explain", "sha256": "52f111fbd213e2200146319d01a9dcc2ea90001617d2a28edc52f7954c2dd70b"}, {"url": "/docs/19/using-explain.html#USING-EXPLAIN-CAVEATS", "path": "using-explain.html", "label": "PostgreSQL 19beta4 \u00b7 using-explain", "sha256": "52f111fbd213e2200146319d01a9dcc2ea90001617d2a28edc52f7954c2dd70b"}], "node_tag": "T_MergeJoin", "sections": [{"title": "EXPLAIN names and attributes", "paragraphs": ["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."]}, {"title": "Memory and temporary storage", "paragraphs": ["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."]}, {"title": "Parallel execution and instrumentation", "paragraphs": ["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."]}, {"title": "Same-version manual discussion", "paragraphs": ["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."]}, {"title": "Examples from this manual build", "blocks": [{"code": "EXPLAIN SELECT *\nFROM tenk1 t1, onek t2\nWHERE t1.unique1 < 100 AND t1.unique2 = t2.unique2;\n\n                                        QUERY PLAN\n------------------------------------------------------------------------------------------\n Merge Join  (cost=0.56..233.49 rows=10 width=488)\n   Merge Cond: (t1.unique2 = t2.unique2)\n   ->  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..643.28 rows=100 width=244)\n         Filter: (unique1 < 100)\n   ->  Index Scan using onek_unique2 on onek t2  (cost=0.28..166.28 rows=1000 width=244)", "source": {"url": "/docs/19/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 19beta4 \u00b7 using-explain", "sha256": "52f111fbd213e2200146319d01a9dcc2ea90001617d2a28edc52f7954c2dd70b"}, "paragraphs": ["Example copied from the PostgreSQL 19beta4 manual; it was not executed for this collection.", "Another possible type of join is a merge join, illustrated here:"]}]}, {"title": "Executor implementation notes", "paragraphs": ["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."]}, {"code": "case T_MergeJoin:\n\t\t\tpname = \"Merge\";\t/* \"Join\" gets added by jointype switch */\n\t\t\tsname = \"Merge Join\";\n\t\t\tbreak;", "title": "EXPLAIN identity in core source"}], "strategies": [], "description": ["Joins ordered input streams using merge clauses."], "evidence_kind": "source and documentation", "explain_names": ["Merge"], "partial_modes": [], "comparison_data": {"node_tag": "T_MergeJoin", "strategies": [], "text_names": ["Merge"], "initializer": "ExecInitMergeJoin", "partial_modes": [], "memory_mechanism": "unclassified", "parallel_callbacks": []}, "comparison_hash": "b17771ee4d48585afbaba91552e5eb00f05a4b6784aa491387217937a4a30511", "explain_prefixes": ["Parallel", "Async"], "runtime_verified": false, "source_inventory": {"explain": "src/backend/commands/explain.c", "executor": "src/backend/executor/execProcnode.c", "implementation": "src/backend/executor/nodeMergejoin.c"}, "parallel_callbacks": []}, "20": {"facts": [{"label": "Core node tag", "value": "T_MergeJoin"}, {"label": "Structured EXPLAIN Node Type", "value": "Merge Join"}, {"label": "Inputs", "value": "Ordered outer and inner child plans"}, {"label": "Output", "value": "Joined tuples according to the selected join type"}, {"label": "Executor initializer", "value": "ExecInitMergeJoin"}, {"label": "Memory mechanism", "value": "unclassified"}], "memory": {"evidence": [{"url": "https://ftp.postgresql.org/pub/snapshot/dev/postgresql-snapshot.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "3ed455579c351eabe38bb89513d3432379ebda43156cabc87ffdd9ebd7409aed", "archive_sha256": "4d3346909b201ac1648232cf290462a7070c119326f56196f1f0253ed80fae41"}], "mechanism": "unclassified", "description": "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.", "source_notes": []}, "tables": [{"key": "explain-labels", "rows": [{"label": "Merge", "identity": "Merge Join"}], "title": "EXPLAIN labels in this source build", "columns": [{"key": "label", "label": "Text-format label"}, {"key": "identity", "label": "Structured node identity"}]}], "related": [{"url": "/wiki/sql/explain/?v=20", "label": "EXPLAIN"}, {"url": "/docs/devel/using-explain.html", "label": "Using EXPLAIN"}, {"url": "/docs/devel/parallel-plans.html", "label": "Parallel plans"}, {"url": "/wiki/guc/enable_mergejoin/?v=20", "label": "enable_mergejoin"}], "release": {"ref": "PostgreSQL 20devel source archive", "label": "20devel", "major": "20", "channel": "devel", "revision": "4d3346909b201ac1648232cf290462a7070c119326f56196f1f0253ed80fae41", "source_url": "https://ftp.postgresql.org/pub/snapshot/dev/postgresql-snapshot.tar.bz2", "source_snapshot_utc": "26-Sep-2026 20:22"}, "sources": [{"url": "https://ftp.postgresql.org/pub/snapshot/dev/postgresql-snapshot.tar.bz2", "line": 1436, "path": "src/backend/commands/explain.c", "label": "src/backend/commands/explain.c:1436", "sha256": "13402758013520451539427b5993db06d463ca11c4e2d4cc5444e82367688077", "archive_sha256": "4d3346909b201ac1648232cf290462a7070c119326f56196f1f0253ed80fae41"}, {"url": "https://ftp.postgresql.org/pub/snapshot/dev/postgresql-snapshot.tar.bz2", "line": 302, "path": "src/backend/executor/execProcnode.c", "label": "src/backend/executor/execProcnode.c:302", "sha256": "5e39b2037bed672da55104229ecc32da5abde44c26bcad01479edcfa044d09ed", "archive_sha256": "4d3346909b201ac1648232cf290462a7070c119326f56196f1f0253ed80fae41"}, {"url": "https://ftp.postgresql.org/pub/snapshot/dev/postgresql-snapshot.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "3ed455579c351eabe38bb89513d3432379ebda43156cabc87ffdd9ebd7409aed", "archive_sha256": "4d3346909b201ac1648232cf290462a7070c119326f56196f1f0253ed80fae41"}, {"url": "https://ftp.postgresql.org/pub/snapshot/dev/postgresql-snapshot.tar.bz2", "path": "src/include/nodes/plannodes.h", "label": "src/include/nodes/plannodes.h", "sha256": "7a94ed1652f0d74d50c39971d1cd3e8051dbc0d6058f31b6de71a433ca343521", "archive_sha256": "4d3346909b201ac1648232cf290462a7070c119326f56196f1f0253ed80fae41"}, {"url": "/docs/devel/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 20devel \u00b7 using-explain", "sha256": "99cfea3035876ea63f88b75ba8c964b51a32a70606544e09f769c0b60a234b31"}, {"url": "/docs/devel/using-explain.html#USING-EXPLAIN-ANALYZE", "path": "using-explain.html", "label": "PostgreSQL 20devel \u00b7 using-explain", "sha256": "99cfea3035876ea63f88b75ba8c964b51a32a70606544e09f769c0b60a234b31"}, {"url": "/docs/devel/using-explain.html#USING-EXPLAIN-CAVEATS", "path": "using-explain.html", "label": "PostgreSQL 20devel \u00b7 using-explain", "sha256": "99cfea3035876ea63f88b75ba8c964b51a32a70606544e09f769c0b60a234b31"}], "node_tag": "T_MergeJoin", "sections": [{"title": "EXPLAIN names and attributes", "paragraphs": ["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."]}, {"title": "Memory and temporary storage", "paragraphs": ["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."]}, {"title": "Parallel execution and instrumentation", "paragraphs": ["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."]}, {"title": "Same-version manual discussion", "paragraphs": ["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."]}, {"title": "Examples from this manual build", "blocks": [{"code": "EXPLAIN SELECT *\nFROM tenk1 t1, onek t2\nWHERE t1.unique1 < 100 AND t1.unique2 = t2.unique2;\n\n                                        QUERY PLAN\n------------------------------------------------------------------------------------------\n Merge Join  (cost=0.56..233.49 rows=10 width=488)\n   Merge Cond: (t1.unique2 = t2.unique2)\n   ->  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..643.28 rows=100 width=244)\n         Filter: (unique1 < 100)\n   ->  Index Scan using onek_unique2 on onek t2  (cost=0.28..166.28 rows=1000 width=244)", "source": {"url": "/docs/devel/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 20devel \u00b7 using-explain", "sha256": "99cfea3035876ea63f88b75ba8c964b51a32a70606544e09f769c0b60a234b31"}, "paragraphs": ["Example copied from the PostgreSQL 20devel manual; it was not executed for this collection.", "Another possible type of join is a merge join, illustrated here:"]}]}, {"title": "Executor implementation notes", "paragraphs": ["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."]}, {"code": "case T_MergeJoin:\n\t\t\tpname = \"Merge\";\t/* \"Join\" gets added by jointype switch */\n\t\t\tsname = \"Merge Join\";\n\t\t\tbreak;", "title": "EXPLAIN identity in core source"}], "strategies": [], "description": ["Joins ordered input streams using merge clauses."], "evidence_kind": "source and documentation", "explain_names": ["Merge"], "partial_modes": [], "comparison_data": {"node_tag": "T_MergeJoin", "strategies": [], "text_names": ["Merge"], "initializer": "ExecInitMergeJoin", "partial_modes": [], "memory_mechanism": "unclassified", "parallel_callbacks": []}, "comparison_hash": "b17771ee4d48585afbaba91552e5eb00f05a4b6784aa491387217937a4a30511", "explain_prefixes": ["Parallel", "Async"], "runtime_verified": false, "source_inventory": {"explain": "src/backend/commands/explain.c", "executor": "src/backend/executor/execProcnode.c", "implementation": "src/backend/executor/nodeMergejoin.c"}, "parallel_callbacks": []}}}, "snapshot": {"facts": [{"label": "Core node tag", "value": "T_MergeJoin"}, {"label": "Structured EXPLAIN Node Type", "value": "Merge Join"}, {"label": "Inputs", "value": "Ordered outer and inner child plans"}, {"label": "Output", "value": "Joined tuples according to the selected join type"}, {"label": "Executor initializer", "value": "ExecInitMergeJoin"}, {"label": "Memory mechanism", "value": "unclassified"}], "memory": {"evidence": [{"url": "https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "df6726b291493e06be7c43e5664bfb4251267eff66481eaf8e04969c39612b25", "archive_sha256": "555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f"}], "mechanism": "unclassified", "description": "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.", "source_notes": []}, "tables": [{"key": "explain-labels", "rows": [{"label": "Merge", "identity": "Merge Join"}], "title": "EXPLAIN labels in this source build", "columns": [{"key": "label", "label": "Text-format label"}, {"key": "identity", "label": "Structured node identity"}]}], "related": [{"url": "/wiki/sql/explain/?v=18", "label": "EXPLAIN"}, {"url": "/docs/18/using-explain.html", "label": "Using EXPLAIN"}, {"url": "/docs/18/parallel-plans.html", "label": "Parallel plans"}, {"url": "/wiki/guc/enable_mergejoin/?v=18", "label": "enable_mergejoin"}], "release": {"ref": "PostgreSQL 18.6 source archive", "label": "18.6", "major": "18", "channel": "stable", "revision": "555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f", "source_url": "https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2", "source_snapshot_utc": ""}, "sources": [{"url": "https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2", "line": 1424, "path": "src/backend/commands/explain.c", "label": "src/backend/commands/explain.c:1424", "sha256": "34c86d6070224a0e981efef51f79101d6d505e5874f1684ace183034bab14bb4", "archive_sha256": "555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f"}, {"url": "https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2", "line": 302, "path": "src/backend/executor/execProcnode.c", "label": "src/backend/executor/execProcnode.c:302", "sha256": "f8a06a3f539077249b20664b2812433db6d7bd12b2c0ca633525db43d06f112a", "archive_sha256": "555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f"}, {"url": "https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2", "path": "src/backend/executor/nodeMergejoin.c", "label": "src/backend/executor/nodeMergejoin.c", "sha256": "df6726b291493e06be7c43e5664bfb4251267eff66481eaf8e04969c39612b25", "archive_sha256": "555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f"}, {"url": "https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2", "path": "src/include/nodes/plannodes.h", "label": "src/include/nodes/plannodes.h", "sha256": "52422b327a8049fbbb20d8b96008a0fc0a6fafa60f7eff3c695d5b2e83830120", "archive_sha256": "555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f"}, {"url": "/docs/18/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 18.6 \u00b7 using-explain", "sha256": "60040c30180093418a0affe56dd27dff9df2504b705b38039589e458bf5c31ed"}, {"url": "/docs/18/using-explain.html#USING-EXPLAIN-ANALYZE", "path": "using-explain.html", "label": "PostgreSQL 18.6 \u00b7 using-explain", "sha256": "60040c30180093418a0affe56dd27dff9df2504b705b38039589e458bf5c31ed"}, {"url": "/docs/18/using-explain.html#USING-EXPLAIN-CAVEATS", "path": "using-explain.html", "label": "PostgreSQL 18.6 \u00b7 using-explain", "sha256": "60040c30180093418a0affe56dd27dff9df2504b705b38039589e458bf5c31ed"}], "node_tag": "T_MergeJoin", "sections": [{"title": "EXPLAIN names and attributes", "paragraphs": ["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."]}, {"title": "Memory and temporary storage", "paragraphs": ["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."]}, {"title": "Parallel execution and instrumentation", "paragraphs": ["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."]}, {"title": "Same-version manual discussion", "paragraphs": ["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."]}, {"title": "Examples from this manual build", "blocks": [{"code": "EXPLAIN SELECT *\nFROM tenk1 t1, onek t2\nWHERE t1.unique1 < 100 AND t1.unique2 = t2.unique2;\n\n                                        QUERY PLAN\n------------------------------------------------------------------------------------------\n Merge Join  (cost=0.56..233.49 rows=10 width=488)\n   Merge Cond: (t1.unique2 = t2.unique2)\n   ->  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..643.28 rows=100 width=244)\n         Filter: (unique1 < 100)\n   ->  Index Scan using onek_unique2 on onek t2  (cost=0.28..166.28 rows=1000 width=244)", "source": {"url": "/docs/18/using-explain.html#USING-EXPLAIN-BASICS", "path": "using-explain.html", "label": "PostgreSQL 18.6 \u00b7 using-explain", "sha256": "60040c30180093418a0affe56dd27dff9df2504b705b38039589e458bf5c31ed"}, "paragraphs": ["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:"]}]}, {"title": "Executor implementation notes", "paragraphs": ["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."]}, {"code": "case T_MergeJoin:\n\t\t\tpname = \"Merge\";\t/* \"Join\" gets added by jointype switch */\n\t\t\tsname = \"Merge Join\";\n\t\t\tbreak;", "title": "EXPLAIN identity in core source"}], "strategies": [], "description": ["Joins ordered input streams using merge clauses."], "evidence_kind": "source and documentation", "explain_names": ["Merge"], "partial_modes": [], "comparison_data": {"node_tag": "T_MergeJoin", "strategies": [], "text_names": ["Merge"], "initializer": "ExecInitMergeJoin", "partial_modes": [], "memory_mechanism": "unclassified", "parallel_callbacks": []}, "comparison_hash": "b17771ee4d48585afbaba91552e5eb00f05a4b6784aa491387217937a4a30511", "explain_prefixes": ["Parallel", "Async"], "runtime_verified": false, "source_inventory": {"explain": "src/backend/commands/explain.c", "executor": "src/backend/executor/execProcnode.c", "implementation": "src/backend/executor/nodeMergejoin.c"}, "parallel_callbacks": []}, "comparison": {"left": "17", "right": "18", "status": "unchanged", "diff": ""}}