《数据库系统概念》第十二章:查询处理

查询处理

1 概述

1.1 基本步骤

  • 语法分析与翻译
  • 优化
  • 执行

《数据库系统概念》第十二章:查询处理

1.2 查询

一个查询,一般都会有多种计算结果的方法。

例如,select salary from instructor where salary<75000;

可以被翻译为以下任意一个关系代数表达式

《数据库系统概念》第十二章:查询处理

要全面说明如何执行一个查询,有以下概念:

  • 计算原语(evaluation primitive):加了“如何执行”注释的关系代数运算
  • 查询执行计划(query-execution plan):用于执行一个查询的原语操作序列,也成为查询计算计划(query-evaluation plan)
  • 查询执行引擎(query-execution engine):接受一个查询执行计划,执行该计划并把结果返回给查询

给定查询的不同执行计划会有不同的代价,选择最高效率的查询计划就是查询优化,是系统的责任

2 查询代价的度量

主要度量:

  • 传送磁盘块数
  • 搜索磁盘次数

假设传输一个磁盘块的数据平均tr秒,磁盘访问时间(磁盘搜索加旋转延迟)ts秒,一次传输b个块以及执行S次磁盘搜索的时间为:

《数据库系统概念》第十二章:查询处理

我们假定开始时的数据必须从磁盘中读出,但实际上可能已经被缓存过了。为了简化,忽略这种情况,所以实际代价可能小于估算代价

因此,很难估算计划的响应时间,原因如下:

  1. 查询开始执行时,响应时间依赖于缓存区内容;对查询进行优化时,该信息无法获取,即使获取了也很难进行计算
  2. 在具有多张磁盘的系统中,响应时间依赖于访问如何分布在各磁盘上,没有对分布在磁盘中的数据的详细了解很难估计

优化器通常努力去降低查询计划的资源消耗,而不是降低响应时间。因为总有一些方法可以以资源换时间,这对于单个查询是降低了响应时间,但如果多个查询同时执行,往往会提高响应时间。

3 选择运算

文件扫描(file scan)是存取数据最低级的操作

3.1 文件扫描和索引选择

《数据库系统概念》第十二章:查询处理

3.2 复杂选择

有以下更复杂的选择谓词

  • 合取 conjunction

    《数据库系统概念》第十二章:查询处理

  • 析取 disjunction

    《数据库系统概念》第十二章:查询处理

  • 取反

    《数据库系统概念》第十二章:查询处理

分别有以下算法

  • A7(利用一个索引的合取选择)

    判断是否有某个属性上存在索引,若存在选择A2-A6中的一个来搜索满足条件的记录,然后在内存缓冲区中,通过测试检索到的记录是否满足其他条件,最终完成这个操作。由选择的θi组合决定。

  • A8(通过使用组合索引和合取选择)

    可能使用组合索引,索引的类型决定使用A2、A3、A4中的哪一个

  • A9(通过标识符的交实现合取选择)

    要求各个条件涉及的字段上带有记录指针的索引。对每个索引进行扫描,获取那些指向单个条件记录的指针,然后取交集。需要注意的是:

    1. 应该把指向一个磁盘块的指针放在一起,这样只需要一次磁盘IO就可以获取该磁盘块上的全部记录
    2. 要按存储次序执行,这样磁盘臂的移动最少
  • A10(通过标识符的并实现析取选择)

    如果析取条件中均有带有记录指针的索引,可以类似A9。

    否则直接线性扫描。(不然的话为了取一个条件也要线性扫描一次,不如直接扫描好了)

  • 取反

    线性扫描A1

4 排序

  • 针对内存中能够完全容纳的情况
    • 标准的排序算法,比如快排
  • 针对不能被内存完全容纳的情况
    • 本节介绍

4.1 外部排序归并算法

对于不能完全放在内存中的关系进行排序,称为外排序(external sorting)

其中最常用的技术是归并排序

  1. 建立多个排好序的归并段(sorted run)

    Repeatedly do the following till the end of the relation:

    ? (a) Read M blocks of relation into memory

    ? (b) Sort the in-memory blocks

    ? (c) Write sorted data to run Ri ; increment i.

    Let the final value of i be N

  2. 归并归并段

    We assume (for now) that N < M.

    (1)Use N blocks of memory to buffer input runs, and 1 block to buffer output. Read the first block of each run into its buffer page

    (2)repeat

    ? (2.1)Select the first record (in sort order) among all buffer pages

    ? (2.2)Write the record to the output buffer. If the output buffer is full write it to disk.

    ? (2.3)Delete the record from its input buffer page.( If the buffer page becomes empty then read the next block (if any) of the run into the buffer. )

    (3)until all input buffer pages are empty:

注:如果N>M,就先排序M-1个段

《数据库系统概念》第十二章:查询处理

4.2 算法分析

《数据库系统概念》第十二章:查询处理

《数据库系统概念》第十二章:查询处理

5 连接运算

5.1 嵌套循环连接

《数据库系统概念》第十二章:查询处理

5.2 块嵌套循环连接

《数据库系统概念》第十二章:查询处理

在最坏的情况下,对于外层关系中的每一个块,内层关系s的每一块只需要读一次,而不是对外层关系的每一个元组读一次。

5.3 索引嵌套循环连接

图12-5中,若在内层循环的连接属性上有索引,可以用索引替代文件扫描。对于外层关系r的每一个元组tr,可以利用索引查找s中和元组tr满足连接条件的元组。

5.4 归并连接

归并连接算法(merge join)又称排序-归并-连接算法(sort-merge join)

先排好序,然后

《数据库系统概念》第十二章:查询处理

5.5 散列连接

《数据库系统概念》第十二章:查询处理

《数据库系统概念》第十二章:查询处理

6 其他运算

6.1 去重

  • 排序:排序时等值元素相互邻近,删除其他副本只留一个即可
  • 散列

6.2 投影

  1. 首先对每个元素作投影
  2. 如果所得结果可能有重复,则去重。(若投影列表中属性含有关系的码,则不会有重复,不必去重)

6.3 集合运算

《数据库系统概念》第十二章:查询处理

6.4 外连接

6.5 聚集

group by

  • 可以用类似去重的方法实现
  • 不必等聚集后再进行聚集运算,如sum、min、max、count、avg可以在过程中进行计算

7 表达式计算

目前为止,我们研究了单个关系运算如何执行,下面我们讨论如何计算包含多个运算的表达式。

一般来说有两种办法

  • 以适当的顺序每次执行一个操作,每次计算的结果被物化到一个临时关系中以备后用。
  • 在流水线上同时计算多个运算,一个运算的结果传递给下一个,不必保存临时关系。

7.1 物化

以该表达上为例

《数据库系统概念》第十二章:查询处理

建立运算符树

《数据库系统概念》第十二章:查询处理

自底向上进行计算。物化的代价不仅仅是涉及的运算代价总和,还要加上将运算结果写到磁盘上的代价。

可以使用双缓冲,即一个缓冲区用于连续执行算法,一个缓冲区用于写出结果

7.2 流水线

好处:

  1. 消除读和写的临时关系代价,减少查询计算代价
  2. 如果一个查询计算计划的根操作符及其输入合并到流水线中,那么可以迅速开始产生查询结果

实现

  1. 需求驱动的流水线

    《数据库系统概念》第十二章:查询处理

  2. 生产者驱动的流水线

    《数据库系统概念》第十二章:查询处理

《数据库系统概念》第十二章:查询处理

上一篇:mysql 查看锁的方式


下一篇:C++ 内存对齐