CMU15-445数据库系统:查询优化I

本文已收录于 CMU数据库系统学习笔记 系列,共计 11 篇,本篇是第 11 篇

视频与PPT

视频:https://www.bilibili.com/video/BV1qR4y1W7v6?spm_id_from=333.880.my_history.page.click

为什么要引入优化器?

因为SQL语句是声明式的,只说了要什么答案,中间的过程没有定义,也就是执行计划是没有指定的。我想要A JOIN B,程序员不用去关心是A JOIN B还是B JOIN A算出来的。这些具体的东西由执行计划决定。

关于执行的两个流派

一个是认为应该由数据库系统替程序员优化;另一个流派认为应该由程序员自己优化。这两个流派直到今天也在争论。

就我们的课程来说,如果我们选择由数据库系统替程序员优化,那么… …请继续往下看

选择由数据库系统帮助优化

面临我们选择的依然会有两种方式:

基于启发:

例如数据库系统会去探查我们的列上面有没有索引,如果有的话就直接走索引。但是数据库系统不会去再详细的看这列的统计信息,他只关心基础信息,有或者没有。

基于代价:

估计多个查询计划的代价,进行比较,选择最小的代价。——前提是需要知道数据,知道数据量才知道时间。

现在大多数数据库以上两种流派都有实现。

体系结构概述

逻辑计划与物理计划

逻辑计划:给SQL程序员用的,基于关系模型。

物理计划:定义具体的执行方式,例如数据库系统里的算子,hash join,走索引还是走扫描?根据具体数据情况选择具体的物理算子。

查询优化是一个很难的问题

如果你很精通查询优化,那么你会拿到会高的薪水。IBM在2000年试图用人工智能来协助纯人工来优化查询,但是人工智能有个问题——不可解释性。很多时候人工智能告诉的结果使人摸不着头脑,不知道怎么得出来的。后来IBM在数据库系统中关闭了这个人工智能插件。

近些年,IBM又开始研究人工智能优化问题了… …

关系表达式的等价优化

两个关系表达式等价的话,他们输出的结果集是一样的。

直观来看,是先连接再筛选然后再投影输出。但是我们可以经过改造,谓词下推。先筛选再连接,达到了更高效的目的。

更多等价:

多条件谓词拆分。

等价拆分。

inter join符合交换律、结合律。多表join有4的n次方种执行方式,这个范围巨大。

投影输出。提前物化(干掉不打算输出的列),晚物化(不管列,我只对id做join,最后你再根据id去找数据列)

逻辑计划的优化

其实就是单纯的计划改写,数据库系统并不知道那种计划更好,更快,因为它没有代价模型。它只能根据你定义好的改写规则去把逻辑计划改写。

原先的查询计划:

改写后的查询计划:把谓词打散成三个谓词

谓词尽量往下推,越接近底层越好。