PostgreSQL扫描方法综述

PostgreSQL扫描方法综述

关系型数据库都需要产生一个最佳的执行计划从而在查询时耗费的时间和资源最少。通常情况下，所有的数据库都会产生一个以树形式的执行计划：计划树的叶子节点被称为表扫描节点。查询节点对应于从基表获取数据。

例如，这一个查询：SELECT *FROM TAB1,TAB2 where TAB2.ID>1000。假设计划树如下：

上面的计划树：“TBL1上的顺序扫描”和“TBL2上的索引扫描”分别对应于表TBL1和TBL2上的表扫描方法。TBL1上的顺序扫描：从对应页中顺序获取数据；索引扫描：使用索引扫描访问表2。选择一个正确的扫描方法作为计划的一部分对于查询性能非常重要。

深入理解PG的扫描方法之前，先介绍几个重要的概念。

HEAP：存储表整个行的存储域。如上所示，整个域被分割为多个页，每个页大小默认是8K。每个页中，item指针（例如上述页中的1,2）指向页内的数据。

Index Storage：只存储KEY值，即索引中包含的列值。也是分割成多个页，每个索引页默认8K。

Tuple Identifier(TID)：TID为6个字节，包含两部分。前4个字节为页号，后2个字节为页内tuple索引。TID可以定位到特定记录。

当前版本，PG支持以下扫描方法：顺序扫描、索引扫描、索引覆盖扫描、bitmap扫描、TID扫描。依赖于表基数、选择的表、磁盘IO、随机IO、顺序IO等，每种扫描方法都非常有用。我们先创建一个表并预制数据，并解释这些扫描方法。

postgres=# CREATE TABLE demotable (num numeric, id int);
CREATE TABLE
postgres=# CREATE INDEX demoidx ON demotable(num);
CREATE INDEX
postgres=# INSERT INTO demotable SELECT random() * 1000,  generate_series(1, 1000000);
INSERT 0 1000000
postgres=# analyze;
ANALYZE

这个例子中，预制1亿条记录并执行analyze更新统计信息。

顺序扫描

顾名思义，表的顺序扫描就是顺序扫描对应表所有页的item指针。如果一个表有100页，每页有1000条记录，顺序扫描就会获取100*1000条记录并检查是否匹配隔离级别以及where条件。因此，即使只有1条记录满足条件，他也会扫描100K条记录。针对上表的数据，下面的查询会进行顺序扫描，因为有大部分的数据需要被selected。

postgres=# explain SELECT * FROM demotable WHERE num < 21000;
                             QUERY PLAN
--------------------------------------------------------------------
 Seq Scan on demotable  (cost=0.00..17989.00 rows=1000000 width=15)
   Filter: (num < '21000'::numeric)
(2 rows)

注意，不计算和比较计划耗费，几乎不可能直到选用哪个扫描方法。但是为了使用顺序扫描，至少需要满足以下关键点：谓词部分没有可用的索引键；或者SQL查询获取的行记录占表的大部分。如果只有少数行数据被获取，并且谓词在一个或多个列上，那么久会尝试使用或者不使用索引来评估性能。

索引扫描

和顺序扫描不同，索引扫描不会顺序获取所有表记录。相反，依赖于不同索引类型并和查询中涉及的索引相对应使用不同的数据结构。然后索引扫描获取的条目直接指向heap域中的数据，然后根据隔离级别判断可见性。因此索引扫描分两步：

从索引数据结构中获取数据，返回heap中数据对应的TID；然后定位到对应的heap页直接访问数据。由于以下原因需要执行额外的步骤：查询可能请求可用索引更多的列；索引数据中不维护可见信息，为了判断可见性，需要访问heap数据。

此时可能会迷惑，索引扫描如此高效，为什么有时不用呢？原因在于cost。这里的cost涉及IO的类型。索引扫描中，为了获取heap中的对应数据，涉及随机IO；而顺序扫描涉及顺序IO，只有随机IO耗时的1/4。

因此只有当顺序IO的代价大于随机IO时，才会选择索引扫描。

针对上表和数据，执行下面查询时会使用索引扫描。随机IO代价小，从而查询标记快。

postgres=# explain SELECT * FROM demotable WHERE num = 21000;
                                QUERY PLAN
--------------------------------------------------------------------------
 Index Scan using demoidx on demotable  (cost=0.42..8.44 rows=1 width=15)
   Index Cond: (num = '21000'::numeric)
(2 rows)

Index Only Scan

仅索引扫描和索引扫描类似，区别在于第二步，仅仅涉及到扫描索引数据。有两个条件：查询获取的数据只有key列，且该列是索引的一部分；所有获取的数据都是可见的。如下所示：

postgres=# explain SELECT num FROM demotable WHERE num = 21000;
                                  QUERY PLAN
-----------------------------------------------------------------------------
Index Only Scan using demoidx on demotable  (cost=0.42..8.44 rows=1 Width=11)
   Index Cond: (num = '21000'::numeric)
(2 rows)

Bitmap Scan

是索引扫描和顺序扫描的混合体。为了解决索引扫描的缺点并充分利用其优点。正如上面所说，对于索引数据结构中的数据，需要找到heap页中对应的数据。因此需要获取一次索引页，然后获取heap页，从而造成大量随机IO。Bitmap扫描方法平衡了不使用随机IO的索引扫描优点。

Bitmap index scan：首先获取索引数据并为所有TID创建bitmap。为了理解方法，可以认为bitmap包含所有页的哈希（基于页号），每个页的entry包含页内所有偏移的数组。

Bitmap heap scan：从页的bitmap中读取值，然后针对页和偏移扫描数据。最后检查可见性和条件并返回tuple。

下面查询使用bitmap扫描，因为他选择的记录很多（比如too much for index scan）但不是大量（too little for sequential scan）。

postgres=# explain SELECT * FROM demotable WHERE num < 210;
                                  QUERY PLAN
--------------------------------------------------------------------------
 Bitmap Heap Scan on demotable  (cost=5883.50..14035.53 rows=213042 width=15)
   Recheck Cond: (num < '210'::numeric)
   ->  Bitmap Index Scan on demoidx  (cost=0.00..5830.24 rows=213042 width=0)
      Index Cond: (num < '210'::numeric)
(4 rows)

再看另一个查询，选择同样多的记录但是仅仅索引列。不需要heap页因次没有随机IO，因此这个查询选择index only scan而不是bitmap scan。

postgres=# explain SELECT num FROM demotable WHERE num < 210;
                                   QUERY PLAN
---------------------------------------------------------------------------
 Index Only Scan using demoidx on demotable  (cost=0.42..7784.87 rows=208254 width=11)
   Index Cond: (num < '210'::numeric)
(2 rows)

TID Scan

TID扫描是PG中非常特殊的一种方式,和Oracle中的基于ROWID查询类似：

postgres=# select ctid from demotable where id=21000;
   ctid
----------
 (115,42)
(1 row)


postgres=# explain select * from demotable where ctid='(115,42)';
                        QUERY PLAN
----------------------------------------------------------
 Tid Scan on demotable  (cost=0.00..4.01 rows=1 width=15)
   TID Cond: (ctid = '(115,42)'::tid)
(2 rows)

此外，PG社区还在讨论其他的扫描方法：MySQL中的“Loose Index Scan”、Oracle中的“index skip scan”、DB2中的“jump scan”。这个扫描方法用在指定场景：选择的B-tree索引的key列值都不同。避免遍历所有相等的key值，而只遍历第一个唯一值然后跳到下一个大值。这项工作PG正在开发，同样被叫做“Index skip scan”，未来可以在release中看到这个特性。

原文

https://severalnines.com/database-blog/overview-various-scan-methods-postgresql