“多个访问路径的RID还可在位图堆访问中按物理出现做AND/OR组合，再按页回表。忘掉槽号的lossy页必须完整重检；同一RID只检索一次，不会把不同RID的同值记录去重，原索引键序也不能沿用。”
形式陈述
输入合同与两种精度
固定同一只读快照，U 为该次执行可能遇到的物理行出现编号集合；每个 i 属于一个堆页 h(i)，同值两行仍是两个编号。可见性函数 visible(i) 由存储层提供；TID在整个构建与消费期指向同一可解释的版本。槽复用、版本链和快照维护是该输入合同的一部分，本页不实现MVCC，也不把TID当跨事务永远不变的业务主键。
对三值谓词p，定义真实匹配 T_p={i∈U:visible(i) 且 p(i)=TRUE}。一个访问路径返回候选超集 C_p，须满足 T_p⊆C_p⊆U；可含不可见版本或谓词假阳性。索引只覆盖部分条件时，缺少的条件仍需重检，不能把“索引交付过”当成整条WHERE已成立。
位图按页保存三种状态：空页∅；Exact(S,r)，其中S为该页的候选槽集合，r为recheck标志；Lossy，表示该页全部合法槽都为候选且必须重检。同一页只保存一种状态。Exact说的是位置已精确列出，不是必然证明谓词为真：r=true的Exact仍可含假阳性；r=false才表示此访问路径对其负责的谓词提供了匹配证据，可见性仍单独核对。
对表示B，以γ(B)记它展开后的候选出现集合。将Exact(S,r)退化为Lossy只会扩大γ(B)，不会删除真结果。访问时先把页pin住，再枚举其指定候选槽，校验可见性并计算完整目标谓词；读失败、无效TID或预算无法满足应报错或进入另行完整执行的退路，不能当作空页略过。
AND与OR的完整逐页规则
下面给出对称、保守的教学组合；A、B是两条访问路径负责的谓词。空页与任一页AND为空，与任一页OR保持后者。非空情况为：
| 左页 | 右页 | AND候选 | OR候选 |
|---|---|---|---|
| Exact(S,r) | Exact(T,s) | Exact(S∩T,r∨s) | Exact(S∪T,r∨s) |
| Exact(S,r) | Lossy | Exact(S,true) | Lossy |
| Lossy | Exact(T,s) | Exact(T,true) | Lossy |
| Lossy | Lossy | Lossy | Lossy |
空的Exact正规化为空页。这里把两个recheck标志作OR是安全的保守传播；有些分支本来已被另一条件证明，也允许多做重检。AND混合时保留较精细的一侧只能证明“最多这些位置匹配”，所以必须置recheck。OR混合必须保留整页，否则可能漏掉仅满足有损一侧的出现。
该表实现γ(B_AND)=γ(B_A)∩γ(B_B)、γ(B_OR)=γ(B_A)∪γ(B_B)。实际系统还可继续降精度，只要求结果γ是这些集合的超集。PostgreSQL滚动master源码的一种原地AND分支会保留左侧lossy页而非恢复右侧精确槽，因此其候选可更粗；它仍满足下述不漏结果证明。本页不宣称逐步复制该源码或PostgreSQL 18固定tag。
不漏与重检恢复的证明
按SQL真值表，A AND B为TRUE当且仅当两者为TRUE；A OR B为TRUE当且仅当至少一个为TRUE。因此
逐页规则保持或扩大右侧候选，任意次合法降精度仍保持真实结果包含于候选。对最终目标q，令C为组合后的候选，则完整输出位置
左到右的包含由输出重检定义得到；右到左由T_q⊆C且每个真结果通过可见性及q检查得到。每个候选TID只访问并交付一次，所以投影后的重数为
完整目标谓词必须保留原布尔结构。q=A OR B时，不能重检为A AND B，也不能要求两个分支都命中。r只是指出不能省去哪些证明工作；本页终点保守地对所有候选重算完整q，所以exact模式也核对。NOT不属于本组合：候选超集的补集可能漏掉真反例，不能把这份AND/OR证明直接用于否定查询。
直觉
位图把“搜索键顺序”转换为“这次该去哪几页、哪些槽”。两个索引都找到同一TID时，把这个访问任务合并为一次；两份值相同却TID不同的记录仍有两个访问任务。这个去重发生在物理出现层，不是SQL DISTINCT。
有损页像只记住门牌而忘了房间号：少存位置细节，代价是进门后多检查几间房。它提供的是不会漏掉真房间的覆盖保证，不能凭“这一页被标记”就把页里所有人都当作答案。
图上0/1表示“是否进入TRUE候选集合”，不是谓词的三值结果编码；位置6的y=NULL产生UNKNOWN，所以y路径的候选位为0。
例子与边界
同一十二行的AND、OR与重复值
每页三份，位置0..11依次分到页0..3。沿用x=[1,1,0,1,0,1,0,1,1,0,1,0]，y=[1,1,1,0,1,1,NULL,1,0,0,1,1]，v=[10,10,20,30,40,50,60,70,80,90,100,110]，所有行可见。
路径A为x=1，精确位置[0,1,3,5,7,8,10]共7份；路径B为y=1，精确位置[0,1,2,4,5,7,10,11]共8份。AND为[0,1,5,7,10]，输出[10,10,50,70,100]，SUM=240。
OR为[0,1,2,3,4,5,7,8,10,11]共10份，输出和为520；位置6的条件为FALSE OR UNKNOWN，不为TRUE，位置9两侧都FALSE。直接拼接两次索引扫描则有7+8=15份，交集中的五份都被重复返回，和会成为760。对值做set又会把两个10压成一个，AND的SUM错误地变为230。正确方法只消除同一个TID的重复检索。
预算迫使候选扩张
对AND结果的页1，把精确槽{2}（全局5）退化为整页{0,1,2}（全局3、4、5）。新候选为[0,1,3,4,5,7,10]共7份。位置3是(1,0,30)，位置4是(0,1,40)，完整AND重检删掉它们，仍为240；若不重检，则错误得到310。
为让预算行为可复算，检查器定义玩具费用：每个非空exact页记3单位，每个lossy页记1单位，空页记0，另有固定控制区；这不是PostgreSQL字节数。预算只约束最终交付的单个位图表示，不是整个执行器的峰值内存；构建期两条输入位图、临时副本和结果同时存活时须另外相加。检查器先构造再复制降精度，没有证明流式构建也在同一预算内完成。四个exact页共12，预算10时按指定次序先退化页1，费用恰降到10；预算4时四页全lossy，检查12份仍只输出5份；预算3连四个lossy页也容不下，必须报CapacityExceeded。这是受限表示的教学策略，不是无限制丢候选以适应任意小内存。
在组合前降精度也成立。例如先将A的页1退化，再与B的该页精确槽{1,2}相交，候选为全局{4,5}且recheck=true；位置4虽在精确位置集合里仍是假匹配，重检删掉它。这个例子说明“结果页不是lossy”不等于“不需要重检”。
读几页不能只数匹配行
固定冷缓存、堆共4页、两个索引路径合计读2个索引页、候选按堆页集中且每页只读一次，均不含输出写入。五个AND候选分布在全部4个堆页，因此索引加回表为2+4=6次页读，无索引全扫只需4。按行选择率5/12认为索引必胜是错误的。
迁移到已由访问路径完整保证只选位置0、1的条件，仍假定索引成本2页，则只读堆页0，共3<4。这里改变了候选分布与条件，不能通过免费扫描全表找出0、1后倒算为3。若实际使用不同索引、额外条件或可见性辅助页，应重新计算索引和辅助费用。
推论与应用
候选结构、计算与存储各有账本
稠密位图长度为N、机器字宽w时，一次完整AND/OR按字级并行需O(ceil(N/w))个字操作；N=0单独处理。它不是每个N都O(1)。稀疏按页哈希、排序的TID列表或压缩位图有不同构建、合并、迭代费用，不能一律照搬稠密界；本页Python集合实现只验证集合合同，不测量该字操作界。
令J为索引页读数、H(C)为候选所覆盖堆页数，理想同页复用下输入页账为J+H(C)。再单独加候选构建、位图操作、可见性检查、完整谓词重检、位置gather、输出复制和辅助状态读取。降精度可降低候选表示空间却增加重检数；本例页1本来就需访问，所以5→7候选未增加堆页，却增加两次完整谓词检查。物理计划成本必须同时核对空间可行性与这些不同费用，不能把少分派当少I/O。
先完成位图再按页访问通常形成一个构建阶段；它不等于逐命中立刻回表的索引流水线。页顺序访问丢掉各索引原有键顺序，ORDER BY需要另有合法排序或顺序证明。例中v碰巧随位置非降；改为u=120−10i后，AND的堆序值为[120,110,70,50,20]，显然不是升序。物理访问次序不能替用户承担排序合同。
与批次接口组合及失败边界
堆页枚举出的候选可由批次接口携带任意I送到重检算子。批次S只标记当前已确认保留的位置，lossy标志不应被当作validity或最终选择掩码；它描述的是证据精度。若消费者保留页内列引用，下一页复用之前必须消费、复制或延长pin。
假如索引构建在第一个页后读失败，未出现的页没有“不匹配”证明；返回部分bitmap会造成假阴性。构建应只有成功完成才能READY，失败须保留FAILED。构建完成后堆读失败也不能把那个页当没有真结果。允许重新规划为全扫时必须重启同一观察合同下的完整查询，并处理已交付前缀的去重/回滚责任；本页检查器选择直接报错，不伪造透明恢复。
本接口与B+树的区别在于多路径位置组合及有损证据；B+树仍负责各自的有序索引查找。它也不是Bloom Filter：这里能枚举候选TID或候选页，误差由忘掉槽号等机制引起，不采用哈希假阳性概率公式。完整任务与检查器把真假出现、预算降精度和6对4页的取舍放在同一终点核对。
参考资料
- PostgreSQL 18，Combining Multiple Indexes，§11.5：多个索引以AND/OR组合、按堆物理顺序访问及索引顺序丢失。十二行数据、6/4与3/4页比较为本文自定条件账本
- PostgreSQL官方tidbitmap.c源码浏览，2026-10-08读取的滚动git master，文件注释第6–29行、逐页表示第51–90行、tbm_union_page与tbm_intersect_page：位置精度和recheck可以分离。此链接不是固定18源码；本文对称逐页表、预算单位和证明是独立教学实现