关系查询处理和查询优化

关系查询处理和查询优化数据库系统原理·查询处理流程与优化策略深度解析Contents课程目录数据库查询优化的核心知识体系从基础原理到实战调优的完整路径01关系数据库查询处理流程02查询优化的重要性与基本原理03代数优化：关系代数等价变换04物理优化：执行策略与代价模型05查询优化实例分析与调优实践CHAPTER01关系数据库查询处理流程从SQL提交到结果返回：解析、检查、优化与执行的完整链路QUERYPROCESSING查询处理的四个核心阶段关系数据库的查询处理是一个从高层语义到低层物理执行的逐层转化过程，其中查询优化是决定系统性能的核心环节。数据库服务器机房实景01查询分析：对SQL语句进行词法与语法分析，识别关键字、表名、列名等元素，构建内部语法树表示语法树02查询检查：验证查询语义合法性，包括数据对象存在性、用户权限校验、完整性约束检查权限03查询优化：生成多个候选执行计划，基于代价模型评估I/O、CPU和内存开销，选择最优方案核心04查询执行：按选定计划调用存储引擎接口，完成数据检索、连接、排序等操作并返回结果引擎QUERYANALYSIS查询分析：从SQL文本到语法树查询分析是数据库理解用户意图的第一步，通过词法分析将SQL文本分解为有意义的基本符号，再通过语法分析验证这些符号的组合是否符合SQL语法规范，最终构建出结构化的语法树，为后续语义检查和优化奠定形式化基础。词法分析扫描SQL字符串，识别SELECT、FROM、WHERE等保留字以及表名、列名、常量、运算符等基本符号LEXICALANALYSIS语法分析根据SQL上下文无关文法检查符号组合的合法性，如SELECT后是否有目标列、FROM后是否有合法表引用SYNTAXANALYSIS语法树构建以树形结构表示查询的层次关系，叶节点为基本符号，内部节点为语法结构，完整记录查询的结构化语义PARSETREESQL编译管线·第一阶段查询检查：语义验证与权限核验查询检查确保SQL语句在语义层面合法且在安全层面被授权。系统通过查询数据字典验证表和列的存在性与类型兼容性，同时根据授权矩阵检查用户的访问权限，只有双重检查通过的查询才能进入优化阶段，从源头保障数据的安全性和一致性。语义检查查询数据字典，验证FROM子句中的表名、视图名是否真实存在，WHERE和SELECT中的列名是否属于对应表数据字典类型兼容性检查确认操作符与数据类型匹配，数值列可参与比较运算，字符串列不可直接与整数做算术运算类型匹配安全性检查依据系统授权表验证用户对目标数据对象的访问权限，包括读权限、写权限和引用权限的逐层核验授权矩阵EXECUTIONENGINE查询执行：执行计划与算子模型查询执行将优化器输出的逻辑执行计划转化为物理操作序列。执行计划以算子树的形式组织，每个算子对应一种数据操作（如扫描、连接、排序），系统通过流水线或物化策略驱动算子树自底向上运行，最终将结果集返回给用户。算子树结构执行计划是算子构成的树形结构，叶节点为数据访问算子（全表扫描/索引扫描），内部节点为连接、聚合、排序等算子。父节点调用子节点的迭代器接口获取数据，形成自底向上的数据流动。OperatorTree流水线执行上层算子按需向下层逐行拉取数据，避免中间结果写盘，显著减少磁盘I/O次数和执行延迟。适用于流式处理和内存充足场景，是现代数据库的默认执行模式。Pipeline物化执行将每个算子的完整结果写入临时表再供上层读取，适用于中间结果需多次引用的场景如子查询和排序。以空间换时间，增加内存或磁盘占用但减少重复计算。MaterializationCHAPTER02查询优化的重要性与基本原理理解优化器的核心优势、代价模型与执行计划生成机制QUERYOPTIMIZATION查询优化的核心地位与系统优势优化器相比用户手动调优具有信息、自适应、全局搜索与技术集成四大优势，使所有用户都能享受专业级查询性能。信息优势优化器可直接从数据字典获取表行数、列分布、索引选择度等统计信息，用户程序难以获得这些底层数据DataDict自适应优势当数据库物理统计信息改变时，系统自动重新优化查询以选择适配的执行计划，无需用户重写程序Auto-Adapt全局搜索优势优化器可评估数百种不同的执行计划并比较代价，而程序员通常只能考虑有限的几种可能性100+Plans技术集成优势优化器集成了谓词推下、连接重排序、子查询平坦化等复杂技术，让所有用户拥有专家级调优能力ExpertQueryOptimization代价模型：衡量执行计划的量化标尺RDBMS通过代价模型量化评估每种执行策略的资源消耗，从而选取代价最小的执行方案。集中式数据库的代价以磁盘I/O为主导，分布式数据库还需叠加网络通信代价。集中式代价构成执行代价由磁盘I/O代价（存取块数）、CPU代价（处理机时间）和内存开销三部分组成，是代价估算的基础框架三维构成磁盘I/O主导磁盘寻道和传输速度比内存访问慢数个数量级，因此减少I/O操作次数始终是查询优化的首要目标，直接影响响应时间首要瓶颈分布式通信代价总代价需在集中式基础上叠加通信代价，包括节点间数据传输量和网络延迟的影响，跨节点操作会显著增加执行开销网络叠加统计信息依赖代价估算高度依赖统计信息的准确性，包括表行数、列值分布、索引选择度等，信息滞后将导致优化器生成低效执行计划精度前提QueryOptimizer数据库统计信息：优化决策的数据基础统计信息是优化器进行代价估算的核心依据。优化器高度依赖这些信息预估执行计划的资源消耗，统计信息的质量直接决定优化器的决策质量。表级统计信息包括总行数、数据页数、平均行长等，是估算全表扫描代价和基数估计的基础数据行数·页数列级统计信息记录数值分布、不同值数量、最大最小值、空值比例，用于估算筛选条件选择率分布·选择率索引统计信息包括索引选择度、聚簇因子、B+树高度和叶节点数，决定是否选择索引扫描选择度·聚簇统计信息更新需定期更新以反映数据变化，大量DML操作后若不重新收集，将导致错误决策DML·时效性QUERYOPTIMIZER基数估计：执行计划决策的核心输入基数估计指预判查询每一个执行步骤所能产出的数据行数，是优化器进行代价评估和策略选择的关键输入。选择率与预期行数通过列统计信息和选择率公式计算每个谓词过滤后的预期行数，等值条件选择率等于不同值数量的倒数选择率连接顺序决策优化器倾向于先执行产出行数少的连接操作，以减少中间结果集规模和后续操作代价连接顺序连接算法选择小结果集适合嵌套循环连接，大结果集更适合哈希连接或合并连接，基数估计直接影响算法决策算法匹配多表误差放大多表连接场景下基数估计误差逐级放大，列相关性假设不成立时偏差可达数个数量级数量级偏差CHAPTER03代数优化关系代数等价变换基于等价变换规则重写查询表达式，从语义层面提升执行效率QueryOptimization代数优化的基本思想与等价概念代数优化通过关系代数的等价变换规则重写查询表达式，在不改变查询结果的前提下获得更高效的执行形式。01代数优化的核心是在保持查询结果不变的前提下，通过等价变换规则将表达式重写为执行代价更低的形式02两个关系表达式等价的条件是：对任何合法的数据库实例，两个表达式的运算结果完全相同——结果集的元组和属性一致03代数优化在逻辑层面进行，关注关系运算的组合顺序和结构，不涉及索引选择、连接算法等物理实现细节04典型的优化目标包括尽早执行选择操作以减少中间结果行数、合并相邻的投影操作以减少扫描次数RelationalAlgebra·Equivalence选择操作的等价变换规则选择操作的等价变换规则是代数优化中最常用且效果最显著的规则集。通过将选择条件分解、交换和推下，可以在查询执行的早期阶段过滤掉大量无关数据，显著减少后续连接、投影等操作的输入数据量，从而大幅降低整体执行代价。选择操作的分解与交换条件分解σA∧B(R)≡σA(σB(R))，将复合选择条件拆分为两个独立的选择操作依次执行，使每个条件单独作用于数据，便于优化器分别处理交换律σA(σB(R))≡σB(σA(R))，两个选择操作的执行顺序可以互换而不影响最终结果，为优化器提供更大的重排空间选择操作的推下规则推下笛卡尔积若条件A仅涉及R的属性，则σA(R×S)≡σA(R)×S，先过滤再做笛卡尔积，避免生成大量无效中间结果，显著降低计算开销推下自然连接若条件A仅涉及R的属性，则σA(R⋈S)≡σA(R)⋈S，在连接前先过滤可显著减少参与连接的元组数，提升连接操作效率RelationalAlgebra·Equivalence投影操作的等价变换规则投影操作的等价变换规则旨在尽早消除不必要的属性列，减少中间结果的数据宽度。通过投影的合并和推下，可以在查询执行的各个环节及时裁剪不需要的列，降低后续操作的内存占用和I/O传输量，是优化查询执行效率的重要手段。投影操作的幂等性πA(πB(R))在A⊆B时等价于πA(R)，多余的中间投影可以被消除以简化表达式投影与选择的交换若选择条件涉及的属性都在投影列表中，则πA(σB(R))≡σB(πA(R))，需注意属性集的包含关系投影对连接的推下若投影列表可分解为分别属于R和S的子集，则π(R⋈S)≡πR'(R)⋈πS'(S)，在连接前裁剪列宽相邻投影操作的合并连续多个投影操作可合并为一个，只保留最终的属性列表，避免多次扫描产生不必要的开销QueryOptimization连接操作的等价变换规则连接操作的等价变换规则为多表查询优化提供理论基础，多表连接顺序的优化空间随表数量指数增长，是查询优化器面临的核心组合优化问题。连接的交换律R⋈S≡S⋈R，两个表的连接顺序可以互换，但物理执行时内外表的选择影响嵌套循环连接的代价R⋈S≡S⋈R连接的结合律(R⋈S)⋈T≡R⋈(S⋈T)，多表连接的分组顺序可以调整，优化器据此搜索最优连接次序(R⋈S)⋈T≡R⋈(S⋈T)选择对连接的推下条件仅涉及单表属性时可推至连接前执行，等价于先过滤再连接，大幅减少连接操作的数据量先过滤·再连接连接与投影的交互投影可推至连接操作数上，在连接前去除不参与连接条件和结果输出的多余列，减少中间数据宽度裁剪多余列QueryOptimization代数优化的启发式策略总结代数优化的启发式策略以"尽早减少中间结果规模"为核心原则，通过选择和投影操作的推下、合并与同步执行，在逻辑层面显著降低后续操作的输入数据量。选择操作尽早执行将选择条件推到关系代数树的尽可能底层，在数据源头过滤掉不满足条件的元组，减少中间结果行数。减少行数投影操作尽早执行在各节点处添加必要的投影操作，及时消除后续运算不需要的属性列，缩减数据宽度。缩减列宽选择与投影同步执行将相邻的选择和投影操作合并为一次扫描，避免对同一数据的多遍遍历，减少磁盘I/O次数。合并扫描笛卡尔积与选择合并将笛卡尔积后紧跟的选择操作合并为等值连接或自然连接，避免产生巨大的中间结果集。避免膨胀CHAPTER04物理优化：执行策略与代价模型为每个关系操作选择最优的访问路径、连接算法和执行策略DATAACCESSPATHS数据访问路径：全表扫描与索引访问数据访问路径的选择是物理优化的基础决策，直接决定了数据检索的I/O代价。优化器根据查询条件与索引可用性，选择代价最小的访问方案。全表扫描读取表内所有数据页，适用于无可用索引或需访问大部分行的场景，I/O代价与表大小成正比聚集索引扫描利用聚集索引有序性按范围读取，适合范围查询和有序输出，减少随机I/O次数二级索引扫描先通过二级索引定位ROWID再回表获取完整行，适合高选择性的等值或范围查询仅索引扫描（覆盖索引）直接从索引叶节点获取所有查询所需列，无需回表，是I/O代价最低的访问方式I/O代价梯度HIGH全表扫描MEDIUM聚集索引扫描LOW二级索引扫描LOWEST覆盖索引扫描合理选择访问路径可将查询代价降低数个数量级QueryExecution连接算法：嵌套循环、哈希连接与合并连接连接算法的选择直接影响多表查询的执行效率。优化器根据数据体量、索引可用性和基数估计结果，为每个连接操作选择最合适的算法。嵌套循环连接外层表逐行扫描，对内层表执行匹配查找，内表有索引时单次查找代价为O(logN)，总体复杂度O(M·logN)适合外表行数少且内表有合适索引的场景，是小结果集驱动大表时的首选算法O(M·logN)哈希连接用较小的表构建哈希表放入内存，扫描较大表时通过哈希函数直接定位匹配行，平均时间复杂度接近O(M+N)适合两个较大表的等值连接，无需预排序或索引支持，但要求哈希表能放入可用内存O(M+N)合并连接两个输入表按连接键排序后同步扫描，按序逐行匹配，时间复杂度O(M+N)但需额外排序代价适合输入已按连接键有序的场景，或查询结果需要按连接键排序输出有序合并QueryRewrite查询重写：从SQL到高效执行形式查询重写是优化器在执行计划生成前对SQL进行的语义保持性转换，将查询从用户编写的形式转化为更利于高效执行的结构。01谓词推下将过滤条件移至查询树的底层执行，在数据源头尽早过滤无关行，减少中间结果集的行数规模过滤前置02子查询平坦化将嵌套子查询转换为等价的连接查询，消除子查询的逐行触发开销，使优化器能全局考虑连接顺序消除嵌套03连接重排序基于基数估计调整多表连接的执行顺序，优先执行产出行数少的连接，控制中间结果集的膨胀基数驱动04冗余消除识别并删除多余的排序、去重和投影操作，例如ORDERBY后紧跟GROUPBY时可能消除独立的排序步骤去冗精简QueryOptimization·FinalStage执行计划的生成、评估与选择优化器为查询生成多套候选计划，通过代价模型逐一评估，最终选取代价最小的方案作为执行计划。01计划生成为每个关系操作枚举可选的访问路径和连接算法，组合形成完整的候选执行计划搜索空间02代价评估利用统计信息估算每套计划的CPU处理时间、磁盘I/O次数、内存占用量和网络传输量03计划选择从候选集中挑选估算代价最低的方案，明确操作顺序、算法选择和资源分配策略04诊断调优通过EXPLAIN命令查看执行计划，帮助开发者理解优化器决策过程并诊断性能瓶颈CHAPTER05查询优化实例分析与调优实践从理论到实践：通过案例分析掌握查询优化的核心方法与调优技巧QueryOptimization实例分析：连接顺序对执行代价的影响同一个多表连接查询的不同执行顺序可能导致数量级的性能差异。连接顺序决定了中间结果集的规模，而中间结果集的大小直接影响后续所有操作的I/O和CPU代价。不同连接顺序的中间结果规模对比连接顺序中间结果行数预估I/O代价优化评估(R×S)⋈T10,000,000极高（笛卡尔积膨胀）先做笛卡尔积产生巨大中间结果，后续操作代价极高(R⋈S)⋈T5,000中等等值连接控制中间结果规模，但R⋈S的选择率影响后续代价R⋈(S⋈T)800低优先执行选择性高的连接，中间结果最小，整体代价最低(R⋈T)⋈S2,000中低次优方案，中间结果规模可控但不是最小Summary—连接顺序的选择直接影响中间结果集规模，最优顺序可将I/O代价降低数个数量级QUERYOPTIMIZATION代数优化实例：选择与投影推下的效果选择操作的推下是代数优化中效果最显著的规则。通过将筛选条件从笛卡尔积或连接之后推至操作数之前，可以在数据源头大幅减少参与后续运算的数据量。BEFORE优化前的执行路径01原始表达式σ(学号=学号∧系名='计算机')(学生×选课)，先做笛卡尔积产生10亿行中间结果02在巨大的中间结果集上执行选择和投影操作，需要大量磁盘I/O和CPU计算资源来处理无关数据10亿行AFTER优化后的执行路径01将σ(系名='计算机')推下至学生表：先筛选出500名计算机系学生再做等值连接，中间结果降至约5000行02进一步将投影推下至连接操作数：在学生表和选课表上分别只保留需要的列，减少每行数据宽度和传输量≈5000行QUERYOPTIMIZATION访问路径选择：索引扫描与全表扫描的权衡索引扫描并非总是优于全表扫描。选择率的临界点（通常在10%-15%）是优化器做出路径切换决策的关键阈值。高选择性查询命中少量数据时，索引扫描通过B+树快速定位目标行，I/O代价远低于全表扫描的顺序读取，是高效查询的首选方案<10%低选择性查询命中大量数据时，全表扫描的顺序I/O效率高于索引扫描的大量随机回表开销，优化器会自动选择更优路径>15%覆盖索引查询查询所需列全部包含在索引中时，仅索引扫描无需回表操作，在任何选择率下都优于全表扫描，是性能优化的最佳实践COVERING聚簇因子影响索引列与数据物理存储顺序一致性高时，索引扫描的顺序性更好，减少随机I/O，优化器更倾向选择索引访问路径CLUSTERINGQUERYOPTIMIZERWORKFLOW查询优化器的完整工作流程查询优化器遵循解析验证→查询重写→计划生成→代价估算→计划选择的标准流程，将SQL声明式查询转化为高效的物理执行方案。STEP01解析验证对SQL进行词法语法分析，确认引用的表、列、索引存在且查询结构符合语法规范词法语法STEP02查询重写应用谓词推下、子查询平坦化、连接重排序等改写规则，转化为语义等价的高效形式谓词推下STEP03计划生成为每个操作枚举访问路径和连接算法，组合形成候选执行计划的搜索空间搜