Access Path Selection in a Relational Database ...

海龙哥

1.概述

​   本文虽然发表于1979年，但在System R这个关系型数据库研究项目中，提出的制定SQL查询计划思想（自下而上+启发式+基于代价评估）至今仍被主流数据库所使用，例如Oracle、DB2、PostgreSQL等。
​   本文解决的主要问题是，用于在不了解数据库存储细节的情况下，执行了一个SQL查询，数据库优化器如何将SQL转换为最优的执行路径，即最高效的执行。
2.处理SQL语句

主要包括四个步骤：

• Parser：对用户输入的SQL语句进行语法解析（如yacc），生成抽象语法树。
  
• Optimizer（逻辑优化）：
  
  
  
  • 执行语义检查（例如检查SQL中的表、字段是否存在），从元数据表中读取关系对象的统计信息、元信息。
    
  • 对SQL语句，确定各个query block的评估顺序，对每个query block，然后，对于每个查询块，将处理FROM列表中的关系。如果一个query block中有多个关系，则计算连接顺序和连接方法的排列。从可选路径选择树中选择块的总成本最小的访问路径。这个最小成本解决方案由parse tree的结构修改表示。返回的结果是一个执行计划（plan），plan使用ASL语言进行描述。
    
  
  
• CODE GENERATOR（物理优化）：为每个查询块选择计划并在parse tree中表示之后，将调用CODE GENERATOR。CODE GENERATOR是一个表驱动程序，它将ASL树转换为机器语言代码，以执行OPTIMIZER选择的计划。为此，它使用了相对较少的代码模板，每种类型的连接方法(包括不连接)都有一个代码模板。用于嵌套查询的查询块被视为“子例程”，它返回值到它们出现的谓词。
  
• 执行：在CODE GENERATOR期间，对parse tree生成可执行的机器代码和它的关联的数据结构。可以直接执行生成的机器码（执行计划），也可以保存到数据库中，以后执行。当代码最终执行时，它通过存储系统接口(RSI)调用System R内部存储系统(RSS)来扫描每个查询中的物理存储关系。这些扫描是沿着OPTIMIZER选择的访问路径进行的。
  

3.The Research Storage System

​   RSS（The Research Storage System）是System R中的存储子系统。RSS负责维护关系的物理存储、这些关系上的访问路径、lock子系统(在多用户环境中)以及日志记录和崩溃恢复。RSS为上层调用提供了RSI接口（tuple-oriented interface）。按page组织tuple数据，分为data page和index page，tuple不跨page，page逻辑上组成segment，一个segment可包含多个relation的page，relation不跨segment。RSS提供表的2中访问方式，顺序扫描和索引扫描。
4.单表多条访问路径的代价评估

​   单表代价评估公式：
​   COST = PAGE FETCHES + W * (RSI CALLS).  
​   其中Cost是IO+CPU的代价，W是CPU和IO之间的权重，RSI CALLS表示实际读取的tuple数量，PAGE FETCHES 是IO代价，包括数据页和索引页（存在可用索引的情况下）两部分。
​   统计信息项

• 关系T
  
  
  
  • NCARD(T)  ：T中tuple的数量
    
  • TCARD(T)  ：T中数据页的数量
    
  • P（T）：在一个segment中，T的数据页占有的比例，即T的数据页/segment总数据页
    
  
  
• 对于T的中任意索引I：
  
  
  
  • ICARD(I)  ：在索引I中去重后key的数量
    
  • NINDX(I)：索引I占用的页的数量
    
  
  

​    用户可以通过调用UPDATE STATISTICS命令，维护统计信息。
​    选择率F说明：

• column = value：
  
  
  
  • F = 1 / ICARD(column index)  ，有索引情况。
    
  • F = 1 /10，无索引
    
  
  
• column1 = column2
  
  
  
  • F = 1/MAX(ICARD(column1 index), ICARD(column2 index))  ，均存在索引
    
  • F = 1/ICARD(column-i index)  ，仅column-i中存在索引
    
  • F = 1 /10，均无索引
    
  
  
• column > value  or （ v1 < column < v2）
  
  
  
  • F = (high key value - value) / (high key value - low key value)  ，column中的value是数值型，且均匀分布
    
  • F = 1/3，value非数值型。这个数字没有任何意义，只是它比没有索引的相等谓词的猜测的选择性更低，而且它小于1/2。我们假设很少有查询使用由超过一半的元组满足的谓词。
    
  
  
• column > value  or （between v1 and v2）
  
  
  
  • F = (high key value - value) / (high key value - low key value)  ，column中的value是数值型，且均匀分布
    
  • F = 1/4，value非数值型。这个选择同样没有意义，除非它是在相等谓词和范围谓词的默认选择因子之间进行选择。
    
  
  
• column IN (list of values)
  
  
  
  • F = (number of items in list) * (selectivity factor for column = value)。This is allowed to be no more than 1/2
    
  
  
• columnA IN subquery
  
  
  
  • 后续补充
    
  
  
• (pred expression1) OR (pred expression2)  ：F = F(pred1) + F(pred2) - F(pred1) * F(pred2)
  
• (pred1) AND (pred2)  ：F = F(pred1) * F(pred2)  ，Note that this assumes that column values are independent.
  
• NOT pred ：F = 1 - F(pred)
  

​    为单个关系选择最优访问路径包括在公式中使用这些选择因子以及可用访问路径的统计信息。在描述这个过程之前，需要定义。使用索引访问路径或排序元组将生成索引值或排序键顺序的元组。如果元组顺序是由查询块的GROUP by或order by子句指定的，我们就说该顺序是一个有趣的顺序。
​    对于单个关系，通过评估每个可用访问路径(关系上的每个索引，加上段扫描)的成本来获得最便宜的访问路径。下文将说明这些代价。对于每个这样的访问路径，将计算预测的成本以及它将产生的元组的顺序。例如，按照升序扫描SALARY索引，将产生一些成本C和一个元组的SALARY(升序)。要为单个关系查询找到最便宜的访问计划，我们只需要检查以每个“有趣”顺序产生元组的最便宜的访问路径和最便宜的“无序”访问路径。注意，“无序”访问路径实际上可能以某种顺序产生元组，但这种顺序并不“有趣”。如果查询中没有GROUP BY或ORDER BY子句，那么将没有有趣的顺序，最便宜的访问路径就是所选择的路径。如果存在GROUP BY或ORDER BY子句，那么产生这种有趣排序的成本必须与最便宜的无序路径的成本加上将QCARD元组按适当顺序排序的成本进行比较。选择这些备选方案中最便宜的作为查询块的计划。
​   单关系访问路径的代价公式如表2所示。这些公式给出了获取的索引页pl获取的数据页加上加权因子乘以RSI元组检索调用。W是页面获取和RSI调用之间的权重因子。在某些情况下，根据检索到的元组集是否完全适合RSS缓冲池(或每个用户的有效缓冲池)，给出了几个备选公式。对于聚集索引，我们假设一个页面在缓冲区中保留足够长的时间，以便从其中检索每个元组。对于非聚集索引，假定对于那些不适合缓冲区的关系，该关系相对于缓冲区的大小足够大，以至于每次元组检索都需要进行页面获取。



5.选择join路径

​   对于2表join，我们将第一个被访问的tuple所在的表成为外表。另一个关系的tuple是否被选择，需要通过外表的tuple进行判断，这个关系成为内表。join谓词，是2表join的公共属性是否相等。
​   （1）nest-loop join
​   遍历外表中的tuple，对于一个外表tuple，遍历内表的所有tuple，进行join 谓词判断。
​   C-nested-loop-join(pathl,path2) = C-outer(path1 + N * C-inner(path2)  
​   N是满足连接谓词的外表的tuple数量。
​   （2）merge join
​   Merge Join 是先将关联表的关联列各自做排序，然后从各自的排序表中抽取数据，到另一个排序表中做匹配。
​   C-merge(pathl,path2) = C-outer(path1) + N * C-inner(path2)  
​   对于inner-relation被排序为临时关系的情况，第4节中的单个关系访问路径公式都不适用。在这种情况下，inner扫描类似于segment扫描，只不过merge扫描方法利用了inner关系已排序的事实，因此不必扫描整个inner关系寻找匹配。在这种情况下，我们使用以下公式计算inner扫描的成本。
​   C-inner(sorted list) = TEMPPAGES/N + W*RSICARD  
​   其中TEMPPAGES是容纳inner关系所需的页面数。这个公式假设在merge过程中，inner关系的每个页面都被获取一次。
6.示例说明




在图1的示例中，我们首先选择单表访问路径，并应用谓词。单表访问路径如图2所示。

• 对于EMP表，备选项DNO列索引扫描、JOB列索引扫描、顺序扫描。在这个示例中，我们假设DNO索引扫描代价最低，因此剪枝掉顺序扫描。
  
• 对于DEPT表，可选2中访问方式，DNO列索引扫描，顺序扫描。假设索引扫描代价低，剪枝顺序扫描。
  
• 对于JOB表，可选2中访问方式，JOB列索引扫描，顺序扫描。假设顺序扫描代价低，两种方式都保留。
  

在search tree中的结果如图3所示，在图中，符号C(EMP.DNO)或C(E.DNO)表示通过DNO索引扫描EMP的成本，应用所有适用的谓词，前提是从指定的关系集中已经获取的元组。用Ni符号表示不同部分结果的基数。


​   接下来，通过2个关系做join扩展search tree。
（1）嵌套连接
​   图4为嵌套循环连接的路径代价评估，从根节点到叶节点，每条路径，都是一个join路线。以最左1、左2侧为例：
​   左1：(EMP, DEPT)  -> Index EMP.DNO -> N1 -> Index DEPT.DNO -> N4 -> C(E.DNO) + N1CE(D.DNO)  DNO排序
​   外表为EMP，按照EMP.DNO索引执行扫描，内表DEPT，按照DEPT.DNO索引执行扫描。总代价 C(E.DNO) + N1*CE(D.DNO)，其中 C(E.DNO) 通过DNO索引扫描EMP的成本， N1表示EMP的tuple数量，CE(D.DNO)表示DNO索引扫描DEPT的成本。
​   左2：(EMP, DEPT)  -> Index EMP.DNO -> N1 -> Index DEPT.DNO -> N4 -> C(E.DNO) + N1CE(D.DNO)  JOB排序
​   外表为EMP，按照EMP.JOB索引执行扫描，内表DEPT，按照DEPT.DNO索引执行扫描。总代价 C(E.JOB) + N1*CE(D.DNO)，其中 C(E.JOB) 通过JOB索引扫描EMP的成本， N1表示EMP的tuple数量，CE(D.DNO)表示DNO索引扫描DEPT的成本。


（2）归并连接
​   原理同上，在merge join中优先考虑有序连接，如果有序代价<无序代价，无序被剪枝。如果有序代价>=无序代价，无序被保留。


（3）总和比较
在leaf level的各种join组合枚举完后，对每个等价类（相同table set+相同interesting order）内，选出一个最优方案，prune掉等价类内其他分支。
嵌套连接和归并连接的路径进行比较，即叶子节点中，各种join枚举后，对于每个等价类（ a. A join B, B join A剪枝，b. A join B中，嵌套连接和归并连接中，相同排序的路径进行选择剪枝 ），选择代价最低的，prune（剪枝）掉等价类内其他分支。
（4）三表连接
将图5中的2表join路径和图3中的单表路径进行枚举，策略同2表join，生成最终结果。