In information retrieval, a disjunctive query (often called an OR query) is a Boolean query that retrieves documents containing at least one of the specified terms. It uses the logical OR operator to broaden the search, increasing recall at the potential cost of lower precision. Disjunctive queries are a fundamental component of Boolean retrieval models and are contrasted with conjunctive (AND) queries, which require all terms to be present. They are widely used in search engines, database systems, and information filtering.

1.1 Boolean retrieval model

The Boolean retrieval model is a classical information retrieval framework in which documents are represented as sets of terms, and queries are formulated as Boolean expressions using operators AND, OR, and NOT. A document is considered relevant if it satisfies the Boolean expression exactly. In this model, each query term corresponds to a postings list—a list of document identifiers containing that term. The model provides a precise, set‑theoretic notion of relevance, but it does not rank results by degree of relevance.

1.2 Disjunction vs. conjunction

Disjunctive (OR) queries retrieve documents that contain any of the query terms, while conjunctive (AND) queries require all terms to be present. The choice between the two significantly affects retrieval behavior: disjunction broadens the result set, conjunction narrows it. For example, a query “cat OR dog” returns all documents mentioning either animal, whereas “cat AND dog” returns only those mentioning both.

1.2.1 Recall and precision trade-off

Disjunctive queries typically achieve higher recall because they capture more potentially relevant documents, but at the cost of lower precision—many returned documents may be only tangentially related. Conjunctive queries often yield higher precision but may miss relevant documents that do not contain every term. The trade-off is a central consideration in query design and system tuning.

1.2.2 Query length considerations

Longer disjunctive queries tend to retrieve very large result sets, as each additional term adds its postings list to the union. Conversely, longer conjunctive queries become increasingly restrictive, often producing few or no results. In practice, search engines frequently default to a conjunctive interpretation or blend both using ranking algorithms.

1.3 Term independence assumption

The Boolean model assumes that terms are independent—the presence of one term does not influence the probability of another. This simplifying assumption underlies the straightforward merging of postings lists for OR queries. While unrealistic for natural language, it enables efficient processing. More sophisticated models, such as probabilistic or vector space models, relax this assumption.

2.1 Postings list merging for OR queries

Processing a disjunctive query requires computing the union of the postings lists of all query terms. The result is a list of document identifiers sorted in ascending order (typically the order in which documents are stored). Efficient merging algorithms are essential for large indexes.

2.1.1 Naïve merge algorithm

The naïve approach iterates through all postings lists simultaneously using a multi‑pointer technique. At each step, the smallest current document identifier is output, and all pointers pointing to that identifier advance to the next posting. If multiple lists contain the same identifier, it is output only once. This algorithm has time complexity proportional to the sum of the lengths of all postings lists.

2.1.2 Optimized merge using skip pointers

To accelerate merging, postings lists can be augmented with skip pointers—additional pointers that jump ahead several positions. When one list’s current identifier is much smaller than another’s, the skip pointer allows the algorithm to skip over irrelevant postings without scanning them one by one. This reduces the number of comparisons and improves performance, especially for long postings lists of common terms.

2.2 Boolean query optimization

Optimizing Boolean queries involves minimizing the computational cost of evaluating the expression. For disjunctive queries, the goal is to reduce the total number of postings list accesses and comparisons.

2.2.1 Heuristic term ordering

One heuristic is to process terms with the shortest postings lists first, because the union of short lists tends to be smaller than that of long lists. By merging short lists early, intermediate result sizes are kept manageable. Another heuristic is to prioritize rare terms, as they contribute fewer documents to the union.

2.2.2 Use of inverted index compression

Inverted indexes are often compressed to reduce storage and I/O. Techniques such as variable‑byte encoding, gamma codes, or delta encoding represent document identifiers using fewer bits. Compressed postings lists can be processed directly without full decompression using specialized merge algorithms, further improving efficiency.

2.3 Handling of synonyms and stemming

Disjunctive queries naturally accommodate synonyms and morphological variants. For example, the query “run OR runs OR running” can be automatically expanded by a query processor using a stemmer (e.g., stemming all terms to “run”) or a synonym dictionary. Stemming reduces distinct terms to a common root, effectively turning a conjunctive query into a disjunctive one over variants. This technique increases recall but may introduce false matches.

3.1 Probabilistic and ranked retrieval models

Many modern retrieval systems move beyond pure Boolean logic. In probabilistic models, documents are ranked by the estimated probability of relevance given the query terms. Disjunctive queries appear implicitly when scoring functions sum over matched query terms.

3.1.1 Disjunctive queries in TF-IDF scoring

In TF-IDF (term frequency–inverse document frequency) scoring, a document’s score is the sum of TF-IDF weights for all query terms that appear in the document. This is inherently disjunctive: each matching term contributes positively, and no term is required. The resulting ranking naturally blends recall (more terms → higher score) with term importance weighting.

3.1.2 Impact on BM25 and language models

BM25, a widely used probabilistic ranking function, also aggregates term‑level contributions from matched query terms. Its design incorporates saturation and document‑length normalization while remaining essentially disjunctive. Similarly, language models for retrieval (e.g., query likelihood) compute the probability of generating the query given a document’s language model, which implicitly multiplies probabilities of observed terms—an operation akin to conjuction—but smoothed models introduce disjunctive effects via background collection probabilities.

3.2 Fuzzy disjunctive queries

Fuzzy queries relax the exact match requirement. A fuzzy disjunctive query retrieves documents containing terms that are similar (e.g., via edit distance) to any of the query terms, broadening recall further.

3.2.1 Proximity and phrase constraints

Some systems allow combining disjunction with proximity requirements. For instance, a query “apple OR orange NEAR/5 fruit” returns documents where either “apple” or “orange” appears within five words of “fruit.” This hybrid maintains the disjunctive spirit while adding a positional constraint.

3.2.2 Wildcards and truncation

Wildcard operators (e.g., “comput*”) match any term starting with the given prefix. In a disjunctive context, the query “comput* OR science” retrieves documents containing any word beginning with “comput” (e.g., “computer,” “computing”) or the word “science.” Truncation effectively expands a single term into a disjunction of all matching dictionary terms.

3.3 Structured and hybrid queries

Many query languages allow mixing AND and OR operators, often with parentheses to specify precedence. This enables complex retrieval logic.

3.3.1 Combining AND and OR with parentheses

For example, “(cat OR dog) AND food” retrieves documents that mention “food” and at least one of “cat” or “dog.” Such expressions are evaluated by first computing the disjunctive sub‑query’s result set, then intersecting it with the conjunctive part. This balance lets users control both breadth and specificity.

3.3.2 Nested queries in query languages (e.g., Lucene)

Lucene’s query syntax supports nested Boolean clauses with boosting. A disjunctive clause can contain multiple terms, each with a weight. The query parser converts such expressions into a Boolean query tree, and the search engine evaluates them using a combination of list merging and scoring. Nested queries allow for fine‑grained control over term contribution.

4.1 Web search engines

Major web search engines (e.g., Google, Bing) predominantly use ranking models, but they still support Boolean operators for advanced search. Disjunctive queries are often the default when multiple terms are entered, although many engines now interpret spaces as an implicit AND to improve precision.

4.1.1 Query expansion via disjunctive terms

Search engines automatically expand user queries by adding synonyms or related terms disjunctively. For example, a query “car” might be internally expanded to “car OR automobile OR vehicle.” This increases recall without requiring explicit user input. Expansion terms are typically drawn from thesauri or mined from click logs.

4.1.2 Handling of stop words and common terms

Stop words (e.g., “the,” “and”) are often removed or treated specially in disjunctive queries. Because their postings lists are enormous, including them would degrade performance and add noise. Many engines simply ignore stop words or convert them into a disjunctive clause with very low weight.

4.2 Database query languages (SQL WHERE clause)

In SQL, the OR operator appears in the WHERE clause: SELECT * FROM documents WHERE term1 = ‘cat’ OR term2 = ‘dog’. Database systems use similar postings‑list merging techniques or index intersection. For large text columns, full‑text indexes support OR‑based queries with ranking.

4.3 Digital libraries and bibliographic databases

Systems like PubMed, IEEE Xplore, and ACM Digital Library offer Boolean search with explicit OR support. Users can construct complex queries to capture all relevant articles, e.g., “(heart attack OR myocardial infarction) AND treatment”. The high recall of disjunctive clauses is critical for comprehensive literature reviews.

In evidence‑based medicine and legal discovery, recall is paramount. Disjunctive queries are used to ensure that no potentially relevant document is missed. For example, a legal search might use “(negligence OR breach of duty) AND damages”. These domains often require exhaustive search, and OR queries are a standard tool.

5.1 Metrics for disjunctive queries

Standard retrieval evaluation metrics apply to disjunctive queries, though their interpretation may shift due to the larger result sets.

5.1.1 Mean Average Precision (MAP)

MAP averages the precision at each point where a relevant document is retrieved, over all queries. For disjunctive queries, MAP tends to be lower than for conjunctive ones because more non‑relevant documents are included in early ranks. However, if relevant documents are scattered across many terms, MAP can still be reasonably high.

5.1.2 Recall at fixed rank

Recall at rank k (e.g., R@10) measures the proportion of all relevant documents that appear among the top k results. Disjunctive queries typically achieve higher recall at low ranks because they surface more documents that match any term, but the top k may still miss relevant documents if they are ranked low due to weak term weighting.

5.2 Efficiency considerations

Processing disjunctive queries on large collections poses performance challenges.

5.2.1 Large-scale indexing strategies

To handle billions of documents, search engines partition indexes across multiple servers (sharding) and use distributed merging. For OR queries, each shard computes a local union, then results are combined globally. Strategies like tiered indexes (keeping short postings lists in memory) help accelerate common terms.

5.2.2 Caching disjunctive results

Frequent queries can be cached. Since disjunctive queries often return large result sets, caching the postings list union for popular term combinations (e.g., “news OR update”) reduces repeated computation. Result‑set caches store the top k documents or compressed bitmaps of document identifiers, enabling fast lookups.