论文笔记：Access Path Selection in a Relation Database Management System
这篇文章是 1979 年由 IBM 发表的。主要介绍了 System-R 查询优化器的设计。
Processing of an SQL statement
- parsing 将 SQL 转换成抽象语法树
- optimization 查询优化
- code generation 使用 code generator 一个表驱动程序，将 ASL 转成机器代码。
- execution 在执行的过程中，parse tree 被替换为可执行的机器代码以及相关的数据结构。
Optimizer 处理流程
- 处理代码块
- 处理每个代码块中的 From 语句
- 输出为执行计划
Code Generator 处理流程
将 ASL（Access Specification Language）语言转换为 machine language code
Execution 处理流程
将 parser tree 转换为机器码和相关的数据结构，生成的机器码可以立即执行，也可以存储到数据库中，稍后执行。当机器码最终执行时，通过 RSI 接口进行数据扫描，这些扫描是沿着 Optimizer 选择的访问路径进行的。
The Research Storage System （RSS）
存储子系统，负责关系的物理存储，访问路径，多用户的锁，日志和恢复系统。RSS 为上层提供了面向 tuple 的接口 RSI。
主要功能
- physical storage
- access paths on relations
- logging
- recovery
physical storage
- tuple 存储在 page（每个 page 4k byte）中，不能跨 page 存储 tuple，且 tuple 间没有间隔。
- page 通过 segment 进行组织。
- tuple 也不能跨 segment 进行存储。
- 每个 tuple 都有一个标识。
two type of scan
- segment scan
- index scan，index 由用户创建，存储于独立的 index page 中。
access times
在这节，反复出现了对于寻找一个 tuple 需要访问几次 page 的描述。这里进行总结。
-
对于 segment scan
所有的非空 page 都会访问到，并且每个 page 只会被访问一次。 -
对于 index scan
index page 只会被访问一次，data page 可能会被访问多次。
clustered index
介绍了一下聚簇索引：
sargable predicate
(SARGS) Both index and segment scans may optionally take a set of predicates, called search arguments.
(Sargable) Search Argument Able.
通过 SARGS 可以减少 RSI 层的工作，在 RSS 层就把无用的 tuple 过滤掉了。
Cost for single relation access paths
先介绍最简单的情况，对单表的查询，然后介绍了 2-ways jon 以及 n-ways joins，最后介绍嵌套查询。
使用如下公式计算计划的代价：
- PAGE FETCHES 反应了 I/O 情况。
- RSI CALLS 是可以通过 RSS 层预知的数量。大部分的 CPU 操作都集中在 RSS 层，所以 RSI CALLS 是一个度量 CPU 操作的很好指标。
- W 是一个可以调整的变量。用于调整 I/O 操作 和 CPU 操作之间的权重。
统计信息所涉及到的元数据如下所示：
随后介绍了一下统计信息是如何生成的。统计信息的生成需要使用独立的命令，并不在 INSERT，DELETE，UPDATE 过程中生成或更新。因为额外的操作会有锁瓶颈，动态化更新统计信息往往会导致修改表的操作变为序列化的操作。
Query Cardinality (QCARD) 查询的基数：From List 中的每个表的基数的乘积 * 所有谓词的选择率。
对于单一的表选择最佳的 access path，使用公式上选择率，结合在access path 上的统计信息。
Access path selection for joins
这部分先介绍了一下几个概念，outer releation，inner releation，以及 join columns。
nested loop joins
不详细介绍了
merge scan joins
使用 mergin scans 的必要条件：
- join 列有序。
- interesting order。
- 如果有多个 join 谓词，只使用其中一个，其他的当作普通谓词。
- 仅支持等值连接。
- 如果 join 列没有索引，必须先排序。
merging scan join
n-ways joins
可以被视为多个 2-way joins 的序列，在 n-ways joins 中只有需要有序的中间结果时，才会物理存储。
computation of costs
nested queries
conclusion
System R 系统的路径选择通过使用单表查询，Join 操作，以及嵌套查询来描述。如何在执行过程中做出正确的选择，将在即将发表的论文中做进一步描述。初步的结果表明，虽然优化器的代价预测的精确度不如绝对值--在大量路径下的真正最优路径。在许多情况下，所考虑的所有路径的估计成本之间的排序与实际测量成本之间的顺序完全相同。
更进一步的，路径选择的压力不应该过大。对于 2-way join，查询优化的代价大概 5-20 次数据库检索，这个数字甚至可能更大，当选择器被放到 System R 的应用程序被编译一次，运行多次的环境中，优化的成本被摊分到多次运行中。
这种路径选择，对比于这个领域中的其他工作，关键之处在于使用统计信息，引入 CPU 的利用到代价计算公式，决定 join 顺序的方法。很多查询是和 CPU 密切相关的，特别是在 merge-sort 的过程中临时表的创建和排序。选择性因子的概念允许优化器尽可能的利用查询的限制性谓词，作用在 RSS 搜索参数和搜索路径中。记住 "interesting ordering" 等价类规范对于 join 和 order 或者 group。本文的优化器会比大多数的路径选择器记录更多，但是这些额外的工作可以避免存储和排序中间结果。Tree pruning 和 tree searching 技术允许额外的记录操作能被高效的执行。验证优化器的代价公式的有更多的工作需要去做，但是我们可以从这些初步的工作中肯定，数据库系统能够支持非过程的查询语言，与当前的支持更多过程式的语言的有相同的性能。
词汇
disjunctive normal form (DNF) 析取范式
任何命题公式，最终都能够化成 \((A1 \wedge A2)\vee(A3 \wedge A4)\)
的形式，这种先\(\wedge\)合取，再\(\vee\)析取的范式，称为析取范式。
conjunctive normal form (CNF) 合取范式
任何命题公式，最终都能够化成 \((A1 \vee A2)\wedge(A3 \vee A4)\)
的形式，这种先\(\vee\)析取，再\(\wedge\)合取的范式，称为合取范式。
cardinality 基数 数据库中某个表的某个列中不重复的行的总个数。
selectivity 选择率 谓词的过滤条件返回的结果的行数占未加谓词过滤条件的行数。
when possible 在可能的情况下
thus far 迄今；现在为止
if any 若有的话；即便要
forthcoming 即将发生（或出版等）的
preliminary 预备性的；初步的；开始的
permits 允许；准许