How do you evaluate Boolean AND and OR over postings lists?

Intersection. With two sorted lists of lengths m and n, walk both with two cursors: equal IDs are a match, otherwise advance the smaller. That costs O(m + n). For several terms, Introduction to Information Retrieval recommends processing in order of increasing document frequency, so the intermediate result is never larger than the rarest list.

Union. Merge the sorted lists, emitting each ID once: also O(m + n).

import java.util.*;

public class Postings {
    // Both lists are sorted doc IDs without duplicates.
    static List<Integer> and(List<Integer> a, List<Integer> b) {
        List<Integer> out = new ArrayList<>();
        int i = 0, j = 0;
        while (i < a.size() && j < b.size()) {
            int x = a.get(i), y = b.get(j);
            if (x == y) { out.add(x); i++; j++; }
            else if (x < y) i++;                         // advance the smaller cursor
            else j++;
        }
        return out;
    }

    static List<Integer> or(List<Integer> a, List<Integer> b) {
        List<Integer> out = new ArrayList<>();
        int i = 0, j = 0;
        while (i < a.size() || j < b.size()) {
            if (j == b.size() || (i < a.size() && a.get(i) < b.get(j))) out.add(a.get(i++));
            else if (i == a.size() || b.get(j) < a.get(i)) out.add(b.get(j++));
            else { out.add(a.get(i)); i++; j++; }        // same doc in both lists
        }
        return out;
    }

    // AND over many terms: start from the rarest list so the candidate set shrinks fastest.
    static List<Integer> andAll(List<List<Integer>> lists) {
        List<List<Integer>> sorted = new ArrayList<>(lists);
        sorted.sort(Comparator.comparingInt(List::size));
        List<Integer> acc = sorted.get(0);
        for (int k = 1; k < sorted.size() && !acc.isEmpty(); k++) acc = and(acc, sorted.get(k));
        return acc;
    }

    public static void main(String[] args) {
        Map<String, List<Integer>> index = Map.of(
            "red", List.of(1, 3, 5, 8, 13), "dress", List.of(2, 3, 8, 21), "linen", List.of(3, 21));
        System.out.println(andAll(List.of(index.get("red"), index.get("dress"), index.get("linen")))); // [3]
        System.out.println(or(index.get("red"), index.get("linen")));                                 // [1, 3, 5, 8, 13, 21]
    }
}

Verified with OpenJDK 21.0.13: it prints [3] and [1, 3, 5, 8, 13, 21].

Making AND faster. Skip pointers, or skip lists in Lucene's postings format, let the cursor on a long list jump past many IDs that cannot match. When one list is far shorter, binary-searching or galloping through the longer one beats a linear walk.

Beyond Boolean. Phrase queries such as "linen dress" also check that positions are adjacent, so they need a positional index. Real engines do not intersect then score; they score while iterating and can skip documents that cannot reach the top K, see the top-K question below.