The question has structure

A support search receives the text router blinking red and these selections:

The prose query expresses relevance. The selections express eligibility. A document for Cable on iOS may repeat every query word and still be the wrong answer.

Suppose a ranker turns each required value into a large bonus. No finite bonus makes the predicate hard: enough other evidence can overcome it. An infinite bonus is merely a filter written obscurely, with awkward missing-value and explanation semantics.

A secondary index is an inverse question

Let $D$ be the finite set of document identities. For an attribute $a$, let $V_a$ be its value domain and record the authored or extracted relation

$$R_a\subseteq D\times V_a.$$

This is a relation rather than necessarily a function: one document may have many tags or languages, and another may have no value at all.

For a value $v$, equality selection asks for its inverse image:

$$E_a(v)=\{d\in D:(d,v)\in R_a\}.$$

That equation is an index specification. A scan, a sorted posting list, and a bitmap are different representations of the same set.

Several query forms follow without a new abstraction:

• categorical equality: $E_a(v)$;
• any of several values: $\bigcup_{v\in Q}E_a(v)$;
• all required values: $\bigcap_{v\in Q}E_a(v)$;
• a range: $\bigcup_{\ell\le v\le h}E_a(v)$, or an ordered index that computes the same set directly;
• presence: $\{d:\exists v.(d,v)\in R_a\}$;
• exclusion inside universe $U$: $U\setminus E_a(v)$.

The phrase “inside universe $U$” matters. A complement without a declared universe is incomplete. For authorization, $U$ must already contain only the documents the principal is permitted to know exist.

Missing is a value only when the product says so

If document $d$ has no platform relation, does platform = Android include it? Usually not. Does platform ! iOS= include it? Three policies are possible:

1. missing means unknown, so neither equality nor inequality admits it;
2. missing means not applicable, so a separate authored value admits it;
3. missing is treated as a literal value, so it can be selected explicitly.

These policies answer different questions. Implementing inequality as a raw complement silently chooses the third unless presence is tracked separately. A reliable query contract records the missing-value policy rather than letting the carrier decide it.

Filters compose as sets

For the support query, define

$$U=E_{product}(\text{Fiber}) \cap E_{platform}(\text{Android}) \cap E_{version}(\text{current}) \cap E_{kind}(\text{troubleshooting}).$$

The text scorer $s_q:D\to\mathbb R$ need only be observed on $U$. The correct answer is

$$\operatorname{TopK}_k\{(d,s_q(d)):d\in U\}.$$

A fused evaluator may test membership while traversing postings instead of materializing $U$. That changes execution, not meaning. It is correct when it admits exactly the same identities and computes the same scores.

The smallest post-filter failure

Let $k=2$ and let three globally ranked documents be

Ranking globally to two results yields $[A,B]$. Filtering afterward yields $[B]$. But exhaustive ranking over the eligible universe yields $[B,C]$.

Proof. The first two procedures rank the same scored pairs $\{(d,s_q(d)):d\in U\}$ under the same total order, so their first $k$ pairs are equal. The three-document table is a counterexample to the post-filtered pipeline. $\square$

Increasing the global cap is not a proof. Any finite over-fetch factor can be defeated by placing enough ineligible documents above the first eligible one. The safe alternatives are to incorporate eligibility during candidate evaluation or to continue retrieval until $k$ eligible results are proven.

Permission is an information boundary

Post-filtering is especially dangerous for access control. Even if forbidden documents are removed from the final list, they may already have affected:

• whether the list is short;
• a reported total count;
• facet counts and available facet labels;
• score normalization or query suggestions;
• latency and cache behavior;
• snippets, explanations, logs, or telemetry.

The authorized universe must therefore bound every derived observation, not only the rendered result rows. An index shard, posting, cache entry, vector, thumbnail, transcript, and explanation derived from a protected document inherits its boundary. A later chapter follows that information-flow rule through multimedia artifacts.

One set, several physical forms

A sorted posting list stores the members of $E_a(v)$ directly. Intersect two lists of lengths $m\le n$ by the adaptive methods from Chapter 4. Its work is related to the smaller set and the gaps it crosses.

An uncompressed bitmap assigns one bit to every dense document ordinal. A machine word of $w$ bits intersects $N$ possible ordinals in

$$\left\lceil N/w\right\rceil$$

word operations, almost independent of how many members survive. Union and relative complement use OR and AND-NOT over the same words.

Neither carrier wins universally:

Word-aligned compressed bitmap schemes retain the ability to combine runs without fully expanding them. But compression changes the crossover: corpus ordering, density, run length, update rate, cache behavior, and the particular Boolean workload all matter. “Low cardinality means bitmap” is a useful first hypothesis, not a representation law.

ELIGIBLE(U, P, STATISTICS)
Input:  declared universe U, predicates P[1:r], carrier STATISTICS
Output: identities that satisfy every predicate inside U

eligible ← U
for each predicate p in estimated increasing survivor order
    carrier ← CHOOSE-CARRIER(p, STATISTICS)
    eligible ← INTERSECT(eligible, EVALUATE(p, carrier))
    if eligible is empty
        return eligible
return eligible

The order may change work but not the set because intersection is associative, commutative, and idempotent. Estimation errors waste time; they must not change membership.

A facet is a counted partition, not a filter wearing a badge

A filter asks whether a document may participate. A facet summarizes how some declared set is distributed across values. A field score asks how much evidence an eligible document contributes. All three can reuse $R_a$, but they have different outputs and identities.

Suppose the corpus has ten documents, the text query matches six, and applying platform=Android leaves three. The label kind=manual might honestly show:

• 5 in the whole authorized corpus;
• 4 among the text-query matches before platform selection;
• 2 in the current eligible result set.

For a facet's own values, interfaces often count against the universe with that facet's current constraint removed so the reader can see alternatives. That is a fourth explicit question, not a magical “dynamic count.”

Name the counted set:

$$\operatorname{count}_{a=v}(Q)=|Q\cap E_a(v)|.$$

The number is meaningless without $Q$. A result contract should carry the universe identity or generation that produced it, so a delayed count cannot be labeled as if it answered a newer question.

Authored facts and inferred concepts

A product field may be authored by the publisher. A topic facet may be inferred from the document–term relation. Both can be useful, but their provenance and failure modes differ.

Authored metadata can be stale, missing, or inconsistent. Inferred concepts can drift when the analyzer, corpus, or clustering rule changes. A hard filter on either can hide the right answer more completely than a weak ranker can demote it. The index therefore records how each attribute was obtained and the generation to which it belongs.

This is also why secondary indexes do not belong in one universal registry of “search boosts.” Their schema, missing policy, provenance, update lifecycle, and authorization label are part of the relation's contract.

What to measure

For every carrier and predicate workload, record:

• corpus ordinals and set cardinalities;
• encoded bytes and retained bytes;
• construction and update cost;
• words, postings, cache lines, or blocks touched;
• conjunction, disjunction, exclusion, range, and count latency distributions;
• the crossover against a direct scan;
• equality with the mathematical set oracle.

The property that protects semantics is simple: for every generated corpus and hard predicate, optimized filtered top-k equals exhaustive ranking over exactly the eligible ordinals. Keep the exhaustive path. A fast filter can otherwise return a plausible but incomplete list.

Lessons

• A primary key names a document; a secondary key locates documents by another relation.
• Equality selection is an inverse image. AND, OR, and exclusion are intersection, union, and relative complement inside a declared universe.
• Filters define participation; scores define order; facets count partitions.
• Filtering a capped global top-k can starve the result and miss eligible winners. No fixed over-fetch factor repairs the proof.
• Missing-value semantics must be declared separately from complement.
• Sparse postings and dense bitmaps represent the same set with different machine costs; measure the crossover.
• Every facet count names the universe it counted.
• Authorization must constrain all derived observations, not just final rows.

Practice

1. Construct a four-document example showing that global top-$2$ followed by a filter returns no result even though two eligible documents exist.
2. Define platform ! iOS= under each of the three missing-value policies. Which sets differ?
3. For $N=1,000,000$ and $w=64$, compare the number of bitmap words touched with a posting intersection whose smaller side has 40 identities. Name the machine effects the operation counts omit.
4. Design facet counts for a selected color facet. State whether each count is over the whole authorized corpus, the text-match set, the current eligible set, or the set with the color constraint removed.
5. Write a generator for small metadata relations and prove that scan, postings, and bitmap evaluation return the same identity set for arbitrary conjunctions and disjunctions.

References

1. Kesheng Wu, Ekow J. Otoo, and Arie Shoshani. “Optimizing Bitmap Indices with Efficient Compression.” ACM Transactions on Database Systems 31, no. 1, 2006.
2. Elizabeth O'Neil, Patrick O'Neil, and Kesheng Wu. “Bitmap Index Design Choices and Their Performance Implications.” 11th International Database Engineering and Applications Symposium, 2007.
3. Ka-Ping Yee, Kirsten Swearingen, Kevin Li, and Marti Hearst. “Faceted Metadata for Image Search and Browsing.” Proceedings of CHI, 2003.
4. Jon Louis Bentley. “Multidimensional Binary Search Trees Used for Associative Searching.” Communications of the ACM 18, no. 9, 1975.