关系系统及其查询优化

关系系统及其查询优化数据库系统核心技术与查询处理深度解析Contents目录数据库查询优化的核心原理与实践策略全景导览01关系系统定义与分类02查询优化基本原理03查询优化技术详解04实例分析与优化策略CHAPTER01关系系统定义与分类从关系模型出发，理解关系系统的核心特征与层次划分RelationalSystem关系系统的定义关系系统的核心定义包含两个必要条件：支持关系数据结构（表）和支持基本关系运算（选择、投影、连接），且运算过程对用户透明，系统自动选择最优存取路径，实现了数据操作的物理独立性。关系数据结构以二维表作为数据的组织与存储形式，这是关系系统区别于层次模型和网状模型的根本特征。二维表基本关系运算支持选择、投影和自然连接三种运算，用户无需指定物理存取路径，由系统自动优化执行策略。σ·π·⋈物理独立性不必要求任何物理存储路径，用户专注于逻辑表达而非底层实现，显著提升开发效率。透明存取RELATIONALMODEL关系模型与关系系统的关系关系系统并非一个非黑即白的概念，而是存在从最小关系到全关系的渐进层次。支持关系模型的程度不同，系统的分类也不同，全关系系统是一个理想目标而非入门门槛。理论与实现的区分关系系统与关系模型是两个相关但不等同的概念，关系模型定义了理论框架，关系系统则是实现该理论的软件产品，实现程度存在差异理论×实现多层次支持并非只有完全支持关系模型的系统才能称为关系系统，根据对数据结构、完整性约束、数据操纵三要素的支持程度，可以划分为多个层次三要素分级全关系理想目标全关系系统是完全支持关系模型所有特征的理想目标，Codd提出了12条基本准则作为评判标准，目前商用系统仍在向此目标努力Codd12准则Classification关系系统的四种分类按照对关系模型三要素（数据结构S、完整性约束I、数据操纵M）的支持程度，关系系统从低到高分为表式关系、最小关系系统、关系完备系统和全关系系统四个层次，呈现递进的完整度梯度。01表式关系仅支持关系数据结构（如倒排表），不支持关系运算操作，是最低层次的关系系统仅数据结构02最小关系系统支持关系数据结构及选择、投影、连接三种基本操作，代表产品如FoxBASE、FoxProFoxBASE03关系完备系统支持关系数据结构和所有关系代数操作，当前主流商用数据库如Oracle、Sybase均属此类Oracle04全关系系统完全支持关系模型所有特征（含12条Codd准则），是理想目标，目前尚无商用系统完全达标12条Codd准则Codd'sRules全关系系统的12条基本准则Codd提出的12条准则是全关系系统的评判基准，涵盖信息规则、保证访问规则、视图更新、集合操作、数据独立性等维度，目前商用系统虽未完全达标，但这些准则持续指导着RDBMS的演进方向。01信息规则关系数据库的所有信息都必须在表值中表示，包括表名、列名等元数据本身也以表的形式存储元数据也以表存储02保证访问规则表中每个值都可以通过表名、主键和列名的组合来逻辑访问，无需依赖物理地址表名+主键+列名03空值的系统化处理DBMS必须支持空值（NULL），用于表示缺失信息或不适用的信息，且与任何数据类型无关NULL·数据类型无关04动态在线目录数据库的描述信息与普通数据采用相同的表示方式，授权用户可使用相同的查询语言访问元数据=普通数据Chapter02查询优化基本原理理解RDBMS如何通过优化器自动选择最高效的查询执行策略QueryOptimization查询优化的地位与目标查询优化是RDBMS查询处理的核心技术，其总目标是选择有效策略、求得给定关系表达式的值并使查询代价最小。高语义级别的关系表达式为系统自动优化提供了天然优势。查询处理核心模块查询处理是关系数据库管理系统的核心功能模块，查询优化技术是影响性能最为关键的环节，直接决定了查询的响应速度性能关键优化的三层目标选择有效的执行策略、正确求得给定表达式的值、使整体查询代价达到最小或接近最小代价最小高语义级别优势关系表达式的语义级别很高，使系统能从中分析查询语义，为非过程化语言的自动优化提供了天然可能性自动优化QUERYOPTIMIZATION查询优化的核心优势系统自动查询优化相比用户手动优化具有显著优势：优化器拥有全局统计信息、可遍历数百种执行计划、内含复杂优化技术，且能在数据分布变化时自动重新优化，相当于让每个用户都拥有顶级程序员的优化能力。声明式查询用户只需表达"做什么"而不必考虑"怎么做最高效"，优化器自动选择最优执行计划，极大降低技术门槛做什么全局统计信息从数据字典获取表大小、索引分布、聚簇情况等关键优化依据，用户程序通常无法获得这些信息数据字典自动重新优化物理统计信息变化时系统自动选择新执行计划，非关系系统中则必须手动重写程序重新优化CostModel查询代价模型查询代价以磁盘I/O为核心，辅以CPU与内存开销；分布式数据库叠加通信代价，总代价=I/O+CPU+内存+通信。集中式代价构成执行代价由磁盘存取块数（I/O代价）、处理机时间（CPU代价）和查询内存开销三部分组成，其中I/O代价是最主要的衡量指标。三维构成磁盘I/O的核心地位磁盘I/O涉及磁头寻道与旋转等机械动作，耗时比内存操作高几个数量级，因此以读写磁盘块数作为核心衡量单位。数量级差异分布式通信叠加分布式数据库的总代价还需叠加通信代价，即数据在网络节点间传输的开销，形成四维代价模型。四维模型QUERYOPTIMIZATION查询优化的四个步骤查询优化遵循标准化四步流程：语法树转换→等价变换优化→存取路径选择→最优方案生成。每一步都逐层细化执行策略，最终从多种候选方案中选取代价最小的执行计划。STEP01语法树转换将SQL查询转换成内部表示形式（通常为关系代数语法树），将用户的逻辑表达转化为系统可处理的结构化中间表示。这一步是后续所有优化工作的基础，确保查询语义被正确解析。STEP02等价变换优化应用等价转换规则反复对查询表达式进行尝试性转换，将原始语法树重构为等价的优化形式，消除冗余操作。通过选择、投影等操作的合理下推，减少中间结果集规模。STEP03存取路径选择根据数据字典中的存取路径、数据的存储分布及聚簇情况选择具体的低层存取算法，进一步改善查询效率。包括索引扫描、全表扫描、哈希连接等物理操作的选择决策。STEP04最优方案生成生成由一系列内部操作组成的多个查询执行方案，通过基于代价的优化算法计算并选择总代价最小的方案执行。综合考虑I/O成本、CPU开销和网络传输等因素。CHAPTER03查询优化技术详解从代数优化到物理优化，全面掌握查询执行效率的提升策略QUERYOPTIMIZATION代数优化与物理优化查询优化分为代数优化和物理优化两大类别：代数优化通过关系代数表达式的等价变换重构查询结构，不涉及底层存取路径；物理优化根据数据统计信息选择具体的存取算法和执行路径，两者协同实现全局最优。代数优化关系代数表达式的等价变换优化，通过改变运算的执行顺序和组合方式来减少中间结果的大小，无需考虑数据的物理存储细节。等价变换物理优化根据数据字典中的统计信息（表大小、索引类型、数据分布）选择具体的存取路径和执行算法，如嵌套循环连接或哈希连接。存取路径基于代价的优化商品化RDBMS大都采用基于代价的优化算法，综合考虑代数优化和物理优化的多种候选方案，计算每种方案的总代价后选出最优解。全局最优RelationalAlgebra常用代数优化等价变换规则代数优化的核心思想是'尽早减少数据量'：选择运算尽量提前、投影运算尽早执行、笛卡尔积与选择合并为连接。这些等价变换规则通过重构运算顺序和组合方式，显著减少中间结果的大小和I/O开销。选择运算提前执行先过滤再连接，大幅减少参与后续运算的元组数量，这是最重要的启发式优化规则σSelectionPushdown投影运算尽早执行及时去除不需要的属性列，减少中间关系的宽度和后续运算的计算量πProjectionPushdown笛卡尔积与选择合并将笛卡尔积与紧随其后的选择运算合并为等值连接或自然连接，避免生成庞大的中间结果×→⋈JoinMergeEXTENDEDTRANSFORMATIONRULES代数优化的扩展变换规则代数优化还包含丰富的扩展规则：选择的串接与交换律允许多条件灵活组合，投影与选择的交换律提供执行顺序灵活性，连接的交换律与结合律使多表连接的执行顺序可优化，为优化器构建广阔的搜索空间。选择的串接定律σF1(σF2(R))≡σF1∧F2(R)多个连续选择可合并为一个复合选择，反之也可拆分为多个简单选择以利用索引合并与拆分投影与选择交换律π(σ(R))≡σ(π(R))当选择条件仅涉及投影保留的属性时，可以先选择后投影，也可以先投影后选择，两者结果等价执行顺序灵活性连接交换律与结合律R⋈S≡S⋈R·(R⋈S)⋈T≡R⋈(S⋈T)允许多表连接时灵活调整执行顺序，优先连接产生最小中间结果的表对搜索空间JOINALGORITHMS物理优化的连接算法连接运算是查询中最昂贵的操作，物理优化提供四种主要连接算法：嵌套循环适用于小表、排序合并适用于大表且已有序、索引连接利用已有索引加速查找、哈希连接在内存充足时效率最高。优化器根据数据特征自动选择最优算法。嵌套循环与排序合并嵌套循环连接外层表逐元组扫描内层表全部元组，适合至少一个表较小的场景。实现简单直观，但大表连接时代价极高，时间复杂度为O(M×N)。排序-合并连接两表先按连接属性排序再同步扫描匹配，对已排序的大表连接效率极高。总时间通常远小于嵌套循环，是大数据量场景的首选方案。O(n²)嵌套循环复杂度O(nlogn)排序合并复杂度索引连接与哈希连接索引连接利用连接属性上的索引直接定位匹配元组，避免全表扫描。当内表有合适索引时性能显著提升，是索引资源充足时的理想选择。哈希连接以连接属性为哈希码将两表元组散列到同一哈希文件，分为划分阶段和试探阶段。内存充足时效率最高，是大规模数据连接的终极方案。B+树索引结构支撑O(n)哈希最优复杂度DATABASE·JOINALGORITHM哈希连接算法详解哈希连接以连接属性为哈希码，通过划分阶段和试探阶段完成两表连接。其核心前提是小表能完全载入内存的哈希桶中，两表各只需扫描一遍，时间复杂度接近线性，是大规模数据连接的高效方案。01划分阶段PartitioningPhase对包含较少元组的表进行一遍处理，按哈希函数将其元组分散到哈希表的各个桶中，构建内存中的哈希索引结构。构建索引02试探阶段ProbingPhase对另一个较大的表进行一遍扫描，将每个元组哈希到对应的桶中，与桶中所有来自第一个表的匹配元组完成连接。匹配连接03核心前提CorePremise较小的表在划分阶段后可完全放入内存的哈希桶中；若不满足则需分块处理，两表各扫描一遍即可完成连接。O(n)DATABASE·JOINALGORITHM排序-合并连接算法详解排序合并连接通过先排序后同步扫描完成大表连接，两表各扫描一遍，对已有序数据效率极高，是大规模等值连接的经典方案。01执行流程取第一个表的连接属性值，依次扫描第二个表中具有相同值的元组进行连接，遇到不同值时返回第一个表取下一个元组，重复直到处理完毕。同步扫描02核心优势两个表都只需扫描一遍即可完成连接，即使原来无序需要先排序，排序后使用此方法的总时间仍远小于嵌套循环连接。单次扫描03适用场景特别适合大表之间的等值连接或自然连接，当表已按连接属性有序（如聚簇索引）时性能最优，无需额外排序开销。大表等值CHAPTER04实例分析与优化策略通过学生-课程数据库实例，量化对比不同查询执行策略的代价差异QUERYOPTIMIZATION实例：查询选修2号课程的学生姓名以学生-课程数据库为实例，查询'选修了2号课程的学生姓名'，涉及Student表与SC表的连接。同一SQL查询可转化为多种等价关系代数表达式，不同表达式的执行代价差异巨大。查询场景在学生-课程数据库中查找选修了2号课程的学生姓名。SELECTSnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno='2'SQL查询数据假设Student表有1,000个学生记录，SC表有10,000个选课记录，其中选修2号课程的记录仅50条，最终结果集很小。1,000Student记录10,000SC记录存储假设每个磁盘块可装10个Student元组或100个SC元组，内存可存放5块Student和1块SC元组。20块/秒DISKI/OSPEEDQUERYOPTIMIZATION方案Q1：先笛卡尔积后选择投影Q1方案先计算两表笛卡尔积再做选择和投影，产生1000万条中间结果。读取耗时105秒，中间结果写入和读回各需5万秒，总耗时约10万秒（约28小时），是最差执行策略，充分说明盲目计算的代价之巨。笛卡尔积读取阶段Student表100块需读20遍配合SC表的100块，总读取块数为2100块，耗时2100÷20=105秒，I/O开销巨大。此阶段是后续灾难性开销的起点，两表全量扫描导致大量磁盘访问。READTIME105秒中间结果写出阶段笛卡尔积产生1000×10000=10⁷条元组，按每块10条计算需10⁶块，写出到中间文件耗时10⁶÷20=50000秒。海量数据溢写到磁盘成为性能瓶颈，远超原始表数据量。WRITETIME50,000秒选择操作阶段将10⁶块中间结果从文件读回内存做选择过滤，同样耗时50000秒，总时间约105+2×50000≈100105秒。读回操作与写出形成对称开销，构成双重灾难。TOTALCOST≈28小时QUERYOPTIMIZATION方案Q2：先自然连接后选择投影Q2方案将笛卡尔积替换为自然连接，中间结果从1000万条骤降至1万条。中间文件写出和读回各仅需50秒，总耗时约205秒，相比Q1的10万秒提升了近500倍。STEP01自然连接读取阶段读取总块数仍为2100块、耗时105秒，但自然连接仅生成10⁴条元组，远小于笛卡尔积的10⁷条，中间结果体积缩小1000倍。10⁴条元组STEP02中间结果写出阶段10⁴条元组按每块10条计算仅需1000块，写出到中间文件耗时1000÷20＝50秒，相比Q1的50000秒减少了99.9%。50秒写出STEP03选择与投影阶段将1000块中间结果读回内存做选择（选修2号课程）和投影，耗时约50秒，总时间约105＋2×50＝205秒（约3.4分钟）。205秒总计≈500×提升QueryOptimization方案Q3：先选择后自然连接（最优策略）Q3方案将选择操作提前到连接之前执行，先筛选SC表中Cno='2'的50条记录（仅5秒），再与Student表连接。由于选择后的中间结果极小无需写磁盘，总耗时约110秒，比Q1提升约900倍，完美诠释了"选择下推"这一最核心优化规则的价值。选择运算阶段先对SC表做选择操作（Cno='2'），只需读一遍SC表的100块，筛选出50条满足条件的选课记录5秒自然连接阶段用50条SC记录与Student表连接，中间结果极小可在内存处理，无需写入中间文件，极大减少I/O开销50条效率对比总结Q3总耗时约110秒vsQ2的205秒vsQ1的100105秒，选择下推使性能提升近900倍×900QueryOptimization·CostAnalysis三种查询执行方案代价对比同一查询的三种等价执行方案性能差距巨大：Q1（笛卡尔积优先）耗时约28小时，Q2（连接优先）约3.4分钟，Q3（选择下推）约1.8分钟。优化策略可将查询效率提升近900倍。三种查询执行方案代价对比执行方案核心策略I/O块数总耗时相对加速比Q1笛卡尔积→选择→投影约10⁶块≈100,105秒(28h)1×Q2自然连接→选择→投影约2,300块≈205秒(3.4min)≈488×Q3选择下推→自然连接→投影约200块≈110秒(1.8min)≈910×I/OReduction5000×I/O块数从10⁶降至200，减少三个数量级TimeSavings≈28h执行时间从28小时缩短至1.8分钟KeyHeuristic选择下推查询优化中最关键的启发式规则QueryOptimization启发式优化规则总结启发式优化规则是查询优化的经验法则，核心原则包括：选择下推、投影下推、避免笛卡尔积、合并同目运算、减少中间结果I/O。选择下推规则选择运算应尽可能靠近叶节点执行，先过滤再连接，可指数级减少后续运算的数据规模，是Q3比Q1快900倍的根本原因。该规则通过尽早过滤无关数据，显著降低连接运算的输入规模。900×加速投影下推规则在运算过程中及时去除不需要的属性列，减少中间关系的宽度，降低后续运算的内存消耗和I/O传输量。通过精简数据列，有效提升缓存命中率和网络传输效率。I/O显著降低避免笛卡尔积规则将笛卡尔积与紧随其后的选择运算合并为等值连接或自然连接，避免生成数量级远超原始数据的中间结果集。此优化可防止内存溢出并大幅减少计算开销。智能JOINQueryOptimization基于代价的优化方法基于代价的优化方法是现代RDBMS的核心技术，优化器通过代价模型评估数百种候选执行计划的I/O、CPU和内存总代价，结合数据字典中的统计信息选出最优方案。比纯启发式更精确，能处理复杂查询，是目前商品化数据库普遍采用的优化策略。计划枚举与选择优化器枚举所有可能的执行计划（包括不同的连接顺序、连接算法、索引使用方式），用代价模型计算每种计划的总代价，选出最小代价方案最小代价统计信息驱动代价计算依赖数据字典中的统计信息：表的元组数、属性值域大小、索引选择率、数据分布直方图、聚簇因子等，统计信息的准确性直接影响优化质量数据字典混合优化策略现代优化器通常结合启发式规则和代价优化：先用启发式规则缩小搜索空间，再在缩减后的空间中用代价模型精确选择，兼顾效率与优化效果启发式+代价QUERYOPTIMIZATION·STATISTICS统计信息在查询优化中的作用统计信息是基于代价优化的数据基础，包括表规模、属性值域、索引选择率、数据分布直方图等。统计信息的准确性和时效性直接决定优化器决策质量，过时或缺失的统计信息可能导致优化器选择次优甚至极差的执行计划。关键统计信息：表的元组总数与页数、每个属性的不同值数量（NDV）、最频繁值和最小/最大值、索引的B+树层数与叶节点数NDVB+TreeMin/Max选择率估算：满足条件的元组占总元组的比例，优化器据此预估选择和连接操作的输出规模，是代价计算的核心参数SelectivityCostModel维护策略：数据库系统在数据大量变更后需执行ANALYZE命令更新统计信息，否则优化器基于过时数据可能产生严重的代价估算偏差ANALYZE数据时效性DATABASE·QUERYOPTIMIZATION查询优化器的体系结构查询优化器是一个多阶段流水线：SQL解析→关系代数转换→启发式代数优化→物理算法选择→代价评估→最优计划生成。每个阶段逐层精炼执行策略，从逻辑表达逐步细化为具体的物理操作序列，最终输出代价最小的执行方案。STAGE01查询解析对用户提交的SQL进行语法分析和语义检查，验证表名、列名的合法性，将SQL转换为内部的关系代数表达式表示SQL→RelationalAlgebraSTAGE02代数优化应用启发式等价变换规则——选择下推、投影下推、连接重排序等，将原始表达式重构为逻辑等价但结构更优的形式HeuristicTransformSTAGE03物理优化与代价评估为每个关系运算选择具体的物理算法（如嵌套循环/哈希连接），生成候选执行计划，用代价模型选出最优方案交给执行引擎Cost-BasedSelectionQueryOptimization·IndexStrategy索引在查询优化中的