分布式查询处理：原理与优化策略

1. 分布式查询处理概述

1.1 查询处理问题

查询处理器的主要功能是将高级查询（通常用关系演算表示）转换为等效的低级查询（通常是某种关系代数的变体）。低级查询实际上实现了查询的执行策略，这种转换必须同时保证正确性和效率。正确性意味着低级查询与原始查询具有相同的语义，即两者产生相同的结果。从关系演算到关系代数的明确定义映射使得正确性问题相对容易解决，但要产生高效的执行策略则更为困难。一个关系演算查询可能有许多等效且正确的关系代数转换，由于每个等效执行策略可能导致计算机资源的消耗差异很大，因此主要困难在于选择能使资源消耗最小化的执行策略。

示例

考虑工程数据库模式的以下子集：
- EMP(ENO, ENAME, TITLE)
- ASG(ENO, PNO, RESP, DUR)

用户的简单查询为：“查找正在管理项目的员工姓名”。使用 SQL 语法（自然连接）在关系演算中表达该查询为：

SELECT ENAME
FROM EMP NATURAL JOIN ASG
WHERE RESP = "Manager"

两个等效的关系代数查询是：
- πENAME(σRESP="Manager"∧EMP.ENO=ASG.ENO(EMP × ASG))
- πENAME(⋊⋉ENO (σRESP="Manager"(ASG)))

显然，第二个查询避免了 EMP 和 ASG 的笛卡尔积，消耗的计算资源比第一个少得多，因此应选择第二个查询。

在分布式系统中，关系代数不足以表达执行策略，还需要补充用于在站点之间交换数据的运算符。除了选择关系代数运算符的顺序外，分布式查询处理器还必须选择处理数据的最佳站点，以及可能的数据转换方式。这增加了选择分布式执行策略的解决方案空间，使得分布式查询处理比集中式查询处理困难得多。

示例

考虑上述查询 πENAME(EMP ⋊⋉ENO (σRESP="Manager"(ASG))) ，假设 EMP 和 ASG 关系水平分割如下：
- EMP1 = σENO≤"E3"(EMP)
- EMP2 = σENO>"E3"(EMP)
- ASG1 = σENO≤"E3"(ASG)
- ASG2 = σENO>"E3"(ASG)

ASG1 、 ASG2 、 EMP1 和 EMP2 分别存储在站点 1、2、3 和 4，结果期望在站点 5。为简单起见，忽略投影运算符。该查询的两个等效分布式执行策略如下：
- 策略 A ：利用 EMP 和 ASG 以相同方式分割的事实，并行执行选择和连接运算符。
- 策略 B ：默认策略，在处理查询之前将所有操作数数据集中到结果站点。

使用简单的成本模型评估这两种策略的资源消耗，假设元组访问（ tupacc ）为 1 单位，元组传输（ tuptrans ）为 10 单位， EMP 和 ASG 分别有 400 和 1000 个元组， ASG 中有 20 个经理，数据在各站点均匀分布， ASG 和 EMP 分别在 RESP 和 ENO 属性上局部聚类。

策略	步骤	成本计算	总成本
策略 A	1. 选择 ASG 生成 ASG′	(10 + 10) * tupacc = 20	460
	2. 将 ASG′ 传输到 EMP 所在站点	(10 + 10) * tuptrans = 200
	3. 连接 ASG′ 和 EMP 生成 EMP′	(10 + 10) * tupacc * 2 = 40
	4. 将 EMP′ 传输到结果站点	(10 + 10) * tuptrans = 200
策略 B	1. 将 EMP 传输到站点 5	400 * tuptrans = 4000	23000
	2. 将 ASG 传输到站点 5	1000 * tuptrans = 10000
	3. 选择 ASG 生成 ASG′	1000 * tupacc = 1000
	4. 连接 EMP 和 ASG′	400 * 20 * tupacc = 8000

策略 A 比策略 B 好 50 倍，并且能更好地在站点间分配工作。如果通信速度较慢和/或分割程度更高，差异会更大。

1.2 查询优化

查询优化是指生成查询执行计划（QEP）的过程，该计划代表查询的执行策略，旨在最小化目标成本函数。查询优化器通常由三个组件组成：搜索空间、成本模型和搜索策略。

1.2.1 搜索空间

搜索空间是表示输入查询的替代执行计划的集合。这些计划是等效的，即它们产生相同的结果，但在运算符的执行顺序和实现方式上有所不同，因此性能也不同。搜索空间通过应用转换规则（如关系代数的规则）获得。

1.2.2 成本模型

成本模型用于预测任何给定执行计划的成本，并比较等效计划以选择最佳计划。为了准确，成本模型必须对分布式执行环境有充分的了解，使用数据统计信息和成本函数。

在分布式数据库中，统计信息通常针对片段，包括片段的基数和大小，以及每个属性的大小和不同值的数量。为了最小化误差概率，有时会使用更详细的统计信息（如属性值的直方图），但这会增加管理成本。统计信息的准确性通过定期更新来实现。

成本的一个良好度量是处理查询将产生的总成本，即查询运算符在各个站点的处理时间和站点间通信时间的总和。另一个良好度量是查询的响应时间，即执行查询所经过的时间。由于运算符可以在不同站点并行执行，查询的响应时间可能比总成本小得多。

在分布式数据库系统中，要最小化的总成本包括 CPU、I/O 和通信成本。CPU 成本是在主内存中对数据执行运算符时产生的；I/O 成本是磁盘访问所需的时间，可以通过快速访问数据的方法和高效使用主内存（缓冲区管理）来减少；通信成本是参与查询执行的站点之间交换数据所需的时间，包括消息处理（格式化/反格式化）和在通信网络上传输数据的时间。

通信成本组件在分布式数据库中可能是最重要的因素。早期的分布式查询优化提议大多假设通信成本远高于本地处理成本（I/O 和 CPU 成本），因此忽略了后者。然而，现代分布式处理环境的通信网络速度更快，带宽与磁盘相当，因此解决方案是对这三个成本组件进行加权组合，因为它们都对查询评估的总成本有显著贡献。

关系代数运算符的复杂性直接影响其执行时间，这为查询处理器提供了一些有用的原则，有助于选择最终执行策略。复杂性的简单定义基于关系基数，与物理实现细节（如分割和存储结构）无关：
- 一元运算符的复杂性为 O(n)，其中 n 表示关系基数，如果结果元组可以相互独立地获得。
- 二元运算符的复杂性为 O(n log n)，如果一个关系的每个元组必须与另一个关系的每个元组基于选定属性的相等性进行比较。此复杂性假设每个关系的元组必须按比较属性排序，但使用哈希和足够的内存来存储一个哈希关系可以将二元运算符的复杂性降低到 O(n)。
- 去重投影和分组运算符要求关系的每个元组与其他每个元组进行比较，因此复杂性也为 O(n log n)。
- 两个关系的笛卡尔积的复杂性为 O(n²)，因为一个关系的每个元组必须与另一个关系的每个元组组合。

1.2.3 搜索策略

搜索策略使用成本模型探索搜索空间并选择最佳计划，它定义了要检查的计划以及检查顺序。分布式环境的细节由搜索空间和成本模型捕捉。

一种直接的查询优化方法是搜索解决方案空间，详尽地预测每个策略的成本，并选择成本最小的策略。虽然这种方法能有效选择最佳策略，但优化本身可能会产生显著的处理成本。问题在于解决方案空间可能很大，即使查询涉及的关系数量较少，也可能有许多等效策略，随着关系或片段数量的增加（例如超过 10 个），问题会变得更糟。不过，如果查询优化一次后可用于多次后续查询执行，高优化成本不一定是坏事。

查询优化器最常用的搜索策略是动态规划，它最早由 IBM 研究的 System R 项目提出。动态规划从基本关系开始构建计划，每次加入一个更多的关系，直到获得完整的计划。它以广度优先的方式构建所有可能的计划，然后选择“最佳”计划。为了降低优化成本，不太可能导致最优计划的部分计划会尽快被修剪（即丢弃）。

对于非常复杂的查询，搜索空间很大时，可以使用随机策略，如迭代改进和模拟退火。它们试图找到一个非常好的解决方案（不一定是最佳方案），在优化时间和执行时间之间取得良好的平衡。

另一种补充解决方案是限制解决方案空间，只考虑少数策略。在集中式和分布式系统中，一个常见的启发式方法是最小化中间关系的大小，可以通过先执行一元运算符，并按中间关系大小递增的顺序排列二元运算符来实现。

查询可以在查询执行的不同时间进行优化，包括静态优化（在查询执行之前）和动态优化（在查询执行时）。静态查询优化在查询编译时进行，优化成本可以分摊到多次查询执行中，因此适合使用详尽搜索方法，但由于策略的中间关系大小在运行时才知道，必须使用数据库统计信息进行估计，估计误差可能导致选择次优策略。动态查询优化在查询执行时进行，在执行的任何时刻，选择下一个最佳运算符可以基于对先前执行运算符结果的准确了解，因此不需要数据库统计信息来估计中间结果的大小，但查询优化是一项昂贵的任务，每次查询执行都必须重复，因此这种方法最适合临时查询。混合查询优化试图提供静态查询优化的优点，同时避免不准确估计带来的问题，它基本上是静态的，但当检测到预测大小与中间关系的实际大小差异很大时，可能会在运行时进行动态查询优化。

1.3 查询处理的层次

查询处理问题本身可以分解为几个子问题，对应于不同的层次。假设一个不利用复制片段的静态查询处理器，输入是用关系演算表达的全局数据查询，该查询针对全局（分布式）关系，即数据分布是隐藏的。分布式查询处理涉及四个主要层次：
1. 查询分解 ：将输入查询转换为关系代数运算符序列。
2. 数据本地化 ：确定查询访问的数据所在位置，将关系上的运算符转换为对本地数据（片段）的操作。
3. 全局查询优化 ：扩展片段上的代数查询，加入通信运算符，并根据要最小化的成本函数进行优化。
4. 分布式查询执行 ：执行查询执行计划并返回查询答案。

前三个层次由中央控制站点执行，使用全局目录中存储的模式信息，将输入查询映射到分布式查询执行计划（分布式 QEP）；第四个层次由本地站点和控制站点执行。

以下是查询处理层次的 mermaid 流程图：

graph LR
    A[关系演算查询] --> B[查询分解]
    B --> C[数据本地化]
    C --> D[全局查询优化]
    D --> E[分布式查询执行]
    E --> F[查询结果]

2. 数据本地化

2.1 数据本地化概述

数据本地化是分布式查询处理中的重要步骤，其重点在于针对不同类型的碎片进行减少和简化。分布式关系通常通过碎片来实现，目的是提高引用局部性，有时还能对最重要的查询实现并行执行。在数据本地化过程中，主要处理四种类型的碎片化：水平、垂直、派生和混合。

2.2 不同类型碎片化的处理

2.2.1 水平碎片化

水平碎片化是将关系按行分割成多个片段。例如，在前面提到的工程数据库模式中， EMP 和 ASG 关系的水平分割：
- EMP1 = σENO≤"E3"(EMP)
- EMP2 = σENO>"E3"(EMP)
- ASG1 = σENO≤"E3"(ASG)
- ASG2 = σENO>"E3"(ASG)

在处理水平碎片化时，需要根据查询条件，确定哪些片段与查询相关。比如对于查询“查找正在管理项目的员工姓名”，需要分别对 ASG1 和 ASG2 应用选择条件 RESP = "Manager" ，然后再与相应的 EMP 片段进行连接操作。

2.2.2 垂直碎片化

垂直碎片化是将关系按列分割成多个片段。例如，将 EMP 关系垂直分割为 EMP_NAME(ENAME) 和 EMP_INFO(ENO, TITLE) 。在处理垂直碎片化时，需要根据查询需求，将相关的片段组合起来。如果查询只需要 ENAME ，则只需要访问 EMP_NAME 片段；如果查询需要 ENAME 和 TITLE ，则需要将 EMP_NAME 和 EMP_INFO 片段进行连接。

2.2.3 派生碎片化

派生碎片化是基于现有关系通过某种计算或操作得到的新片段。例如，通过对 ASG 关系按 PNO 分组，计算每个项目的平均持续时间，得到派生片段 AVG_DUR(PNO, AVG_DUR) 。在处理派生碎片化时，需要根据查询条件，确定是否需要重新计算派生片段，或者直接使用已有的派生片段。

2.2.4 混合碎片化

混合碎片化是水平和垂直碎片化的组合。处理混合碎片化时，需要综合考虑水平和垂直碎片化的处理方法，先根据查询条件确定相关的水平片段，再从这些水平片段中选择相关的垂直片段进行组合和处理。

2.3 数据本地化的步骤

数据本地化的主要步骤如下：
1. 确定查询涉及的关系和碎片 ：根据查询语句，确定需要访问哪些关系以及这些关系的哪些碎片。
2. 应用选择条件 ：对相关的碎片应用查询中的选择条件，减少需要处理的数据量。
3. 连接碎片 ：如果查询需要多个碎片进行连接操作，根据连接条件将相关的碎片进行连接。
4. 合并结果 ：将处理后的碎片结果进行合并，得到最终的查询结果。

3. 分布式查询中的连接排序优化

3.1 连接排序问题

在分布式查询中，连接排序是一个重要的优化问题。不同的连接顺序会导致不同的资源消耗和查询性能。例如，在处理多个关系的连接时，如果先连接基数较小的关系，可能会减少中间结果的大小，从而降低后续连接操作的成本。

3.2 半连接策略

半连接是一种替代的连接策略，它可以减少参与连接的元组数量，从而降低连接操作的成本。半连接的基本思想是先在一个关系上应用选择条件，然后将满足条件的元组投影到连接属性上，再将这些投影结果发送到另一个关系所在的站点进行连接操作。

示例

考虑 EMP 和 ASG 关系的连接查询，使用半连接策略可以先在 ASG 关系上应用选择条件 RESP = "Manager" ，然后将满足条件的元组投影到 ENO 属性上，得到 ASG′(ENO) ，再将 ASG′ 发送到 EMP 关系所在的站点进行连接操作。这样可以减少参与连接的 ASG 元组数量，降低连接成本。

3.3 连接排序优化步骤

连接排序优化的步骤如下：
1. 分析查询涉及的关系和连接条件 ：确定查询中需要连接的关系以及连接条件。
2. 评估不同连接顺序的成本 ：使用成本模型，预测不同连接顺序的总成本。
3. 选择最优连接顺序 ：根据成本评估结果，选择总成本最小的连接顺序。
4. 应用半连接策略（可选） ：如果半连接策略可以降低成本，则应用半连接策略进行优化。

4. 分布式成本模型

4.1 成本模型概述

分布式成本模型用于预测查询执行的成本，帮助选择最优的执行策略。成本模型考虑了 CPU、I/O 和通信成本，通过对这些成本进行加权组合，得到查询执行的总成本。

4.2 成本组件分析

4.2.1 CPU 成本

CPU 成本是在主内存中对数据执行运算符时产生的。例如，对数据进行排序、选择和投影等操作都需要消耗 CPU 资源。CPU 成本的大小与操作的数据量和运算符的复杂性有关。

4.2.2 I/O 成本

I/O 成本是磁盘访问所需的时间。可以通过快速访问数据的方法（如索引）和高效使用主内存（缓冲区管理）来减少 I/O 成本。例如，使用索引可以直接定位到需要的数据，避免全表扫描，从而减少磁盘访问次数。

4.2.3 通信成本

通信成本是参与查询执行的站点之间交换数据所需的时间，包括消息处理（格式化/反格式化）和在通信网络上传输数据的时间。通信成本与传输的数据量和网络带宽有关。

4.3 成本计算方法

成本计算方法通常是将 CPU、I/O 和通信成本进行加权组合。例如，可以使用以下公式计算总成本：
总成本 = CPU 成本 * CPU 权重 + I/O 成本 * I/O 权重 + 通信成本 * 通信权重

其中，CPU 权重、I/O 权重和通信权重根据具体的分布式环境和查询特点进行调整。

5. 分布式查询优化方法

5.1 动态优化方法

动态优化方法在查询执行时进行优化，根据对先前执行运算符结果的准确了解，选择下一个最佳运算符。动态优化方法的优点是可以避免不准确估计带来的问题，选择更优的执行策略，但缺点是每次查询执行都需要进行优化，成本较高。

5.2 静态优化方法

静态优化方法在查询编译时进行优化，使用数据库统计信息估计中间关系的大小，选择最优的执行策略。静态优化方法的优点是优化成本可以分摊到多次查询执行中，适合使用详尽搜索方法，但缺点是估计误差可能导致选择次优策略。

5.3 混合优化方法

混合优化方法试图结合静态和动态优化方法的优点，基本上是静态的，但当检测到预测大小与中间关系的实际大小差异很大时，可能会在运行时进行动态查询优化。

5.4 优化方法的选择

选择优化方法时，需要考虑以下因素：
| 因素 | 动态优化 | 静态优化 | 混合优化 |
| ---- | ---- | ---- | ---- |
| 查询频率 | 适合临时查询 | 适合频繁执行的查询 | 适合查询模式变化较大的情况 |
| 数据变化频率 | 适合数据变化频繁的情况 | 适合数据相对稳定的情况 | 可以适应数据变化 |
| 优化成本 | 每次查询执行都需要优化，成本较高 | 优化成本可以分摊到多次查询执行中 | 平衡了优化成本和执行效果 |

6. 自适应查询处理

6.1 自适应查询处理概述

自适应查询处理是指在查询执行过程中，根据实际情况动态调整查询执行策略。例如，当检测到某个站点的负载过高时，可以将部分查询任务转移到其他站点；当发现某个连接顺序的成本过高时，可以及时调整连接顺序。

6.2 自适应查询处理的步骤

自适应查询处理的主要步骤如下：
1. 监控查询执行情况 ：实时监控查询执行过程中的各种指标，如 CPU 使用率、I/O 吞吐量、通信延迟等。
2. 分析监控数据 ：根据监控数据，分析查询执行的性能和资源消耗情况。
3. 判断是否需要调整策略 ：如果发现查询执行性能不佳或资源消耗过高，判断是否需要调整查询执行策略。
4. 调整查询执行策略 ：根据判断结果，动态调整查询执行策略，如改变连接顺序、转移查询任务等。
5. 继续执行查询 ：应用调整后的查询执行策略，继续执行查询。

6.3 自适应查询处理的优点

自适应查询处理的优点是可以根据实际情况动态调整查询执行策略，提高查询性能和资源利用率，适应不同的分布式环境和查询特点。

以下是自适应查询处理的 mermaid 流程图：

graph LR
    A[查询开始] --> B[监控查询执行情况]
    B --> C[分析监控数据]
    C --> D{是否需要调整策略?}
    D -- 是 --> E[调整查询执行策略]
    D -- 否 --> F[继续执行查询]
    E --> F
    F --> G{查询是否完成?}
    G -- 否 --> B
    G -- 是 --> H[查询结束]