How To Efficiently Execute Two Phase Queries​

In a recent benchmark, SereneDB's search engine IResearch outperformed established search engines across query types and collection modes. This post is part of the Search optimization journey series, a set of technical reports examining the implementation decisions behind those results.

This articles focuses on lazy evaluation in the query execution layer. Search engines are machines for merging sorted streams of document IDs and nearly every interesting query like conjunctions, exclusions, phrase queries, geo filters, fuzzy matching, nested document joins requires iterators to cooperate and avoid doing expensive work on documents that will ultimately be rejected.

The mechanism IResearch uses for this is a two-contract seek API:

• a strict Seek for when you need the next document definitively;
• a weaker LazySeek that only answers "are you at this exact document?" and skips all the expensive machinery when the answer is no.

We'll follow this idea from the single posting list block all the way up through the full query tree and then show how the same principle extends to position-level intersection for phrase queries.

The Problem: Not All Seeks Are Equal​

Every search engine built on inverted indexes is, at its core, a machine for merging sorted streams of document IDs.

• Lucene calls it DocIdSetIterator
• Tantivy calls it DocSet
• In IResearch we call it DocIterator

The interface is the same: advance through documents in sorted order and optionally jump ahead to a target document ID via Seek.

But not all seeks are created equal. Some callers need the next document at or after a target. Others only need to know whether the target itself is present — and if it isn't, they don't care where the iterator ended up.

Two examples make this concrete:

• Phrase query: "quick brown fox": first confirm all three terms appear in the document (cheap, posting list check), then verify they appear consecutively (expensive, decode positions). If the first check fails, there is no reason to touch positions at all.
• Geo filter: "find restaurants within 2km": first confirm the document's indexed S2 cell overlaps the query region (cheap, posting list check), then load the stored coordinates and run the precise distance calculation (expensive, column read + math). If the cell check fails, the geometry is never loaded.

In both cases the second phase only runs when the first has already confirmed the document is a plausible candidate. LazySeek is the mechanism that makes this gating work across the entire query tree.

This distinction is the seed from which IResearch's lazy execution model grows.

The Two Seek Contracts​

Seek always positions the iterator at the smallest document ≥ target and returns it definitively. LazySeek has a weaker, three-outcome contract: given a target, it may stay on the current document (if it already equals target), jump exactly to target or jump to some document larger than target. All three outcomes are valid and the result can be freely mixed with all other iterator API calls, there is no indeterminate state to reason about.

value() ≤ LazySeek(target) ≤ Seek(target)

The key difference from Seek is that when LazySeek returns a value greater than target, it may have taken a shortcut — returning the first convenient value ≥ target rather than the precise next document. This is valid for callers who only need a confirmation ("are you at this exact document?") rather than a definitive forward advance.

The default implementation of LazySeek simply calls Seek. The interesting behavior emerges in the overrides and in how composite iterators exploit the weaker contract to avoid work entirely.

Why This Matters: Four Query Types That Exploit Laziness​

1. Two-phase queries (Phrase, Geo, N-gram, Nested)​

Two-phase execution is very intuitive pattern. Every query that has a cheap approximation and an expensive exact check benefits from LazySeek. The approximation runs first using LazySeek and if it misses, the exact check is skipped entirely. The exact check only fires when the approximation confirms the document is a plausible candidate.

This matters because the exact check is expensive — decoding positions, deserializing geometry, checking sequence continuity, scanning child documents. LazySeek on the approximation means that cost is never paid for documents that would fail it anyway.

The two-phase pattern is universal.

Phrase queries are the most familiar example, but the same two-phase structure appears across every non-trivial query type in IResearch. The approximation is always a cheap posting-list operation; the exact check is whatever domain-specific work cannot be avoided once a candidate document is confirmed.

Fig. 1 — Positions are decoded only when the conjunction confirms all terms are present. A missed document in phase 1 costs nothing in phase 2.

Geo filter — the query region is decomposed into a covering of S2 cells, each indexed as a term. The approximation is a disjunction over those cell posting lists: if the document's indexed cells don't overlap the query region, LazySeek returns immediately and the stored geometry is never read. Only when the approximation confirms the document does the exact check deserialize the geometry from columnar storage and run the spatial predicate.

N-gram similarity — a fuzzy text query like "quikc" is split into character n-grams ("quik", "uikc") and matched using a MinMatchDisjunction requiring at least k n-grams to be present. This is phase 1. Phase 2 then verifies that the matched n-grams form a contiguous sequence in the document confirming that. This is a genuine fuzzy match rather than an accidental overlap. Position decoding only happens in phase 2, and only when phase 1 confirms enough n-grams are present.

Nested filter (child-to-parent join) — in a document model with nested objects (e.g. an ORDER containing LINE ITEMS), a query might ask for orders where any line item matches a predicate. The parent iterator confirms the parent document with LazySeek. Only then does the child iterator Seek through the range of child doc IDs belonging to that parent. If no child satisfies the child filter, the parent is rejected and the search continues without having paid for a full child scan on every candidate parent.

Fig. 2 — The exact check differs per query type, but the gating is always the same: a cheap LazySeek confirms the document before any expensive I/O is attempted.

The cost asymmetry is what makes the pattern so valuable. A posting list bit check costs nanoseconds. Deserializing a stored geometry, decoding a position stream, or scanning a range of child documents can cost microseconds or more. Across millions of candidate documents the difference compounds dramatically.

2. Conjunction (AND / Intersection)​

Conjunction is where LazySeek earns most of its keep. The lead iterator (sorted by cost, cheapest first) drives forward with full Seek calls. All other iterators only need to confirm they are at the same document. If any follower returns a value greater than the target, the conjunction immediately short-circuits and the lead jumps forward without checking any remaining followers.

Fig. 3 — In step 1, follower B misses and short-circuits the loop. The lead jumps to 31. In step 2, both followers confirm. Total follower work: two LazySeek calls, zero forward scans.

3. Exclusion (NOT / Negation)​

In the exclusion iterator, the include side uses a full Seek to advance to the next candidate — it must commit to a definitive next document. Only the exclude side uses LazySeek, because it only needs to answer one question: "are you at this exact document?" If the include Seek advances past the target without landing on it, the exclude side is never touched at all.

Fig. 4 — The include side uses Seek to advance definitively. The exclude side uses LazySeek for a cheap presence check, and is never called at all when the include side did not land exactly on a candidate.

4. Required + Optional (MUST / SHOULD)​

A common boolean query pattern is MUST + SHOULD: a required clause that must match, plus optional clauses that boost the score if they also match. BoostIterator implements this. The required side drives iteration with advance() and Seek — it must find the next real document. The optional sides use LazySeek to check whether they happen to be at the same document: if opt.LazySeek(doc) == doc, the optional clause matched and contributes its score boost; if it returned something larger, the optional clause missed this document and is simply skipped. The optional iterators never need to find the next document, they only need to answer "are you here right now?"

Fig. 5 — The required iterator drives via Seek. The optional iterator uses LazySeek purely to decide whether to add a score boost — it never advances the iteration.

5. A Complex Example​

Consider the query "quick brown fox" AND NOT "lazy dog". The full iterator tree, and how laziness flows through every layer:

Fig. 6 — The complete query tree. The include branch uses Seek; the exclude branch is only consulted if the include side produces a match, and uses LazySeek throughout.

At each step, work is deferred until strictly necessary. Position data is never decoded unless the document-level conjunction confirms all terms are present. The exclude side is never consulted unless the include side finds a candidate.

Results: Why This Matters for the Benchmark​

The search-benchmark-game runs over the English Wikipedia corpus with queries from the AOL dataset, measuring throughput on phrase queries, conjunctions, disjunctions and count-only variants. Phrase queries exercise every layer of the lazy evaluation stack simultaneously:

• The conjunction approximation filters documents cheaply before any position I/O;
• LazySeek in the conjunction loop avoids full seeks on non-lead posting lists;
• Position intersection via frequency-sorted term positions;
• For count-only phrase queries, the loop exits after the first position match without full position enumeration.

These savings compound. The performance gap over systems that enumerate all positions or always perform full Seeks widens on queries with common terms, long documents and dense posting lists — exactly the conditions the Wikipedia corpus creates.

What's Next​

This post covered the lazy evaluation layer — the first line of defense against unnecessary work at query execution time. The next post in the Search optimization journey series will examine adaptive posting formats: how posting lists can choose layouts that fit both dense and sparse workloads without forcing every query through the same representation.

Other articles in the Search optimization journey series:

• Benchmark overview
• Search optimization journey 1: Collecting top-K candidates
• Search optimization journey 2: Block scoring
• Search optimization journey 3: Optimize norm gathering
• Search optimization journey 5: Adaptive posting format (coming soon)

---

IResearch is open source (Apache 2.0) and available as part of SereneDB. The benchmark results referenced here can be reproduced using the search-benchmark-game framework.

If you find this work interesting, we would appreciate your support — star us on GitHub goes a long way for an early-stage project.