CMU-15-445笔记(十)

Processing Models

DBMS的processing modesl定义了系统如何取执行一个query plan

Interator Model

又叫做volcano(火山)模型或者pipeline模型，是最常用的model，每个query plan操作都会实现一个Next function

• 对于每一个调用，操作符就会返回一个tuple或者如果不没有tuple的话，返回null
• 操作符实现了一个循环来调用它下一个子节点来遍历所有的tuples然后处理它们。相当是一个链式的调用来获取要处理的tuple

以hash join为例子

首先顶部调用child.next()来获取join好的tuple，调用执行到了(2)，(2)会遍历left的tuple，也就是(3)所返回的tuple，进行hash构建，然后同样遍历right的tuple并判断是否要join，执行了(4)(5)，返回tuple给(2)，最后(2)的tuple返回给(1)
需要注意的是所有的next函数都是一次一次执行，不是将所有的结果全部返回。

Materialization Model

每个operator会一次性的处理它的input，然后一次性的发送它的output。

在oltp中这个model很实用，因为queries只会访问少量大的tuple，但是olap就不适用，它会需要大量的中间结果.

Vectorization Model

next返回的不是一个tuple而是一批tuples

Plan Processing Direction

上面的方式都是top to bottom的方式来调用执行query plan的，其实还有bottom to top（这种方法需要所有的数据都在内存中）

Access Methods

访问数据有两种方式，一个是根据索引来访问，这个的优先级最高，但是不一定有，备胎选项就是顺序扫描table来获取数据

Sequential Scan

DBMS会保存一个内部的cursor来追踪上一个page的位置，方便下一次被next调用后找到要返回的page

Optimization

• Perferching
• Buffer Pool Bypass
• Parallelization
• Zone Maps
  • 提前计算page中的聚合的attribute value，DBMS检查Zone Map来判断是否要访问这个page
  • 
  • 比如以上这个，根据Zone Map中的Max就可以得知不需要去访问这个page
• Late Materialization
  • 在列式存储中，获取一个tuple的数据是需要多次读取操作的，所以可以推迟读取操作
  • 
  • DBMS将查询操延迟，比如a>100的操作，结果向操作树传递结果的时候，只传递tuple的offset，同理join操作，等真正需要这些数据的时候，再根据offset来获取数据。
• Heap Clustering
  • 直接用index来扫描，因为tuple根据index的书顺序来存储，所以是要给顺序IO
    

Index Scan

DBMS会挑选最合适的index进行查找，具体会在下一节中讲解

Multi-Index Scan

如果多个index效果都差不多，可以使用多个索引共同查找

• 获取每个匹配的index扫描结果的Record IDs的集合
• 然后将这些集合根据query的条件来combine在一起
• 遍历这些records，然后根据query条件来获取最终结果
  

Index Scan Page Sorting

如果直接用非聚簇索引叶子节点的顺序来访问每个page的话，是低效的，因为它们对应的tuple可能不是顺序的，所以如果结果并不需要一定是和叶子节点顺序是一样的，DBMS就可以先扫一遍叶子节点，获取全部的page id后，排序page id，然后再进行访问，这样就可以是顺序IO

By the way，聚簇索引维护tuple顺序的方式很粗暴，就是重排一遍。

Expression Evaluation

DBMS会将where子句表示为一个表达式树
节点是不同的表达式类型

• 比较(= < > ! =)
• AND，OR
• 计算符
• 常量
• Tuple的属性
  
  以这个为例，每次判断都会从根节点出发，深度遍历，然后最后回到根节点来判断是否为true
  
  这种方式是比较慢的，因为每次判断都需要遍历整个表达式树，对于一些高级数据库来说，它们会直接使用JIT来编译判断条件，从而更好的执行。