11. Query Execution

Processing Models

Iterator Model

迭代器模型，也叫做火山或者流水线模型

大量函数调用，指令缓存会很快失效

Materialization Model

生成所有数据然后返回给上层

对于 OLTP 表现不错，因为没有很大的表需要传递

Vectorized/Batch MOdel

在物化模型和火山模型间是一个良好的平衡
可以使用 SIMD 指令加速

Plan Processing Direction

自上而下对于上面的模型来说更加自然

Access Methods

Sequential Scan

Optimization

  • Prefetching
  • Buffer Pool Bypass
  • Parallelization
  • Heap Clustering
    • 只是取回 RID，最后才取回真正的数据
  • Late Materialization
  • Data Skipping
Data Sipping

ZONE MAPS

one zone map in one zone，zone 的大小取决于我们的实现，一般为页
当 zone map 存储在区域之外，与索引的工作流程很像

Index Scan

Multi-Index Scan

Modification Queries

Halloween problem: 跟踪已经修改过的 record id，一般在操作符内部使用数据结构来跟踪，避免下一次再次修改
materailization 不会有这样的问题

Expression Evaluation

JIT compilation 可以高效地评估表达式；表达式会被编译成常量或函数

Scheduler

quickstep 的 scheduler 原型；工作线程池是无状态的、弹性可伸缩的，可以对查询进行优先级的执行


Process Models

  1. Process per DBMS Worker
  2. Thread per DBMS Worker
  3. Embedded DBMS

Execution Parallelism

Inter-query Parallelism

Intra-query Parallelism

Intra-Operator(Horizontal)

通过硬件并行性动态确定，现在一般通过调度器来实现


Inter-Operator(Vertical)

投影运算符在下层运算符还没有执行完成时，就开始工作

Bushy

I/O Parallelism

Multi-Disk Parallelism

Database Partitioning