表达式变换与优化的分配律/交换律/结合律

优化器最核心的工作之一就是把一个关系表达式变换成逻辑等价、但执行代价更低的 另一个表达式，这依赖关系代数满足的若干形式化数学法则。书中用一个具体的数量级 案例说明”尽早限制”的威力：查询”获得供应P2型号零件的供应商及数量”写作 (S JOIN SP) WHERE PNO='P2'，假设1000个供应商、100万条出货、其中500条是P2； 若先连接再限制，需要约100万+2000+1000=1002001000次元组读写；若先把SP限制到 只剩500条P2记录、再和S连接，只需约100万+1000+1000=1001000次读写——后者快 约1000倍。这两个表达式能互相变换的理论依据是分配律：一元运算符f对二元运算符 g可分配，当且仅当f(g(a,b))=g(f(a),f(b))对所有a、b成立（类比SQRT(a*b)= SQRT(a)*SQRT(b)，但SQRT对加法不可分配）；关系代数里限制对并、交、差都可 分配，限制条件是两个各自对应一个连接运算元的AND条件时，限制对连接也可分配， 这正是上例”尽早限制”合法的依据；类似地投影对并可分配，只要所有连接属性都在 投影范围内，投影对连接也可分配，同样支持”尽早投影”这类优化直觉。另外两条支撑 优化器自由调整执行顺序的法则是交换律（g(a,b)=g(b,a)，交、并、连接满足，差 不满足，因此连接运算不需要纠结哪个表是”外层”哪个是”内层”，系统可以自由选更小 的表做外层）和结合律（g(a,g(b,c))=g(g(a,b),c)，交、并、连接满足，差不满足， 因此涉及多表连接时不需要预先固定连接顺序，系统可以自由尝试各种连接配对次序找 最优解）。书中特别提醒：这些变换全部只依赖关系代数本身的数学性质，完全不需要 考虑数据库物理存储或索引等存取路径细节；但一旦引入[[SQL查询结果中重复的产生 与真重复的辨识困境]]里讨论的重复行、SQL的列排序位置、以及[[NULL与三值逻辑 逻辑正确与现实正确的分离]]里的3VL，这些原本干净的数学变换法则大部分都会失效 或变得极其有限。