16

PG归并排序算法详解

 5 years ago
source link: http://www.cnblogs.com/letsfly/p/12497460.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

前言

  • 归并排序算法是连接算法中比较复杂的算法，相比嵌套循环与Hash匹配而言。本节会通过实例来说明该算法在PG中的具体实现。

  • 在PG中，通过状态机来实现——归并-连接。当然这里的完整流程是排序——归并——连接，由于排序通过Sort操作来完成，这里就不赘述。

  • 这里的状态机一共有11中状态，在这11中状态的转换过程中，会根据外表(inner)或内表(inner)读取到数据的状态分为——

    MJEVAL_MATCHABLE、MJEVAL_NONMATCHABLE、MJEVAL_ENDOFJOIN。可以简单理解为读取到非空数据，读取到数据为空以及所有数据读取完成。

  • 前置条件，内外表均已排序完成且都是升序策略。
-----------初始状态-----------------
EXEC_MJ_INITIALIZE_OUTER    
EXEC_MJ_INITIALIZE_INNER        
-----------中间状态-----------------                
EXEC_MJ_NEXTOUTER           
EXEC_MJ_TESTOUTER           
EXEC_MJ_NEXTINNER           
EXEC_MJ_SKIP_TEST           
EXEC_MJ_SKIPOUTER_ADVANCE   
EXEC_MJ_SKIPINNER_ADVANCE       
-------------结束状态-----------------
EXEC_MJ_JOINTUPLES
EXEC_MJ_ENDOUTER            
EXEC_MJ_ENDINNER

举例

  • 接下来，以一个实例来说明状态机转换的具体流程。这里假设有两张表进行全外连接——outer/inner。数据如下所示：
outer  inner
  5      5 
  5      5
  6      8
  6      8  
  7     12
  8     14
  • 简单提及一下后面说明过程中会涉及到的变量
  • 1 (current) outer tuple扫描到的一条外表数据，eg: 5/6/7
  • 2 (current) inner tuple扫描到的一条内表数据，eg: 8/12/14
  • 3 marked tuple 上一次与outer tuple匹配到的inner tuple，记录为marked tuple(描述的是inner tuple)

  • 4 offset tuple 在方法ExecMarkPos执行时，会将当前inner tuple的位置做标记，以便后面inner tuple的重新扫描。通过方法ExecSortRestrPos实现标记。通过方法ExecRestrPos来实现将(current) inner tuple恢复为offset tuple。

  • 1 第一轮，初始状态为EXEC_MJ_INITIALIZE_OUTER，外表游标下移获取到outer tuple——5(1)。通过MJEVAL_MATCHABLE切换到状态EXEC_MJ_INITIALIZE_INNER。

    在状态EXEC_MJ_INITIALIZE_INNER下，内表游标下移获取到——5(1)。通过MJEVAL_MATCHABLE切换到EXEC_MJ_SKIP_TEST。

    来到状态EXEC_MJ_SKIP_TEST，这里执行方法MJCompare，也就是对outer tuple与inner tuple进行了比较，5(1) == 5(1)。标记offset为current，同时将marked tuple置为当前tuple。然后切换到状态EXEC_MJ_JOINTUPLES。

    在状态EXEC_MJ_JOINTUPLES下，首先更改状态为EXEC_MJ_NEXTINNER，然后将匹配到的数据返回。

    到这里为止，完成了外表/内表的数据匹配，一轮匹配就结束了。

  • 匹配结果 5(1) == 5(1)
outer  inner
outer tuple -  5       5  - marked tuple - offset tuple - inner tuple
               5       5
               6       8
               6       8  
               7      12
               8      14

  • 2 第二轮，由于上一轮在退出时将状态置为EXEC_MJ_NEXTINNER，因此，这一轮从状态EXEC_MJ_NEXTINNER出发。该状态下，内表游标下移获取数据——5(2),然后调用方法MJCompare比较outer tuple与inner tuple，5(1) == 5(2)，切换到状态EXEC_MJ_JOINTUPLES。同样，切换状态为EXEC_MJ_NEXTINNER，并且完成该轮扫描(后面不再赘述)。

  • 匹配结果 5(1) == 5(2)
outer  inner
outer tuple -  5       5  - marked tuple  - offset tuple
               5       5  - inner tuple
               6       8
               6       8  
               7      12
               8      14

  • 3 第三轮，继续来到状态EXEC_MJ_NEXTINNER，此时内表游标下移获取数据——8(1)，与outer tuple相比——5(1) < 8(1)，切换到状态EXEC_MJ_NEXTOUTER。

    在状态EXEC_MJ_NEXTOUTER下，外表游标下移获取到outer tuple——5(2)，同时通过MJEVAL_MATCHABLE切换到EXEC_MJ_TESTOUTER。

    在状态EXEC_MJ_TESTOUTER下，这里对于 outer tuple与marked tuple 进行了比较，也就是5(2) == 5(1)，这里调用方法ExecRestrPos重置了内表的游标，将inner tuple置为offset tuple，也就是说，下一次内表游标的下移后获取的数据是——5(2)。然后切换状态为EXEC_MJ_JOINTUPLES，同时结束了本轮的匹配。

  • 匹配结果 5(2) == 5(1)
outer  inner
               5       5  - marked tuple - offset tuple - inner tuple 
 outer tuple - 5       5  
               6       8  
               6       8  
               7      12
               8      14

  • 4 第四轮，其实与第二轮的描述基本一致，只是结果发生了变化

  • 匹配结果 5(2) == 5(2)
outer  inner
               5       5  - marked tuple - offset tuple 
 outer tuple - 5       5  - inner tuple 
               6       8  
               6       8  
               7      12
               8      14

  • 5 第五轮，在状态EXEC_MJ_NEXTINNER下，内表游标下移获取数据——8(1)，需要注意的是，这里将 mj_MatchedInner标记为false 。与outer tuple比较——5(2) < 8(1)，切换到状态EXEC_MJ_NEXTOUTER。

    在状态EXEC_MJ_NEXTOUTER下，外表游标下移获取到outer tuple——6(1)，同时通过MJEVAL_MATCHABLE切换到EXEC_MJ_TESTOUTER。

    在状态EXEC_MJ_TESTOUTER下，这里对于 outer tuple与marked tuple 进行了比较——6(1) > 5(1)，重新载入current inner tuple——8(1)，然后切换到状态EXEC_MJ_SKIP_TEST。

    在状态EXEC_MJ_SKIP_TEST下，调用方法MJCompare比较outer tuple与inner tuple——6(1) < 8(1)。切换到状态EXEC_MJ_SKIPOUTER_ADVANCE。

    来到状态EXEC_MJ_SKIPOUTER_ADVANCE。由于在该轮开始，变量mj_MatchedOuter已经被置为false，因此，这里并没有继续外表的游标下移，而是修改变量mj_MatchedOuter为true，然后调用MJFillOuter将其关联的inner tuple置为空。这里没有进行状态的切换。该轮循环结束。

  • 关联结果 6(1) null
outer  inner
               5       5  - marked tuple  - offset tuple 
               5       5  
 outer tuple - 6       8  - inner tuple 
               6       8  
               7      12
               8      14

  • 6 由于上面一轮并没有发生状态的切换，因此，该轮继续从状态EXEC_MJ_SKIPOUTER_ADVANCE出发，只是，上一轮结束时，将变量mj_MatchedOuter置为true，因此，外表游标下移获取到outer tuple——6(2)，将 mj_MatchedOuter置为false ，然后切换到状态EXEC_MJ_SKIP_TEST。

    来到状态EXEC_MJ_SKIP_TEST，调用方法MJCompare比较outer tuple与inner tuple——6(2) < 8(1)。切换到状态EXEC_MJ_SKIPOUTER_ADVANCE。与上一轮相似，这里同样调用MJFillOuter将其关联的inner tuple置为空。这里没有进行状态的切换。该轮循环结束。

  • 关联结果 6(2) null
outer  inner
               5       5  - marked tuple  - offset tuple 
               5       5  
               6       8  - inner tuple 
 outer tuple - 6       8  
               7      12
               8      14

  • 7 这一轮的流程基本与第六轮相似，只是外表游标下移获取到outer tuple——7。

  • 关联结果 7 null
outer  inner
               5       5  - marked tuple  - offset tuple 
               5       5  
               6       8  - inner tuple 
               6       8  
outer tuple -  7      12
               8      14

  • 8 该轮同样从状态EXEC_MJ_SKIPOUTER_ADVANCE出发，外表游标下移获取到outer tuple——8，状态切换到EXEC_MJ_SKIP_TEST。

    来到状态EXEC_MJ_SKIP_TEST，调用方法MJCompare比较outer tuple与inner tuple——8 == 8(1)。这里标记offset为current，同时将marked tuple置为当前tuple。然后切换到状态EXEC_MJ_JOINTUPLES。同时结束了本轮的匹配。（不要忘记，下一轮从状态EXEC_MJ_NEXTINNER出发）

  • 关联结果 8 == 8(1)
outer  inner
               5       5  
               5       5  
               6       8  - marked tuple  - offset tuple  - inner tuple 
               6       8  
               7      12
outer tuple -  8      14

  • 9 该轮从状态EXEC_MJ_NEXTINNER出发，内表游标下移获取数据——8(2)，调用方法MJCompare与outer tuple相比较——8 == 8(2)，因此，切换到状态EXEC_MJ_JOINTUPLES，同时结束本轮的匹配。

  • 关联结果 8 == 8(2)
outer  inner
               5       5  
               5       5  
               6       8  - marked tuple  - offset tuple  
               6       8  - inner tuple 
               7      12
outer tuple -  8      14

  • 10 该轮同样从状态EXEC_MJ_NEXTINNER出发，内表游标下移获取数据——8(2)，同时将 变量mj_MatchedInner设置为false ，调用方法MJCompare与outer tuple相比较——8 < 12，故切换到状态EXEC_MJ_NEXTOUTER。

    在状态EXEC_MJ_NEXTOUTER下，外表游标下移，同时将变量mj_MatchedOuter置为false，由于此时外表已经没有数据了，因此通过MJEVAL_ENDOFJOIN切换到状态EXEC_MJ_ENDOUTER。

    来到状态EXEC_MJ_ENDOUTER，由于变量mj_MatchedInner为false，这里重置mj_MatchedInner为true后，调用方法MJFillInner，将inner tuple——12关联的outer tuple填充为null。这里没有状态切换。该轮循环结束。

  • 关联结果 null 12
outer  inner
               5       5  
               5       5  
               6       8  - marked tuple  - offset tuple
               6       8  
               7      12  - inner tuple   
               8      14   
outer tuple - eof    eof

  • 11 该轮从上一轮结束的状态EXEC_MJ_ENDOUTER出发。由于mj_MatchedInner为true，首先调用方法ExecMarkPos标记offset为current，然后内表游标下移，同时将变量变量mj_MatchedInner设置为false，状态不变。

    继续来到状态，这里与继续调用方法MJFillInner，将inner tuple——14关联的outer tuple填充为null。这里没有状态切换。该轮循环结束。

  • 关联结果 null 14
outer  inner
               5       5  
               5       5  
               6       8  - marked tuple 
               6       8  
               7      12  - offset tuple 
               8      14  - inner tuple    
outer tuple - eof    eof

  • 12 仍然是状态EXEC_MJ_ENDOUTER，这里同样首先调用方法ExecMarkPos标记offset为current，然后内表游标下移，同时将变量变量mj_MatchedInner设置为false。由于此时内表的扫描结束，返回为空，同时该轮循环结束。

  • 关联结果 null
outer  inner
               5       5  
               5       5  
               6       8  - marked tuple 
               6       8  
               7      12  
               8      14  - offset tuple   
outer tuple - eof    eof  - inner tuple
  • 至此，归并排序的举例就结束了。我推荐大家在阅读本文的时候最好参照pg源码——nodeMergejoin.c文件中的ExecMergeJoin方法，有事半功倍之效。

总结

  • 状态EXEC_MJ_NEXTINNER，该状态的前置状态只有EXEC_MJ_JOINTUPLES。在该状态下内表游标下移获取数据，因此，outer tuple与inner tuple比较只有两种情况
    • 1 outer tuple = inner tuple
    • 2 outer tuple < inner tuple
  • 状态EXEC_MJ_TESTOUTER，该状态的前置状态只有EXEC_MJ_NEXTINNER与EXEC_MJ_NEXTOUTER。而在该状态下外表游标下移获取数据，因此，outer tuple与inner tuple比较只有两种情况
    • 1 outer tuple = inner tuple
    • 2 outer tuple > inner tuple

  • 状态EXEC_MJ_NEXTOUTER与EXEC_MJ_SKIPOUTER_ADVANCE的区别：

    前者会切换到状态EXEC_MJ_TESTOUTER来比较。

    而后者会切换到EXEC_MJ_SKIP_TEST来比较。

  • 状态EXEC_MJ_SKIP_TEST与EXEC_MJ_TESTOUTER区别：

    前者outer tuple与inner tuple比较有三种可能的结果。这里比较的是current outer tuple与current inner tuple。

    而后者只有两种可能的情况。而这里比较的是current outer tuple与makred inner tuple。

    如果current outer tuple > marked inner tuple，那么inner tuple从current tuple与outer tuple切换到状态EXEC_MJ_SKIP_TEST进行比较。

  • 恢复标记

    在状态EXEC_MJ_TESTOUTER中遇到outer tuple == marked tuple时，这里会置inner tuple为offset tuple，并且将inner tuple置为之前保存的offset tuple。

图示

euqI3uf.png!web


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK