4. 2025题目四：查询优化¶

¶

前置题目：查询执行¶

题目种类：基础功能

代码框架：https://gitlab.eduxiji.net/csc1/csc-db/db2025/-/tree/main/rmdb

** **

题目描述:¶

查询优化是数据库系统中的重要组成部分，其目标是在保证查询结果正确性的前提下，通过改写 SQL 语句或调整执行计划，减少中间数据量、降低计算开销，从而提高查询执行效率。本题要求实现一个简化版的查询优化器，能够生成规范的查询计划树。

具体来说，我们要求实现以下三种优化：

基于规则的选择运算下推（谓词下推）。选择运算下推要求在查询计划树中，利用选择运算与投影运算，以及选择运算与笛卡尔积的交换律等，通过交换节点在树中的位置，尽可能将选择运算对应的节点放到查询计划树的底层。其目的是：尽可能早地过滤掉与后续操作无关的行，避免中间结果生成后再进行过滤所带来的额外开销。选择运算下推有助于减少中间数据中不必要的行，降低中间数据的传递和处理量，从而提高查询效率。
基于规则的投影运算下推。同上，投影运算下推要求在查询计划树中，利用投影运算与笛卡尔积的分配率，以及投影的串接定律等，通过交换节点在树中的位置，尽可能地先执行查询中的投影操作。其目的是：尽可能早地去除与后续操作无关的列，避免中间结果生成后再进行投影所带来的额外开销。投影运算下推有助于减少中间数据中不必要的列，可以显著降低数据传输和处理的开销。
基于简单代价估计的连接顺序优化。连接顺序优化是指在涉及多表连接的查询中，通过调整表的连接顺序，减小中间结果的大小，以降低查询的执行代价。本题要求实现以下连接顺序优化策略：

a. 采用左深树结构组织多表连接

b. 使用贪心算法选择连接顺序，具体规则如下：

- 首先选择基数最小的两个表作为初始连接

- 之后每次从剩余表中选择一个表加入，使得连接后的中间结果基数最小

- 表的基数指表中的行数，通过存储模块获取，需自行设计

c. 在连接顺序确定后，仍需应用选择运算下推和投影下推规则进行优化

对于本题，我们默认采用嵌套循环连接算法(Nested Loop Join)，并假设数据均匀分布。

要求：在现有SQL查询语句的基础上，增加对EXPLAIN关键字的支持，基于下列所述的规范格式，显示优化后的查询计划树内容。题目的输入为EXPLAIN + SQL查询语句，输出需要采用树状结构展示SQL查询计划，利用缩进 (在输出中为\t) 表示节点层级关系，每个节点包括算子类型和相关属性。

本题目共需实现四种查询计划节点：

- Scan：表扫描节点；- Filter：过滤节点（对应选择运算）；- Project：投影节点；- Join：连接节点

具体算子规范¶

节点类型	格式	备注
Scan节点	Scan(table=表名)	即叶节点
Filter节点	Filter(condition=[条件1,条件2,...])	1.确保谓词的左值是表的列，多个条件按字典序排序2.条件中的列名必须包含表名前缀（多表查询时）
Project节点	Project(columns=[表名1.列名1,表名2.列名2,...])	1.列名按字母顺序排序2.多表查询时使用表名前缀3.需要保留全部的列则输出Project(columns=[*])4.对于select语句根节点一定是Project节点
Join节点	Join(tables=[表名1,表名2,...], condition=[条件1,条件2,...])	1.表名按字母顺序排序，表名为此节点下所有表的集合2.连接条件按字典序排序

同一层级下的多个节点，按照字典升序输出，即先按照Filter Join Project Scan的顺序输出，同类型的节点，Scan节点和Join节点按照table升序输出，Filter按照条件的字典序升序输出，Project节点按照“表名.列名”升序输出。所有的列输出时均要先输出各自的表名，如果表有别名，则使用别名。Condition的输出格式和原始的SQL语句保持一致。

测试示例:¶

输入：

EXPLAIN SELECT a, b FROM t WHERE a > 1 AND b < 10;

输出：

Project(columns=[t.a,t.b])

Filter(condition=[t.a>1,t.b<10])

Scan(table=t)

测试点1：选择运算下推

测试示例：

CREATE TABLE orders (

order_id int,

customer_id int,

order_date char(40),

total_amount float

);

CREATE TABLE customers (

customer_id int,

name char(50),

email char(100),

address char(200)

);

EXPLAIN SELECT * FROM customers c

JOIN orders o ON c.customer_id = o.customer_id

WHERE o.total_amount > 1000;

期望输出：

Project(columns=[*])

Join(tables=[customers,orders],condition=[c.customer_id=o.customer_id])

Filter(condition=[o.total_amount>1000])

Scan(table=orders)

Scan(table=customers)

测试点2：投影下推

测试示例：

CREATE TABLE orders (

order_id int,

customer_id int,

order_date char(40),

total_amount float

);

CREATE TABLE customers (

customer_id int,

name char(50),

email char(100),

address char(200)

);

EXPLAIN SELECT c.name, o.order_id

FROM customers c

JOIN orders o ON c.customer_id = o.customer_id;

期望输出：

Project(columns=[c.name,o.order_id])

Join(tables=[customers,orders],condition=[c.customer_id=o.customer_id])

Project(columns=[c.customer_id,c.name])

Scan(table=customers)

Project(columns=[o.customer_id,o.order_id])

Scan(table=orders)

测试点3：连接顺序优化（在进行连接顺序优化后，需要支持选择运算下推和投影下推）

测试示例：

CREATE TABLE orders (

order_id int,

customer_id int,

order_date char(40),

total_amount float

);

CREATE TABLE products (

product_id int,

name char(50),

price float

);

CREATE TABLE order_items (

order_id int,

product_id int,

quantity int

);

注：此处省略表插入的完整过程，插入后的metadata如下

customers: 50 行记录

orders: 200 行记录

order_items: 1000 行记录

products: 20000 行记录

EXPLAIN SELECT * FROM customers c

JOIN orders o ON c.customer_id = o.customer_id

JOIN order_items oi ON o.order_id = oi.order_id

JOIN products p ON oi.product_id = p.product_id

WHERE o.total_amount > 200;

期望输出：

由于采用嵌套循环连接算法并假设数据均匀分布，选择根据表的条目从低到高进行连接。确定连接顺序后应用规则选择运算下推。

Project(columns=[*])

Join(tables=[customers,order_items,orders,products],condition=[oi.product_id=p.product_id])

Join(tables=[customers,order_items,orders],condition=[o.order_id=oi.order_id])

Join(tables=[customers,orders],condition=[c.customer_id=o.customer_id])

Filter(condition=[o.total_amount>200])

Scan(table=orders)

Scan(table=customers)

Scan(table=order_items)

Scan(table=products)