上一篇把索引从内存搬到了磁盘。现在对一个两词查询 “Java GC”，BM25 需要遍历两个词项的全部 posting list、对每个候选文档计算精确分数、维护 Top-K 堆。“Java” 的 posting list 有 5,000 条，“GC” 有 800 条——OR 查询的候选集最多 5,800 个文档，每个都要算一次 BM25。

但用户只看前 10 条结果。为了找到 Top-10，穷举 5,800 个文档是否必要？

答案是不必要。如果已经找到了分数很高的 10 篇文档，后面的文档只要能证明"它不可能比当前第 10 名更高"，就可以直接跳过。这就是查询剪枝的核心思路。

穷举的成本

穷举 Top-K 流程回顾

第 09 篇的 Top-K 算法对所有候选文档计算 BM25：

for (int docId : candidateDocs) {
    double score = bm25(queryTerms, docId);
    if (heap.size() < k || score > heap.peek().score()) {
        if (heap.size() == k) heap.poll();
        heap.offer(new ScoredDoc(docId, score));
    }
}

时间复杂度 O(N × Q × log K)，其中 N 是候选文档数，Q 是查询词项数，K 是返回结果数。对 Web 规模（N 可能数百万），这个成本不可接受。

实际观察

对一个两词查询，实际进入 Top-10 的文档只有 10 篇。剩下的 5,790 篇都白算了——它们的分数不够高。如果能提前判断"这个文档不可能进入 Top-10"，跳过它的 BM25 计算，查询就能快很多。

Skip List：跳过不相关的 Posting

问题

AND 查询的双指针交集算法遍历两个 posting list，时间 O(m + n)。当 “the”（m = 100,000）和 “NullPointerException”（n = 50）做 AND 时，“the” 的 posting list 中 99,950 条都不会出现在结果中，但线性扫描还是要一条一条走。

Skip Pointer

在 posting list 上每隔固定距离放一个跳跃指针。假设 “the” 的 posting list 是：

1	`[3, 5, 8, 12, 15, 20, 24, 28, 33, 41, 50, 62, ...]`

每隔 4 个放一个 skip pointer：

1
2
3

[3, 5, 8, 12] → skip to 15
[15, 20, 24, 28] → skip to 33
[33, 41, 50, 62] → skip to ...

交集算法的改进：当短列表指向 docID = 33，长列表指向 docID = 5 时，检查 skip：下一个 skip 目标是 15（< 33），跳过 [5, 8, 12]；再检查 skip：下一个 skip 目标是 33（= 33），跳过 [15, 20, 24, 28]，直接落在 33 上。

List<Integer> intersectWithSkip(PostingList p1, PostingList p2) {
    List<Integer> result = new ArrayList<>();
    while (p1.hasDoc() && p2.hasDoc()) {
        if (p1.docId() == p2.docId()) {
            result.add(p1.docId());
            p1.next();
            p2.next();
        } else if (p1.docId() < p2.docId()) {
            if (p1.hasSkip() && p1.skipDocId() <= p2.docId()) {
                p1.skip(); // 跳过一段
            } else {
                p1.next();
            }
        } else {
            if (p2.hasSkip() && p2.skipDocId() <= p1.docId()) {
                p2.skip();
            } else {
                p2.next();
            }
        }
    }
    return result;
}

Skip 间距选择

间距太小——skip pointer 本身占空间，每次判断是否跳也有成本。间距太大——跳过的机会少，退化为线性扫描。

理论最优间距：sqrt(L)，L 是 posting list 长度。直觉是：平衡了"跳跃次数"和"每次跳过的距离"，类似于分块查找的最优块大小。

posting 长度	最优间距	skip pointer 数量
100	10	10
10,000	100	100
1,000,000	1,000	1,000

实际系统（如 Lucene）使用固定间距（128），不按 sqrt(L) 调整——实现简单，效果足够。

DAAT：Document-At-A-Time

两种查询执行策略

TAAT（Term-At-A-Time）：逐词项处理。先遍历 “java” 的全部 posting，为每个 docID 在一张评分表（accumulator）中累加 BM25 贡献；再遍历 “gc” 的全部 posting 做同样的事。最后从评分表中选 Top-K。

问题：评分表大小等于所有出现过的文档数（OR 语义下可能很大），内存开销不可预测。

DAAT（Document-At-A-Time）：同时维护所有词项的 posting 指针，按 docID 从小到大推进。每次处理一个 docID，计算该文档在所有词项上的完整分数，立即决定是否进入 Top-K 堆。

List<ScoredDoc> daatTopK(List<PostingList> postings, int k) {
    PriorityQueue<ScoredDoc> heap = new PriorityQueue<>(
        Comparator.comparingDouble(ScoredDoc::score));

    while (anyHasDoc(postings)) {
        // 找到所有指针中最小的 docID
        int minDoc = Integer.MAX_VALUE;
        for (PostingList p : postings) {
            if (p.hasDoc() && p.docId() < minDoc) {
                minDoc = p.docId();
            }
        }

        // 计算 minDoc 的完整 BM25 分数
        double score = 0;
        for (PostingList p : postings) {
            if (p.hasDoc() && p.docId() == minDoc) {
                score += bm25Component(p, minDoc);
                p.next();
            }
        }

        // 更新 Top-K 堆
        if (heap.size() < k) {
            heap.offer(new ScoredDoc(minDoc, score));
        } else if (score > heap.peek().score()) {
            heap.poll();
            heap.offer(new ScoredDoc(minDoc, score));
        }
    }
    return sortedDesc(heap);
}

DAAT 不需要全量 accumulator——一次只处理一个文档，内存只需要 Top-K 堆和各词项的指针。更重要的是，DAAT 天然适配剪枝：因为始终知道当前 Top-K 堆的最低分（threshold），可以用这个阈值判断后续文档是否值得计算。

WAND：安全的 Top-K 剪枝

核心观察

BM25 的每个词项对一篇文档的贡献有上界。“gc” 在任何文档中的最大可能 BM25 贡献不会超过某个值 UB_gc——这个值在最短文档、最高词频情况下取得。

如果某个文档在所有查询词项上的贡献上界之和仍然低于当前 Top-K 阈值，这个文档不可能进入结果集，可以安全跳过。

上界分数计算

对词项 t，预计算全局上界：

double upperBound(String term) {
    double idf = computeIdf(term);
    // BM25 的 TF 部分在 tf → ∞ 时趋近于 (k1 + 1)
    // 在 dl = 最短文档长度时归一化项最小
    double minNorm = 1 - b + b * (minDocLength / avgDocLength);
    double maxTfComponent = (k1 + 1) / (1 + k1 * minNorm);
    // 实际上界：实际最高 tf 对应的精确值
    return idf * maxTfComponent;
}

粗略上界：UB_t ≈ idf(t) × (k1 + 1)，因为 BM25 的 TF 饱和项上界是 k1 + 1 = 2.2。

WAND 算法

WAND（Weak AND）由 Broder 等人在 2003 年提出。它在 DAAT 框架内增加了一步：在计算精确分数之前，先用上界判断是否值得计算。

function wand_topk(query_terms, k):
    heap = MinHeap(capacity=k)
    threshold = 0

    while any posting list has remaining docs:
        // 按各词项当前指向的 docID 排序
        sort query_terms by current_docId ascending

        // 找 pivot：累加上界直到 >= threshold
        cumulative_ub = 0
        pivot_index = -1
        for i = 0 to len(query_terms) - 1:
            cumulative_ub += UB[query_terms[i]]
            if cumulative_ub >= threshold:
                pivot_index = i
                break

        if pivot_index == -1:
            break  // 没有文档能超过 threshold，结束

        pivot_doc = query_terms[pivot_index].current_docId

        // 检查 pivot_doc 之前的所有词项是否也指向 pivot_doc
        if all terms[0..pivot_index] point to pivot_doc:
            // 完全候选：计算精确 BM25 分数
            score = exact_bm25(pivot_doc, query_terms)
            update_heap(heap, pivot_doc, score)
            threshold = heap.size() == k ? heap.peek().score : 0
            advance all terms past pivot_doc
        else:
            // 不完全候选：把最前面的 term 跳到 pivot_doc
            first_term = terms[0]  // docId 最小的那个
            first_term.advance_to(pivot_doc)  // 用 skip list 加速

手算示例

查询 “java gc”，Top-3，UB_java = 1.2，UB_gc = 1.8。当前堆最低分 threshold = 1.5。

java posting: [3, 7, 12, 20, 35, ...]  当前指向 doc 7
gc posting:   [5, 12, 18, 22, ...]     当前指向 doc 5

排序后: gc(doc=5), java(doc=7)

累加上界: UB_gc = 1.8 >= threshold(1.5) → pivot_index = 0, pivot_doc = 5

terms[0..0] 只有 gc，检查 gc 是否指向 doc 5 → 是
但 java 不指向 doc 5（指向 doc 7）
→ 不完全候选（只有 gc 的上界就够了，但 java 不在 doc 5）

方案A：直接对 doc 5 算精确 BM25（只有 gc 的贡献）
方案B：按严格 WAND，把前面的 term 跳到 pivot_doc

实际上 doc 5 只包含 gc 不包含 java，精确分数 = BM25_gc(doc5)。
如果这个分数 > threshold，进堆。

剪枝效果

WAND 跳过的文档不会影响结果正确性——它跳过的都是"上界都不够"的文档，精确分数只会更低。

对典型 Web 查询，WAND 可以跳过 80-95% 的候选文档评分计算。效果取决于：

查询词的 IDF 分布：高 IDF 词的上界更大，更容易成为 pivot
Top-K 堆的阈值：阈值越高，越多文档被剪枝

BlockMaxWAND

WAND 的上界是全局的——UB_java 是 “java” 在所有文档中的最大可能贡献。但对一个特定的 posting list 区间，实际最大贡献可能远低于全局上界。

BlockMaxWAND（Ding & Suel, 2011）把 posting list 切成固定大小的 block（如 128 个 posting），预计算每个 block 内的最大贡献。

1 2	`java posting: [block0: max=0.8] [block1: max=1.2] [block2: max=0.3] ... gc posting: [block0: max=1.5] [block1: max=0.9] [block2: max=1.8] ...`

当 threshold = 1.6 时，java 的 block2（max=0.3）加上 gc 的 block0（max=1.5）= 1.8 >= 1.6，需要检查。但 java 的 block2（max=0.3）加上 gc 的 block1（max=0.9）= 1.2 < 1.6，整个 block 可以跳过。

BlockMaxWAND 的上界比 WAND 更紧，跳过更多文档。Lucene 从 8.0 版本开始默认使用这种策略。

本篇不实现 BlockMaxWAND——它需要修改段文件格式来存储每个 block 的最大分数。但理解它的思路有助于后续阅读 Lucene 源码。

验证

场景	验证方法
Skip list 正确性	有 skip 和无 skip 的 AND 查询返回相同 docID 集合
DAAT 正确性	与穷举方式返回相同的 Top-K 和分数
WAND 正确性	与穷举 DAAT 返回相同的 Top-K，分数精确到小数点后三位
剪枝效果	记录 WAND 实际计算 BM25 的文档数 vs 候选总数

关键验证指标：对 10 个查询，记录穷举访问的文档数和 WAND 访问的文档数，计算跳过比例。

for (Query q : testQueries) {
    List<ScoredDoc> exhaustive = exhaustiveTopK(q, 10);
    List<ScoredDoc> wand = wandTopK(q, 10);

    assert exhaustive.size() == wand.size();
    for (int i = 0; i < exhaustive.size(); i++) {
        assert exhaustive.get(i).docId() == wand.get(i).docId();
        assert Math.abs(exhaustive.get(i).score() - wand.get(i).score()) < 1e-3;
    }

    System.out.printf("查询 '%s': 穷举 %d 篇, WAND %d 篇, 跳过 %.1f%%\n",
        q.text(), exhaustiveCount, wandCount,
        100.0 * (exhaustiveCount - wandCount) / exhaustiveCount);
}

当前局限

Skip list 间距是固定的，没有根据查询模式自适应
WAND 实现是教学级的，排序用 Arrays.sort 而非原地维护
没有实现 BlockMaxWAND——第 15 篇迁移到 Lucene 后自动获得
上界计算比较粗糙，更紧的上界需要更多预计算
多词项查询（3+ 个词项）的 WAND 效果更好，但本篇的小数据集可能体现不出优势

练习

对一个 1,000 条的 posting list，分别用 skip 间距 10、32、100 做 AND 查询，记录比较次数
构造一个 WAND 可以跳过大量文档的场景：一个高 IDF 词和一个低 IDF 词的 OR 查询
对同一组查询，分别用穷举 Top-10 和 WAND Top-10，验证结果一致并记录时间差异
将 threshold 固定为 0（空堆），观察 WAND 退化为穷举的行为——理解 threshold 对剪枝效果的关键作用
阅读 Lucene 源码中 MaxScoreBulkScorer 的注释，理解 BlockMaxWAND 在工程上的实现选择

从零构建现代搜索引擎（11）：查询为什么不必扫描全部候选