skip to content

In a document tag filter, which set operation returns documents tagged either label, and which returns documents tagged both?

level: juniorimportance: must knowfreq 72%

answer

  1. a label names a set of documents
  2. one filter widens, the other narrows
  3. or here is inclusive, never exclusive
  4. at least one versus every operand
  5. check the empty selection case

basics

~20 s

Union gives 'either' — every document carrying at least one of the labels. Intersection gives 'both' — only documents carrying every selected label. As a user ticks more labels a union can only stay the same or grow; an intersection can only stay the same or shrink.

solid answer

~50 s

Model each label as the *set of documents carrying it*: `A` is everything tagged `invoice`, `B` everything tagged `paid`. 'Tagged either' is the **union** `A ∪ B` — a document qualifies if it is in `A`, in `B`, or in both, because the 'or' of set algebra is inclusive, never exclusive. 'Tagged both' is the **intersection** `A ∩ B`, which requires membership in every operand. The consequence that matters in a product is that the two move in opposite directions: adding another label to a union can only keep the result the same size or enlarge it, while adding one to an intersection can only keep it the same or shrink it. Both operations are commutative and associative, so the order the user ticks the boxes cannot change the result set — only the wording of the filter can.

go deeper

for a junior

Know which word maps to which operation: 'any' is union, 'all' is intersection, 'but not' is difference. Be able to say which filter widens and which narrows as more labels are selected.

for a middle

Explain the monotonicity bounds and the identities behind them — commutativity, associativity, idempotence, absorption — and why they let an engine reorder the operands without changing the answer.

for a senior

Show you have specified the edges: empty selection, an unused label, a duplicated label in the request. Say which convention your product ships and where that is written down.

for a principal

Whether the default filter is 'any' or 'all' changes result sizes by orders of magnitude and changes what users believe the product does. Own that as a contract decision, not as an implementation detail each surface re-decides.

## Model a label as a set of documents The first move is a change of viewpoint, and everything else follows from it. The obvious mental model is 'a document has a list of tags'. The useful one is the dual: **each label names the set of documents that carry it**. Let `A` be the set of documents tagged `invoice` and `B` the set tagged `paid`. Every filter a user can build from those two checkboxes is now an expression in set algebra over `A` and `B`, and questions like 'what does this return?' and 'how big can it get?' become algebra instead of guesswork. The collection everything is drawn from — the whole corpus — is the **universe**, written `U`. Every set in play is a subset of `U`. ## The three operations a filter is built from - **Union** `A ∪ B` — every document that is in `A`, in `B`, or in both. This is the *inclusive* or. A document tagged both labels is in the union, and it is in it exactly once. This implements 'match any of the selected tags'. - **Intersection** `A ∩ B` — only the documents that are in `A` **and** in `B`. This implements 'match all of the selected tags'. - **Difference** `A \ B` — the documents in `A` that are not in `B`: 'tagged invoice but not paid'. | The user sees | The expression | What it does as more labels are ticked | |---|---|---| | Match any of these tags | `A ∪ B ∪ C` | stays the same or grows | | Match all of these tags | `A ∩ B ∩ C` | stays the same or shrinks | | Tagged this but not that | `A \ B` | shrinks as the excluded side grows | ## Why the direction of movement matters The two operations are **monotone in opposite directions**, and that single fact explains most filter bugs that reach a bug tracker: 1. A union is bounded below by its biggest operand: `|A ∪ B| ≥ max(|A|, |B|)`. Ticking another label can never remove a document that already matched. 2. An intersection is bounded above by its smallest operand: `|A ∩ B| ≤ min(|A|, |B|)`. Ticking another label can never add a document that did not already match. 3. Neither is *strict*. If every document tagged `paid` is also tagged `invoice`, then `A ∪ B = A` and `A ∩ B = B`: the result does not move at all. 'Can only stay the same or grow' is the honest statement; 'always grows' is not. So a screen whose result count goes **up** when a user adds a restriction is telling you the filter is a union where the copy promises an intersection, or the reverse. Exact sizing of a union of many overlapping label sets is a separate problem with its own machinery; the bounds above are all you need to sanity-check a filter. ## The identities you are allowed to lean on These hold for any sets, and query planners rely on them: - **Commutative**: `A ∪ B = B ∪ A`, `A ∩ B = B ∩ A`. The order the user clicks does not matter. - **Associative**: `(A ∪ B) ∪ C = A ∪ (B ∪ C)`. Grouping does not matter, so an engine may combine the cheapest pair first. - **Idempotent**: `A ∪ A = A`, `A ∩ A = A`. A duplicated label in the request is harmless. - **Distributive**: `A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)`. 'Invoices that are paid or overdue' can be evaluated either way round. - **Identity and annihilator**: `A ∪ ∅ = A`, `A ∩ U = A`, `A ∩ ∅ = ∅`, `A ∪ U = U`. - **Absorption**: `A ∪ (A ∩ B) = A`. Adding a narrower condition to a union changes nothing. Together these say a filter is *not* a sequence of steps whose order the user controls; it is an expression whose value is fixed by which labels were chosen and which connective the product uses. ## The edge case interviewers actually push on What should the filter return when **no labels are selected**? Set algebra gives a clean answer, and it is different for the two connectives: a union over an empty family of sets is the empty set, while an intersection over an empty family is the whole universe — every document vacuously satisfies 'all zero of these labels'. Most products therefore show the whole corpus for an empty selection, which is the intersection convention, even when the filter itself is an 'any of these' union. That is a deliberate choice, not a derivation, and it belongs in the contract rather than in whichever branch the code happened to take. The second edge is a label nobody uses: its set is `∅`, so it is invisible in a union and catastrophic in an intersection, where it empties the result. A filter that silently returns nothing after a typo in a label name is this rule firing exactly as specified.

  • What should the filter return when the user has selected no labels at all?
    Algebraically the two connectives disagree: a union over an empty family is the empty set, an intersection over an empty family is the whole universe, because every document vacuously carries all zero labels. Most products show everything, which follows the intersection convention. The point is that it is a stated product choice, not an accident of which loop the code runs.
  • A user ticks a label that no document carries. What happens to each kind of filter?
    That label's set is empty. In a union it changes nothing, since the empty set is the identity for union. In an intersection it wipes the result out, since intersecting with the empty set gives the empty set. A filter that suddenly returns zero results after one extra tick is usually this, most often caused by a mistyped or newly renamed label.
  • Why may a query planner evaluate 'tagged all of X, Y and Z' in whatever order it likes?
    Intersection is commutative and associative, so every grouping and ordering of the three sets yields the same set. That freedom lets an engine start with the smallest label set and shrink the working set as fast as possible. It is a performance choice with no effect on the answer, which is exactly what those two identities guarantee.

saying these in an interview costs you the question

  • Reads 'tagged either label' as excluding documents that carry both.
  • Expects an 'any of these tags' filter to narrow as more labels are ticked.
  • Says an intersection can be larger than the smaller of its two inputs.
  • Believes the order the user selects labels changes the result set.
  • Assumes a document tagged both labels appears twice in the union.
  • Claims adding a label to a union must strictly increase the result.