CMU 15445 lab3 QUERY EXECUTION

总览

这个lab要实现executors,executor负责query plan(就是operator形成的树)上的operator并执行它们，对于每个executor，需要实现：

对于这个lab，没有SQL，执行的查询计划都是写好的算子树，并且用的是火山模型，每个算子的执行器(executor)必须实现Next函数，Next函数的执行粒度是一个tuple，也就是每次执行要么返回一个tuple，要么返回一个空指针来表示当前没有tuple了。那么每个算子executor需要实现一个循环去调用子算子的Next函数

Task#1 SYSTEM CATALOG

catalog存的信息是用来显示一个database有什么table以及table被存在哪里，其中还存有了table的index

table怎么存的？

复习一下数据库的存储模型，每个页存n个tuple，对于一个table，可以根据key，建立B+树index，去查询tuple

可以看到在lab中的实现中，leaf node节点的value就是page_id和slot_num,

那么页的布局就是slotted page

catalog

catalog需要实现在数据库中添加tables和通过name或则内部标识符table_oid_t取tables，主要是实现：

index的添加

Task#2 EXECUTORS

需要实现sequential scans, index scans, inserts, updates, deletes, nested loop joins, nested index joins, limits with offset and aggregations等算子的executor，每个executor都有两个方法——Init用来获取需要scan的table和Next用来迭代读取table中的tuple，当前算子的Next方法就是执行循环去执行子算子的Next，
调用子算子是有惯例的顺序。这里的ExecutionEngine采取了工厂模式。
ExecutionEngine中调用ExcutionFactory类去将一个AbstractPlanNode转化为对应的executor，ExecutorContext保存了一个query的查询状态，每次执行一个PlanNode，需要先Init，在execute，

executor的抽象的执行流程

这里拿seq_scan_executor举例，

• 该类继承于AbstractExecutor
• AbstractExecutor只有一个成员函数ExecutorContext *exec_ctx_，AbstractExecutor还两个纯虚函数，Init和Next，这是每个executor都需要实现的
• ExecutorContext中保存了一个transaction执行一个query时的context，
• 一个executor还需要planNode，SeqScanPlanNode继承于AbstractPlanNode，AbstractPlanNode两个成员变量分别用于限定输出的schema与其子planNode
• SeqScanPlanNode有自己的成员变量，分别用于指定其需要扫描的表与扫描表的tuple需要满足的谓词
• 谓词是AbstractExpression，决定了返回的结果的schema

修改execution_engine.h中的异常处理？

sequential scan

• Iterator的每次迭代会获取一个没有被删除的tuple不论是在当前Pgae，还找到新的一个Page的第一个没被删除的tuple
• Next函数如果得到了一个tuple，那么返回true，否则false
• 由于根据predicate计算一个tuple是否可行的Evaluate函数返回的是一个Value类型所以需要GetAs把Value转换为bool类型
• 创建一个column需要使用AbstractExpression类的子类ColumnValueExpression，ColumnValueExpression的Evaluate方法是主要是tuple->GetValue(schema, col_idx_);，Evaluate的第二个schema参数使用来获取对应列的类型的而GetValue获取是分别获取类型与列中的真实数据
  对于varchar类型的数据，由于不定长，所以在tuple的对应column中记录的是一个四字节的地址，而对于inline的数据(inline应该就是指不是varchar的数据)，就放在tuple的对应位置可以猜测存储的varchar数据的头4个字节是varcahr数据的大小
• 传指针返回值

Index Scans

• 只考虑Keysize为8的Iterator
• protected是指基类与继承类都可以直接访问
• 这个predicate检查所有的列比较合理？

INSERT

• 需要做两件事，一是把tuple插入到table中，二是更新tale的所有索引
• 插入的tuple也分为两种，一种是原生的tuple，列的值放在InsertPlanNode之中，另一种是从其他table中复制一个tuple插入
• 用InsertPlanNode中的这个方法判断是否是原生插入
• KeyFromTuple可以从一个table的tuple构造一个index entry的key tuple
• 一个index的keyAttrs是一个数组，表明了table的tuple中的列号
• 这里涉及了编译器的一种优化RVO

UPDATE

• update的子planNode，update的planNode用给定的谓词去遍历需要更新的tuple

DELETE

• Delete需要删除tuple并在index中删除index entry，和Update一样，Delete一定会有一个child executor
• 为什么不删除，而是标记，用了实现MVCC吗？

NESTED LOOP JOIN

此处的join采取一种simple join的join方式

• join算子，需要分别执行两个子算子
• left算子得到的每一个tuple需要与right算子的每一个tuple都判断谓词，都如果满足就输出一个结果tuple，由于Next函数是一个协程，那么需要保存当前left算子得到的当前tuple，还需要保持一个状态，表明当前join的left算子是否遍历完了所有的tuple
• 一个NestedLoopJoinExecutor尤其对应的OutputSchema，而OutputSchema中是一个Column数组，每个Cloumn对象有一个AbstractExpression成员变量那么根据AbstractExpression的EvaluateJoin中的tuple_idx_成员变量可以知道该column来子join的左table还是右table
• 不过RID有啥用？

INDEX NESTED LOOP JOIN

• 要求outer table的每一个tuple去与inner的每一个tuple做谓词判断，不用谓词判断，获取plan中的指定，通过plan设定的索引的key_schema

• 点查询为什么要传一个vector？

AGGREGATION

• 在GROUP BY子句后面包含了一个HAVING子句。HAVING类似于WHERE（唯一的差别是WHERE过滤行，HAVING过滤组）HAVING支持所有WHERE操作符。
• 这个函数用来实现聚合，当一个聚合函数还没被使用时，将其插入map中并作出合理的初始化这个函数用来做实际聚合操作
• plan指定了该算子会做哪些聚合
• 一个plan的有指定的OutPutSchema，而OutPutSchema有一个Cloumn数组，其中每个Column对象指定了用来创建该Column的AbstractExpression，那么每次获取一个输出tuple中每一列就是调用OutPutSchema的每一个col的Expression聚类需要把key与val都放到output的tuple中

LIMIT

问题

• 这个三个参数是干嘛用的？key_schema用来表示key的列的样子？
• 一个表可以有很多个index
• 一个Table就有一个TableHeap，用来存储Table的页且采取doubly-linked list的存储页的方式
• 这里返回的是一个Iterator它重载了->
• 创建索引的时候需要把一个表中的所有的tuple的对于index放到索引数据解构中
• 一个TablePage删除tuple的时候，不会真的删除，用来实现MVCC吗？
• 用make_unique会出错？
• 测试的时候，找到一个lab2的错误，在CoalesceOrRedistribute中Coalesce的时候忘记给sibling_node解锁了