深圳网站建设微赢天下,网站模板能自己做吗,手机网站设计图标,无锡网站制作企业Sorting 排序如果可在内存里面排#xff0c;用经典的排序算法就ok#xff0c;比如快排 问题在于#xff0c;数据表中的的数据是很多的#xff0c;没法一下都放到内存里面进行排序 所以就需要用到#xff0c;外排#xff0c;多路并归排序 看下最简单的#xff0c;2路并归…Sorting 排序如果可在内存里面排用经典的排序算法就ok比如快排 问题在于数据表中的的数据是很多的没法一下都放到内存里面进行排序 所以就需要用到外排多路并归排序 看下最简单的2路并归排序 设文件分为N个pagememory中一次最多可以放入B个pages 所以在sort过程一次性可以载入B个page在内存中page内排序写回disk称为一轮run那么如果一共N个page需要N/B1个run 在merge过程如果双路并归排序只需要用到3个page的buffer多了也没用 Merge过程的cost 每个pass都需要读写一遍所有的数据cost为2N2 way所以一共有1 logN个pass 多路并归排序的通用公式如下 其他都比较容易理解为什么way数是B-1 因为memory一共B个buffer需要留一个output剩下的用于merge所以最多是B-1路并归排序 如果我们有B index的情况下 分两种情况要排序的字段有Clustered B索引那么直接从左到右遍历叶子节点就好 排序的字段不是Clustered B索引比如是secondary 索引 那么从索引里面只能获取到排好序的id然后要通过id去Clustered B索引中取真正的value效率也很低每个record都需要一次io Aggregation Aggregation有两种思路 一种先排序sorting然后再按顺序做aggregate 这个方法明显的问题就是比较费有些场景不需要sort比如group bydistinct 所以第二种思路是Hashing 在memory里面临时维护一个hash table去重或聚合都在hash table上完成 问题就是如果hash table太大内存放不下怎么办 所以解法的思路放不下就切开切成能放下的一个个partition并且要保证一个key的数据都在一个partition里面这样只要保证内存能够放下一个partition就可以aggregate不需要去读其他的partition 第一次partition划分成几个partition如果内存B个buffer划分成B-1个partition如果划分完了某个partition还是放不下怎么办那就继续划分直到所有partition都可以放到内存中 这里有几个问题 首先一个partition应该不止一个key如果只有一个第二步里面的h2感觉没用第二假设数据是均匀分布的不会出现太大的倾斜不会有partition overflow Join 为什么需要join 因为不同的数据存在不同的表里面所以要查询就需要关联那么为什么不能放在一张表里面关系表的设计有范式的要求避免大量的数据重复 Join Operator Output 直接输出data这样好处是后续operator不用回到数据表再去读数据这个方法比较实用于TP需求结果数据较少的情况 仅仅输出ids适合AP需求join结果集非常大的情况 尤其适用于列存因为这样你只需要读出join id列也不浪费 然后在最后要显示的时候才去把需要的数据从表里面查出来这叫做late materialization 这样的好处过程中可能还有其他的join过滤等所以开始读可能浪费到最后真正需要的时候再读 Join Cost 如何去评价join算法的好坏就是要评价cost 传统的数据库的瓶颈在disk IO所以这里就以磁盘IO的次数来评价join算法的好坏这个和为何使用Btree作为index的理由一样所以就是读写page的个数 Join算法 Nested Loop Join Simple直觉的方式就是遍历两个表这里的概念分为Outer和Inner表从Cost上看最要取决于Outer的tuples数所以如果把较小的表N作为Outer会效率高些 比较明显的问题是没有必要读那么多遍的inner表 如果我能把outer表直接放在内存中那么只需要读一遍inner就可以了如果不行就用如下的block的方式 如果内存大小是B那么要用两块来放inner和output所以可以用B-2来放outer Costouter表M需要读一次inner表需要读M/(B-2)次 这里也写了如果memory比较大那么cost就是MN只需要读一遍inner 如果有index是否可以加快join的效率应该可以但是效果要看是什么index如果hashCO(1)BtreeCO(logn) Sort-Merge Join 这个方法要求两个表先排序然后做一轮幷归就可以完成join所以这个方法适用于两个表本身就有序或是在join key上有index这个方法附带的好处是结果有序 这个算法的Cost主要是两个表排序的cost幷归的cost就是MN Hash Join HashJoin分为两步两步的hash函数用同一个 Build对较小的表建临时的hash table Probe读取另一张表进行join 这有个类似的问题Hash Table里面存什么 当然可以直接存join的结果也可以存tuple id这个选择就取决于场景 自然有个疑问如果内存放不下这个hash table怎么办 既然放不下就需要分而治之两个表用相同的hash函数hash到相同数目的buckets里面去 在内存中一次只读一组bucket来进行join是不是很ok 那么如果hash成bucket的时候不均衡一个bucket也overflow怎么办答案是继续分 Grace Hash Join的cost 所有join算法的Cost对比 转载于:https://www.cnblogs.com/fxjwind/p/10906161.html
