GP索引调优测试--原理篇

时间:2024-10-09 07:21:31

    • 说明
    • 原理
    • 解释
    • 附录
      • 查询大量特定数据
      • 排序大量数据


说明

之前对Postgres/GP的索引测试见GP索引调优测试–基本篇.mdGP索引调优测试–排序篇,此文给出原理解释。


原理

建议先阅读“深入理解计算机系统(原书第2版)的第6章 存储器层次结构”,再了解B树,最后阅读数据库索引原理及优化,可以对索引的原理有很清楚的了解。

这里给出使用索引和不使用索引时,查询时间的复杂度,

查询类型 无索引复杂度 有索引复杂度
特定数据(= O(n) (注:n次顺序读取) O(lgn+1) (注:lgn次查找+1次随机读取)
特定范围(range) O(n)(注:n次顺序读取) O( lgn+m)(注:lgn次查找+m次随机读取,m为range的范围)
排序 O(nlgn) (注:这里认为排序的复杂度为nlgn) O(lgn+n)(注:lgn次随机读取找到第一个值,之后往后读取)

解释

故之前的测试结果可以给出解释,

1. 查找特定数据走索引,而且很快

随机读取虽然花费时间比较长,但次数很少,故走索引

2. 特定范围数据,数据量小时走索引,大时并不走

数据量小时m比较小,故走索引;数据量大时,比如为n,此时lgn+n>n,故不走索引(注意,复杂度中n为常量,m才是变量)!

3. 排序走索引

有索引的复杂度要低一些


附录

查询大量特定数据

实际上,在上述查找特定数据时,也可能是不走索引的。比如,来自高效使用PostgreSQL索引的一个例子,

从表中检索到的行数可以基于特定的常数值的查询检索而变化。(我注:即不同的常量值,会导致不同的结果行数)。因此,例如,查询计划器对于查询select * from foo where bar = 1使用索引可能是正确的,但对于查询select * from foo where bar = 2却可能不使用索引,这发生于对于bar值为2的行有比较多的话。发生这种情况时,顺序扫描实际上是最有可能比索引扫描快得多,因此,查询计划器实际上是判断正确的,这时顺序扫描的性能代价相比索引扫描更低。

即,实际上查询特定值的复杂度分别为O(n)(注:n次顺序读取)O( lgn+m)(注:lgn次随机读取,m为该值重复的次数),故当该值重复较多时并不走索引,与范围查询类似。更深入的分析见为什么我在Sql Server上创建的索引用不上? - 知乎。

更多关于不走索引的情况分析见笔记–索引失效情况分析.md。

排序大量数据

实际上参见笔记–Postgres索引测试–基本篇.md,针对排序,在大量数据下使用索引反而可能变慢,参见11.4. 索引和ORDER BY,如下,

对于一个需要扫描表的大部分的查询, 明确的排序可能要比使用索引快的多,因为它使用顺序存取模式所以需要较少的磁盘I/O。 当只需要获取几行时,索引是更有效的。