EthanWeee 的个人日志
0%

发表于 更新于 分类于

查询执行

在数据库查询执行中，查询管道（pipelining）和物化（materialization）是两种核心的执行模型。查询管道通过让元组在操作符之间持续流动，实现了流水线式的处理，从而减少了中间结果的写入和读取开销；而物化模型则在每个操作之后将中间结果保存为临时表，再由下一个操作读取，便于管理和重用，但会引入额外的 I/O 和存储成本。

在数据库查询执行中，要在既定的查询计划不变的前提下进一步提升性能，常见的三大技术杠杆正好对应经典的 CPU 性能方程：

CPU Time=Instruction Count×Cycles Per Instruction×Clock Cycle Time \text{CPU Time} = \text{Instruction Count} \times \text{Cycles Per Instruction} \times \text{Clock Cycle Time}

。

基于这一方程，我们可以通过以下三种途径分别作用于各项，从而整体降低查询的执行时间。

  1. 减少指令数：通过让同样的计算工作消耗更少的指令，直接降低方程中的 Instruction Count。

    解决方案：

    • 算法与逻辑优化：在查询执行层面，合并相邻的过滤或算子，避免产生冗余的中间操作，如将多重过滤合并成单次扫描中的复合条件。
    • 编译器与JIT优化：利用现代数据库的即时编译（JIT）技术，将高频 SQL 模板编译成高效机器码，去除不必要的抽象层次。
    • 简化控制流：减少分支与函数调用，利用内联（inlining）与分支预测友好的代码组织，降低分支错判带来的指令重执行。

  2. 降低每条指令的平均周期数：在保证指令数大致不变的情况下，通过加速每条指令的执行来降低平均周期数，使得每个周期内能执行更多的指令。

    解决方案：

    • 向量化执行：一次处理多个数据元素（SIMD），使单条指令能够并行作用于多份数据，显著减少每元素的平均周期开销。
    • 缓存友好布局：优化内存访问模式、减少缓存未命中、利用预取（prefetch）技术，降低内存访问延迟对 CPI 的影响。
    • 流水线与乱序执行：让 CPU 同时处理多条指令的不同阶段，掩盖指令间的依赖与等待，提高指令吞吐能力。

  3. 并行化执行：利用多线程／多进程将查询拆分为若干可并行处理的子任务，以共享整个系统的计算资源。

    解决方案：

    • 并行扫描 (Parallel Scan)：将表或分区划分为多个数据块，每个 worker 进程或线程独立扫描其负责的数据块。
    • 并行聚合 (Parallel Aggregation)：类似 MapReduce，在每个节点本地先做部分聚合，再在汇总阶段合并结果，降低网络与锁竞争开销。
    • 动态分区与调度：根据实时负载与数据分布，自动调整任务划分与调度策略，避免因数据倾斜或节点瓶颈造成性能倒挂。

在现代关系型数据库中，**查询执行（Query Execution）**依赖于三个核心概念：查询计划、操作符实例和任务/流水线。查询计划被表示成一个操作符的有向无环图（DAG），它定义了不同运算节点及数据流依赖；操作符实例则是将某一操作符应用到数据的具体调用；任务（也称流水线）由一个或多个操作符实例顺序组成，在同一执行上下文中连续运行，从而实现元组的流式处理和高效并行执行。

假设我们要执行如下 SQL 命令：

1
2
3
4
SELECT A.id, B.val
FROM A JOIN B
ON A.id = B.id
WHERE A.val < 88 AND B.val > 214;

此时的查询执行的示意图如下：

img

但是在以上的查询执行中，会出现两种普遍发生的性能瓶颈：

  1. 指令依赖：当一条指令的操作数依赖于前一条指令的输出时，就会出现数据依赖，导致后续指令必须等待前一指令完成写回，才能安全地执行。这会导致流水线停顿（Pipeline Stall），也就是依赖链未解除之前，流水线必须插入空周期，暂停取指与执行，直到数据可用。每出现一次停顿，均减少了可用的执行周期，尤其在长依赖链或深度流水线中，性能损失更为显著。

    解决方案：

    1. 前递（Forwarding/Bypassing）：处理器在执行阶段即可将尚未写回的结果转发给下游指令，减少等待时间。
    2. 指令重新排序（Out-of-Order Execution）：乱序发射允许非依赖指令先行执行，填补停顿周期，提高资源利用率。
    3. 软件优化：编译器或 JIT 在生成代码时，通过指令调度将依赖指令错开，或插入无关指令填充空档，降低数据冒险带来的停顿。

  2. 分支预测：处理器在遇到分支指令时，会猜测分支是否成立，并预取／预执行分支路径上的指令，以保持流水线连续。这会导致流水线冲刷（Pipeline Flush）：若预测错误，必须将已加载但未提交的指令全部作废，并重新从正确目标地址逐级取指，造成数十至上百个周期的空闲；以及分支惩罚随流水线深度增加而增大：深度更高的流水线需要冲刷更多级的指令，带来更高的性能损失。

    缓解方案：

    1. 动态分支预测：利用分支历史表（Branch History Table）等硬件结构根据过去执行情况进行预测，大幅提高准确率。
    2. 无分支代码：使用位运算和逻辑运算消除显式的 if 判断语句，从而让 CPU 不依赖分支预测。
    3. 索引下推：将分支条件判断尽量前移到索引扫描阶段，减少进入后续流水线的无效数据。
    4. 向量化执行：批量处理多条记录，将过滤逻辑应用于整个向量数组，在单条循环中执行多次条件判断并记录掩码，减少分支次数。

    [!NOTE]

    数据库中的分支失误：过滤操作

    在顺序扫描过程中，每访问一行记录，都要执行对该行是否满足过滤条件的判断（if 语句），这构成了 DBMS 中最频繁的分支指令序列。由于行数据的分布通常不可预测，过滤条件的真/假结果几乎是随机的，硬件分支预测器难以积累稳定的历史。

    对于这种情况，我们可以采用无分支代码来解决。假设我们要执行如下命令：

    1
    SELECT * FROM user WHERE age > $(low) AND age < $(high);

    那么这个 SQL 命令对应的有分支的代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    i = 0;
    for (t in table) {
      key = t.key;
      if ((key > low) && (key < high)) {
        copy(t, output[i]);
        i = i + 1;
      }
    }

    在以上代码中，每次 if 检查都生成一条或多条分支，过滤条件结果依赖于数据值分布，通常呈随机模式，硬件分支预测器难以积累有效历史，同时预测错误时需刷新流水线，放弃已取但未执行完的指令，造成 10–20 个周期的空洞。

    因此我们可以将其改成无分支的代码：

    1
    2
    3
    4
    5
    6
    7
    i = 0;
    for (t in table) {
      copy(t, output[i]);
      key = t.key;
      delta = (key > low ? 1 : 0) & (key < high ? 1 : 0);
      i = i + delta;
    }

    这段代码使用三目运算符和按位与（&）生成布尔掩码（0 或 1），避免 if 分支，消除了流水线刷新风险，可保持稳定的指令流，而且无分支的循环更符合 SIMD 自动向量化特性，编译器和 JIT 能将单条循环转换为批量处理指令，并利用 AVX/SSE 等向量指令集。

处理模型

在关系型数据库中，**处理模型（Processing Model）**决定了执行器如何遍历并执行优化器生成的查询计划树。不同处理模型在函数调用开销、中间结果管理、内存与 I/O 使用等方面各有取舍，因而对 OLTP（短事务、小结果集）与 OLAP（大批量分析查询）场景会产生截然不同的性能影响。

迭代器模型（Iterator / Volcano Model）

每个查询计划算子实现一个 next() 方法：调用时返回一个元组或标记结束（null），而且 next() 内部通常是一个循环：对子算子连续调用 next() 以获取下一个元组并进行处理，实现拉取式（pull-based）流水线。

在该模型中，JOIN、ORDER BY 和子查询等算子却会一直被阻塞直到子算子发送完了所有的元祖。

下图展示了迭代器模型的执行流程，其中绿色箭头大小控制流，红色箭头代表数据流，之后的图都是如此：

img

上图中，在系统层面，这两个流水线各自由不同的执行线程或调度实体运行，可以在硬件资源（CPU 核、线程）许可下同时活跃。但哈希连接的建表阶段是一个管道断裂点（pipeline breaker）：建表阶段只依赖 R 表，与 Pipeline #2 无关，因此当建表线程在后台扫描 R 时，Pipeline #2 可以同时并发进行 S 表的过滤。一旦建表完成，Pipeline #2 的探测阶段才会真正开始消费 Filter 的输出；如果 Filter 还没产出下一个符合条件的行，探测就会等待。反之，如果过滤很快，探测也会快速拉取并处理。

[!NOTE]

拉取式流水线中，调用者（上层算子或执行引擎）通过自顶向下的递归调用不断拉取数据，直到叶子算子从底层存储读取到元组并逐层返回。这种设计将控制流和数据流分离，上层算子负责驱动执行进程，下层算子被动提供数据，适合行级的管道处理。

优点：

  1. 内存占用小：元组生成后可立即沿计划树上下游传递，无需完整物化中间结果。
  2. 早期返回：可以在部分数据处理完后就立即返回这部分的结果。

缺点：

  1. 函数调用开销：深度计划树和高频 next() 调用在高并行度或大结果集场景下带来显著开销。
  2. 难以并行化：对多核或批处理的支持不够友好。

因此，该模型在 OLTP 场景中表现优异。

物化模型（Materialization Model）

Materialization 模型是数据库管理系统中常见的查询执行模型之一，其中每个操作符一次性处理所有输入并一次性输出所有结果，称为物化操作 。该模型适用于 OLTP 场景，因其函数调用较少、协调开销低，能够快速返回少量元组；但对于中间结果集庞大的 OLAP 查询，则可能因临时结果需要写入磁盘而导致性能下降 。DBMS 可通过下推诸如 LIMIT 的执行提示（hints）来避免扫描过多元组，并支持行式存储或列式存储的物化输出方式。

img

向量化模型（Vectorization Model）

Vectorization 模型是一种批量处理的查询执行策略，其中每个操作符在内部循环中一次性读取并处理一批（batch）的元组，然后一次性向外输出该批结果。这种方式通过利用现代 CPU 的 SIMD 指令加速批量数据处理，显著降低函数调用次数并提升缓存命中率，因而特别适合 OLAP 查询；但对于需要低延迟、逐一元组处理的 OLTP 工作负载，则并不理想。该模型的批大小可根据硬件能力（如 AVX 寄存器宽度）和查询属性动态调整，以实现最优性能。

每个查询操作符实现一个 next() 函数，但不是返回单个元组，而是返回一批元组。操作符的内部循环一次性在向量或批量数据上执行相同的操作，而非逐个元组调用。

img

需要强调的是，以上的三种处理模型都是属于 pull-based 的。

Pull 模型从根节点发起，通过连续调用 next() 向下拉取数据，适合传统行式、阻塞操作较多的场景；Push 模型则从叶子节点开始，将处理结果推送给父节点，并可在单一循环内融合多个算子，减少中间结果存储，更适合 OLAP 工作负载。

Push-based 模型的示意图如下：

img

Pull-based 和 Push-based 模型的对比：

特性／模型 Pull（Top-to-Bottom） Push（Bottom-to-Top）
输出控制 易于对 LIMIT、TOP-N 等操作进行控制，父算子可随时停止拉取 不易实现 LIMIT，消费者难以及时通知生产者停止推送
管道阻塞支持 原生支持排序、聚合等阻塞算子 复杂算子需额外物化或流水线断点才能正确执行
函数调用开销 每条元组多次调用 next()，虚拟函数和分支跳转较多 同一循环内推送，函数和分支开销更低
缓存 & SIMD 利用 难以批量处理，SIMD 和缓存局部性利用有限 算子融合后易于批量处理，充分利用缓存和 SIMD
实现复杂度 基于 Volcano 模型，逻辑清晰、易于实现与维护 需算子融合、回调机制和调度框架，开发调试成本高
适用场景 OLTP、交互式小批量查询，带 LIMIT 的场景 OLAP、大规模扫描与聚合，列式存储与 MPP 系统

发表于 更新于 分类于

查询优化是构建高性能数据库管理系统时最困难的部分之一，它需要在大量等价的查询执行方案中找到资源消耗最小的那个方案。其核心目标是以某种成本函数衡量每个候选计划，并选择估算成本最低的计划。

查询优化的首要目标就是在可行的计划中选出“最低成本”的一个，通常采用成本模型对 I/O、CPU、网络等资源进行加权求和，得出一个标量成本值，不同系统也可能纳入缓冲区命中率、并行度等额外因素。

成本评估

在关系型数据库的**代价优化器（Cost-Based Optimizer）**中，会将一个查询计划的总代价定义为其所有算子（Operator）估算代价的累加：

CostofPlan=∑(CostofeachPlanOperator) Cost\:of\:Plan = \sum (Cost\:of\:each\:Plan\:Operator)

而每个算子的估算代价又通常与该算子所处理的输入规模成正比：

Cost(Operator)∝SizeofOperatorInput Cost(Operator) \propto Size\:of\:Operator\:Input

以上两条公式构成了代价估算的基础：先通过输入规模得出算子代价，然后累加得到整个执行计划的成本。接下来，需要详细说明如何确定算子输入规模，以及如何基于选取性（Selectivity）估算非基表算子的输出规模。

对于基表扫描（Table Scan）或索引扫描（Index Scan），输入规模通常等于表或索引在磁盘上的物理存储量（页数或行数）。

[!NOTE]

对于此类扫描操作，我们可以在有索引的情况下，可将过滤条件下推至索引层，只读取满足谓词的行或页，以减少输入规模和 I/O 操作，也就是进行索引下推。

对于投影（Project）、选择（Filter）等算子，优化器首先根据输入规模和选取性估算输出规模；连接（Join）算子则需基于两侧子计划的输出规模与连接选取性共同计算其输出规模，也就是：

OutputSize=Selectivity×(∣Left∣×∣Right∣) Output\:Size = Selectivity \times (|Left| \times |Right|)

选取性（Selectivity）是算子发出数据量与接收数据量之比，取值范围 0–1，表示谓词或连接条件对数据的过滤强度。

OutputSize=Selectivity×InputSize Output\:Size = Selectivity \times Input\:Size

假设我们针对有 100 条记录的部门表 dept，10000 条记录的职员表 emp，30000 条记录的儿童表 kids，执行如下 SQL 语句：

1
2
3
4
5
SELECT * 
FROM emp, dept, kids
WHERE sal > 10000 
  AND emp.dno = dept.dno 
  AND emp.eid = kids.eid;

其中，每 100 条记录是一个页面，10 KB 是一个页面的大小，内存大小是 10 个页面。

对于每种执行计划，我们可以进行如下步骤：

第一步，评估表（关系）的大小：

  • dept 只有 100 条记录，占用 1 页（10 KB/页）；
  • emp 有 10000 条记录，占用 100 页（10 KB/页）；
  • kids 有 30000 条记录，占用 300 页（10 KB/页）。

第二步，评估选择性：

  • WHERE sal > 10k 的选择性为 0.1；
  • dept 和 emp 的 JOIN 操作的选择性为 0.01，产生结果集 A；
  • A 和 kids 的 JOIN 操作的选择性为 0.0001，产生结果 B。

第三步，计算中间结果的大小，如下执行计划树所示，其中冒号右边的数据为此次操作得到的结果集的大小：

img

需要注意的是，整棵树的阅读顺序推荐从叶子到根。

第四步，评估各个执行计划的成本并选出最低的。

以上只是一个简单的流程，下面基于 Selinger 等人提出的 System R 成本优化器框架给出每个步骤的详细解释，该框架迄今仍被主流关系型数据库（如 DB2、PostgreSQL、MySQL 等）沿用。

第一步，评估关系的大小，其中的统计量如下：

  • NCARD(T)：关系 T 的基数，即元组总数；
  • TCARD(T)：关系 T 所占用的数据页数；
  • ICARD(I)：索引 I 中不同键值的数量；
  • NINDX(I)：索引 I 在磁盘上占用的页数。

[!NOTE]

现代数据库在 System R 的统计量基础上引入多种增强策略：

  1. 直方图（Histograms）

    • 等宽直方图（Equi-width）：将值域划分为固定宽度的 k 个区间，区间内数据不均匀时易失真 。
    • 等深直方图（Equi-depth）：保证每个桶内的元组数近似相同，可更准确估算范围谓词 。

  2. 最常见值列表（Frequency List）：维护出现频率最高的 m 个键值及其频率分布，对高频值谓词（如 col IN (…)）提供精确估算。

  3. 聚簇因子（Clustering Factor）：描述索引键值在数据块中的物理聚集度，值越低表示更紧密的簇集，有助于优化随机 vs 顺序 I/O 的成本估算。

  4. 分区增量统计：对于分区表，会为每个分区单独收集统计信息，并维护全局统计，通过分区修剪（Partition Pruning）显著降低查询开销。

  5. 分层采样：在全表采样成本过高时，数据库可基于分区或分层样本抽样（如 1% 分区样本），动态更新统计，同时避免全表扫描统计带来的停机与高 I/O 负载。

第二步，评估选择性：

我们这里先定义 F 或者 F(pred) = 谓词的选择性 = 没有被过滤掉的记录的占比。

那么，对于等值谓词 col == val：若有索引，则假设均匀分布，选取性

F=1/ICARD F = 1 / ICARD

；否则粗略取 1/10。

对于范围谓词 col > val 或类似开区间比较：若有索引，则线性插值计算

F=(high_key−val)/(high_key−low_key) F = (high\_key\:-\:val) / (high\_key\:-\:low\_key)

；否则取 1/3。

对于列间相等谓词 col1 = col2：

若两列均有索引，取两索引基数（ICARD）较大值的倒数：

F=1max(ICARD(col1),ICARD(col2)) F = \frac{1}{\max\bigl(\text{ICARD}(col_1),\,\text{ICARD}(col_2)\bigr)}

；

若只有单列有索引，则

F=1/ICARD F = 1/ICARD

；否则取 1/10。

此外，在查询中常有多重谓词组合，Selinger 优化器使用以下规则在逻辑优化和成本估算阶段快速合成最终选取性 F：

逻辑与（AND）：

Fand=F(p1)×F(p2) F_{\text{and}} = F(p_1)\,\times\,F(p_2)

逻辑或（OR）：

For=1−Fand=F(p1)+F(p2)−F(p1)F(p2) F_{\text{or}} = 1 - F_{\text{and}} = F(p_1) + F(p_2) - F(p_1)\,F(p_2)

逻辑非（NOT）：

Fnot=1−F(p) F_{\text{not}} = 1 - F(p)

思考：

为什么等值谓词在没有索引的时候要取 1/10？

在缺乏精确统计时，优化器宁可假设谓词对数据的过滤效果较弱（即选取性估算偏大），也不轻易假设它过滤得非常彻底。

如果低估谓词效果（认为它能过滤掉更多行），某些访问路径（如索引扫描）看起来成本极低，以至于优化器可能跳过对其他方案的评估；而高估则保证几乎所有可行方案都被保留用于比较，从而不至于因估算过于乐观而错过实测可能更优的计划。

假设有两种访问 emp 表的方案：

  1. 索引扫描+连接：若低估谓词效果（认为只过滤 1%），算出极低的中间行数，导致优化器只评估此方案并剪掉全表扫描方案。
  2. 高估策略（假设过滤 10%）：使得索引扫描方案看起来代价更高，全表扫描的成本也被评估，优化器才会真正比较两者。

最终在实际运行中，全表扫描+哈希连接可能因顺序 I/O 更快而胜出，但若一开始就剪掉它，就永远不会被考虑。

第三步，计算中间结果的大小，该步骤的内容之前已经叙述过。

第四步，评估每个执行计划的成本：

在基于成本的优化器中，每个物理算子的总代价通常由以下两部分构成：

  • I/O 代价：以读取页面的次数为单位，乘以相应的 I/O 权重（如顺序读取 seq_page_cost 或随机读取 random_page_cost） 。
  • CPU 代价：以处理记录或执行谓词的次数为单位，乘以对应的 CPU 权重（如 cpu_tuple_cost、cpu_operator_cost） 。

最终，优化器对算子代价取页读次数与记录处理次数的线性组合来估算：

Cost=(pages read)+W×(records evaluated) \text{Cost} = (\text{pages read}) + W \times (\text{records evaluated})

，其中 W 表示单位记录的 CPU 权重 。

对于带唯一索引的等值谓词，访问路径通常为：

  1. B-Tree 索引查找：读取根到叶的路径上若干索引页（假设固定深度），通常记为 “1 页 I/O” 来表示一次查找操作的近似代价。
  2. 堆表行定位（Heap File lookup）：利用索引返回的行定位信息，再读取对应数据页，平均也是一次 I/O 操作。

综合起来，此算子的总代价可表示为：

1 (index page read)+1 (data page read)+W (CPU) 1\ (\text{index page read}) \;+\; 1\ (\text{data page read}) \;+\; W\ (\text{CPU})

。

该模型假设索引组织为聚簇或近似聚簇结构，因此每次索引查找可定位到唯一一条记录。

对于聚簇索引的范围扫描，算子需扫描多个索引条目并可能访问多条数据行，I/O 代价为

F×(NINDX+TCARD) F \times (\text{NINDX} + \text{TCARD})

，CPU 代价为

W×(tuples read) W \times (\text{tuples read})

，因此整体成本为：

F×(NINDX+TCARD)+W×(tuples read) F \times (\text{NINDX} + \text{TCARD}) + W \times (\text{tuples read})

，其中 NINDX 为索引页数，TCARD 为表的总页数，F 为谓词选取性；每个匹配索引条目对应一次数据页顺序 I/O。

对于非聚簇索引的范围扫描，CPU 成本和聚簇索引的一致，但是 I/O 成本为

F×(NINDX+NCARD) F \times (\text{NINDX} + \text{NCARD})

，因此整体成本为：

F×(NINDX+NCARD)+W×(tuples read) F \times (\text{NINDX} + \text{NCARD}) + W \times (\text{tuples read})

，此时每个匹配条目都可能落在不同的数据页上，平均需一次随机 I/O，因此用 NCARD（行数）来近似页数。

对于分段顺序扫描，不利用索引，需读取表的所有页并评估所有行：

Cost=TCARD+W×NCARD \text{Cost} = \text{TCARD} + W \times \text{NCARD}

，其中 TCARD 为全表页数，NCARD 为元组总数；顺序扫描的 I/O 可享有预取（prefetch）与缓冲优势，故只计算页面读取的总数。

接着，我们来看 JOIN 的成本计算，以嵌套循环连接（Nested-Loop Join）为例。

它的总代价公式：

CostNLJ(A,B)=Cost(A)+NCARD(A)×Cost(B) \mathrm{Cost}_{\text{NLJ}}(A,B) = \mathrm{Cost}(A) \;+\;\mathrm{NCARD}(A)\times \mathrm{Cost}(B)

，其中 A 为外层计划，B 为内层基表，NCARD(A) 为外层输出元组数。

为了控制连接顺序的枚举复杂度，System R 优化器仅考虑左深树：

  • 每一步连接的右子树 B 必须为尚未使用的基表，而非先前连接出的中间子树。
  • 这样能保证枚举过程中只需维护基表之间的累积连接，而无需考虑更复杂的树形拓扑，大幅减少计划数量（从 $O(N!)$ 降到约 $O(2^N)$)。

[!NOTE]

之前例子中的图就是一棵左深树。

对于谓词形如 B.key = A.key，且在 B 的 key 列上存在唯一或聚簇索引，优化器近似认为：

  1. 一次 B+Tree 索引查找需 “1 页” I/O（从根到叶路径平均代价）。
  2. 根据索引返回的行定位信息，再一次 Heap File lookup 也需 “1 页” I/O。
  3. 最后对该行执行谓词或投影等操作，产生 W 单位的 CPU 代价。

综合得到：

Cost(B)=1+1+W \mathrm{Cost}(B) = 1 \;+\; 1 \;+\; W

，该模型忽略了缓存预取及并行扫描等复杂因素，但其简洁性足以支撑海量计划的快速比较。

若内层无可用索引，则只能顺序扫描整个表：

  • I/O 代价：需读取 TCARD(B) 页（表在磁盘上的总页数）；

  • CPU 代价：对 NCARD(B) 条元组逐一评估谓词和产生输出，共

    W×NCARD(B) W\times \mathrm{NCARD}(B)

    。

因此：

Cost(B)=TCARD(B)+W×NCARD(B) \mathrm{Cost}(B) = \mathrm{TCARD}(B)\;+\;W\,\times \mathrm{NCARD}(B)

，该模型同样简化了缓冲与批量读写等优化手段，但体现了顺序扫描的典型开销。

如果是 Sort-Merge Join 的话，代价模型：

Cost=Cost(A)+Cost(B)+sortcost Cost = Cost(A) + Cost(B) + sort\:cost
  1. Cost(A)：外层子计划（子树）A 的总代价；
  2. Cost(B)：内层子计划 B（可以是基表或中间结果）的总代价；
  3. sort cost：对 A 和 B 各自执行排序的代价之和。

排序—归并连接是一种基于将两输入关系各自按连接键排序，随后线性归并扫描输出匹配对的算法。

  • 阶段一：排序（Sort）
    • 对输入关系 A、B 按连接属性（pred 中指定的字段）各自进行排序。
    • 如果输入已经部分或完全有序，则可跳过或简化排序步骤。
  • 阶段二：归并（Merge）
    • 维护两个游标，分别指向 A、B 的当前最小键值记录。
    • 比较当前 A、B 键值：
      • 若 A.key < B.key，则将 A 游标前移；
      • 若 A.key > B.key，则将 B 游标前移；
      • 若相等，则输出所有相同键值的配对（可能需要在一个输入保留缓冲区中暂存重复键值），并前移游标。
    • 该归并过程只需一次顺序扫描，两边各推进，故 I/O 和 CPU 都相对高效。
  • 适用场景
    • 两输入均可顺序访问或已排序，且连接键上无合适哈希索引时最优；
    • 特别适合大批量数据输出且需要顺序结果的场景。

如果后续操作涉及选取最大最小值，那么最好使用 Sort-Merge Join 先得出排序后的 JOIN 结果。

第五步，选出成本最低的执行计划：

若对所有可能的联接树与交叉产品一一枚举，计划数目将呈阶乘级增长，无法承受 。System R（Selinger 优化器）的核心思想是，通过启发式剪枝大幅减少搜索空间，同时用自底向上动态规划保证在受限空间内选出最优左深计划。

  • 全空间规模：对 n 个基表，所有可能的联接树数约为 n!（叶深树）。例如 6 表联接时有 6! = 720 种联接顺序；10 表时增至 3 628 800 种。
  • 启发式目标：在保证生成足够优质计划的前提下，剪掉绝大多数计划，避免枚举交叉组合、子查询作为内层的树形连接等无效情况。

这里展示三大启发式规则：

  1. 谓词下推

    越早执行过滤谓词，可最大程度减少后续算子的输入规模与 I/O 或 CPU 代价。

    在构建执行计划时，把每个谓词 $\sigma$ 尽可能下推到最接近基表扫描或索引扫描的层面，不把过滤延迟到后面再算。

  2. 避免笛卡尔积

    对无关联谓词的表进行笛卡尔积会产生极大中间结果，通常不可接受。

    仅在所有过滤条件均已消耗殆尽（即查询本质需要交叉连接）时，才枚举产生交叉产品的计划；否则只枚举带有有效联接谓词的表对。

  3. 仅枚举左深树

    在左深树中，每次联接的右子树必须是一个基表，而不能是先前联接所得的中间子树。

    这样可以使得搜索空间大幅缩减：从全空间的 O(n!) 降至约 O(2ⁿ) 或更小；以及流水线执行：左深树可实现完全流水线（pipelining），中间结果无需写入磁盘临时表；对大多数算子（NLJ、Hash Join、Merge Join）均适用。

自底向上的动态规划

以上的三种启发式规则带来的提升有限，所以 System R 还引入了动态规划。

动态规划算法利用了最优子结构的性质：如果在所有包含关系集 {A,B,C} 的计划中，连接 A、B、C 最优的顺序是 (A ⋈ B) ⋈ C，那么无论这个三表子集在更大计划中如何出现，(A ⋈ B) 必然是 {A,B} 的最优子计划之一，不需要再次枚举.

由于子计划不依赖于外部上下文，其最优性是全局性的，只需计算一次，即可复用到所有包含该子集的更大计划中。这一思想即 “不要在更大的计划中重新考虑子计划”。

System R 优化器按照子计划包含的基表数目，从小到大分层枚举：

  1. 第 1 轮（1-表计划）：分别为每个基表 $R_i$ 选择成本最低的访问路径（全表扫描或索引扫描）并记录其成本与输出行数。
  2. 第 2 轮（2-表计划）：对第 1 轮中的每个单表计划 P（作为外层），将尚未使用的每个基表 $R_j$ 作为内层，计算连接成本，并在所有方案中保留最优者。
  3. …
  4. 第 k 轮（k-表计划）：对所有包含 k-1 表的最优子计划 S，尝试将每个剩余基表 R 连接进来，更新并保留每个大小为 k 的子集的最优左深计划，直至包含所有 n 张表。

如此，算法以 n 轮完成枚举，每轮仅对上一轮的最优子计划进行扩展，不必遍历所有 O(n!) 种联接树，空间和时间复杂度可控制在指数级但远低于阶乘级别。

用伪代码来表示就是：

1
2
3
4
5
6
7
8
9
10
11
12
13
R ← set of relations to join
for i in {1…|R|}:                              // 按子集大小自底向上
  for S in {all subsets of R of size i}:
    optcost_S = ∞
    optjoin_S = ∅
    for a in S:                              // 枚举将 a 作为最后连接的基表
      c_sa = optcost_{S–{a}}
             + min_cost_to_join((S–{a}), a)
             + min_access_cost(a)
      if c_sa < optcost_S:
        optcost_S = c_sa
        optjoin_S  = optjoin_{S–{a}} ⨝ a
    // 计算并缓存 S 的最优子计划，包括 optcost_* 和 optjoin_*

该算法默认只搜索左深树，因为可以在子集拆分的时候采用 S - a + a 的方式来选取已有的子树和要 JOIN 的基表，并大幅减小搜索空间。

以 PostgreSQL 中的最优子计划复用为例：

1
2
3
4
5
6
-- 第一次：emp ⋈ kids 的最低成本执行计划
Hash Join  (cost=347292.59..498019.60 rows=3000001 width=36)
 Hash Cond: (kids.eno = emp.eno)
   -> Seq Scan on kids         (cost=0.00..49099.01 rows=3000001 width=18)
   -> Hash                   (cost=163696.15..163696.15 rows=10000115 width=22)
        -> Seq Scan on emp    (cost=0.00..163696.15 rows=10000115 width=22)
1
2
3
4
5
6
7
8
9
-- 第二次：dept ⋈ (emp ⋈ kids) 的最低成本执行计划
Hash Join  (cost=350376.61..556245.96 rows=3000001 width=40)
 Hash Join  (cost=347292.59..498019.60 rows=3000001 width=36) -- 最优子结构复用
  Hash Cond: (kids.eno = emp.eno)
    -> Seq Scan on kids 
    -> Hash 
         -> Seq Scan on emp -- 最优子结构复用结束
   -> Hash  (cost=1443.01..1443.01 rows=100001 width=8)
        -> Seq Scan on dept

假设有四个表 A、B、C、D，它们通过动态规划选出最优执行计划的步骤如下：

当前计算出 A 的最优执行计划是索引扫描，B 是顺序扫描（C 和 D 这里不展示），那么 {A, B} = AB or BA，{A, C} = AC or CA，{B, C} = BC or CB。

经过一系列计算，我们可以在动态规划中得出如下的备忘录：

Relations Best Plan Cost
A Index Scan 5
B Seq Scan 15
… … …
{A, B} B ⨝ A 75
{A, C} A ⨝ C 12
{B, C} C ⨝ B 22
… … …

之后，我们要计算 {A, B, C}，那么就是要计算：

  1. 不包含 A 的：比较 A({B, C}) 和 ({B, C})A；
  2. 不包含 B 的：比较 ({A, C})B 和 B({A, C})；
  3. 不包含 C 的：比较 C({A, B}) 和 ({A, B})C。

这个时候我们发现 {A, B}、{A, C}、{B, C} 的最优执行计划已经被缓存起来了，可以直接复用。perfecto！

最终，我们可以得出如下的备忘录表：

Relations Best Plan Cost
A Index Scan 5
B Seq Scan 15
… … …
{A, B} B ⨝ A 75
{A, C} A ⨝ C 12
{B, C} C ⨝ B 22
… … …
{A, B, C} (CB) ⨝ A 35
{B, C, D} (CB) ⨝ D 42
… … …
{A, B, C, D} ((CB) ⨝ D) ⨝ A 57

因此，我们可以知道 JOIN ABCD 这四个表的最低成本和最优执行计划了。

并且该算法在最差情况下需要枚举所有表子集并对每个子集尝试所有可能的最后加入表，因此具有指数级时间复杂度：O(n · 2ⁿ)。

我们可以将该问题等价成类似 01 子集问题，也就是 n 张表对应一串长度为 n 的二进制串，第 i 位为 1 代表关系 i 已经被 JOIN 了，因此有 2ⁿ - 1 个子集。而且每个子集要进行 n 次状态转移计算，也就是尝试去除集合中的某一个表来构建连接计划。最终两者相乘可得出如上的时间复杂度。

有趣排序（interesting order）

查询优化器在枚举左深执行计划时，除了比较不同访问路径和连接算法的代价外，还要考虑输出结果的排序属性——若某计划天然生成了对后续算子（如 Merge Join、ORDER BY、GROUP BY、去重等）有用的顺序，则称该排序为有趣排序。优化器会为每个子集在每种有趣排序下各自缓存最优子计划，从而保证后续算子能够直接利用已有排序，避免额外排序或物化开销，但这也会使枚举空间按有趣排序数量 k 成倍增长，总体复杂度增加 k + 1 倍。

尽管枚举空间增加，优化器借此能提前利用排序属性，减少后续全局排序及临时物化，往往在整体查询时间上取得收益，尤其在多级排序或多次归并连接链中更为明显。

1
2
3
4
for each subset S of relations:
  for each interesting order o in {unordered} ∪ Orders(S):
    compute min-cost plan producing S with order o
    keep plan if cost smaller than previous best for (S,o)

基数估算

基数估算（Cardinality Estimation）是成本模型的核心环节，优化器需要对每一种可能的关联操作都进行行数估算；当查询涉及 8–16 张表关联时，由于关联顺序的组合数呈指数级增长，可能需要上百到上千次估算；为了避免优化阶段延迟过大，估算器通常要在毫秒级完成一次估算；因此，各数据库系统普遍采用各种快速而简化的假设或采样策略，在估算精度与执行开销之间做权衡。

PostgreSQL 在 pg_statistic 系统目录中，为表的每一列收集的两大核心统计：

  1. 直方图边界（histogram_bounds）：按等频原则划分的区间边界，用于估算范围查询的选择性。
  2. 最常见值列表（most_common_vals）：出现频率最高的一组值及其对应频率，用于快速处理等值查询。查询优化器在生成执行计划时，会结合这两类统计信息来估算谓词的行数（selectivity），进而比较不同执行策略的成本。

下面将介绍这两种方案。

直方图又分为等宽和等深两种类型：

  1. 等宽直方图（Equal-Width Histogram）是最简单的直方图类型，它将数据值范围等分成若干个固定宽度的桶（bins），并统计每个桶内数据所占的比例（selectivity）。下图将总共 7854 条记录分入等宽的若干个区间（比如 0–5K、5K–10K 等），并在每个桶上方标注该区间内记录占总量的比例（如 0–5K 桶占 61%）。查询优化器可以利用这些比例估算范围查询或不在最常见值列表中的等值查询的行数，从而评估不同执行计划的成本。

    img

    根据上图，如果我们要选取小于 5000 的数据，那么操作的范围只局限于第一个桶中，因此估算的基数为 0.61 * 7854 = 4796。

    但这里会有个问题：如果范围查找的数值不是某个同的边界呢？也就是比如我们想查找小于 7500 的数据，而这个值刚好在第二个桶的正中间。这个时候我们只能假设数据为均匀分布，但是实际情况并不总是如此：可能大部分数据都集中在第二个桶的 5-6K 这一部分，也可能集中在 9-10K 这一部分，因此会存在较大误差。同时为了减少误差，我们又不可能无限制地缩小每个桶的宽度，因为最终会导致大量的桶，反而会加剧查询和存储的开销。因此我们需要等深直方图。

  2. 等深直方图（Equal-Depth Histogram）通过保证每个桶内的行数（频数）大致相同来划分数据范围。下图仍然是针对 7854 条记录使用 100 个桶来划分，每个桶含有相似数量的值，因此即使值域跨度不均，桶高（selectivity）也差不多（≈0.008），更能反映底层数据分布的真实密度。

    img

    在上图中，如果我们要选取小于 195.5K 的数据，那么操作范围在最后两个桶中，因此估算的基数为 (0.008 + 0.008) * 7854 =126。

    通常来说，等深直方图由于等宽直方图，因为它保证了每个桶的选取性的一致，从而导致数据分布更密集的桶更窄，数据分布更稀疏的桶更宽，这更好地反映出了数据分布。但是这样的维护成本也会更高，尤其是某些 DML 操作导致一个桶的高度变化时，它之后的桶需要不断地移动一些数据到这个桶直到选取性达到 0.008，之后的每个桶需要不断往前一个桶移动数据来保证每个桶的高度达到 0.008，每个桶的在 X 轴上的范围也可能会因此变化，甚至某些情况下的工作量不亚于从头构建。此外，每个桶中的数据倾斜仍然无法被避免。

    也就是，如果我们要选取小于 347866 的数据，那么仍然需要假设为均匀分布，这个时候遇到的问题和等宽直方图的是一样的。

通常情况下导致数据倾斜的大概率是一些极端离群值（outliers），我们可以通过下面这个方案来处理它。

等深直方图 + 最常见值（Most Common Values）

这个方案中，对于出现极高频率或明显偏斜的值，等深直方图会将它们剔除到最常见值列表，以免扭曲桶的划分边界和高度。

img

Value Selectivity
0 0.07
1 0.0048
2 0.00407
… …
94 0.0002
850 0.0007
Total 0.14

上面这个表格就是最常见值列表。

如果我们要选取等于 0 的数据，那么直接从最常见值的表里获取 0.07，然后 0.07 * 7854 = 550 就是预估的基数。

如果我们要选取大于 812 且小于 860 的数据，那么估算的基数为 (0.008 + 0.0007) * 7854 = 68.45。

但是这个方案仍然存在问题：当我们对多字段（列）的谓词过滤进行基数预估的时候，往往会低估基数，也就是预估的基数往往会比真实操作的元组的基数要低。这是因为不同列的过滤谓词被假设彼此独立，即联合选择性等于各单列选择性的乘积。这种做法在实际数据分布中往往并不成立：当列之间存在相关性时，单列乘积往往远小于真实的联合选择性，导致估算行数被严重低估，从而可能选择次优的执行计划。

为了克服完全独立性假设在多谓词估算中严重低估结果的问题，SQL Server 引入了三种谓词相关性假设：

  1. 完全独立：各谓词假设互不相关，联合选择性直接相乘。
  2. 完全相关：各谓词假设完全相关，联合选择性取最小者。
  3. 部分相关：折中假设，既不完全独立也不完全相关，通过对较低的选择性取根号后再相乘，减缓低估程度。

而多列 MCV 是将单列 MCV 的思路扩展到多列组合上：在统计收集阶段，为常一起出现在 WHERE 条件中的列组建立一个联合 MCV 列表，记录这些组合值及其联合频率；查询时，若谓词中出现该组合值，优化器即可直接使用其真实联合选择性，而无需依赖独立性假设或柱状图估算，从而显著提升多谓词过滤的准确性。

balance age selectivity
4776 34 0.009
76325 41 0.0005
…

但是这种方案的构建成本会随着查询涉及的列数的增长而增长。

同样，多列直方图也面临多个列的组合的爆炸式增长问题。

最后一种方案是 BayesCard：传统查询优化器常用独立直方图，对每列单独建模并将联合选择性取乘积 P(A)P(B)P(C)，这种方法速度极快但在列高度相关时严重低估真实结果；若对多列直接建立三维直方图，空间开销将成指数级

O(∣N∣3) \mathcal{O}(|N|^3)

，也无法在生产环境中普及。图形模型（如 Bayesian 网络）通过学习列间条件依赖，并将联合分布因子化为若干局部条件概率：

P(A)P(B∣A)P(C∣A,B) P(A)\,P(B\mid A)\,P(C\mid A,B)

，在保留关联性的前提下，将参数规模控制到

O(2∣N∣2) \mathcal{O}(2|N|^2)

，从而在毫秒级完成联合 Selectivity 推断，并在多项基准测试中显著降低估算误差，实现了精度与性能的平衡。

img

关于 BayesCard 的具体内容可参考：https://arxiv.org/pdf/2012.14743

传统关系型数据库对等值和范围谓词均有成熟的统计信息（如直方图、最常见值列表）支持，但对于 LIKE 和 UDF 这两类黑箱谓词，数据库优化器往往难以利用现有统计直接估算、只能退而求其次使用启发式规则或假定常数选择性，导致估算误差大、执行计划次优。近年来，研究界针对 LIKE 查询提出了模式/序列模型（pattern-based 或 positional histograms）来改善精度，而 UDF 则几乎无法通过统计建模，只能依赖运行时采样或成本抑制策略。

模式/序列直方图方法

SPH（Sequential Pattern-based Histogram）：通过挖掘字符串的频繁子序列，将常见的子串模式构建成模式直方图，在优化时根据查询模式匹配度快速估算 selectivity，从而显著优于传统直方图和常数假定。

Positional Sequence Patterns：针对 SPH 偶尔会高估的问题，引入位置序列模式区分相邻匹配与可插入匹配，通过信息熵剔除冗余模式，再结合分区匹配策略，使 LIKE 查询的平均误差率降低约 20%。

深度学习方法：近期有工作利用神经网络对 LIKE 模式进行表征和回归预测，能够学习复杂通配符下的非线性分布，但目前仍处于研究阶段，工业界应用有限。

样本采样（Sampling）

样本采样是一种简单直接的基数估算方法：在数据库中为每张表维护一个小规模的随机样本（例如，1% 的行）并常驻内存；在优化阶段，针对查询谓词仅在样本上执行过滤，计算样本命中率，然后将其外推到全表数据，得到整体选择性和估算行数。

该方案的优点是：

支持任意谓词：由于直接在样本上运行过滤运算，不依赖预先计算的直方图或分布假设，对任何运算符或 UDF 都有效。

摆脱独立性等假设：无需假设列间相互独立，也无需假设值在桶内均匀分布；样本大致反映真实分布，即可获取估算。

易于集成：只要在优化器中加入样本访问路径，就能在编译阶段快速完成过滤并计算比例，无需维护复杂的统计结构。

缺点是：

可能遗漏极端值：如果查询谓词对应的行在样本中未出现（例如极端离群值或低频组合），会导致估算为零或极小，严重低估真实行数。

编译时开销：需要在优化阶段执行过滤运算，若样本量或谓词复杂度较高，编译时间可能显著增加；采样比例若过低，则准确度下降，否则延迟上升。

不适用于多表连接：在多表连接查询中，需要对多个表的样本进行笛卡尔组合或联动抽样，开销与实现复杂度呈指数级增长，因此通常不对连接使用样本采样估算，只针对单表谓词有效。

下面展示 PostgreSQL 中是如何进行基数估算的：

PostgreSQL（沿用 System R 的经典做法）对单列等值联结 R₁ ⋈ R₂ ON R₁.a = R₂.a 估算行数时，先分别估算表过滤后行数 |R₁|、|R₂| 及各自该列的基数 (d₁、d₂)，然后假定联结属性在两表中同构分布并采用最保守的分母：

∣R1⋈R2∣≈∥R1∥×∥R2∥max(d1,d2). \bigl|R_1 \Join R_2\bigr| \;\approx\; \frac{\|R_1\|\;\times\;\|R_2\|}{\max(d_1,\,d_2)}.

，其中 max(d₁,d₂) 是两表中该列唯一值数量的较大者，用作平均每个值匹配行数的分母，以避免乘积模型在高度偏斜场景下的严重低估。

假设有三个表 emp，dept，kids：

emp：

eid employee
1 Lee
2 Kim
3 Sam

dept：

eid department
1 财务部
2 财务部
3 行政部

kids：

eid name
1 Neil
1 Lebron
2 Justin
3 Tom

如果执行 SELECT * FROM emp, dept, kids WHERE eid = eid AND emp.eid = kids.eid;，也就是没有过滤条件的情况，那么

∣emp∣=3∣dept∣=3∣kids∣=4 \lvert emp\rvert = 3 \quad \lvert dept\rvert = 3 \quad \lvert kids\rvert = 4 de,eid=3dd,eid=3dk,eid=3 d_{e,\mathrm{eid}} = 3 \quad d_{d,\mathrm{eid}} = 3 \quad d_{k,\mathrm{eid}} = 3 ∣emp⋈dept∣≈3×3max(3,3)=3×33=3 \bigl|\text{emp}\Join\text{dept}\bigr| \approx \frac{3\times3}{\max(3,3)} = \frac{3\times3}{3} = 3 ∣emp⋈kids∣≈3×4max(3,3)=3×43=4 \bigl|\text{emp}\Join\text{kids}\bigr| \approx \frac{3\times4}{\max(3,3)} = \frac{3\times4}{3} = 4 ∣(emp⋈dept)⋈kids∣≈3×4max(3,3)=3×43=4 \bigl|(\text{emp}\Join\text{dept})\Join\text{kids}\bigr| \approx \frac{3\times4}{\max(3,3)} = \frac{3\times4}{3} = 4

，

如果执行 SELECT * FROM emp, dept, kids WHERE dept.department = '财务部' AND emp.eid = dept.eid AND emp.eid = kids.eid;，那么

∣emp∣=3∣dept∣=1∣kids∣=4 \lvert emp\rvert = 3 \quad \lvert dept\rvert = 1 \quad \lvert kids\rvert = 4 de,eid=3dd,eid=1dk,eid=3 d_{e,\mathrm{eid}} = 3 \quad d_{d,\mathrm{eid}} = 1 \quad d_{k,\mathrm{eid}} = 3 ∣emp⋈dept∣≈3×1max(3,1)=3×13=3 \bigl|\text{emp}\Join\text{dept}\bigr| \approx \frac{3\times1}{\max(3,1)} = \frac{3\times1}{3} = 3 ∣emp⋈kids∣≈3×4max(3,3)=3×43=4 \bigl|\text{emp}\Join\text{kids}\bigr| \approx \frac{3\times4}{\max(3,3)} = \frac{3\times4}{3} = 4 ∣(emp⋈dept)⋈kids∣≈1×4max(1,3)=1×43=1.3 \bigl|(\text{emp}\Join\text{dept})\Join\text{kids}\bigr| \approx \frac{1\times4}{\max(1,3)} = \frac{1\times4}{3} = 1.3

。

思考：

这里出现小数点有影响么？

实际上是没有影响的，这个指标只用于基数评估并最终用于确定执行计划，实际的操作执行和这个无关。

基数的低估和高估问题

基数估算问题可分为低估（Under-Estimates）和高估（Over-Estimates）两类。两者均会导致选错执行计划，但低估往往更具破坏性：当优化器低估中间结果行数时，可能选择内存嵌套循环而不是外部哈希连接，导致大量磁盘溢写和 I/O 阻塞，从而极度拖慢查询。独立性假设是导致低估的主要根源之一，因为真实数据中列间高度相关时，简单的乘积模型会大幅低估联合选择性。

发表于 更新于 分类于

B+Tree

B+Tree 通过宽而浅的多路平衡结构，以及对页级 IO、顺序访问、并发保护和崩溃恢复的深度优化，完美契合 OLTP 系统对低延迟点查找、高并发访问和安全写入的严格要求，因此成为主流关系型数据库（MySQL、PostgreSQL、Oracle 等）在 OLTP 场景中最常用的索引实现。

性能特点

  1. O(log n) 查找复杂度：树高 ≈ logₘ N，当 m 很大时，即使 N 达到亿级，树高也通常只有 3～4 层，单次查找只需 3～4 次磁盘／页访问。
  2. 磁盘友好：每个节点对应一个（或多个）磁盘页（页大小常见 4 KB、8 KB），节点内存储大量键／指针，充分利用页读取的预读和缓存特性，减少 IO。
  3. 顺序访问高效：叶子节点通过链表串联，做范围查询（e.g. WHERE key BETWEEN A AND B）时，只要从第一个叶子开始，顺序遍历链表即可，不必回溯到内节点，再次查找。
  4. 并发控制：在多事务并发访问时，对节点（页）加共享或独占的轻量级锁（latch），确保在结构调整（分裂／合并）期间不会破坏其他事务的读取或写入视图。
  5. 安全写入：配合 WAL 或 双写缓冲 机制，即使在页分裂或更新过程中发生崩溃，也能借助日志或双写页恢复到一致状态，不会丢失或损坏索引结构。

各种 Latch 实现方式的比较

实现方式 原理与特点 适用场景
Test-and-Set Spinlock 原子地执行一条 test and set 操作：读—改—写一个标志位
若已被占用，则不断自旋（busy-wait）直到释放
实现简单、开销低（无系统调用）		 持有时间极短、线程数少、CPU 空闲时可快速获得锁
Blocking OS Mutex 调用操作系统的互斥锁原语（如 pthread_mutex）
若锁被占用，线程进入睡眠（阻塞），由内核调度唤醒		 线程可能长时间等待、锁竞争激烈、无法一直自旋时
Adaptive Spinlock 结合自旋与阻塞：先自旋若干次（避免短期冲突），超时后再阻塞
在多核系统上可减少线程睡眠、上下文切换开销		 对临界区长度不稳定、短时冲突多长时冲突时都需兼顾
Queue-based Spinlock 基于队列（如 MCS、CLH）组织申请线程
自旋在各自本地节点上，避免全局自旋总线抖动
公平性好，防止饥饿		 高并发竞争场景，需要严格 FIFO 公平性
Reader-Writer Locks 区分读锁（shared）与写锁（exclusive）
允许多个读者并行、写者独占
可基于自旋或阻塞实现		 读多写少场景，如 B+Tree 查找（多数是读），偶尔分裂/合并（写）

Test-and-Set Spinlock 的实现

1
2
3
4
5
std::atomic_flag latch;
…
while (latch.test_and_set(...)) {
    // Yield? Abort? Retry?
}

以上代码中，test_and_set 是一个原子指令：读取锁标志，置 1，并返回旧值。如果返回值表明锁已被占用，线程就在 while 循环中不断自旋重试。

优点

  • 极低的延迟：一次原子 CPU 指令即可完成加／解锁，若临界区非常短，开销远小于一次系统调用。
  • 实现简单：依赖硬件指令，无需操作系统介入。

缺点

  • 忙等：自旋期间 CPU 一直在循环，占用周期，却不做实质性工作。
  • 总线抖动：多核同时自旋会争抢同一缓存行，导致缓存一致性流量剧增。
  • 可扩展性差：并发度一高就容易产生严重争用，甚至导致某些线程长期拿不到锁（饥饿）。这种情况在多机器／多核环境下更为明显：TaS 自旋锁会导致耗费大量总线带宽，甚至在远程节点上更容易饿死。

Latch Coupling

在遍历 B+Tree（从根到叶）过程中，始终维持一条“锁链”：

  1. 加锁当前节点；
  2. 在确定要访问的子节点加锁后，再释放父节点的锁。

保证任何时刻，对正在操作路径上的节点都有锁保护，避免结构变化（分裂/合并）导致的不一致访问。

思考：

为什么要锁父节点？

避免并发操作导致子节点增删时引发的父节点分裂或合并，从而避免多线程访问到不一致的数据。

[!NOTE]

何时可以释放父节点锁？

当子节点被判定为“安全”（safe）时，父节点锁可提前释放：

  • 插入场景：子节点没有达到最大容量，插入后不会触发分裂；
  • 删除场景：子节点删除后依旧保持超过一半的填充度，不会触发合并。

优点

  • 锁粒度细化：仅对正在操作的节点及其立即父节点加锁，其他分支无关节点不受影响
  • 提高并发度：减少持锁时间，其他事务可以更快地访问不同的子树

缺点

  • 频繁的锁操作：每向下一层移动，都要做一次 lock(child) + unlock(parent)，系统调用和内核开销不可忽视
  • 层次深度敏感：树越深，锁–解锁次数越多；在高并发或极深树结构中，延迟和 CPU 开销上升明显

Read Path 中：

  1. 在根节点加读锁；
  2. 定位到要访问的下层子节点；
  3. 对该子节点加读锁；
  4. 释放其父节点的读锁；
  5. 重复 2–4，直到到达叶节点并完成读取。

Write Path 中：

  1. 在根节点加写锁；
  2. 定位到要访问的下层子节点；
  3. 对子节点加写锁；
  4. 检查子节点是否安全：
    • 插入时：子节点未满（不会触发分裂）；
    • 删除时：删除后填充度仍 >= 50%（不会触发合并）；
  5. 如果安全，释放所有祖先节点的写锁，仅保留子节点锁往下继续；
  6. 若不安全，则继续在上层保留必要锁，直至完成分裂/合并，再逐级释放。

示例 1：搜索数据 23（示例中 B+ 树变化的顺序是从上到下，从左到右）

img

示例 2：删除数据 44

img

示例 3：插入 40

img

重要观察

传统的 B+Tree 是为慢磁盘／页式存储优化的，而在纯内存数据库中，我们可以选用更 CPU 缓存友好、指针开销更小、分支因子更灵活的数据结构。比如：

Adaptive Radix Tree (ART)

一种基于 Radix-Trie（前缀树）的变体，根据子节点数动态压缩节点类型（4／16／48／256 分支），兼顾空间与速度。

优势：

  • 存储密度极高；按 key 前缀快速定位，指针跳转少
  • 支持前缀查询，范围查询也只需一次遍历即可顺序扫描叶子
  • 插入／删除时节点扩张／收缩成本低

适用于对内存利用率敏感、需要高吞吐点查和范围查的 OLTP 场景。

Bw-Tree（Latch-Free）

微软提出的无锁 B+Tree，核心是 delta record 日志链 + 原子 CAS 更新，所有结构修改都追加写入 LSN，读者通过多版本链合并视图。

优势：

  • 无全局锁或页级 latch，天然适合超高并发写入；
  • 写热点变为对内存日志的追加，分裂／合并操作也只是更新 delta。

适用于写密集型、高并发事务环境。

Masstree

结合了 B+Tree 与 Trie 的优点，对多列复合键可层级拆分，且各层使用紧凑数组存储。

优势：

  • 支持多列复合索引，Trie 能快速跳过公共前缀
  • 使用 per-node lock-coupling + optimistic read 提升并发性能

适用于典型 KV 或多字段查找场景。

之后的内容会重点介绍 Bw-Tree。

Bw-Tree

BW-Tree 是微软 Hekaton 内存数据库中用于 OLTP 场景的无锁索引结构。它通过增量记录（delta record）和映射表（mapping table）两大核心机制，实现了对 B+Tree 操作的完全无锁化。

Delta 机制：无就地更新

  • 增量链：每次对某个页的插入、删除、分裂等修改，都不是直接改写页本身，而是在映射表条目后面追加一个小的 delta 节点，记录本次的修改操作。

  • 好处

    • 无锁安全：对页的修改仅是往链尾追加，不会破坏其他读者正在访问的旧版本数据。
    • 减少缓存抖动：不改写原页，旧页仍然稳定驻留在 CPU 缓存中，新 delta 追加只影响少量缓存行。

  • 读取时合并视图

    读者先通过映射表定位基础页（base page），然后顺着 delta 链向前合并各个 change record，最终得到当前一致性视图。

Mapping Table：页指针的原子替换

  • 映射表结构：类似于页 ID → 页物理地址（或页链表头节点）的一个数组／哈希表。每个索引页（或叶子页）在映射表中有一条定长条目。
  • CAS 原子切换
    • 当需要分裂一个 leaf page 或合并多个 delta 到一个新的 consolidated page 时，只需在映射表中对该页条目执行一次 Compare-And-Swap 操作。
    • 线程安全、无锁：所有并发读者只要先读一次映射表，就能看到分裂前或分裂后的整块页内容；中间状态对读者透明。

img

上图中，绿色的虚线箭头是逻辑指针，黑色的实线箭头是物理指针。

物理指针的用途：

  • 在直接访问数据的场景中使用，提供快速访问能力。
  • 通常用于叶子节点内部或数据页的局部操作。

逻辑指针的用途：

  • 在节点之间（特别是父子节点之间）的连接中使用，提供动态调整的灵活性。
  • 逻辑指针指向的是映射表中的条目，映射表将逻辑指针解析为实际的物理位置。
  • 节点分裂或合并时，映射表更新物理位置，而逻辑指针保持不变。

思考：

为什么节点之间用 logical pointer 连起来？

在 BW-Tree 中，当某个子节点发生分裂或合并等变化时，只需要在映射表中更新该节点的 Page ID 对应的物理地址，一定程度上和父节点进行解耦。

父节点里存的只是 Page ID（逻辑指针），因此父节点无需做物理修改或大范围加锁，这样极大提升了并发能力和更新效率。

更新与搜索（Delta Updates & Search）

每次对页的更新操作都会产生一个新的 delta 节点，该节点通过物理指针指向基页（base page），之后通过 CAS 操作将原来从映射表指向基页的物理指针指向新的 delta 节点。

img

思考：

为什么 delta 节点使用 physical pointer 指向基页？

物理指针一旦写入即不可变，读者沿着物理地址可以无歧义地遍历历史记录节点，即便映射表后续对该 Page ID 做了 CAS 更新也不影响已追加的 Delta 链的正确合并和回放。而逻辑指针（Page ID）会随映射表更新而变化，若 Delta 节点也存逻辑指针，就无法区分应访问旧页还是新页；物理指针则始终指向原有的内存位置，确保版本链的完整性和一致性。

并发更新是怎么进行的？

秉持着先来先服务的理念，后到的操作则会被驳回或者重试，从而避免两个 delta 节点指向同一个下层节点。

下图中，我们假设 DELETE K8 先来，那么 INSERT K6 就会被驳回或重试。

img

[!NOTE]

在并发更新场景下，上图的竞争中通常会加锁。

之后如果要搜索的话，流程如下：

  1. 从根到叶，像常规 B+Tree 那样遍历；
  2. 定位到叶子页后，检查映射表指向；
  3. 如果映射表指向 Delta 链：
    1. 自上而下遍历 Delta 链，对每个 Record（Insert/Delete）检查：
      1. 若 Record 的键等于查询键，则：
        1. 如果是 Delete 类型，说明该键已被删除，搜索可提前返回不存在；
        2. 如果是 Insert 类型，说明该键最新就在此处，立即返回对应的值；
    2. 如果遍历完整个 Delta 链都没命中，再回退到 Base Page；
  4. 否则，或 Delta 链未命中：
    1. 对 Base Page 执行二分查找（就像普通 B+Tree 的叶页内搜索那样）；
    2. 若在 Base Page 中找到该键且未被后续的 Delete 覆盖，即返回对应记录；否则返回不存在。

合并与清理（Consolidation/Garbage Collection）

  • 随着 delta 不断追加，链条会变长，读者合并成本上升。
  • 后台合并线程会定期：
    1. 扫描映射表，选取 delta 链过长或更新频繁的页；
    2. 将所有 delta 应用到一个新建的基础页，生成新的 base page；
    3. 用 CAS 原子地在映射表中替换旧页指针；
    4. 将旧的 base page + delta 链标记为可回收。

img

合并完成后，我们会把 old page 2 放入一个池子中，便于之后的复用。

思考：

在合并的过程中，如果执行了大量的操作，那是怎么处理的？

img

上图中，合并期间加入的 delta 节点会一开始指向 INSERT K5，待合并完成后这些节点会指向 new page 2。

结构变更

Split Delta Record

表示将基页中一部分键范围（key range）移动到了另一个页面，并使用逻辑指针指向新的页面。

Separator Delta Record

提供一种快捷路径，用于告诉父节点：应该在哪个键范围中查找已经被拆分出来的新页面。

以上两个组件会带来如下优势：

  1. 位置变化无需修改 BW-Tree 索引结构：一旦某个页面的位置发生变化，只需修改 mapping table 即可，无需更改 BW-Tree 上层结构中的索引节点。这是因为 BW-Tree 的索引项记录的是页面的 page id，而非物理地址。这样避免了传统 B-Tree 中频繁重建索引的开销。
  2. 页面大小灵活，提升空间与性能利用率：mapping table 中的 page 大小不必固定为如 8KB 这类块对齐的大小。可以根据业务需要进行更细粒度的划分或合并，从而减少因空间浪费或合并而产生的额外写放大。
  3. 解耦内存与存储结构，便于系统各层独立优化：BW-Tree 通过逻辑页和 mapping table 的机制，将存储管理与内存结构解耦。这样使得存储层可以专注于持久化效率优化，而内存层则可专注于读写性能与并发控制，彼此互不干扰，从而实现系统整体性能提升。

假设 BW-Tree 中的 page 3 发生分裂，具体分裂步骤如下：

img

需要注意，一个 split delta record 就对应要创建一个 separator delta record，多个 separator delta record 也会形成跟之前一样的 delta record 链。

在以上的节点分裂过程中，无需加锁，而且不论何时都可以访问到对应的节点，不会出现空指针异常。

思考：

为什么 split delta 节点指向 page 3 的是物理指针，而不是逻辑指针呢？

跟之前的 delta record 通过物理指针指向基页的原理是一样的。

[!NOTE]

Split 节点同时使用物理和逻辑指针，既可以保证老的读操作（可能还在访问旧的物理页 3）不受影响，又能让新的读写操作访问到新的页面 5 上去。

关键观察

在每一层节点上进行查找时，若缓存中没有相应数据，就会发生 cache miss，导致额外的内存访问延迟，尤其是当树高较大时，每层都有潜在的 miss。

传统设计中，内部节点和叶节点大多存于随机内存地址，查找时经常会产生多次 cache miss。

如何减少 Cache Miss？

  1. 节点预取

    • 硬件级预取：CPU 的硬件预取器可以根据访问模式（如 stride 或 stream）提前将相邻缓存行加载到缓存中。

    • 软件或路径预取：在树的搜索路径上提前发起预取，例如先加载 root，再预测加载下层 child 块 。

  2. 缓存友好型节点结构

    • 调整节点大小至多个缓存行，让一个节点的多个缓存行能并行预取，减少单节点内部的 miss 数量。

  3. 增加树扇出，降低树高

    • 增大节点容量（存更多键/指针）可以减少树的高度，也就减少访问叶子需访问的层数，从而降低总体 cache miss 数量 。

  4. 避免路径中的重复访问

    • 可记录较热的路径节点，实现快速访问。

  5. 批量预加载

    • 对于范围扫描或批量插入，可以一次性预加载整颗叶子区域，从 root 之后连续加载所有相关叶子节点，提高顺序访问的 cache 命中率。

发表于 更新于 分类于

摘要

该论文解决了三个问题：

  1. 如何以低延迟处理用户更复杂多样的查询；
  2. 如何设计一种友好且统一的数据布局，使其兼容列式存储和行式存储，能够处理复杂数据类型，并保持低延迟；
  3. 如何以低延迟处理每秒海量请求。

该论文提出了 5 个创新性想法，并详细阐述了每个想法的实现方法：

  1. 读写分离： 工作节点专用于处理读操作或写操作，确保读操作不会干扰写操作。在实时读模式下，引入版本验证机制（最新版本 = max(V₁, V₂)）以保证每次查询都能检索到最新数据。此外，每次写操作完成后，写节点会主动将最新版本拉取到相应的读节点，以避免后续读操作出现高延迟。
  2. 混合行列存储： 用于存储复杂类型数据。一个明细文件 (detail file) 由 n 个行组 (row group) 组成；一个行组由 k 个数据块组成；一个数据块由 p 个 FBlock 组成；一个 FBlock 存储一个或多个行的部分行中某一列的 x 个值。
  3. 高效索引管理： 包括对基线数据和增量数据的索引构建与维护。对于基线数据，AnalyticDB 构建倒排索引并引入过滤比 (filter ratio) 来优化读操作。对于增量数据，AnalyticDB 在读节点上构建轻量级的排序索引，以加速在完成该类型数据的倒排索引异步构建之前的读操作。
  4. 优化器： AnalyticDB 引入了 STARs 框架来同时评估存储能力和关系代数能力，并采用动态规划技术，以实现高效的谓词下推 (predicate push-down)。该数据库最小化了联接下推 (join push-down) 所需的表重排 (shuffling) 成本。对于基于索引的联接和聚合，它采用左深树 (LeftDeepTree) 来高效利用全列索引 (index-on-all-columns)，同时下推谓词和聚合操作。此外，优化器和执行引擎采用基于采样的基数估计 (cardinality estimation)，辅以缓存先前采样结果、优化的采样算法和改进的派生基数 (derived cardinality)。
  5. 执行引擎： 能够直接在序列化的二进制数据上操作，而非 Java 对象，从而消除了在大数据重排过程中序列化和反序列化的高昂开销。

分析与实验结果： 在 1TB 数据集上，AnalyticDB 的性能优于 PrestoDB、Druid、Spark SQL 和 Greenplum，并且在扩展到 10TB 数据集时，其性能未受到显著影响。随着写节点数量的增加，AnalyticDB 的写入吞吐量呈现稳定增长。在 TPC-H 基准测试中，AnalyticDB 在 22 个查询中的 20 个上，其完成时间仅为次快数据库所需时间的一半。然而，对于查询 2，由于选择了不同的联接顺序，AnalyticDB 的速度慢于 PrestoDB 和 Greenplum。

论文优势

  • 论文中概述的 3 项挑战精准地指向了 OLAP 系统在实现实时高效响应时所面临的关键障碍。解决这些挑战不仅能显著提升数据库对多样化查询和复杂数据类型的兼容性，还能改善其在生产环境中的响应能力，突显了其高度的研究价值。读写分离与版本验证的结合确保了读写操作的隔离性，同时始终为读查询提供最新数据。混合数据布局和索引的设计融入了对 JSON、全文和向量数据等复杂数据类型的支持，为多样化的数据操作提供了统一的访问接口。这极大地拓宽了 AnalyticDB 在更广泛用例中的适用性。此外，执行引擎将基于采样的基数估计与缓存、优化的采样算法等技术相结合，以低开销和最小延迟实现了高精度的估计。总而言之，AnalyticDB 引入的改进和优化方案代表了在增强 OLAP 系统数据多样性和实时响应能力方面迈出的重要一步，其综合性解决方案将在高并发电商场景中充分展现其能力。
  • 论文提供了全面的文献综述。第 2 节 Related Work 讨论了不同数据库的不足。例如，OLTP 数据库中昂贵的索引更新会降低吞吐量并增加延迟；而 OLAP 数据库（如 TeradataDB 和 Greenplum）中的列式存储会导致点查 (point-lookup) 查询产生高昂的随机 I/O 成本。上述问题在 AnalyticDB 中得到了有效解决。此外，论文还概述了 AnalyticDB 相较于 Amazon Redshift 的改进，以及与 Google BigQuery 在查询和聚合方面的差异。
  • 论文详细描述了 AnalyticDB 中各项功能的过程，包括：
    1. 从读和写两个角度对读写分离过程进行了透彻的解释，并附有流程图专门说明更复杂的读操作。
    2. 查询执行 (Query Execution) 涉及的 3 个算法的关键指令的伪代码和注释。
    3. 将基线数据与增量数据合并过程分解为 3 个阶段的示意图。

论文不足

  • 论文中对某些功能的描述不够完整。在论文第 3.4 节 Read/Write Decoupling 中，仅提到了实时读 (real-time read)，而遗漏了有限延迟读 (bounded-staleness read)。对于 OLAP 而言，读取过时数据是可以接受的，有限延迟读允许读节点在写操作完成后的特定延迟之后才访问写节点上的最新数据，因此它在一定程度上确保了 AnalyticDB 的快速响应。然而，论文中并未解释这种读取模式。
  • 论文对某些新引入概念的描述不够清晰。在第 5.1.1 节中，关于谓词下推的讨论仅对 STARs 框架做了简要概述，没有解释它如何应用关系代数、如何进行成本计算，以及优化器如何使用动态规划来封装关系代数运算符。这些遗漏可能会让读者感到困惑。
  • 论文中的性能评估实验相对简单。首先，仅测试了 3 条 SQL 语句，覆盖的查询类型范围狭窄，且仅针对特定的表分区策略、特定的表和字段以及特定的数据类型。测试并未涉及如 JSON 等复杂数据类型。其次，实验仅测试了 1TB 和 10TB 的数据集。然而，在生产环境中，每日新增数据量可达数十甚至数百 PB。在双 11 或 618 等高峰促销日，每日数据处理量可达数百甚至数千 PB。例如，在 2022 年双 11 期间，淘宝和天猫的订单支付峰值达到每秒 583,000 笔。因此，实验所用的数据集远远不足以反映真实场景的规模。第三，基于 TPC-H 基准的测试仅评估了 22 个查询，不足以全面反映这 5 个数据库的真实性能。因此，建议纳入生产环境中涉及的所有数据和查询，例如 MySQL binlog、ElasticSearch 索引日志和 Kafka 日志等，并在这 5 个数据库上开展为期一周或更长时间的稳定性测试，以提供更真实的评估。

参考文献：https://www.vldb.org/pvldb/vol12/p2059-zhan.pdf

发表于 更新于 分类于

Data Skipping

我们可以利用辅助数据结构标识表中哪些部分可以跳过扫描，避免对每一行（tuple）都做判断。

OLAP 场景下为什么要用 Data Skipping？

在 OLAP 场景中，查询往往是扫描大量历史数据，筛选满足某种复杂条件的子集，典型例子如数据仓库的多维分析、报表查询等。此时：

  1. 表非常大：可能有数十亿、上百亿行，逐行检查每个行是否满足条件，代价非常高。
  2. 查询通常按若干列做过滤：比如 WHERE 年份 = 2024 AND 地区 = '北京'，而且常常只要少量数据就够了（高选择性场景）。
  3. 批量扫描 vs. 随机读取：读整个表，会触发大量 I/O；如果能一眼就知道哪些数据页根本不用读，就能省下大量 I/O 时间。

因此，Data Skipping 的核心思路，就是通过在数据块或分区级别维护一些辅助信息，让查询在执行过滤时能够判断“某个数据块（比如一个文件区块、一个数据页、一个段/partition）肯定不包含满足过滤条件的行，就直接跳过，不去读取和解析该块中的每一行”，从而大幅减少 I/O，以及后续的行级计算。

常见的 Data Skipping 技术主要有以下几类：

  1. Zone Map / Min-Max 索引
    • 每个数据块（block 或 segment）存一对最小值和最大值，例如按时间分块后，记录该块中时间列的 [min_timestamp, max_timestamp]。
    • 查询时，如果查询条件为 timestamp BETWEEN '2024-01-01' AND '2024-03-01'，当某个块的最大时间都早于 ‘2024-01-01’，或者最小时间都晚于 ‘2024-03-01’，就可以完全跳过该块。
    • 优点：实现简单、维护开销低；适用于列值分布相对平缓的场景。
    • 缺点：如果一个块里 min–max 范围很宽（分布倾斜或块太大），就容易出现“区间重叠”，跳不过去，效率下降。
  2. 位图索引（Bitmap Index）
    • 针对低基数的列（如性别、地区、状态等），为每个可能的离散取值维护一个位图（bitset）。
    • 每个数据块也可以维护该位图的摘要（比如每 N 行分一个小位图），查询时快速根据位图判断该数据段中是否存在某个值，若不存在就跳过。
    • 优点：在基数较低、数据倾斜度不高时，效果很好；位图操作位运算开销低。
    • 缺点：对于高基数列，位图会很大，且维护成本高。
  3. 布隆过滤器（Bloom Filter）
    • 保存每个数据页中的列值集合的 Bloom Filter，当查询时先检查 Bloom Filter 是否可能包含该值，若 Bloom Filter 结果为不可能存在，则跳过整个页。
    • 优点：Bloom Filter 占用空间小，查询时布尔判断开销低。
    • 缺点：存在误报率（false-positive），即有时候 Bloom Filter 误判可能存在，需要再回退到读页；但绝不会误判真正存在而跳过，保证正确性。
  4. Skip List／Skip Table 结构
    • 某些列可以对数据块按值范围做多级跳跃索引，比如最外层根据范围将整个表划分为若干区域，里层再分页索引。
    • OLAP 引擎（如 Apache Parquet、ORC）通常在文件格式层面（列存格式）会同时维护多层次的自底向上的统计信息（Statistics）。
    • Query Planner 就会根据统计信息决定哪些 Row Group（行组）或 Stride（步长）可以跳过。
  5. 分区表（Partitioning）
    • 将大表水平拆分成多个分区（按时间、地区、业务线等），在查询时如果过滤条件里包含分区键（如 date），可以直接分区剪裁，跳过不相关分区。
    • 其实分区本质也是一种粗粒度的 Data Skipping，跳过整个分区文件。

设计 Data Skipping 时的关键考虑点

1. 谓词选择性

  • 低选择性场景

    比如查询 WHERE gender = 'M'，如果全表大约一半行都是 gender='M'，则满足谓词的行很多，跳过就算跳掉了另一半行，也意味着还要扫描一半行，节省有限。

  • 高选择性场景

    比如查询 WHERE customer_id = 123456789，或 WHERE event_date = '2025-06-01' AND region = '北京'，只会有极少量行符合条件。此时如果辅助结构能识别掉绝大多数数据块，就能极大节省 I/O。

2. 列值分布

  • 如果某列的值高度偏斜，例如某个列绝大多数行都是同一个值，其余值极少，Zone Map 或基于统计的跳过就不太准。
    • 举例：某列几乎全是 ‘A’，只有很少行是 ‘B’，若文件切分并不按照该列聚簇，那么即便大多数块里都是 ‘A’，但每块的最小值/最大值同样会显示为 ‘A’，所有块看起来都可能包含 ‘B’，无法跳过。
  • 因此，一般会结合物理排序（clustering）或分桶（bucketing）：
    • 在生成文件时先按该列做排序/分桶，这样相同值会被写到同一数据块里；
    • 有了同一数据块里只有一个值的特性，块级统计就变得非常有效。

Bitmap Indexes

位图索引为某个属性（列）的每个不同取值，都存储一份单独的位图，位图中的第 i 位对应了表中第 i 条记录。

对于下表的原始数据：

order_id paid
1 Y
2 Y
3 Y
4 N

压缩后的数据如下：

order_id paid
Y N
1 1 0
2 1 0
3 1 0
4 0 1

对于多列多值的组合过滤，Bitmap 索引支持高效的按位与（AND）、或（OR）、非（NOT）等位运算。

如果把整个表的行数记为 N，那么一个属性值对应的位图长度就是 N 位。当表非常大（数千万、上亿行），单张位图也会变得很大。为避免一次性分配庞大、连续的内存块，常见做法是分段（segment/chunk）：把总行数 N 划分成若干个固定大小的块（例如每块 1 百万行），那么位图也相应地分成若干个子段，每个子段只需要维护该区间内的位。查询时只需要扫描与目标区间重叠的位段。

思考：

为什么使用 Bitmap？

  1. 空间利用率较高

    位图本质上是一个位数组，对于低基数或中等基数的列，位图能精确记录行与属性值的映射，且只需 1 位/行。

  2. 位运算速度快，适合多条件混合过滤

    多列过滤条件时，只要获取每个条件对应的位图，对它们做位与/或/非等操作，就能快速算出满足所有条件的行集合。

为什么位图索引适合压缩？

  • 如果某个取值非常稀疏地分布在整个表中，那么位图中绝大多数位都是 0，只有少数位置是 1。或者，若有些连续行都满足该取值，又会出现连续的 1 序列。利用这种长串 0 或长串 1 可用压缩算法（如 Run-Length Encoding、WAH、Roaring Bitmap 等）进一步缩小存储空间。
  • 现代 OLAP 引擎（例如 Apache Druid、ClickHouse、Presto 等）在底层都会选择一些成熟的压缩位图实现，这些实现不仅压缩率高，而且能够在压缩态下做位运算，避免了每次查询都需要先把整个位图解压到内存。

常见的四种编码技术

位图索引常见的四种编码技术：等值编码（Equality Encoding）、区间编码（Range Encoding）、分层编码（Hierarchical Encoding）和位切片编码（Bit-sliced Encoding）。

  1. 等值编码

    为某一列（属性）中的每个唯一取值都维护一份独立的位图。也就是说，如果该列有 m 个不同取值，则总共有 m 个位图，每份位图长度为表的总行数 N。这种编码形式上类似 One-Hot 独热编码。具体示例可参考之前的两张表。

    优点：直观简单并且等值查询高效。

    缺点：占用大量空间。

  2. 区间编码

    与等值编码不同，不为每个单一取值都建一份位图，而是按照若干有意义的区间（interval）来划分，每个区间对应一份位图。

    举例：以一个数值列 age 为例，表中 age 范围在 0–100 岁之间，可以把区间划分为 [0–17]、[18–30]、[31–50]、[51–70]、[71–100]。

    为每个区间建一份位图：

    • Bitmap_0_17：标记哪些行的 age 落在 0–17 之间；
    • Bitmap_18_30：标记哪些行的 age 落在 18–30 之间；
    • 以此类推。

    优点：适合范围查询并且比等值编码更节省空间。

    缺点：区间的粒度需要权衡。划分的区间越细，能更精准地匹配查询，但要维护的位图份数越多；划分区间越粗，则位图份数越少，但位图对应的行集合范围更大，查询时跳过的效率会下降。

  3. 分层编码

    通过构建树形层次结构（hierarchy），在不同层级对值或值范围做分段统计/位图标识，用于快速识别那些整个子树/子范围内没有数据的情况。

    通常从较粗的范围到较细的范围构建多层位图：

    1. 第一层（根层）：记录整个列的全部可能值范围，并标注哪些子范围是非空（或者空）。
    2. 第二层：把根层范围继续细分为若干更小区间，分别维护各自的标识。
    3. 依次向下，直到最底层是单个取值或某个可接受的最小分区。

    以一列 zipcode（邮政编码）为例，取值范围是 00000–99999，总计 100,000 个可能值。如果直接对每个具体的 5 位数字都建一份位图，太耗空间。改用分层编码：

    1. 第一层：只看邮编的第一位，共 10 种可能（0、1、2、…、9），
      • 构建 10 个顶层位图，分别标记表中哪些行的 zipcode 第一位是 0、哪些行的第一位是 1，以此类推。
    2. 第二层：假设在第一层为前缀 = 3（假设查询潜在目标值的前缀为 3）的情况下，第二层把 zipcode 的前两位 30 ～ 39 这 10 个前缀，各自再建位图；
    3. 第三层：再细分为 300 ～ 309 等前缀，递归向下，直到精确到具体 5 位。

    优点：快速剪裁空范围且适用于高基数/稀疏分布的列。

    缺点：存储与维护复杂度更高。需要为每层维护对应的位图，并保持各层之间的一致性。

  4. 位切片编码

    不是将每个取值或每个区间映射到一份位图，而是针对某个数值列的二进制表示，维护按位的位置拆分的一组位图。

    假设有一个 8 位的整数列，如下：

    行号 value（原始值） value（二进制） Bit_0 Bit_1 Bit_2 Bit_3 Bit_4 Bit_5 Bit_6 Bit_7
    1 5 00000101 1 0 1 0 0 0 0 0
    2 18 00010010 0 1 0 0 1 0 0 0
    3 7 00000111 1 1 1 0 0 0 0 0
    4 25 00011001 1 0 0 1 1 0 0 0

    上表中，Bit_0 代表的是最低位，Bit_7 代表最高位。

    位切片编码中，如果要基于上表中的数据进行如下条件过滤：

    1
    SELECT * FROM tbl WHERE value > 17;

    我们先将 17 转换成二进制：10001，并在位切片编码过的位图索引中搜索并过滤：

    1
    2
    3
    4
    5
    6
    10100000
    01001000
    11100000
    10011000
    --------
    10001000 # 17

    我们先找出 17 的最高位是 Bit_4，并得出表中 4 行的这一位以及更高位中只有第 2 和第 4 行是和 17 至少一样大，因此可以快速过滤掉第 1 和第 3 行。

    优点：

    1. 支持任意数值比较：当需要执行 WHERE value > K 或 WHERE value BETWEEN L AND R 之类的数值比较时，只需根据 K、L、R 的二进制表现，结合多份 Bit_j 位图做布尔代数运算（AND、OR、NOT），就能快速构造出满足条件的行号位图。
    2. 对高基数数值列尤为合适：与等值编码相比，高基数字段如果直接为每个取值建位图会产生海量位图；而位切片只需按二进制位宽度建 B 份位图，无论具体取值基数多大，都只需 B 份（例如 32 或 64）位图。

    缺点：

    1. 查询时位运算代价较大：与简单的等值位图（只要读取并返回一份位图）、区间位图（只要读取一份或几份位图）相比，位切片编码在做数值比较或范围查询时，需要对多份位图做组合运算（AND/OR/NOT），逻辑比较稍复杂，CPU 开销更高。但总体仍比全表扫描或传统 B+ 树索引的多次随机 I/O 要高效得多，尤其在 OLAP 大规模并行计算场景下，位运算的吞吐量很大。

BitWeaving

BitWeaving 项目由威斯康星大学 Quickstep 团队提出和实现，旨在在主内存分析型 DBMS 中以“裸机”速度运行全表扫描操作 。

它利用处理器的位级并行性，将来自多个元组和列的位在单个时钟周期内同时处理，从而将每列的扫描周期降低到低于 1 个周期的级别 。

为支持复杂谓词评估，BitWeaving 提出了算术框架，将列值编码转换为适合位操作的格式，并生成结果位向量，用于后续布尔组合运算 。

与传统列式存储的比较

  • 传统列式存储：将压缩后或原始列值按值连续存储，为了适配 SIMD 指令集，通常需要将每个值填充到固定边界（如 32 位、64 位），这会造成大量空间浪费，并增加对齐开销 。
  • SIMD 扫描：将多个字典编码值打包到 SIMD 寄存器槽中，利用向量指令并行比较，但依然存在填充浪费和对齐处理两个瓶颈 。
  • BitWeaving/V：将每个列值的同一比特位聚集存储，实现完整利用字宽，且通过“早期剪枝”可在满足或不满足条件时跳过后续比特的处理，极大减少处理位数和内存带宽 。
  • BitWeaving/H：将编码后的整值按交错方式存储，并在每个值中预留一位结果标记，既可支持快速位级扫描，也可在需要完整重构列值时一次性提取，兼顾扫描和输出需求 。

BitWeaving 包括两种主要存储布局：

  • BitWeaving/Vertical：按位平面（bit-plane）垂直存储，每个比特位平面连续排列，天然支持按位剪枝；
  • BitWeaving/Horizontal：按元组水平交错存储，附加一位用于记录谓词结果，便于整值提取和多阶段谓词级联

以下详细说明 Horizontal 和 Vertical Storage。

Horizontal storage

把每条记录的全部 k 位 code 串成一块，按记录依次存放。

在内存中，一个 SIMD 寄存器会同时装入多条记录的全部位，对这些记录做并行比较。

我们以某个整数类型的字段为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
Segment#1:
t0: bits=[0, 0, 1] -> 1
t1: bits=[1, 0, 1] -> 5
t2: bits=[1, 1, 0] -> 6
t3: bits=[0, 0, 1] -> 1
t4: bits=[1, 1, 0] -> 6
t5: bits=[1, 0, 0] -> 4
t6: bits=[0, 0, 0] -> 0
t7: bits=[1, 1, 1] -> 7

Segment#2:
t8: bits=[1, 0, 0] -> 4
t9: bits=[0, 1, 1] -> 3

以上内容中，t0 到 t9 为行号，bits 为该字段的二进制表示，箭头右边的是原始数据。全部的数据被分成了多个段。

假设一个处理器 word 只能容纳 8 个 bit 用于并行处理，那么以上代码块中的内容会被表示为如下结构：

img

[!NOTE]

Word 是处理器一次能够自然处理的固定长度数据单元，其长度称为字长（word length 或 word size），通常是处理器数据总线宽度的整数倍或分数。字长决定了CPU在单次操作中能读取、写入或传输的数据量，同时影响指令长度、寄存器宽度、寻址能力等关键特性。

如果要处理如下 SQL 指令：

1
SELECT * FROM tbl WHERE val < 5;

那么会进行如下 SIMD 计算（以 t0 和 t4 为例）：

img

最终，分割符为 1 的就是符合条件的数据。

但是之后我们需要如何汇总所有的过滤结果来确定要获取哪些数据呢？

我们可以通过 shift 操作输出所有的过滤结果到一个 bitmap 中，这个 bitmap 的每一位对应表中数据的行号。我们以 Segment#1 为例给出汇总过程：

img

上图中的位图也被称为 selection vector。

现在我们汇总得到了哪些数据符合条件以及哪些不符合，那要如何转成实际的下标或者是偏移量呢？

有两种常见的方法：

  1. 迭代扫描

    1
    2
    3
    4
    5
    6
    List<Integer> sel = new ArrayList<>();
    for (int i = 0; i < N; i++) {
      if (selectionVector[i] == 1) {
        sel.add(i);
      }
    }

    优点：实现简单，不需要预处理。

    缺点：每次都要检查 N 位，分支预测失效会有开销；对于高选择率或低选择率都要遍历全阵列。

  2. 预计算位置表

    把 selection vector（这里是 8 位）转换成十进制数据作为表的 key，而下标数组作为 payload。

    img

    优点：避免了每个位的分支判断，大大提高吞吐；字节级批量处理，利用了查表的连续读缓存。

    缺点：需要额外的 256 条查表开销，及存储这些小列表。

Vertical storage

把所有记录在同一位位置 i 上的 bit 聚到一起，形成一条长长的位向量，然后依次存放各个位向量（从最低位到最高位）。

在内存中，一个 SIMD 寄存器会拿到同一位向量的一大段数据，一次性对所有记录的该位进行逻辑运算。

还是用之前的例子，数据如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
Segment#1:
t0: bits=[0, 0, 1] -> 1
t1: bits=[1, 0, 1] -> 5
t2: bits=[1, 1, 0] -> 6
t3: bits=[0, 0, 1] -> 1
t4: bits=[1, 1, 0] -> 6
t5: bits=[1, 0, 0] -> 4
t6: bits=[0, 0, 0] -> 0
t7: bits=[1, 1, 1] -> 7

Segment#2:
t8: bits=[1, 0, 0] -> 4
t9: bits=[0, 1, 1] -> 3

在 Vertical Storage 中，以上数据会被表示为以下结构：

img

也就是说，同一 segment 的 bits 数组中的同一下标的数据会被放到一个 word 中处理。

如果我们要处理如下命令：

1
SELECT * FROM tbl WHERE val = 2;

会进行如下计算：

img

这里在处理完 col1 之后，我们观察到结果已经全是 0（即没有任何记录同时满足前两位匹配），就可以 跳过 第三轮比较（早剪枝），直接得出最终结果全 0。

优点：

  • 极高的查询性能：在 OLAP 场景下，Bit Weaving 能在压缩数据上直接进行位运算（如 AND、OR、XOR 等），极大提升聚合、过滤、排序等操作的速度。
  • 空间效率高：采用位存储和压缩技术，极大节省磁盘和内存空间，同时也减少了 I/O 成本。
  • 良好的向量化和 SIMD 支持：在现代 CPU（如 AVX、SSE）下可充分利用 SIMD 指令集，实现高并发、高吞吐量的位级操作。

缺点：

  • 对点查询不友好：相较于 B+ 树等结构，Bit Weaving 在单点查找或小范围查找时效率较低，主要优势在大范围数据扫描和聚合分析中。

近似位图索引

传统的位图索引对每一个值都精确地维护一个 bitmap，而近似位图索引只保留粗略信息，牺牲部分准确性（即可能出现 false positives，假阳性），以便在常见查询场景下更快速地过滤大部分不匹配的元组。

当位图判断某条记录可能匹配时，还需要回到原始数据进行最后一次精确检查，从而消除 false positives。

两种主流技术

  • Column Imprints（列印迹）

    将列值按块（如每 64 或 128 个值）划分，对每个块维护一个小位图，位图的每一位对应一个值范围（bucket）。

    查询时只需查块级位图，快速过滤掉整个块都不可能包含目标值的部分；再对剩余块逐条扫描。

    img

    或者更通用的方式是：

    在 Column Imprint 中，每个 0 或 1 表示的是缓存行中的信息。具体来说，每一位表示某个直方图区间是否在对应的缓存行中有数据值：

    • 如果缓存行中的某些值落入某个区间，则该区间对应的位被设置为 1；

    • 如果缓存行中的数据都不在该区间中，则该区间对应的位为 0。

    一个缓存行可以包含多个数据值（例如 64 字节的数据）。Column Imprint 并不记录每个数据值的精确位置，而是粗粒度地表示这些值的分布范围。

    同样用之前的例子，假设缓存行中有三个值：1，8，4。

    这些值会被映射到直方图的不同区间，例如：值 1 属于区间 [1, 2)；值 8 属于区间 [8, 9)；值 4 属于区间 [4, 5)。

    最终的位向量可能是 10010001，其中：第 1 位表示缓存行中有值落入区间 [1, 2)；第 4 位表示缓存行中有值落入区间 [4, 5)；第 8 位表示缓存行中有值落入区间 [8, 9)。

    如果之后要查询如 val BETWEEN 4 AND 8 → 对应要检查的 bins 为 B₃…B₇ → mask = 00011111：

    • 位向量 AND mask ≠ 0 → 说明该缓存行可能包含符合条件的值 → 需要回表做精确过滤；
    • 位向量 AND mask = 0 → 直接跳过整个缓存行。

  • Column Sketches（列摘要/草图）

    用固定长度码（通常只有几位）替代完整位图。每个记录只存一个小码，表示它属于哪几个预定义区间。

    整体流程如下：

    首先根据列的值分布，在直方图中将整个值域划分成若干区间。之后为每个区间分配一个固定长度的二进制码，每条记录的 sketch，就是它所属区间的那个短码。

    假设原数据为 [13, 191, 56, 92, 81, 140, 231, 172]，那么分布直方图和用于映射区间和 compression map 如下：

    img

    map 中的对应关系代表：小于 60 的数据映射到 00 代码，小于 132 大于 60 的数据映射到 01 代码，以此类推。

    因此原数据对应的 sketched column 为：[‘00’, ‘11’, ‘00’, ‘01’, ‘01’, ‘10’, ‘11’, ‘11’]。

    此时，如果我们要执行如下命令：

    1
    SELECT * FROM tbl WHERE val < 90;

    首先会确定要在区间 [0, 60] 和 (60, 132] 中找数据，接着对于代码为 00 的数据可直接确定为符合条件，对于代码为 01 的数据则要回表查看实际数据是否小于 90。

    也就是，对于 [‘00’, ‘11’, ‘00’, ‘01’, ‘01’, ‘10’, ‘11’, ‘11’] 中的 01，我们要查看原数据，分别是 92 和 81，92 > 90，因此排除掉 92，保留 81。