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
