Positional Indexes and Phrase Verification

A non-positional index answers the question “which documents contain this term?” and cannot answer “which documents contain these terms next to each other?” A phrase query needs to know where within a document a term occurred, not just that it occurred. The positional index stores that location, and the cost is a dramatic increase in index size: every occurrence of a term becomes a stored number, not just every document.

The reason for the size blow-up is that term frequency distribution is skewed. A term appearing in many documents tends to appear many times in each; a positional index stores the tail of repeated occurrences that a document-level index collapses into a single posting. The standard estimate is that a positional index is two to four times the size of a non-positional one before compression, and the compression story is where the design gets interesting, because positions inside a document are a different kind of sequence from document identifiers.

What a positional posting looks like

For each term, a positional postings list holds document identifiers in ascending order, and inside each document, the ascending list of positions where the term occurs. Positions are usually word offsets — the term is the k-th token of the document — measured from the start of the document. The list is a nested structure: outer level sorted by document, inner level sorted by position, and both levels are delta-encoded, so the on-disk form is a sequence of gaps interleaved with per-document counts.

The per-document count (the term frequency) has to be stored or inferred. It cannot be inferred from positions alone without a delimiter, so the common layout stores, per posting, a frequency and then that many position gaps. Alternatively, the frequency is stored separately from the positions, which is what a non-positional index carries anyway, and the position stream is a flat sequence of gaps that a decoder segments using the frequencies.

# A posting is (docid, positions); serialize docid gaps then position gaps.
def serialize(postings):
    out = []
    prev_doc = 0
    for docid, positions in postings:
        out.append(('doc', docid - prev_doc))
        prev_doc = docid
        out.append(('freq', len(positions)))
        prev_pos = 0
        for p in positions:
            out.append(('pos', p - prev_pos))
            prev_pos = p
    return out

The reason document identifiers and positions are encoded as gaps is the same as for document identifiers alone: both sequences are ascending, so differences are small on average. But the two gap distributions differ. Document gaps reflect how frequently a term appears across documents and can be large for rare terms. Position gaps reflect the word spacing within a document and are small, often one or two, because terms that occur in a phrase occur close together. A code that works well for one distribution does not necessarily work well for the other, which is why positional indexes often use different encodings for the document-gap stream and the position-gap stream.

Phrase verification as a position merge

Given a two-word phrase, the query finds the documents in the intersection of the two terms’ document sets — cheap, from the document-level lists — and then, for each shared document, checks whether the terms occur at consecutive positions. The check is a merge of the two position lists:

def phrase_match(p1, p2, dist=1):
    i = j = 0
    while i < len(p1) and j < len(p2):
        if p1[i] + dist == p2[j]:
            return True
        elif p1[i] + dist < p2[j]:
            i += 1
        else:
            j += 1
    return False

The merge walks both position lists once, so verification of a document costs O(|p1| + |p2|) in that document. For a phrase of length m, the generalisation is a merge of m position lists with an offset of one between each adjacent pair, and it is correct because positions are sorted. The work is dominated by the common terms: a phrase containing a stopword has to merge that stopword’s long position list in every candidate document, which is why phrase queries containing common words are dramatically more expensive than the same words as an unranked conjunction.

The failure mode worth naming is that the candidate set is the document intersection, but the verification may find no consecutive occurrence in a candidate. A document containing “the” and “cat” far apart passes the conjunction and fails the phrase, and the cost of the position merge is paid anyway. This is the cost of exact phrase matching that approximate phrase models try to avoid, and it is why phrase verification is described as “post-filtering”: the intersection is the filter, the position merge is the post-filter.

Proximity and the offset parameter

The phrase is the special case of a proximity query with distance one. A proximity query “machine within five words of learning” verifies with an offset of five rather than one, and the merge condition becomes a window test rather than an exact-offset test. The general proximity merge checks whether any pair of positions is within the window, which is still a linear merge but with a wider acceptance band.

Phrases in practice use a more nuanced notion of “consecutive” than word offsets. Punctuation, stopword gaps, and stemming all complicate the naive adjacent-word definition, and real systems either index multiple granularities or relax the match at query time. The index itself stores only positions; the semantics of adjacency are a query-time policy. This is a clean separation: the positional index is a general facility for phrase and proximity queries, and the specific phrase definition is not baked into the structure.

Compression specifics for position streams

Position gaps are small and their distribution is sharply peaked near one, so they compress well with the right code, and badly with the wrong one. A variable-byte code wastes a byte on a gap of one; a Golomb-Rice code with a small divisor, or a bit-packed frame-of-reference block with a narrow width, captures gaps of one in a couple of bits. This is the strongest argument for separating the two streams: encoding document gaps and position gaps with one code means choosing a code that is mediocre for both.

There is also a structural trick specific to positions. Because a position gap of one is so common, some encodings treat the position stream as a run-length problem: long runs of consecutive positions, which arise from repeated adjacent occurrences or from a term that spans a whole sentence, compress to a near-constant stream. A code that detects and encodes runs of one explicitly can beat a per-value gap code on exactly the terms that cost the most.

The trade-off is decode complexity. A position stream that mixes run-length encoding with a gap code has a data-dependent decode with two modes, which is slower than a uniform code and harder to vectorise. Whether the extra compression is worth it depends on whether the index is bound by storage bandwidth or by CPU, which is the same axis that decides between variable-byte and bit packing.

What a positional index cannot do

The positional index answers phrase and proximity queries exactly, and nothing more. It does not capture the order of documents within a phrase’s broader context, the grammatical relation between words, or any semantic relationship, and it is indifferent to the tokeniser that produced the positions, so two systems with different tokenisation rules have different and incompatible position semantics.

The deeper limitation is that positions are per document, so a phrase spanning two documents is invisible, and positions are word offsets, so a phrase across a hyphenation or a line break depends on how the tokeniser counted. These are data-preparation decisions, not index limitations, but they surface as index behaviour and are worth knowing before trusting a phrase count.

The size cost remains the deciding factor in practice. Many systems build a non-positional index for broad retrieval and a positional index only for the fields where phrases matter, or they keep positions for a subset of terms. A positional index over the whole collection is the price of exact phrase search, and the two-to-four-times size figure is the number that decides whether the feature is worth it.