数据库查询优化

ID: 730

Type: Default

1000ms

512MiB

Tried: 6

Accepted: 2

Difficulty: 10

Uploaded By:

CYMario

Tags>

CCSP

模拟

工程应用

编译原理

递归下降法

字符串处理

动态规划

子集DP

题目来自 CCSP2025 T4，评测使用官方数据。我们承认原始题面、大样例、官方数据版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

经核查，原始题面存在大量错误、未解释的歧义且未提供部分分数据范围，因此基于官方数据对题意进行大幅修正以及数据范围的补充。

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

在现代软件应用中，数据库扮演着至关重要的角色，它们如同海量数据的“中央图书馆”。为了从这个“图书馆”中高效地检索信息，我们使用一种名为 SQL（Structured Query Language）的“查询语言”。然而，对于同一个查询需求，数据库内部可以有多种执行方式，这些方式的效率天差地别，就像从图书馆找一本书，你可以逐层逐个书架地毯式搜索，也可以先通过索引系统定位到书架再寻找。一个优秀的数据库，其核心组件之一就是查询优化器，它的任务是在所有可能的执行路径中，选择成本最低、效率最高的一条。

本题目需要你扮演查询优化器的角色。我们先通过一个具体的例子来理解数据库是如何工作的。

在本题目中，我们将使用一种我们称之为 BaseSQL 的简化类 SQL 语言。

BaseSQL 定义

1. 核心结构

一个 BaseSQL 查询是一个选择-投影-连接（Select-Project-Join, SPJ）查询。它包含 SELECT、FROM 子句，可以包含 WHERE 子句。没有条件时可以省略 WHERE（如样例中的 SELECT COUNT(*) FROM Enrollments）。

SELECT T1.C1, T1.C2, T2.C1 AS C
FROM T1, T2, ...
WHERE condition1 AND condition2 AND ...

在 SELECT 子句中，投影列可以是以下形式之一：

*：表示选择所有列；
带表名前缀的列，如 T1.C2，则在结果表中，该列名字为 C2；
带显式别名的列，如 T1.C2 AS ColAlias 或 T1.C2 ColAlias（即 AS 可省略，二者语义完全相同），则在结果表中，该列名字为 ColAlias。

2. 表（ $T_i$ ）

在 FROM 子句中的“表”可以是以下两种之一：

一个数据库中的基表（如 Students）。同一基表可以在一个 FROM 中以不同别名出现多次；每次出现均为独立的表实例，行数、扫描代价和连接关系分别计算。
一个子查询，也就是另一个嵌套在括号内并赋予别名的 BaseSQL 查询。子查询可以包含投影列的显式别名；若使用 SELECT * 则继承底表或子查询的列名。子查询必须有别名；作为 FROM 项时，其输出列名应唯一，必要时通过列别名区分。不同 FROM 项之间可以有同名列，使用表名前缀区分；顶层 SELECT * 可以输出同名列。示例：
```
(SELECT Students.name AS student_name FROM Students WHERE Students.age = 21) AS SeniorStudents
```

这个子查询会首先被执行，其结果被视为外部查询的一个临时表。

表或子查询的别名可通过空格直接声明，如 FROM Students S，也可以使用 AS 关键字声明，如 FROM Students AS S；两种写法在本题中完全等价。引入别名后，后续条件中引用该表需使用别名（例如 S.student_id），这与引用原表名具有相同语义。

3. 条件

在 WHERE 子句中的“条件”是一个等值连接，意味着它只使用 = 操作符。它可以是：

两个表之间的连接条件：T1.columnA = T2.columnB。
与一个整数常量值比较的过滤条件：T1.columnC = 123。

4. 子链接（Sublink）

条件还可以是一个子链接，即一个列的值与一个聚合子查询的结果进行比较（列名一定在等号左边）。我们唯一支持的聚合是 COUNT(*)。需要注意的是，子链接的 WHERE 子句中最多只能有一个与外部查询相关的条件。

相关子链接：子链接的 WHERE 子句引用了外部查询表中的一个列。这意味着对于外部查询的每一行，子链接都必须被重新求值。

-- 对于每一门课程，子链接计算该特定课程的报名人数。
Courses.credits = (SELECT COUNT(*) FROM Enrollments E2 WHERE E2.course_id = Courses.course_id)

非相关子链接：子链接的 WHERE 子句不引用任何外部的表。它可以被计算一次，其结果可以被复用。

-- 子链接一次性计算出课程 '101' 的总报名人数。
T1.c1 = (SELECT COUNT(*) FROM Enrollments WHERE Enrollments.course_id = 101)

相关性检测和处理：
- 相关子链接：子链接的 WHERE 子句中包含对外部查询表的直接列引用
- 非相关子链接：子链接完全独立，不依赖任何外部查询的数据
- 相关性判断规则：检查子链接条件中引用的表是否属于当前查询作用域外的表
- 示例：
```
WHERE T1.c1 = (SELECT COUNT(*) FROM T2 WHERE T2.c2 = T1.c3)
```
  - T1.c3 是外部引用，因此这是一个相关子链接
  - 对于 T1 的每一行，都要用该行的 T1.c3 值重新计算子链接
重要约束 - 相关子链接的引用限制：
- 约束规则：在相关子链接中，子查询内部只能引用与子链接条件左侧相同的外部表。同时，该引用只能出现在子查询 WHERE 子句中，不会出现在 FROM 中的子查询中。限定列名先按当前查询块的 FROM 实例名绑定；当前块没有该实例时，才按相关子链接的限制查询直接父层。同名内层实例遮蔽外层实例，不能把当前层引用误判为相关引用。普通查询的投影与 FROM 子查询不能引用外层列。
- 正确示例：
```
SELECT * FROM T1
WHERE T1.col = (
  SELECT COUNT(*)
  FROM T2
  WHERE T2.x = T1.y)
```
  - 子链接条件左侧是 T1.col，子查询内部引用的是 T1.y，满足约束
- 错误示例：
```
SELECT * FROM T1, T3
WHERE T1.col = (
  SELECT COUNT(*)
  FROM T2
  WHERE T2.x = T3.y)
```
  - 子链接条件左侧是 T1.col，但子查询内部引用的是 T3.y，违反约束
- 错误示例:
```
SELECT * FROM T1, T3
WHERE T1.col = (
  SELECT COUNT(*)
  FROM T2, (SELECT * FROM T3 WHERE T1.x = T3.y))
```
  - 子链接条件左侧是 T1.col，但子查询内部引用的 T1.x 在 FROM 中，违反约束
  - 多表连接中的应用：在 SELECT * FROM T1, T2, T3 的查询中，如果有子链接 T1.a = (SELECT COUNT(*) FROM T4 WHERE ...)，则子查询内部的相关条件只能引用 T1 的列，不能引用 T2 或 T3 的列

5. 列引用规范

所有列引用必须以“表名或子查询别名. 列名”的形式书写；不允许未限定列名。例如：Students.age = 21，Enrollments.course_id = Courses.course_id。

6. 标识符大小写约定

SQL 关键字统一使用大写形式，包括 SELECT、FROM、WHERE、AND、AS、COUNT。表名、列名和别名按原拼写匹配，所有引用的拼写及字母大小写必须与对应声明完全一致。

实例中的 BaseSQL

下面让我们通过一个例子来继续介绍 BaseSQL。

1. 基础数据表

假设我们的大学数据库中有三张核心表：

Students（学生表）：存储学生信息。

`student_id`	`name`	`age`
1	Alice	21
2	Bob	20
3	Charlie	21
4	David	19

Courses（课程表）：存储课程信息。

`course_id`	`course_name`	`credits`
101	Math	2
102	Physics	3
103	History	2

Enrollments（选课表）: 记录学生选修了哪些课程。

`student_id`	`course_id`
1	101
1	103
2	102
3	101
	102
	103

2. 一个复杂的查询请求

现在，我们想提出一个有点复杂的需求：“找出所有年龄等于 21 岁的学生，他们所选修的课程中，有哪些课程的学分（credits）恰好等于选修该门课程的总人数？”

这个需求转换成我们的 baseSQL，是这样的：

SELECT *
FROM
    (SELECT
        Students.student_id,
        Students.name AS student_name,
        Students.age
     FROM Students
     WHERE Students.age = 21
    ) AS SeniorStudents,
    Enrollments,
    Courses
WHERE
    SeniorStudents.student_id = Enrollments.student_id
AND
    Enrollments.course_id = Courses.course_id
AND
    Courses.credits = (SELECT COUNT(*)
                       FROM Enrollments E2
                       WHERE E2.course_id = Courses.course_id);

这个查询包含了子查询、子链接和连接：

子查询（Subquery）：FROM 后面的 (SELECT Students.student_id, Students.name AS student_name, Students.age FROM Students WHERE Students.age = 21) AS SeniorStudents 就是一个子查询。数据库会先执行这个查询，生成只包含年龄等于 21 岁学生的临时表 SeniorStudents，其中姓名列重命名为 student_name，然后在后续操作中使用它。
连接（Join）：FROM 子句中列出了三个表（SeniorStudents、Enrollments、Courses），WHERE 子句中的 SeniorStudents.student_id = Enrollments.student_id 和 Enrollments.course_id = Courses.course_id 则是连接条件，用于将这三张表的数据按照正确的对应关系拼接起来。
相关子链接（Correlated Sublink）：WHERE 子句中最后的条件 Courses.credits = (SELECT COUNT(*) ...) 是一个典型的相关子链接。它的特殊之处在于，内部的子查询 (SELECT COUNT(*) ...) 并非只计算一次，而是“相关” 于外部的查询。对于外部查询处理的每一行数据，特别是每一行的 Courses.course_id，它都会被传入内部子查询中，重新计算一次选课人数。

3. 执行计划与执行过程

数据库有多种方式来执行上述查询，一个简单的执行计划可能是 Join(Join(SeniorStudents, Enrollments), Courses)。我们来看看它是如何一步步得到结果的。

Step 1：执行子查询

首先，执行

(SELECT
    Students.student_id,
    Students.name AS student_name,
    Students.age
 FROM Students
 WHERE Students.age = 21)

得到临时表 SeniorStudents，其中既保留列 student_id、age，也把 name 重命名为 student_name。

`student_id`	`student_name`	`age`
1	Alice	21
3	Charlie	21

Step 2：连接 `SeniorStudents` 和 `Enrollments`

将上一步的结果与 Enrollments 表根据 SeniorStudents.student_id = Enrollments.student_id 进行连接。

这个过程可以想象成一个嵌套循环：

// 伪代码
for rowA in SeniorStudents:
    for rowB in Enrollments:
        if SeniorStudents.student_id == Enrollments.student_id:
            output(rowA, rowB)

得到中间结果 Temp1，由于纸张宽度限制，SeniorStudents 缩写为 SS，Enrollments 缩写为 En，Courses 缩写为 Co，下同。Temp1 为：

`SS.student_id`	`SS.student_name`	`SS.age`	`En.student_id`	`En.course_id`
1	Alice	21	1	101
1	Alice		1	103
3	Charlie		3	101
				102
				103

Step 3：连接 `Temp1` 和 `Courses`

将上一步的结果 Temp1 与 Courses 表根据 Enrollments.course_id = Courses.course_id 连接，得到完全连接后的结果 Temp2。

`SS.student_id`	`SS.student_name`	`SS.age`	`En.student_id`	`En.course_id`	`Co.course_name`	`Co.credits`
1	Alice	21	1	101	Math	2
1	Alice		1	103	History
3	Charlie		3	101	Math
				102	Physics	3
				103	History	2

Step 4：应用相关子链接进行过滤

现在，对 Temp2 的每一行执行过滤条件 Courses.credits = (SELECT COUNT(*) FROM Enrollments E2 WHERE E2.course_id = Courses.course_id)。

对于第一行（Math）: Courses.credits 是 2。执行 SELECT COUNT(*) FROM Enrollments WHERE Enrollments.course_id = 101，结果是 2（Alice 和 Charlie 都选了）。2 == 2 为真，保留该行。
对于第二行（History）: Courses.credits 是 2。执行 SELECT COUNT(*) FROM Enrollments WHERE Enrollments.course_id = 103，结果是 2 (Alice 和 Charlie 都选了)。2 == 2 为真，保留该行。
对于第三行（Math）: 与第一行逻辑相同，2 == 2 为真，保留。
对于第四行（Physics）: Courses.credits 是 3。执行 SELECT COUNT(*) FROM Enrollments WHERE Enrollments.course_id = 102，结果是 2（Bob 和 Charlie 选了）。3 == 2 为假，丢弃该行。
对于第五行（History）: 与第二行逻辑相同，2 == 2 为真，保留。

Step 5：最终结果

经过过滤后，最终的查询结果为：

`SS.student_id`	`SS.student_name`	`SS.age`	`En.student_id`	`En.course_id`	`Co.course_name`	`Co.credits`
1	Alice	21	1	101	Math	2
1	Alice		1	103	History
3	Charlie		3	101	Math
3	Charlie		3	103	History

这个例子展示了数据库执行查询的复杂性。不同的连接顺序（比如先连接 Courses 和 Enrollments）会产生不同的中间结果大小和计算成本，而你的任务就是找到那个“最优”的顺序和方法。

题目描述

在本题中，你需要读取并解析一个简化版的 SQL 查询（baseSQL），并为该查询找出一个最优的执行计划。执行计划决定了表的连接顺序和连接算法，你的目标是使整个查询的总执行代（Cost）最小。

核心概念定义

表（Table）：数据库中的基础数据单元，我们用 $T_i$ 表示第 i 张表。
列（Column）：表中的一个字段，用 $T_i.C_j$ 表示表 $T_i$ 的第 j 列。
行数（Rows）：一个表或一个中间结果中包含的数据行数，表示为 $Rows(T)$ 。
NDV（Number of Distinct Values）: 某一列中不重复值的数量，表示为 $NDV(T.C)$ 。例如，Enrollments 表的 course_id 列值为 (101, 103, 102,101, 102, 103)，其 NDV 为 3。

执行计划

一个执行计划是一棵二叉树，其叶子节点是表，内部节点是连接操作。我们支持两种连接操作：哈希连接（Hash Join） 和 嵌套循环连接（Nested Loop Join）。计划由一个嵌套表达式表示，例如 H(L(T1, T2), T3)。

计划空间枚举要求

完整枚举：必须枚举所有可能的连接顺序，包括左深树、右深树和 bushy 树结构
算法选择：对每个连接操作，必须同时考虑哈希连接和嵌套循环连接两种算法
最优计划：在所有可能的计划中选择总代价最小的方案

代价模型

查询的执行过程被分解为一系列的过滤（Filter） 和 连接（Join） 操作，每个操作都会产生新的中间结果（其行数需要估算），并带来一定的执行代价。代价的计算需要进行“行数估算”和“操作代价”计算。

1. 行数估算（Cardinality Estimation）

过滤（Filter）

对一个表 $T_i$ 应用过滤条件 $T_i.C_j=constant$ ，过滤后的期望行数为：

Rows(FilteredT_i)=Rows(T_i)/NDV(T_i.C_j)

解释：这假设了数据是均匀分布的。如果一个列有 $100$ 个不同的值，那么筛选其中任何一个特定值的记录，期望会得到总行数的 $1/100$ 。
多个等值过滤的累积效应：当同一表存在多个等值过滤条件（包括常量等值与子链接等值）时，对行数按各自列的 NDV 依次独立缩减；若多次作用于同一列，则按该列的 NDV 再次缩减。例如： $Rows=Rows/NDV(c_1)/NDV(c_2)/\ldots$ ；若同列两次等值，则 $Rows=Rows/NDV(c)/NDV(c)$ 。
这种计算方法也适用于子链接过滤。因为在子语句执行完之后，等号右边的值已经确定，子链接会变化为 $T_i.C_j=constant$ 的形式。

连接（Join）

对两个节点 A 和 B（A 和 B 自身可以是基础表或已连接的中间结果）进行连接，连接条件为 $A.C_a=B.C_b$ 。

选择率（Selectivity）：首先，定义单个连接条件的“选择率”，它表示数据能通过该条件过滤的概率。 $Sel(A.C_a=B.C_b)=1/\max(NDV(A.C_a),NDV(B.C_b))$
连接后行数：连接后产生的期望行数为：$Rows(A\bowtie B)=Rows(A)\times Rows(B)\times Sel_1\times Sel_2\times\ldots$。其中 $Sel_1,Sel_2,\ldots$ 是所有应用在节点 A 和 B 相关表之间的连接条件的选择率。如果没有连接条件（即笛卡尔积），则 $Rows(A\bowtie B)=Rows(A)\times Rows(B)$ 。
注意：行数可以是浮点数，因为它代表的是一种数学期望。
统计量的继承与条件计数： 本题只按所给模型估算，不根据实际 SQL 结果修正统计量。过滤、连接和普通投影均不更新或裁剪列的 NDV；子查询投影或重命名后，列的 NDV 沿其来源继承。每条过滤条件按出现次数独立生效，包括完全相同的重复条件；不得通过去重、矛盾检测或传递推理消除条件。

2. 操作代价（Cost Calculation）

扫描/过滤代价

在 SQL 执行时，会首先对所有 FROM 中的表（包含子查询产生的临时表）进行扫描，并在扫描过程中进行过滤。对于每个表 $T_i$ ，其扫描/过滤代价为：

$$\begin{aligned} Cost(Filter(T_i))={}&Rows(T_i)\times0.1 &&\text{（基础 I/O 扫描代价）}\\ &+\sum_{\text{相关子链接}}Rows(T_i)\times Cost(\text{相关子链接}) &&\text{（对每一行计算相关子链接）}\\ &+\sum_{\text{非相关子链接}}1\times Cost(\text{非相关子链接}) &&\text{（非相关子链接只需计算一次）} \end{aligned}$$

不论 WHERE 中是否有与 $T_i$ 表相关的过滤，均需要对其进行扫描。若 WHERE 中有该表相关的子链接，则需要额外考虑子链接的代价。

若 $T_i$ 是 FROM 中的子查询，应先计入该子查询自身的最优总代价，再按其输出行数计入外层扫描代价。相关子链接的调用次数使用所属表扫描前的行数，不使用其他过滤后的行数。

子链接的代价

即 $Cost(\text{相关子链接})$ 与 $Cost(\text{非相关子链接})$ 部分，这部分 = 按照子语句生成结果表的代价 + 对结果表进行聚合的代价。

例如，对于子链接条件 T1.c1 = (SELECT COUNT(*) FROM T2 WHERE T2.c2 = T1.c3)，其子链接的代价为 $Rows(T_2)\times0.1+Rows(T'_2)\times0.05$ ，由两部分组成：

生成结果表格，相当于执行 SELECT * FROM T2 WHERE T2.c2 = T1.c3，其代价为扫描表 $T_2$ 的代价： $Rows(T_2)\times0.1$
COUNT(*) 聚合的代价为 $Rows(T'_2)\times0.05$ ，其中 $T'_2$ 表示过滤后的 $T_2$ ，即上一步中执行后的结果表； $0.05$ 为聚合的代价系数。

相关条件的常量化：由于相关子链接由外表驱动，在对子链接进行每次求值时， $T_1.c_3$ 的具体取值已确定，因此 $T_2.c_2=T_1.c_3$ 被视为对 $T_2.c_2$ 的等值常量过滤。
相关子链接：由于外部列 $T_1.c_3$ 的值随 $T_1$ 的每一行变化，需要对 $T_1$ 的每一行重新计算整个子链接代价。
非相关子链接：子链接中的条件不依赖外部列，只需计算一次。
子链接对行数的影响：正如前面“行数估算”中所说，子链接条件 T1.c1 = (SELECT COUNT(*) ...) 被视为对列 $c_1$ 的等值过滤，会将表 $T_1$ 的行数按该列的 NDV 进行缩减： $Rows(T'_1)=Rows(T_1)\div NDV(T_1.c_1)$ （其中 $T'_1$ 表示过滤后的 $T_1$ ）。
在进行扫描时，会通过一次扫描处理完所有的过滤（包括子链接），因此公式中的 Rows(T_i) 为扫描时行数。
子链接内部的子查询如果包含更复杂的结构，需要递归应用本代价模型。

连接代价

我们支持两种连接算法。

哈希连接（Hash Join）：将表 A 的结果读入内存构建一个哈希表，然后流式读取表 B 的结果进行探测匹配。$$Cost(HashJoin(A,B))=Rows(B)\times1.5+Rows(A)\times3.5+Rows(A\bowtie B)\times0.1$$其中构建哈希表的代价为 $Rows(A)\times3.5$ ，探测匹配的代价为 $Rows(B)\times1.5$ ，结果扫描的代价为 $Rows(A\bowtie B)\times0.1$ 。
嵌套循环连接（Nested Loop Join）：对于表 A 中的每一行，遍历表 B 中的所有行进行匹配。$$Cost(NestedLoopJoin(A,B))=Rows(A)\times Rows(B)\times1.0+Rows(A\bowtie B)\times0.1$$其中 $Rows(A)\times Rows(B)\times1.0$ 是嵌套循环匹配的代价， $Rows(A\bowtie B)\times0.1$ 是结果扫描的代价。
总代价（Total Cost）：一个执行计划的总代价，等于其中所有操作的代价之和。

3. 最优计划代价

通过不断调整 Join 的方式和顺序，找到的总代价最低的执行计划。注意，本题目中不能通过对 WHERE 中条件的逻辑推理进行优化。换句话说，即使 WHERE T.a=1, T.b=T.a, T.b=2，也需要按部就班去做计算。

提示：先扫描表格并进行过滤，再将过滤后的表进行连接。

任务要求

给定数据库中所有表的统计信息（行数和每列的 NDV）以及一个 BaseSQL 查询。你需要：

解析 SQL，理解查询意图。
探索所有可能的执行计划（即不同的连接顺序和连接算法组合）。
使用上述代价模型计算每个计划的总代价。
找出那个总代价最小的最优执行计划，输出最终的估算行数和该计划的总代价。

一个执行计划可以用括号表达式表示，例如 H(L(T2, T3), T1) 表示先用嵌套循环连接 T2 和 T3，再将结果与 T1 进行哈希连接。

示例图解

对于计划 H(L(T1, T2), T3)，其执行树如下所示：

图例：

叶子节点：基础表或子查询
中间节点：连接操作（H = 哈希连接，L = 嵌套循环连接）
图中箭头从父节点指向子节点；实际求值顺序为自底向上，先执行子节点，再执行父节点。

执行流程：

T1 和 T2 通过嵌套循环连接（Nested Loop Join）生成中间结果
中间结果再与 T3 通过哈希连接（Hash Join）得到最终结果
该计划的 Total Cost 就是最终的执行代价值。

输入格式

从标准输入读入数据。

第一行包含一个整数 $N$ ，表示数据库中的基础表数量。

接下来 $N$ 个表的数据块，每个块：

第一行是表名 $T_i$ ，一个整数 $M$ 和 $R$ ，表示该表有 $M$ 列和 $R$ 行。
接下来 $M$ 行，每行是列名 $C_j$ 和该列的 NDV 值。

最后一部分是 SQL 查询，多行字符串，以分号 ; 结尾。SQL 规模限制：每层最多只有 12 个表，子链接和子查询的数量一共不超过 12。

输出格式

输出到标准输出。

输出一行两个浮点数，用空格隔开，分别表示最优计划的最终估算行数和总执行代价，保留两位小数。请使用精度不低于 double 的数据类型进行处理和输出，无需考虑不同数据类型在保留两位小数时四舍五入的差异。

3
Students 3 10000
student_id 10000
name 9500
age 80
Courses 3 100
course_id 100
course_name 100
credits 10
Enrollments 2 100000
student_id 100
course_id 100
SELECT *
FROM (
        SELECT *
        FROM Students
        WHERE Students.age = 21
    ) AS SeniorStudents,
    Enrollments,
    Courses
WHERE SeniorStudents.student_id = Enrollments.student_id
    AND Enrollments.course_id = Courses.course_id
    AND Courses.credits = (
        SELECT COUNT(*)
        FROM Enrollments E2
        WHERE E2.course_id = Courses.course_id
    )
    AND Courses.credits = (SELECT COUNT(*) FROM Enrollments);

12.50 1133061.25

样例 1 解释

1. 节点 `SeniorStudents`（先执行子查询，再扫描其结果）

行数 $=10000\div80=125$
子查询内部扫描 Students 的代价 $=10000\times0.1=1000$
外层扫描临时表 SeniorStudents 的代价 $=125\times0.1=12.5$
该节点的累计代价 $=1000+12.5=1012.5$

2. 节点 `Enrollments`（基表扫描）

行数 $=100000$
代价 $=100000\times0.1=10000$

3. 节点 `Courses`（带相关 + 非相关子链接的筛选）

基础行数 $=100$
子链接基数缩减：credits 列出现两次等值子链接（一次相关、一次非相关）
筛选后行数 $=100\div10\div10=1$ （credits 的 NDV $=10$ ）
代价 $=cost(\text{scan})+cost(\text{correlated sublink})+cost(\text{non-correlated sublink})$
- $cost(\text{scan})=100\times0.1=10$
- 相关子链接（针对每个 course_id 一次）：
  - 扫描 Enrollments： $100000\times0.1=10000$
  - 相关过滤后行数： $100000\div100=1000$
  - COUNT 聚合： $1000\times0.05=50$
  - 单次子链接代价： $10000+50=10050$
  - $cost(\text{correlated})=100\times10050=1{,}005{,}000$
- 非相关子链接（仅一次）：
  - 扫描 Enrollments： $100000\times0.1=10000$
  - COUNT 聚合： $100000\times0.05=5000$
  - $cost(\text{non-correlated})=10000+5000=15000$
- 总代价 $=10+1{,}005{,}000+15000=1{,}020{,}010$

4. 执行计划对比分析

枚举所有可能的连接顺序和连接算法组合后，对比两个代表性方案：

方案 A（最优）：H(SeniorStudents, L(Enrollments, Courses))

步骤 1：嵌套循环连接 Enrollments 和 Courses
- 输入行数：100000（Enrollments）、1（Courses 过滤后）
- 连接选择性： $1\div\max(100,100)=1\div100$
- 输出行数： $100000\times1\times(1\div100)=1000$
- 代价：$cost(\mathrm{Enrollments})+cost(\mathrm{Courses})+Rows(\mathrm{Enrollments})\times Rows(\mathrm{Courses})\times1.0+Rows(\mathrm{result})\times0.1$
- 代价：$10000+1020010+100000\times1.0+1000\times0.1=1130110$
步骤 2：哈希连接 SeniorStudents 和中间结果
- 输入行数：125（SeniorStudents）、1000（中间结果）
- 连接选择性： $1\div\max(10000,100)=1\div10000$
- 输出行数： $125\times1000\times(1\div10000)=12.5$
- 代价：$cost(\mathrm{SeniorStudents})+cost(\mathrm{intermediate})+Rows(\mathrm{intermediate})\times1.5+Rows(\mathrm{SeniorStudents})\times3.5+Rows(\mathrm{result})\times0.1$
- 代价：$1012.5+1130110+1000\times1.5+125\times3.5+12.5\times0.1=1133061.25$
方案 A 总代价： $1133061.25$

方案 B（另一非最优方案）：H(H(Courses, Enrollments), SeniorStudents)

步骤 1：哈希连接 Courses 和 Enrollments
- 输入行数：1（Courses 过滤后）、100000（Enrollments）
- 连接选择性： $1\div\max(100,100)=1\div100$
- 输出行数： $1\times100000\times(1\div100)=1000$
- 代价：$cost(\mathrm{Courses})+cost(\mathrm{Enrollments})+Rows(\mathrm{Enrollments})\times1.5+Rows(\mathrm{Courses})\times3.5+Rows(\mathrm{result})\times0.1$
- 代价：$1020010+10000+100000\times1.5+1\times3.5+1000\times0.1=1180113.5$
步骤 2：哈希连接中间结果和 SeniorStudents
- 输入行数：1000（中间结果）、125（SeniorStudents）
- 连接选择性： $1\div\max(10000,100)=1\div10000$
- 输出行数： $1000\times125\times(1\div10000)=12.5$
- 代价：$cost(\mathrm{intermediate})+cost(\mathrm{SeniorStudents})+Rows(\mathrm{SeniorStudents})\times1.5+Rows(\mathrm{intermediate})\times3.5+Rows(\mathrm{result})\times0.1$
- 代价：$1180113.5+1012.5+125\times1.5+1000\times3.5+12.5\times0.1=1184814.75$
方案 B 总代价： $1184814.75$

对比结论：

方案	执行计划	第一步累计代价	总代价	最终行数
A	`H(SS, L(E, C))`	1130110	1133061.25	12.5
B	`H(H(C, E), SS)`	1180113.5	1184814.75	12.5

方案 A 的第一步嵌套循环连接开销为 $100000\times1+1000\times0.1=100100$ ；方案 B 的第一步哈希连接开销为 $100000\times1.5+1\times3.5+1000\times0.1=150103.5$ ，比前者高 $50003.5$ 。第二步中，方案 A 用 125 行的 SeniorStudents 建哈希表，方案 B 用 1000 行的中间结果建哈希表，后者再多花费 $1750$ 。因此方案 B 总代价比方案 A 高 $51753.5$ ，约为 $52000$ 。

最终答案：估算行数 12.50，总执行代价 1133061.25。

最优执行计划树（方案 A）：

说明：

子链接的基数影响（可累积）：子链接条件 T.c = (SELECT COUNT(*) ...) 视为对列 c 的等值过滤。若同一列出现多个等值条件（例如同时存在相关与非相关子链接），其基数缩减按 NDV 累乘；本样例中 Courses.credits 同时受两条子链接约束： $Rows(\mathrm{Courses\_filtered})=100\div10\div10=1$ （其中 Courses_filtered 表示过滤后的 Courses 表）。
计划空间探索：实际需要枚举所有可能的连接顺序（包括不同的连接算法组合），从所有执行计划中选择总代价最小的方案。
代价权衡：在本题“先扫描过滤、再连接”的模型下，每个输入表或子查询的既定扫描/过滤代价在完整计划中各计入一次。因此，这些固定代价本身不会改变不同连接顺序之间的优劣；连接顺序和算法的比较应看过滤后的行数、连接选择率、产生的中间结果，以及哈希构建与探测的方向。

5
AccountsSimple 4 65536
account_id 65536
segment 8
region_id 16
risk_flag 2
TransactionsSimple 3 131072
txn_id 131072
account_id 65536
merchant_id 2048
MerchantsSimple 3 4096
merchant_id 2048
region_id 16
category 64
RegionsSimple 3 64
region_id 16
zone_id 8
country_id 4
RiskSimple 3 32
zone_id 8
risk_grade 4
policy_id 16
SELECT *
FROM AccountsSimple AS A, TransactionsSimple AS T, MerchantsSimple AS M, RegionsSimple AS R, RiskSimple AS RS
WHERE A.account_id = T.account_id
    AND T.merchant_id = M.merchant_id
    AND A.region_id = R.region_id
    AND R.zone_id = RS.zone_id
    AND M.region_id = R.region_id
    AND RS.risk_grade = 2;

65536.00 727813.60

子任务

对于所有数据，满足：

指标	范围
基表数量 $N$	$1\le N\le 40$
每层表数	最多为 $12$
子链接和子查询的总和	不超过 $12$
每个查询块的 `FROM` 项数 $F$	$F\le 12$
包括顶层在内的查询块总数 $B$	$B\le 13$
每张基表的列数 $M$	$1\le M\le6$
所有基表的列数之和	不超过 $300$
基表行数 $R$ 与基表列 NDV	$1\le NDV\le R\le 2\times 10^5$
SQL 中的整数常量	$1$ 至 $200$ 的十进制整数，不带显式正负号
查询嵌套深度 $D$ （顶层计为 $1$ ）	$1\le D\le 4$
全部条件数量	不超过 $300$
标识符长度	不超过 $20$ 个字符
SQL 文本长度与标准输入文件长度	不超过 $3\times10^4$ 字节
全部查询块 FROM 项列数与普通投影输出列数之和	不超过 $3000$
顶层最终估算行数	不超过 $7\times10^4$
最优总代价	不超过 $2\times10^6$
每个查询块任意非空 `FROM` 子集的估算行数	在 $[10^{-7},7\times10^{13}]$ 内
对应子集的最优累计代价	不超过 $7\times10^{12}$
每块各 `FROM` 项扫描前行数的 $\max(1,Rows)$ 之积	不超过 $6\times10^{30}$

数据可能出现的情况：同一基表以不同别名重复出现、完全重复的常量过滤、嵌套的 FROM 子查询、相关与非相关 COUNT(*) 子链接、投影列重命名、隐式表别名、AS 表别名与 SELECT *、WHERE 的子链接。

数据一定不会出现的情况：零行基表、零 NDV、负整数常量、超大整数、常量在等号左侧、同一表实例内的两列比较、自等条件、条件分组括号、SQL 注释、跨越直接父层的相关引用、相关条件中外部列置于左侧，以及同一对表实例之间的多条连接条件。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分值	$N\le$	$F\le$	$B\le$	$D\le$	特殊性质
1	10	$5$	$5$	$1$		不含 `FROM` 子查询或 `COUNT` 子链接
2	30	$10$	$5$	$4$	$3$	无
3	20	$40$	$10$	$13$	$3$
4	40	$40$	$12$	$13$	$4$

#CCSP2025D. 数据库查询优化