Phrases with gaps, intervals and slop

An exact phrase is the strictest question a text index answers: these words, in this order, at consecutive positions. People rarely mean it that strictly. A search for quick and fox with one word between them should find "quick brown fox". Sometimes any of a few words may sit between, sometimes the order doesn't matter as long as the words are close and sometimes the words should be allowed to drift a little. SereneDB answers all of these from the same positional field with one filter, and the shapes differ only in what the matcher checks inside a document.

This post goes through what a positional field stores, how an exact phrase is matched, what gaps and intervals change, how proximity is spelled and what slop buys, with the cost of each. The examples run on 26.10.1 against a table of eight rows and, where the syntax overlaps PostgreSQL's, on PostgreSQL 18 as well.

Positions

An inverted index maps each term to the documents that contain it. A dictionary that records positions also keeps, for each of those documents, where in it the term occurs, which is what tells "quick brown fox" from "the fox was quick". POSITION requires FREQUENCY (see the feature flags). This is the table the examples use:

SQL

CREATE TEXT SEARCH DICTIONARY pos_en AS
    split_text(case := 'lower') | normalize_tokens('en_US.UTF-8', accent := false)
    WITH (frequency, position);
CREATE TABLE lines (id INTEGER PRIMARY KEY, body VARCHAR);
CREATE INDEX lines_idx ON lines USING inverted (id, body pos_en);
INSERT INTO lines VALUES
  (1, 'quick fox'), (2, 'quick brown fox'), (3, 'quick red angry fox'),
  (4, 'quick and the very red fox'), (5, 'fox quick'),
  (6, 'fox ran very quick'), (7, 'slow grey turtle'),
  (8, 'quick fox and another quick brown fox');
-- publish the rows to the index now rather than at the next background refresh
VACUUM (REFRESH_TABLE) lines;

The index counts positions from 1, as PostgreSQL's tsvector does, so row 8 has quick at 1 and 5 and fox at 2 and 7. A dictionary can also put several tokens at one position, the synonyms of expand_solr_synonyms for example, and a phrase slot then matches any of them.

The examples below run queries of this shape and show only what follows @@:

SQL

SELECT id FROM lines_idx WHERE body @@ ts_phrase('quick fox') ORDER BY id;

Star UsContact Us

One filter, many spellings

Every spelling of a phrase compiles to one filter: a slop for the whole phrase and a list of parts, each with a window of positions it may occupy relative to the part before it. EXPLAIN prints the windows as (min, max) position offsets, and on 26.10.1 these spellings come out as:

CODE

ts_phrase('quick fox')                   Term:quick(0, 0); Term:fox(1, 1);
ts_phrase('quick', 1, 'fox')             Term:quick(0, 0); Term:fox(2, 2);
'quick' ## 1 ## 'fox'                    Term:quick(0, 0); Term:fox(2, 2);
tsquery_phrase('quick'::TSQUERY,
               'fox'::TSQUERY, 2)        Term:quick(0, 0); Term:fox(2, 2);
ts_phrase('quick', [1, 2], 'fox')        Term:quick(0, 0); Term:fox(2, 3);
to_tsquery('"quick 2-3 fox"')            Term:quick(0, 0); Term:fox(2, 3);
ts_phrase('quick fox', slop := 2)        Term:quick(0, 0); Term:fox(1, 1); Slop: 2

Each window is relative to the part before it, not to the first part: ts_phrase('quick brown fox') prints Term:quick(0, 0); Term:brown(1, 1); Term:fox(1, 1);.

The spellings count differently. ts_phrase and the ## operator count the words between two parts, so 1 means one word between. tsquery_phrase counts the distance between positions, the convention of PostgreSQL's <N> operator, where, in the PostgreSQL documentation's words, "N is an integer constant that specifies the distance between the two lexemes being searched for. <-> is equivalent to <1>." A gap inside a quoted to_tsquery phrase, 2-3, is a distance range in the same units.

PostgreSQL 18 returns the same rows for the same phrases, with its queries run against to_tsvector('simple', body):

Phrase	PostgreSQL	SereneDB	Rows
exact phrase	phraseto_tsquery('simple', 'quick fox')	phraseto_tsquery('quick fox')	1, 8
one word between	to_tsquery('simple', 'quick <2> fox')	'quick' ## 1 ## 'fox'	2, 8
one or two words between	to_tsquery('simple', 'quick <2> fox | quick <3> fox')	ts_phrase('quick', [1, 2], 'fox')	2, 3, 8

• tsquery_phrase('quick'::TSQUERY, 'fox'::TSQUERY, 2) spells the middle row on both servers.
• to_tsquery on SereneDB parses Lucene's syntax rather than PostgreSQL's, so 'quick <2> fox' is a parse error here.
• PostgreSQL has no range operator, so its query for the last row is an OR of distances 2 and 3.

Exact phrases

Positions are read only for documents that hold every term: a document-level conjunction runs first, as How To Efficiently Execute Two Phase Queries describes. Inside a candidate document, the matcher orders the parts by how many positions each has there, so the rarest term leads. The lead walks its positions; for each one, every other part seeks to the position it must hold, and a part that lands past its target sends the lead forward to the position that target implies:

CPP

for (auto it = begin; it != end; ++it) {
  const auto target =
    (lead_pos - new_lead_offset) + it->second.lead_offset;
  const auto sought = it->first->seek(target);
  if (sought != target) {
    if (pos_limits::eof(sought)) [[unlikely]] {
      return phrase_freq;
    }
    lead_pos =
      lead.seek((sought - it->second.lead_offset) + new_lead_offset);
    goto restart;
  }
}

Each part's lead_offset is its distance from the first part, so one subtraction turns any part's position into the lead position it implies. The parts leapfrog: every seek moves forward, so the walk reads each part's positions in the document at most once, and it ends when any part runs out. A filter stops at the first match. A scored query keeps walking and counts matches, which is the phrase frequency a scorer such as BM25 uses. A fixed gap only changes the offsets, so ts_phrase('quick', 1, 'fox') runs the same loop.

Gaps and intervals

A range of words between two parts turns each target into a window: after a part matches at position p, the next one must sit between p + min and p + max. In row 8, from quick at 5, the window of ts_phrase('quick', [1, 2], 'fox') is positions 7 and 8, and fox is at 7; from quick at 1 it is positions 3 and 4, which hold no fox:

Two things the exact path relies on stop working. Sorting by rarity reorders the parts, but the windows are defined between neighbors in query order, so the only reordering that keeps them is reversing the whole phrase: the matcher reverses when the last part has fewer positions than the first. And a scored query has to count every combination of positions that fits the windows, because one position of a part can pair with several positions of the next. raw_tf, the scorer that returns the raw frequency, shows it: for ts_phrase('quick', [0, 6], 'fox') it gives row 8 a frequency of 3, from quick at 1 with fox at 2 and at 7 and from quick at 5 with fox at 7. When a later part misses, the walk goes back to an earlier part and moves it inside its window before trying again.

How the walk goes back decides the cost. The backtracking is the work of deymon-d, a student contributor, who checked it against a brute-force enumeration of position tuples. On a miss it jumps an earlier part straight to the lowest position from which the part that missed could still fit. That jump is safe only while every part stands on its first position inside its window, so once a part has been walked further, the walk steps one position at a time and rewinds the moved parts at the next lead position. Stepping alone would also be correct, but on a document where a dense lead term never matches it turns a linear walk into a quadratic one. In deymon-d's measurements from August 2026, with the lead occurring 1,600 times, stepping alone decoded 810 times as many positions as the walk: 1,301,584 against 1,606. His rule for a slot that holds several alternatives, such as synonyms or the terms a prefix expands to, holds as well: the slot sits at the lowest of their positions, similar to how Lucene's MultiPhraseQuery treats one.

Ranges change the score bound too. Top-k pruning skips the position walk for a document whose best possible score can't beat the current threshold, and that needs an upper bound on the phrase's frequency in the document. For an exact phrase it is the rarest part's position count. With windows, one lead position can pair with several followers, so it multiplies the lead's count by the widths of the windows, capped by the product of all parts' counts. For ts_phrase('quick', [0, 6], 'fox') in row 8 that is two quick positions times a window of seven, capped at two times two: a bound of 4 for a true frequency of 3.

Interval gaps and slop don't combine: ts_phrase('quick', [0, 2], 'fox', slop := 1) is refused with "slop is incompatible with interval gaps ([min, max])".

Star UsContact Us

Proximity

Proximity asks for words near each other. In order, that is a range starting at zero: ts_phrase('quick', [0, 4], 'fox') finds fox after quick with at most four words between them, which is rows 1, 2, 3, 4 and 8. Bounded proximity in either order is a slop phrase. The Lucene parser behind to_tsquery also accepts the function syntax of Lucene's intervals (the interval sources behind Lucene's IntervalQuery). Each function becomes the SereneDB query that matches the same rows. But there are two distinctions that limits supported Lucene intervals.

First one is that Lucene's SpanNearQuery has two separate settings: "One can specify slop, the maximum number of intervening unmatched positions, as well as whether matches are required to be in-order." In SereneDB each gap has its own interval and the order is part of the budget: ts_phrase('quick fox', slop := 4) matches the two words in order with up to four words between them (rows 1, 2, 3, 4 and 8), or swapped with up to two words between them (rows 5 and 6).

Secondly Lucene's intervals implement minimal-interval semantics with the algorithms of Boldi and Vigna's Efficient Optimally Lazy Algorithms for Minimal-Interval Semantics; the semantics go back to the algebra for structured text search of Clarke, Cormack and Burkowski. Under those semantics a document's frequency counts only its minimal matches, those that contain no smaller match; SereneDB counts every way the terms fill the gap. The same rows match, but frequencies can differ: in quick quick fox, Lucene counts one match for fn:ordered(quick fox) and SereneDB counts two.

For fn:maxgaps(4 fn:ordered(quick fox)) SereneDB uses ts_phrase('quick', [0, 4], 'fox') as there is only one gap to use interval budget. For fn:maxwidth(3 fn:ordered(quick fox)) we use ts_phrase('quick', [0, 1], 'fox'), since the pair may then span at most three positions. But fn:maxgaps(2 fn:ordered(quick brown fox)) is refused with "fn:maxgaps is supported over two terms, where what it bounds is a distance rather than a total" - as with 3 terms there are 2 gaps but only one interval, and SereneDB requires interval for each gap not total interval budget. For fn:ordered(quick fox) alone SereneDB's analog is ts_phrase('quick', [0, 16777215], 'fox'): any distance, as long as the order holds. On the other hand fn:unordered(quick fox) is a plain AND of the two terms, which is what an unordered interval with no limit on its width means when filtering documents. For words near each other in either order, use a slop phrase (see Slop).

Slop

Slop is a budget of position moves. One can read it as an edit distance between respective positions of terms. SereneDB computes the cost of a match the way Lucene's PhraseQuery does. Shift each query term by its document position minus its offset in the query, and take the largest shift minus the smallest. One word between two terms costs 1. A swapped pair costs 2, because one shift goes up by one and the other down by one. In row 8, ts_phrase('fox quick', slop := 2) puts fox at offset 0 and quick at offset 1. It accepts quick fox at 1 and 2, with shifts 2 for fox and 0 for quick. It also accepts fox at 2 with quick at 5, with shifts 2 and 4. Over the whole table the query returns rows 1, 5, 6 and 8. A slop of 0 is an exact phrase. With a fixed gap, the budget counts deviation from the declared gap, so ts_phrase('quick', 1, 'fox', slop := 1) takes rows 1, 2, 3 and 8.

There are three spellings: the slop := N argument of ts_phrase, the ::slop(N) modifier on a phrase built elsewhere (phraseto_tsquery included) and Lucene's "..."~N through to_tsquery. For quick fox at a budget of 2, all three return rows 1, 2, 3, 5 and 8. The two SQL spellings are the work of aksel2904, a student contributor, who also wrote the first native sloppy matcher, most of the tests that pin slop today and its benchmark. The matcher is a sweep that follows Lucene's SloppyPhraseMatcher and scores like it, a rework that zhemalb, another student contributor, started and we completed.

The sweep keeps one cursor per part, and a cursor's shift is its position minus the part's offset in the query. The window is the largest shift minus the smallest. The sweep advances the part with the smallest shift, and when that part has to move past the next smallest, it reports the window it just closed if the window fits the budget. A window too wide to fit sends the part seeking straight to the first position that could fit. The work is a pass over the parts' positions in the document whatever the budget; a bigger budget only admits more windows.

A term that occurs twice in the query may not use one document position for both. ts_phrase('fox fox', slop := 2) matches nothing: row 8 would cost 1 if both parts could take fox at 2, but with fox at 2 and 7 the cost is 4, and slop := 4 does return row 8.

The alternative to a matcher is to rewrite a sloppy phrase as a disjunction of exact phrases, one for each allowed arrangement, which grows with the budget. aksel2904's benchmark measured both in August 2026 on 10,250 Europarl documents with his matcher. At slop 5, the matcher was 13 times faster than the disjunction on "european union" (13,546 ns against 173,995 ns) and 41 times faster on a four-word phrase (30,830 ns against 1,255,792 ns). The matcher has changed since, so the figures show the size of the gap rather than today's timings.

What each shape costs

Shape	Per candidate document	A filter	A score
exact phrase, fixed gap	a leapfrog from the rarest part	stops at the first match	counts every match
gap range, ordered proximity	seeks into windows, moving earlier parts back on a miss	stops at the first match	counts every fitting combination
fn:unordered	no positions: an AND of the terms	checks no positions	uses each term's own frequency
slop	one sweep over every part's positions	stops at the first window within budget	uses Lucene's sloppy frequency

Every shape that reads positions reads them only in documents that hold every term, and a filter never counts. A shingle column adds one more option, a run of adjacent words that it holds whole as a single term, which Phrase search on shingle columns covers; a phrase with slop matches word by word there. The phrase and proximity cookbook has more examples of each spelling.

---

If you find this work interesting, a star on GitHub helps an early-stage project more than you might think.