PG归并排序算法详解

栏目: IT技术 · 发布时间: 4年前

前言

  • 归并 排序 算法是连接算法中比较复杂的算法,相比嵌套循环与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。

图示

PG归并 <a href='https://www.codercto.com/topics/21904.html'>排序算法</a> 详解


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

创投42章经

创投42章经

曲凯 / 中信出版集团 / 2018-10-20 / 58.00

《创投42章经》是拥有百万粉丝的微信公众号“42章经”的精选文章合集,全书共分为心法、内功、招式和江湖传奇四部分。 在心法部分,读者可以学到一些创业与投资的底层思维方式;在内功部分,读者可以了解到,投资人看待一家公司经营状况的标准;在招式部分,读者可以看到作者作为一名资深投资人和睿智的观察者,对过去几年主要的公司、模式以及风口的判断;最后的江湖传奇部分,作者通过一些故事,帮助读者更好地理解当......一起来看看 《创投42章经》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器