合并连接算法采用两个按合并键排序的数据集并返回有序输出。输入数据集可以通过索引扫描进行预排序或显式排序。
下面是合并连接的示例。请注意计划中的MergeJoin节点。
EXPLAIN(costsoff)SELECT*FROMticketstJOINticket_flightstfONtf.ticket_no=t.ticket_noORDERBYt.ticket_no;QUERYPLANMergeJoinMergeCond:(t.ticket_no=tf.ticket_no)>IndexScanusingtickets_pkeyonticketst>IndexScanusingticket_flights_pkeyonticket_flightstf(4rows)在这里，优化器选择了这种连接方法，因为它返回按ORDERBY子句下指定的键排序的输出。选择计划时，优化器会考虑输入的顺序，并尽可能避免完全排序。除此之外，只要顺序保持不变，生成的输出就可以用作另一个合并连接的输入：
EXPLAIN(costsoff)SELECT*FROMticketstJOINticket_flightstfONt.ticket_no=tf.ticket_noJOINboarding_passesbpONbp.ticket_no=tf.ticket_noANDbp.flight_id=tf.flight_idORDERBYt.ticket_no;QUERYPLANMergeJoinMergeCond:(tf.ticket_no=t.ticket_no)>MergeJoinMergeCond:((tf.ticket_no=bp.ticket_no)AND(tf.flight_...>IndexScanusingticket_flights_pkeyonticket_flightstf>IndexScanusingboarding_passes_pkeyonboarding_passe...>IndexScanusingtickets_pkeyonticketst(7rows)ticket_flights和boarding_passes表首先合并。这些表有一个复合主键(ticket_no,flight_id)，因此输出按这两列排序。tickets然后将生成的行集与按排序的表合并ticket_no。
合并在两个数据集上一次完成，不需要任何额外的内存。该算法使用两个指针，它们指向两个集合的当前（或最初，第一）行。
如果当前行的键不匹配，则其中一个指针（指向具有较低键的行的指针）向前移动一步。重复此过程，直到找到匹配项。匹配的行返回到父节点，内部集合指针向前移动一步。该算法重复直到到达任一组的末尾。
这种特定的算法可以处理内部集合中的重复键，但不能处理外部集合中的重复键。引入了一个额外的步骤来解决这个问题：每当外部指针移动但键保持不变时，内部指针就会返回到与键匹配的第一行。这样，每个外部集合行都将与所有具有相同键的内部集合行匹配。
该算法还有另一种变体可以执行外连接，但它基于相同的原理。
合并连接旨在与权益运算符一起使用，因此它仅支持等值连接（但也努力支持其他比较运算符）。
参考之前的例子：
EXPLAINSELECT*FROMticketstJOINticket_flightstfONtf.ticket_no=t.ticket_noORDERBYt.ticket_no;QUERYPLANMergeJoin(cost=0.99..822358.66rows=8391852width=136)MergeCond:(t.ticket_no=tf.ticket_no)>IndexScanusingtickets_pkeyonticketst(cost=0.43..139110.29rows=2949857width=104)>IndexScanusingticket_flights_pkeyonticket_flightstf(cost=0.56..570975.58rows=8391852width=32)(6rows)最初，启动成本至少包括子节点的启动成本。
除此之外，您通常必须在找到第一个匹配项之前扫描两个数据集的至少一部分。要估计这个分数，您可以使用直方图来比较两组中的最小连接键。但是，在这种情况下，两个表中的票号范围是相同的。
节点的总成本是从其子节点检索数据的成本和数据处理成本的总和。
因为算法在到达两个集合中的任何一个的末尾时停止（当然，执行外连接时除外），所以第二个集合的一小部分可能保持未扫描状态。您可以通过比较两组的最大键来估计该部分的大小。在这种情况下，我们的两个集合都将被完全扫描，因此我们将子节点的全部总成本包含在父节点的总成本中。
此外，重复键可能会导致某些内部集合行被多次扫描。重复扫描的次数与连接结果和内部集基数之间的差异成正比。
在这里，这些基数是相同的，这意味着没有重复。
数据处理成本包括关键比较和结果输出。比较的次数可以通过将两组的基数和重复的外部组行扫描的次数相加来估计。一次比较的成本估计为cpu_operator_cost，行输出成本估计为cpu_tuple_cost。
现在我们可以计算示例的连接成本：
SELECT0.43+0.56ASstartup,round((139110.29+570975.58+current_setting('cpu_tuple_cost')::real*8391852+current_setting('cpu_operator_cost')::real*(2949857+8391852))::numeric,2)AStotal;startup|total+0.99|822358.66(1row)并联模式合并连接算法可用于并行计划。
工作人员可以并行扫描外部集合，但每个工作人员单独扫描内部集合。
下面是一个带有合并连接的并行计划示例：
SETenable_hashjoin=off;EXPLAIN(costsoff)SELECTcount(*),sum(tf.amount)FROMticketstJOINticket_flightstfONtf.ticket_no=t.ticket_no;QUERYPLANFinalizeAggregate>GatherWorkersPlanned:2>PartialAggregate>MergeJoinMergeCond:(tf.ticket_no=t.ticket_no)>ParallelIndexScanusingticket_flights_pkeyo...>IndexOnlyScanusingtickets_pkeyonticketst(8rows)此模式不支持全外连接和右外连接。
合并联接支持所有逻辑联接类型。唯一的限制是，对于完全和右外连接，连接条件必须是合并操作的有效表达式（outercolumnequalsinnercolumn或columnequalsconstant）。对于其他逻辑连接类型，在合并完成后，任何不可合并的条件都将应用于输出，但对于完全和右外连接是不可能的。
下面是一个完全合并连接的例子：
EXPLAIN(costsoff)SELECT*FROMticketstFULLJOINticket_flightstfONtf.ticket_no=t.ticket_noORDERBYt.ticket_no;QUERYPLANSortSortKey:t.ticket_no>MergeFullJoinMergeCond:(t.ticket_no=tf.ticket_no)>IndexScanusingtickets_pkeyonticketst>IndexScanusingticket_flights_pkeyonticket_flightstf(6rows)内部和左外部合并连接保留顺序。全外连接和右外连接不会，因为数据中可能出现的NULL值会破坏排序。这是Sort节点用于重新排序输出的地方。它增加了成本，使散列连接成为更有吸引力的替代方案，因此我们必须明确禁用它以进行演示。
但是，在下一个示例中，无论如何都选择了散列连接，因为不能以任何其他方式完成具有不可合并条件的完全连接。
EXPLAIN(costsoff)SELECT*FROMticketstFULLJOINticket_flightstfONtf.ticket_no=t.ticket_noANDtf.amount>0ORDERBYt.ticket_no;QUERYPLANSortSortKey:t.ticket_no>HashFullJoinHashCond:(tf.ticket_no=t.ticket_no)JoinFilter:(tf.amount>'0'::numeric)>SeqScanonticket_flightstf>Hash>SeqScanonticketst(8rows)RESETenable_hashjoin;排序如果任一集合（或两者）没有按连接键排序，则必须在合并之前对其进行排序。这种必要的排序是在计划中的排序节点下完成的。
EXPLAIN(costsoff)SELECT*FROMflightsfJOINairports_datadepONf.departure_airport=dep.airport_codeORDERBYdep.airport_code;QUERYPLANMergeJoinMergeCond:(f.departure_airport=dep.airport_code)>SortSortKey:f.departure_airport>SeqScanonflightsf>SortSortKey:dep.airport_code>SeqScanonairports_datadep(8rows)排序算法本身是通用的。它可以由ORDERBY子句本身或在窗口函数中调用：
EXPLAIN(costsoff)SELECTflight_id,row_number()OVER(PARTITIONBYflight_noORDERBYflight_id)FROMflightsf;QUERYPLANWindowAgg>SortSortKey:flight_no,flight_id>SeqScanonflightsf(4rows)在这里，WindowAgg节点计算由Sort节点预先排序的数据集的窗口函数。
规划器有多种排序模式可供选择。上面的例子展示了其中的两个（排序方法）。与往常一样，您可以通过以下方式深入了解更多详细信息EXPLAINANALYZE：
EXPLAIN(analyze,costsoff,timingoff,summaryoff)SELECT*FROMflightsfJOINairports_datadepONf.departure_airport=dep.airport_codeORDERBYdep.airport_code;QUERYPLANMergeJoin(actualrows=214867loops=1)MergeCond:(f.departure_airport=dep.airport_code)>Sort(actualrows=214867loops=1)SortKey:f.departure_airportSortMethod:externalmergeDisk:17136kB>SeqScanonflightsf(actualrows=214867loops=1)>Sort(actualrows=104loops=1)SortKey:dep.airport_codeSortMethod:quicksortMemory:52kB>SeqScanonairports_datadep(actualrows=104loops=1)(10rows)快速排序如果要排序的数据完全适合允许的内存(work_mem)，则使用良好的旧快速排序算法。你可以在任何计算机科学教科书的第一页找到它的描述，所以我不会在这里重复。
对于实现，排序由特定组件完成，该组件为任务选择最合适的算法。
让我们看一下算法是如何对一个小表进行排序的：
EXPLAINSELECT*FROMairports_dataORDERBYairport_code;QUERYPLANSort(cost=7.52..7.78rows=104width=145)SortKey:airport_code>SeqScanonairports_data(cost=0.00..4.04rows=104width=...(3rows)对n个值进行排序的复杂度为O(nlog2n)。一个比较操作的成本是cpu_operator_cost值的两倍。您需要对整个集合进行扫描和排序才能得到结果，因此启动排序成本将包括比较操作成本和子节点的总成本。
除此之外，总排序成本将包括排序节点输出的每一行的处理成本，估计为每行的cpu_operator_cost（而不是默认的cpu_tuple_cost，因为它很便宜）。
因此，上面示例的排序成本将计算如下：
WITHcosts(startup)AS(SELECT4.04+round((current_setting('cpu_operator_cost')::real2104*log(2,104))::numeric,2))SELECTstartup,startup+round((current_setting('cpu_operator_cost')::real*104)::numeric,2)AStotalFROMcosts;startup|total+7.52|7.78(1row)前N堆排序前N堆排序是当您只希望对集合的一部分进行排序（直到某个LIMIT）而不是整个集合时执行的操作。LIMIT更准确地说，当将过滤掉至少一半的输入行，或者当输入不适合内存但输出适合时，使用此算法。
EXPLAIN(analyze,timingoff,summaryoff)SELECT*FROMseatsORDERBYseat_noLIMIT100;QUERYPLANLimit(cost=72.57..72.82rows=100width=15)(actualrows=100loops=1)>Sort(cost=72.57..75.91rows=1339width=15)(actualrows=100loops=1)SortKey:seat_noSortMethod:topNheapsortMemory:33kB>SeqScanonseats(cost=0.00..21.39rows=1339width=15)(actualrows=1339loops=1)(8rows)为了找到n中的k个最高（最低）值，该算法首先创建一个称为堆的数据结构并将k前行添加到其中。然后它继续将行一一添加到堆中，但在每一行之后，它从堆中驱逐一个最低（最高）的值。当它用完要添加的新行时，堆会留下k个最高或最低值。
这里的术语堆是指一种特定的数据结构，不应与数据库表混淆，后者通常具有相同的名称。
算法复杂度为O(nlog2k)，但是每次操作的成本都比Quicksort高，所以成本计算公式以nlog22k作为估计。
WITHcosts(startup)AS(SELECT21.39+round((current_setting('cpu_operator_cost')::real21339log(2,2100))::numeric,2))SELECTstartup,startup+round((current_setting('cpu_operator_cost')::real*100)::numeric,2)AStotalFROMcosts;startup|total+72.57|72.82(1row)外部排序每当执行器发现它正在读取的数据集太需要在内存中排序时，排序节点就会切换到外部合并排序模式。
到目前为止扫描的行由Quicksort排序并转储到临时文件中。
然后另一批行被扫描、排序和转储，等等。重复此过程，直到所有数据都存储在磁盘上的一堆排序文件中。
然后，算法开始合并文件。该过程与合并连接非常相似，尽管这里可以一次合并两个以上的文件。
合并不会占用大量内存。从本质上讲，每个文件的单行大小就足够了。该算法扫描每个文件的第一行并存储它们。然后，它在存储的值中选择最低（或最高）值并将其作为输出返回。之后，它需要另一行并将其放入存储返回行的内存中。
在实践中，不是逐一扫描行，而是分批扫描每行32页，以节省I/O成本。一次合并的文件数由可用内存量决定，但绝不会少于六个。它也永远不会超过500，因为算法效率会在大量并发合并文件时受到影响。
如果无法在一次迭代中合并所有临时文件，则第一次合并的结果将转储到其自己的临时文件中。每次迭代都会增加从磁盘读取和写入磁盘的数据量，从而减慢该过程，因此拥有尽可能多的内存以使外部合并排序有效运行是有益的。
第二次迭代获取第一次迭代产生的临时文件并重复该过程。
最终的合并通常会被推迟，并且仅在父节点拉取数据时执行。
让我们EXPLAINANALYZE来看看排序用了多少磁盘空间。buffers您还可以使用该选项检查临时文件（临时读取和写入）的缓冲区使用统计信息。读取和写入的缓冲区数量大致相同，并且转换为KB后，将与计划中的Disk值匹配。
EXPLAIN(analyze,buffers,costsoff,timingoff,summaryoff)SELECT*FROMflightsORDERBYscheduled_departure;QUERYPLANSort(actualrows=214867loops=1)SortKey:scheduled_departureSortMethod:externalmergeDisk:17136kBBuffers:sharedhit=610read=2017,tempread=2142written=2150>SeqScanonflights(actualrows=214867loops=1)Buffers:sharedhit=607read=2017(6rows)在服务器日志中有更多关于临时文件的统计信息（使用参数log_temp_bufferson）。
我们再看一下外部归并排序方案：
EXPLAINSELECT*FROMflightsORDERBYscheduled_departure;QUERYPLANSort(cost=31883.96..32421.12rows=214867width=63)SortKey:scheduled_departure>SeqScanonflights(cost=0.00..4772.67rows=214867width=63)(3rows)在这里，基本的比较成本与快速排序中的相同，但还增加了I/O成本。所有输入数据首先转储到磁盘，然后从磁盘读取以进行合并（多次，如果有太多单独的文件需要一次合并）。
写入磁盘的数据量取决于输入数据集中的行数和大小。在此示例中，查询从表中提取所有列flights，因此数据大小将接近表大小，除了它不包含任何元组标题和页面元数据（2309个页面与2624个页面）。在这里，一次迭代就足以对数据进行排序。
所以最后，排序成本会这样计算：
增量排序通过将集合分成多个较小的组来减少内存需求，并且还可以开始逐组输入输出，而无需等待整个集合被处理。
实际实现采用了额外的优化：虽然它将较大的行块分成组以单独排序，但较小的子集被放入一个组并一起排序。与准系统算法相比，这降低了排序启动开销成本。
计划中的增量排序节点是进行排序的地方：
在PostgreSQL14及更高版本中，增量排序也适用于窗口函数：
EXPLAIN(costsoff)SELECTrow_number()OVER(ORDERBYtotal_amount,book_date)FROMbookings;QUERYPLANWindowAgg>IncrementalSortSortKey:total_amount,book_datePresortedKey:total_amount>IndexScanusingbookings_total_amount_idxonbookings(5rows)增量排序成本取决于估计的组数和对平均组进行排序的估计成本（我们之前已经介绍过）。
启动成本显示了对一个（第一个）组进行排序的成本，因为这足以让节点开始输出。总成本包括对所有组进行排序的成本。
EXPLAINSELECT*FROMbookingsORDERBYtotal_amount,book_date;QUERYPLANIncrementalSort(cost=45.10..282293.40rows=2111110width=21)SortKey:total_amount,book_datePresortedKey:total_amount>IndexScanusingbookings_total_amount_idxonbookings(co...(4rows)我将在此处跳过计算的详细信息。
排序可以并行执行。也就是说，虽然工作人员返回排序后的输出，但Gather节点不会以任何方式对它们进行排序，只会按照输入的任何顺序附加输入。为了保持行排序，使用了另一个节点：GatherMerge。
EXPLAIN(analyze,costsoff,timingoff,summaryoff)SELECT*FROMflightsORDERBYscheduled_departureLIMIT10;QUERYPLANLimit(actualrows=10loops=1)>GatherMerge(actualrows=10loops=1)WorkersPlanned:1WorkersLaunched:1>Sort(actualrows=8loops=2)SortKey:scheduled_departureSortMethod:topNheapsortMemory:27kBWorker0:SortMethod:topNheapsortMemory:27kB>ParallelSeqScanonflights(actualrows=107434lo...(9rows)GatherMerge节点使用二叉堆对来自工作人员的行进行排序。本质上，它只是合并了几组行，很像外部合并排序，但在底层存在一些差异，其中之一是GatherMerge节点针对处理少量固定数量的数据源和用于逐行接收，无需块I/O。
GatherMerge启动成本取决于子节点启动成本。与Gather节点一样，还有工作进程启动成本，估计为parallel_setup_cost参数值。
除此之外，还有二进制堆构建成本，其中包括对n个项目进行排序，其中n是并行工作器的数量，即nlog2n。比较操作成本估计为cpu_operator_cost乘以2。由此产生的成本通常是微不足道的，因为工人的数量从来没有那么高。
然后，总成本加上子节点（由多个工作人员执行）的数据检索成本和工作人员的数据输出成本。考虑到可能的延迟，检索和输出成本估计为每行的parallel_tuple_cost加上5%。
最后是二叉堆更新，它需要log2n比较操作加上辅助操作。它的成本估计为logN(2cpu_operator_cost)+cpu_operator_cost每个输入行。
这是另一个带有GatherMerge的计划：
EXPLAINSELECTamount,count(*)FROMticket_flightsGROUPBYamount;QUERYPLANFinalizeGroupAggregate(cost=123399.62..123485.00rows=337wid...GroupKey:amount>GatherMerge(cost=123399.62..123478.26rows=674width=14)WorkersPlanned:2>Sort(cost=122399.59..122400.44rows=337width=14)SortKey:amount>PartialHashAggregate(cost=122382.07..122385.44r...GroupKey:amount>ParallelSeqScanonticket_flights(cost=0.00...(9rows)请注意，这里的工作人员在将结果传递给排序节点之前执行部分哈希聚合。这是有效的，因为聚合减少了行数。然后，Sort节点将输出传递给领导进程，由GatherMerge节点组装。最终聚合使用排序的值列表而不是散列。
在本例中，有3个并行进程（包括领导者），因此GatherMerge成本计算如下：
WITHcosts(startup,run)AS(SELECTround((--startinguptheprocessescurrent_setting('parallel_setup_cost')::real+--buildingtheheapcurrent_setting('cpu_operator_cost')::real23*log(2,3))::numeric,2),round((--transmittingtherowscurrent_setting('parallel_tuple_cost')::real1.05674+--updatingtheheapcurrent_setting('cpu_operator_cost')::real2674*log(2,3)+current_setting('cpu_operator_cost')::real*674)::numeric,2))SELECT122399.59+startupASstartup,122400.44+startup+runAStotalFROMcosts;startup|total+123399.61|123478.26(1row)分组和不同的值前面的示例表明，聚合值的分组（和删除重复值）既可以通过散列也可以通过排序来完成。在排序列表中，可以在一次遍历中找到一组重复值。
一个名为Unique的简单节点执行从给定列表中选择不同值的任务：
EXPLAIN(costsoff)SELECTDISTINCTbook_refFROMbookingsORDERBYbook_ref;QUERYPLANResult>Unique>IndexOnlyScanusingbookings_pkeyonbookings(3rows)聚合本身在GroupAggregate节点下执行。
EXPLAIN(costsoff)SELECTbook_ref,count(*)FROMbookingsGROUPBYbook_refORDERBYbook_ref;QUERYPLANGroupAggregateGroupKey:book_ref>IndexOnlyScanusingbookings_pkeyonbookings(3rows)在并行计划中，此节点将被PartialGroupAggregate替换，聚合将在FinalizeGroupAggregate下完成。
GROUPINGSETS在PostgreSQL10及更高版本中，当对多个集合（下、、CUBE和ROLLUP子句）执行分组时，同一节点可以使用散列和排序。该算法的细节过于复杂，无法在本文的范围内涵盖，但我们可以看一个示例。在这个计划中，分组是在三个不同的列上执行的，并且内存是有限的。
SETwork_mem='64kB';EXPLAIN(costsoff)SELECTcount(*)FROMflightsGROUPBYGROUPINGSETS(aircraft_code,flight_no,departure_airport);QUERYPLANMixedAggregateHashKey:departure_airportGroupKey:aircraft_codeSortKey:flight_noGroupKey:flight_no>SortSortKey:aircraft_code>SeqScanonflights(8rows)聚合节点MixedAggregate接收一组按飞机代码预先排序的行。
首先，扫描集合，将行按aircraft_code（GroupKey）分组。在扫描行时，它们由flight_no重新排序（通过内存中的快速排序（如果足够）或通过磁盘上的外部排序，就像排序节点一样）。同时，这些行被记录到一个散列表中，键为“department_airport”（内存中或磁盘上的临时文件，就像HashAggregate一样）。
接下来，对刚刚按flight_no排序的集合进行扫描，并按相同的键（SortKey和嵌套的GroupKey）进行分组。如果需要按另一列分组，则在此阶段将相应地重新排序行。
最后，扫描第一步的哈希表，并将值按离开机场（哈希键）分组。
可以使用三种方法连接两个数据集，每种方法都有自己的优点和缺点。
当数据量增加时，该算法的缺点变得明显。对于笛卡尔积计算，算法的复杂性是二次的：成本与两个数据集大小的乘积成正比。在实践中，纯笛卡尔积计算并不经常出现。通常，每个外部集合行的内部集合索引扫描中都有一定数量的行，并且该数量与内部集合中的总行数无关（例如，每次预订的平均票数不t取决于预订总数或预订的门票总数）。因此，复杂度的增加通常是线性的，而不是二次的，尽管线性系数很高。
嵌套循环连接的另一个重要特性是它的多功能性。虽然其他连接方法仅支持等连接，但此算法可以在任何连接条件下运行。这使得该算法几乎适用于任何类型的查询和条件（完全连接除外，它不能在嵌套循环中完成）。但是请记住，大型数据集的非等连接本质上是低效的。
散列连接是您想要用于大型数据集的方法。有了足够的内存，散列连接可以一次连接两个数据集。换句话说，它的复杂性是线性的。哈希联接与顺序扫描一起使用，最常见于处理大量数据的OLAP查询环境中。
该算法不适合延迟比吞吐量更重要的用例，因为它在整个哈希表完成之前无法开始返回数据。
除此之外，散列连接仅限于等值连接。最后，您使用的数据类型必须是可散列的（但这很少是问题）。
在PostgreSQL14及更高版本中，嵌套循环连接有时会与哈希连接竞争，这要归功于Memorize节点（也基于哈希表）缓存内部集合行的能力。嵌套循环连接可以在某些条件下提前，因为它不必像散列连接那样扫描整个内部集。
合并连接适用于短OLTP查询和长OLAP查询。它具有线性复杂性（两组只需扫描一次），需要很少的内存并且可以立即开始输出。唯一需要注意的是数据集必须预先排序。理想的情况是输入来自索引扫描。这也是小型行集的自然选择。对于大量数据，索引访问只有在几乎没有表访问时才保持高效。
如果没有适当的索引，就必须对数据集进行排序，并且排序具有高于线性的复杂度：O(nlog2n)。因此，合并连接通常落后于散列连接，除了输出也必须排序的情况。
合并连接不区分内部集和外部集，这是一个不错的好处。如果计划器错误地分配内部和外部集，嵌套循环连接和哈希连接的效率都会下降，而对于合并连接，这不是问题。
与散列连接一样，合并连接只能与等值连接一起使用。此外，数据类型必须具有B-Tree运算符类。
下图说明了在不同连接选择性值下不同连接方法的近似成本。
Whenselectivityishigh,thenestedloopjoinscansbothtablesbyindex,butathighselectivityitswitchestofullscanandthegraphbecomeslinear.
在此示例中，散列连接对两个表都使用全扫描。图上的“步骤”表示哈希表不再适合内存并且数据开始溢出到磁盘的时刻。
随着选择性的增加，带有索引扫描的合并连接显示成本略有增加。有了足够的work_mem，散列连接优于合并连接，但是当涉及到临时文件时，合并连接会领先。
合并连接和排序图显示了当索引扫描不可用且需要进行预排序时成本如何增加。与散列连接一样，“步骤”表示算法耗尽内存并开始将数据溢出到临时文件中的时刻。