面试题：PostgreSQL位图扫描的基本原理

Question

请阐述PostgreSQL位图扫描的基本原理，以及在何种场景下会触发位图扫描？

Answer 1

PostgreSQL位图扫描基本原理

1. 初始扫描：
   • 首先进行一个或多个子扫描（通常是索引扫描），这些子扫描会产生一组指向表中数据行的物理位置（即元组标识，简称TIDs）。
   • 例如，假设表employees有两个索引，一个按department列，另一个按salary列。如果查询条件是department = 'HR' AND salary > 50000，就可能先分别使用这两个索引进行扫描，得到两组TIDs。
2. 位图构建：
   • 把这些子扫描得到的TIDs收集起来，构建成一个位图。位图是一种紧凑的数据结构，它以位（bit）为单位来表示表中每一行是否被选中。
   • 比如，表有1000行数据，对应位图有1000个位，第1个位对应表的第1行，第2个位对应表的第2行，依此类推。如果某一行被选中，对应的位就设为1，否则设为0。
3. 最终扫描：
   • 利用构建好的位图，一次性扫描表中的数据行。只访问位图中标记为1的那些行，避免了对未选中行的不必要访问。
   • 例如，通过前面的例子构建好位图后，直接扫描表时，只读取那些在位图中对应位为1的行，这样就大大减少了I/O操作。

触发位图扫描的场景

1. 多条件组合查询：
   • 当查询涉及多个过滤条件，且这些条件分别有可用的索引时，可能触发位图扫描。例如上述employees表的例子，department = 'HR' AND salary > 50000，department和salary列都有索引，PostgreSQL可能选择位图扫描，先分别利用索引得到满足单个条件的TIDs，再通过位图合并处理满足两个条件的行。
2. OR条件查询：
   • 如果查询条件使用OR连接，且每个OR分支都有可用索引，也可能触发位图扫描。比如查询department = 'HR' OR salary > 50000，PostgreSQL可以通过不同索引分别扫描，构建位图并最终合并结果。
3. 部分索引场景：
   • 当表上存在部分索引，并且查询条件能有效利用这些部分索引时，可能触发位图扫描。例如，表orders上有一个部分索引idx_orders_high_value，只对total_amount > 1000的行创建索引。如果查询是total_amount > 1000 AND order_status = 'completed'，PostgreSQL可能利用这个部分索引结合其他索引（如果order_status有索引）进行位图扫描。