DS4.2 Query 相关 设计
2025-4-11
| 2025-4-12
Words 4437Read Time≈ 12 min
type
status
date
slug
summary
tags
category
icon
password

QueryOperator 设计

notion image
这个 QueryOperator 抽象类是一个典型的关系型查询执行计划中**逻辑算子（Logical Operator）**的抽象基类，设计上体现了以下几个核心思想与目标：

核心职责与设计思想

1. 职责明确：抽象代表“关系代数操作符”

每个 QueryOperator 对应一个数据库执行计划中的一个操作符（如投影、选择、连接等）。类中的方法和字段围绕以下内容展开：
  • 操作类型（OperatorType）识别
  • 与其他操作符之间的连接（source）
  • 输出模式/结构（Schema）
  • 查询记录迭代（iterator()）

2. 可组合性：构建操作符链条

通过 source 字段支持链式连接（例如：SELECT → JOIN → PROJECT），实现一个查询操作链（即查询执行计划树/图）：

3. 支持不同类型操作符的多态行为

用 OperatorType 枚举表示操作符类型，同时提供 isSelect()、isJoin() 等便捷方法进行类型判断，方便优化器或执行器进行分支处理。

类的结构详解

成员
说明
source
上游数据源，构成操作符链
outputSchema
该操作输出的字段结构（列名、类型等）
stats
估计的统计信息，如记录数、分布等（用于优化）
type
当前操作符类型（如 SELECT、JOIN）

方法功能概览

Schema & 连接

  • computeSchema()：抽象方法，子类实现时根据自身逻辑和 source 推导输出 schema。
  • setSource()：设置 source 并重新计算 outputSchema。
  • getSchema() / getSource()：获取 schema 与上游操作符。

类型判定

  • isJoin(), isSelect(), isProject() ...：通过枚举值判断类型，提升可读性和处理灵活度。

执行与物化

  • iterator()：抽象方法，获取记录迭代器，定义核心执行逻辑。
  • materialized() / materialize()：是否是物化操作符，如果不是，可以封装成 MaterializeOperator。

工具方法

  • getBlockIterator(...)：按页读取一定数量记录形成支持回溯的迭代器（用于块嵌套连接等算法）。
  • backtrackingIterator()：可选的回溯支持（默认不支持）。

成本估算（供优化器使用）

  • estimateStats()：估算输出记录的统计信息（记录数、分布等）。
  • estimateIOCost()：估算 I/O 成本。

抽象设计优点

  • 统一接口：所有子类（如 SelectOperator, JoinOperator, GroupByOperator 等）都基于统一接口扩展，便于组合和替换。
  • 可扩展性强：添加新类型操作符只需继承并实现少量方法。
  • 面向优化器设计：支持估算成本（统计和 I/O），为查询优化提供输入。
  • 可插拔执行策略：子类可实现不同的迭代方式（如嵌套循环 join、索引 scan 等）。

典型子类预期行为（举例）

子类
computeSchema()
iterator()
特点
SelectOperator
返回与 source 相同的 schema
返回过滤后的记录迭代器
WHERE 条件
ProjectOperator
只保留部分列
返回映射后的记录迭代器
SELECT 子句
JoinOperator
合并两个 schema
返回连接后记录
可实现嵌套或索引连接
GroupByOperator
分组键 + 聚合列
返回聚合结果
支持 HAVING、聚合函数

总结评价

这个 QueryOperator 类设计非常符合数据库系统中逻辑查询执行框架的标准模式：
  • ✅ 抽象清晰（关系代数式的操作符建模）
  • ✅ 支持组合、继承和成本估算（适配优化器和执行器）
  • ✅ 支持 iterator-based iterator model（流式查询处理）
  • ✅ 可扩展（新增操作符/执行方式不影响主框架）

QueryPlan 设计

这段 QueryPlan 类的代码是一个简化版 SQL 查询优化器和执行器的实现框架。它主要承担的是从 SQL-like 命令构建逻辑查询计划（Query Plan），再经过若干变换执行成物理查询计划，最终产出结果的迭代器。我们可以从几个维度来讲解其设计逻辑：

总体结构定位

类职责：

QueryPlan 是构建、优化和执行查询计划的控制中心。用户通过调用方法如 select(), project(), join(), groupBy() 等“声明”查询内容，系统内部构建起对应的 QueryOperator DAG（有向无环图），在执行阶段选择最优路径。

成员变量的设计

这些变量体现了对 SQL 查询语义的映射：
字段
SQL 对应
说明
projectColumns, projectFunctions
SELECT 子句
支持列名和表达式
tableNames, aliases, cteAliases
FROM 子句与别名
管理数据源与表名映射
joinPredicates
INNER JOIN
保存连接条件
selectPredicates
WHERE 子句
保存选择条件
groupByColumns
GROUP BY
保存分组列
sortColumn
ORDER BY
只支持一个列排序
limit, offset
LIMIT, OFFSET
记录截取控制
finalOperator
最终构建的逻辑执行计划
一个 QueryOperator DAG 的根节点
transaction
执行上下文
数据库运行时支持的事务环境

方法设计逻辑详解

1. SQL 映射构建阶段

用户通过如下方法构建查询内容：
  • project(...)：声明 SELECT 的投影列或表达式；
  • select(column, op, value)：声明 WHERE 条件；
  • join(...)：声明 INNER JOIN；
  • groupBy(...)：声明 GROUP BY；
  • sort(...) / limit(...)：声明排序与限制。
这些方法并不会立即构建 Operator，而是记录信息以延迟执行。

2. 执行计划构建阶段

执行逻辑主要由 execute() 和 executeNaive() 两种方式实现：

executeNaive()：直接构建执行计划（按操作顺序）

类似手动拼装的计划 DAG，顺序是：
代码中使用 finalOperator 逐步“包裹”上层算子，形成一个迭代器链条。execute()：System R 风格的代价优化器（TODO 实现）
这一方法应当实现基于 System R 的查询优化流程：
  • Pass 1：对每张表，选择最低成本的访问方式（Index Scan 或 Seq Scan）；
  • Pass i (i ≥ 2)：动态规划遍历所有表集合，尝试各种 Join 顺序，找最优；
  • 最终计划：找到包含所有表的最低代价 Operator，再加上 GroupBy、Project 等后续操作。

3. 计划优化相关方法

单表访问选择

考虑 SequentialScan vs IndexScan，选择最低 IO 成本的方式并 push-down 可用的 Select 条件。

Join 选择

在 SNLJ（嵌套循环）和 BNLJ（块嵌套）之间选择最低成本的实现。

动态规划 Join 顺序

基于前一轮 pass 的表集合，尝试加入新的表构建 Join DAG，保留最优代价路径。

辅助类设计

SelectPredicate 和 JoinPredicate 是谓词封装类：

类
对应语义
用途
SelectPredicate
table.col op value
封装 WHERE 条件逻辑
JoinPredicate
LEFT.col = RIGHT.col
表示 JOIN 的等值连接条件，便于构建逻辑连接树

设计亮点

  • 模块清晰：将 SQL 各部分独立拆解，按阶段组合。
  • 逻辑/物理算子分离：逻辑层（QueryPlan）不直接执行，构建的是 QueryOperator 树。
  • 支持延迟优化：只在 execute() 时确定最终 Operator。
  • 抽象灵活：留有大量 TODO/扩展点，适合教学/实验用。

总结：系统性 SQL 执行计划生成器

QueryPlan 的设计提供了一个微型的“SQL 查询引擎”，它的实现思路如下：
SQL 声明 → 内部表达式存储 → 构建 Operator 树 → 查询优化（可选）→ 生成执行迭代器

common/iterator

BacktrackingIterator<T> 接口设计要点

这个接口扩展了 Java 的 Iterator<T>，加入了**标记-重置（mark-reset）**机制。它的设计意图是让某些算法（如块嵌套循环连接、排序合并连接等）能够回溯读取过的数据，避免重新扫描整个表。

使用示例解释

你给的示例运行行为如下：
notion image

接口常见方法（概念性）

ArrayBacktrackingIterator<T> 实现

这是一个标准实现类，它接收一个数组或列表（List），并记录迭代位置和标记点。

内部机制大致如下：

  • 用一个 int cursor 指针记录当前迭代位置；
  • 用一个 int mark 保存上一次 markPrev() 或 markNext() 的位置；
  • reset() 时把 cursor = mark；
  • 对 hasNext() 和 next() 的实现就像普通迭代器。

应用场景

  • 块嵌套循环连接（BNLJ）：内层表的扫描在外层每个块后需要“重置”回开头；
  • Sort-Merge Join：扫描时需要回退某一段排序区间；
  • GroupBy 实现时对连续 group 的处理。
 

query/QueryOperator.java

描述了这个项目里执行 SQL 查询背后的逻辑查询算子的分层设计理念。我来帮你整理一下重点脉络，并指出这个结构对你编程/调试有什么帮助：

核心设计理念：算子树（Query Operator DAG）

一个 SQL 查询（如 SELECT * FROM A JOIN B WHERE A.x > 5 ORDER BY A.y）在系统中会被转化为一个操作符树（或 DAG），其中每一个操作都对应一个继承自 QueryOperator 的对象。
所有操作符都实现了：
意味着它们都可以通过 iterator() 返回一批 Record 进行遍历。

操作符分类

1. 扫描算子（Scan Operators）

从磁盘读取表数据，是所有查询的入口：
类名
功能
SequentialScanOperator
顺序扫描整个表，读取所有记录
IndexScanOperator
利用已有索引，只扫描满足某个谓词的记录（如 col >= 2020）
你只需要传入表名、列名、操作符和目标值，它就帮你用索引高效返回匹配的行。

2. 连接算子（Join Operators）

位于 query/join 目录，是你 Part 1 的重点！这些算子将多个表的行组合起来，方式包括：
类名
功能
SNLJOperator
Simple Nested Loop Join
BNLJOperator
Block Nested Loop Join
JoinOperator
抽象父类，提供辅助方法和基础字段
提示：你不应该直接操作 Table 或 TransactionContext，而是通过 JoinOperator 中已有的方法调用。

3. 专用算子（Special Operators）

用于完成某一特定的查询语义：
类名
功能
SelectOperator
实现 σ（选择）操作。保留满足 WHERE 条件的记录
ProjectOperator
实现 π（投影）操作。只保留指定的列
SortOperator
返回排序后的记录。你会在 Part 1 中实现它

4. 其他算子（辅助 / 测试用）

类名
功能
MaterializeOperator
把数据写到临时表中并立即“物化”，用于控制 I/O 测试
GroupByOperator
按字段分组记录并插入 MarkerRecord。项目中不需要实现

使用方式与组合（例子）

假设有如下 SQL 查询：
这个查询在代码层面会被转化为如下算子链（构成一棵执行树）：

编程建议

目的
推荐做法
写连接算法
只继承 JoinOperator，使用它提供的工具函数
想测试某个操作的输出
给它调用 iterator()，直接打印每条 Record
需要做调试
打印 toString() 会自动格式化整个执行计划
想要控制 I/O 执行顺序
用 MaterializeOperator 强制 materialize 中间结果
想要优化性能
在 minCostSingleAccess 中用 IndexScanOperator 替代 SequentialScanOperator

结尾建议

你正在构建的是一个简化版的数据库查询执行引擎，QueryOperator 是它的“执行指令层”，QueryPlan 则是它的“构建与优化层”。
类比来说：
QueryPlan 就是“SQL 编译器”，负责从 SQL 语句构建出一个优化后的执行图。
QueryOperator 是“执行器”，每个节点知道如何按规则去执行。

query/aggr 目录的作用

这个目录下的类用于实现 SQL 中的各种聚合函数，例如：
SQL 聚合函数
可能对应的类
COUNT(*)
CountFunction
SUM(col)
SumFunction
AVG(col)
AvgFunction
MIN(col)
MinFunction
MAX(col)
MaxFunction
这些类通常会定义：
  • 如何“接收”一个记录；
  • 如何“累加”；
  • 如何在最后“输出”一个聚合值。

为什么说它是非必需的？

  • 在你当前项目的重点（如连接算法、索引选择、排序）中，不需要处理 SQL 中 GROUP BY + AGG() 的情况；
  • ProjectOperator 虽然有一个字段 projectFunctions，支持聚合表达式，但这部分逻辑是后续扩展或 bonus 部分，不影响主线任务；
  • 如果你查看 GroupByOperator，它也会依赖这些函数，但同样是“不会被调用”的路径（unless for testing or extension）。

如果你想浏览，可以了解：

  1. 每个聚合函数类都实现了统一接口，比如：
    1. GroupByOperator 可能会使用它们，将一组记录分组并传给聚合函数；
    1. 它们提供了扩展的设计：你可以自行实现 MEDIAN()、STDDEV() 等。

    总结

    你要做的
    与 aggr 的关系
    实现 Join、Sort、Select、Project 等逻辑
    ❌ 不需要 query/aggr 中的类
    实现 GroupBy 和聚合输出
    ✅ 会用到（扩展部分）
    对数据库系统感兴趣，想了解聚合函数如何实现
    ✅ 可以阅读学习，但非必需

    query/QueryPlan.java

    notion image

    Volcano Model（火山模型）

    概念

    每个算子（operator）只在需要下一条输出时，向下请求（pull）下一条输入元组（tuple）。这种模型类似“逐层往下烧”的流水线。

    图中执行流：

    对应的执行链如下：
    每当最上层的 next() 被调用（如用户请求下一条记录），整条链就会自下而上懒惰地拉数据。

    QueryPlan 的职责

    1. QueryPlan 是一个“执行计划构建器”

    你不会直接操作 SelectOperator, JoinOperator 等类，而是：
    最终将这些操作按顺序构建成执行树（如图）。

    2. 执行方式：execute vs executeNaive

    • 当前实现中 execute() = executeNaive()，不考虑代价，仅按添加顺序连接；
    • 在 Part 2 中，你将替换 execute()，使用 System R 优化器构建更优执行计划。

    SelectPredicate 类回顾

    每一个 WHERE 子句条件都变成一个 SelectPredicate。

    JoinPredicate 类回顾

    每一个 INNER JOIN 的 ON 条件都会变成一个 JoinPredicate。

    总结

    关键词
    说明
    Volcano Model
    一种延迟拉取数据的执行模型，操作符之间逐层向下拉取元组
    QueryPlan
    SQL 构建器，把用户调用转换为一个 Operator 树（DAG）
    Operator 树
    每个节点是一个继承自 QueryOperator 的执行算子
    SelectPredicate
    表示 WHERE 子句中一条选择条件
    JoinPredicate
    表示 ON 子句中的一条连接条件
    execute()
    最终返回一个 iterator，懒惰地产生记录

    对应 SQL 查询：

    Mermaid 执行图代码：

    效果说明：

    • 算子从上到下组成一个 火山模型的执行树；
    • 数据是从底部开始流动（拉取记录），从两个 Sequential Scan 中获取元组；
    • Join 将符合 c = c 条件的记录组合；
    • Selection 过滤掉 d <= 10 的元组；
    • Projection 最后只保留你 SELECT 的字段。

    查询接口使用流程（最小示例）

    输出说明（执行计划树）

    输出样例：
    这是基于 火山模型（Volcano Model） 的执行计划树，以缩进形式展现每一层算子：
    • 最顶层是 SNLJOperator（Simple Nested Loop Join）；
    • 它有两个子算子，分别是顺序扫描 S 表和 E 表；
    • 每个节点还带上了估计成本（estimateIOCost() 的返回值）。

    你可以用这个做什么？

    目的
    用法
    ✅ 检查是否使用了索引
    看是否有 IndexScanOperator
    ✅ 验证连接顺序是否优化
    看连接顺序、join 算子类型
    ✅ 判断是否正确加入 project/select/sort 等
    输出中应包含对应的 ProjectOperator, SelectOperator 等
    ✅ 辅助调试优化器实现
    比较 naive 和 optimize 模式的 plan 差异
    ✅ 测试 Part 2 实现
    execute() 中构建的计划结构直接反映优化器效果

    建议结合测试文件使用

    你可以查看测试例子里的这种结构：

    总结

    核心方法
    作用
    execute()
    构建并执行查询（返回 Iterator<Record>）
    getFinalOperator()
    获取逻辑执行计划根节点（Operator DAG）
    toString()
    展示完整的 Operator 结构与成本信息（缩进形式）

    query/disk

    你给的这段说明是关于 query/disk 目录下的两个核心类 —— Partition 和 Run 的设计目的和用法说明，它们是为了实现 基于磁盘的查询算法（比如 Grace Hash Join 和 External Sort）服务的。下面我来帮你详细解析它们在整个系统中所扮演的角色。

    背景：为什么需要 Partition 和 Run

    在内存有限时，某些数据库操作（比如连接、排序）不能把整个表加载进内存。于是就引入了：
    算法
    对应操作
    背后概念
    Grace Hash Join
    哈希分区连接
    Partition（分区）
    External Sort
    外部排序
    Run（有序运行）
    这两者都基于一种思想：将大数据分块（外存中）处理，每次只在内存中处理一页（page）。

    类别与作用

    Partition

    • 用于：Grace Hash Join 中的分桶（每个桶存到磁盘文件中）
    • 作用：
      • 提供 add(Record) 方法来向分区中写入数据；
      • 提供 iterator() 方法按顺序读取数据；
      • 使用内置缓冲控制，保证最多只在内存中保留一个 page；
    • 使用方式：
      • 第一次扫描输入表时，记录按哈希分配到不同 Partition；
      • 第二轮读这些 Partition 时，执行 join 操作。

    Run

    • 用于：External Sort 中的有序子文件（run）
    • 作用：
      • 每次只加载一个 page；
      • 提供插入和迭代器，支持从多个 run 归并；
      • 保证内部是“稳定排序的子文件”（比如每 5000 条记录构成一个 Run）；
    • 使用方式：
        1. 对内存能容纳的部分排序 → 存成一个 Run；
        1. 多个 Run 合并 → 更大的有序 Run；
        1. 最终输出结果。

    统一特点

    特性
    描述
    ✅ 支持 add(Record)
    插入记录时自动写入磁盘缓存区
    ✅ 支持迭代
    可以流式读取数据，一次只加载一个 page
    ✅ 遵循 iterator 接口
    可在外部用 for-each 或 while 迭代
    ✅ 后台 I/O 缓冲
    帮你隐藏磁盘 page 的读写细节

    示例用途简述

    Grace Hash Join 中使用 Partition：

    在后续阶段：

    External Sort 中使用 Run：

    归并多个 Run 时：

    总结

    类
    用于哪种算法
    关键词
    功能
    Partition
    Grace Hash Join
    Hash Bucket
    按分区写入+读出
    Run
    External Sort
    Sorted Sublist
    记录排序结果，支持归并
    它们的设计让你可以“放心地写算法逻辑，而不用担心磁盘 I/O 细节”。
    Relate Posts :
    数据库
  2. database
    3. Database System （五）DS4.1 关系代数操作符总结
    Loading...
    Catalog
    0%