Join Indices for Search Engines: a Prunable Parallel Semijoin over Lucene Segments

Join Indices for Search Engines: a Prunable Parallel Semijoin over Lucene Segments Mikhail Khludnev Reksoft mkhl@apache.org August 2026

arXiv:2608.01173v1 [cs.DB] 2 Aug 2026

Abstract Joins are second-class citizens in search engines: existing query-time join implementations in Lucene are limited either in performance or in capability, forcing a choice between fast joins scoped to a single index and slower joins that span independently managed indices. We carry Valduriez’s join-index technique from relational systems to Lucene’s flush-based (LSM-style) segment storage: for every pair of a parent and a child segment we materialize an append-only, ordinal-to-ordinal join-index column Jij [c] = p, avoiding any query-time translation of external variable-length keys. On top of this structure we build a semijoin algorithm that is computed per parent segment, in parallel, without a global barrier between stages; it prunes at three levels (segment-level, the first of which comes free from per-segment execution; a-priori min/max; and document-level two-phase confirmation with a lazily accumulated half-read union) so that it composes with arbitrary engine queries instead of wasting computation on matches that a sibling filter would later discard. A prototype implemented as an Apache Solr query parser, benchmarked on 1M products joined against 10M skus, cuts average query latency 5.4× (359.8 ms vs. 1934.6 ms) relative to Solr’s built-in query-time join, and the advantage widens monotonically with load, reaching 8.3× at a concurrency of eight: on 4 vCPUs the baseline peaks at 1.18 queries/s and then loses throughput, while the join index is still gaining, at 8.04 — 6.8× the baseline’s best. Both arms return identical result counts on every query of every run. Instrumenting that run places the credit on the structure rather than on the pruning built over it: the benchmark draws foreign keys uniformly at random, which flattens every column’s bounding ranges to the full parent segment, and the two range-based levels consequently fire on under 2% of segment pairs. The speedup is thus the join index’s own, measured on a workload that defeats its own optimizations. What we establish for the pruning hierarchy is composability; what it delivers on correlated key distributions remains to be measured.

Keywords: join index, semijoin, inverted index, Lucene, LSM-tree, query-time join, segmentlevel pruning, dynamic pruning, cross-index join, Apache Solr

1

Introduction

Inverted indexes [20] are the standard technology behind full-text and faceted search — powering web search engines, digital library catalogs, and e-commerce product search alike. Their key feature is the picking of the top k relevant results. Many optimizations known as dynamic pruning have been applied to this algorithm. We describe them closely in §4.4 using Apache Lucene1 [3] as an example implementation. Relational databases, on the other hand, provide highly performant join algorithms. Join operations in search engines remain a less developed area, and existing implementations are limited in either performance or capability, or both. 1

Apache Lucene and Lucene are trademarks of the Apache Software Foundation.

1

The task of this paper is therefore: • to implement a fast join algorithm for inverted index, but only assuming equijoin in a form of semijoin [7] (see the SQL sketch in §6); • to make it compatible with dynamic pruning algorithms of search engines; • to make it suitable for parallel execution to achieve high performance and scalability. This paper uses Apache Lucene [8] as a concrete example of the search engine, but the ideas are applicable for other search engines and many NoSQL databases, which share key design elements.

2

Contributions • applying Valduriez’s join-index [25] idea to inverted index, meaning the flush-produced, unmerged runs of an LSM-tree [21] or L0 in terms of RocksDB [13], using Apache Lucene as a concrete example; • the semijoin algorithm suitable for parallel execution, with no global barrier between stages; • a three-level pruning hierarchy (segment, a-priori, document) — the first of which comes free from per-segment execution — which lets the semijoin enter an existing dynamicpruning engine as an ordinary conjunct. The claim here is composability, not effectiveness: §11.3 measures the two range-based levels firing on under 2% of segment pairs on our benchmark, and what they are worth on correlated key distributions is left open (§11.4); • an instrumented evaluation that separates those two questions, and attributes the measured speedup to the join-index column and the per-segment execution rather than to the pruning built on top of them (§11.3).

3

Results Summary

Section 11 benchmarks a prototype implementation, built as an Apache Solr2 query parser, against Solr’s existing cross-collection join, {!join score=none}. On an index of 1M products joined against 10M skus, over 500 queries per arm, the join-index approach cuts average query latency 5.4× at a concurrency of one (359.8 ms vs. 1934.6 ms), rising to 8.3× at a concurrency of eight. Swept across concurrencies 1 to 8 on 4 vCPUs, the baseline peaks at 1.18 queries/s and then declines, while the join index is still gaining at 8.04 — 6.8× the baseline’s best figure at any concurrency, and 7.2× its figure at the same one. Both arms execute the same query set and agree on the result count of every query. Section 11.3 then instruments that same run to ask which part of the design earns the speedup, and the answer is not the part we set out to claim. The benchmark’s foreign keys are drawn uniformly at random, which flattens every join-index column’s bounding ranges to the full parent segment; the a-priori level consequently bypassed 1.6% of segment pairs and the document level spared 1.5% of column reads. The speedup is therefore the join index’s own — the ordinal-to-ordinal column that removes query-time key translation, and the per-segment, barrier-free execution — obtained on a workload that happens to defeat the pruning layered over it. We report the pruning hierarchy accordingly: as a composability property, always available and cheap enough that it cost nothing visible here, whose effectiveness under correlated key distributions is a question §11.4 is designed to answer and this paper does not. 2

Apache Solr and Solr are trademarks of the Apache Software Foundation.

2

4

Background: the Execution Model

4.1

Flush-produced segments

An Apache Lucene index [8] consists of segments (or extents in common terms) and might be viewed as an LSM-tree [21, 18], but specifically it is a flush-produced unmerged runs. These segments are autonomous inverted indices and suitable for independent parallel searching that is already done in Apache Lucene and Lucene-based engines such as OpenSearch3 [23], Apache Solr, and others. Note: a slice — a unit of concurrent processing — might be less or more than a segment, but this detail is transparent to this paper.

4.2

Virtual IDs

Lucene is a system with virtual IDs [1]. Adopting a notation akin to relational algebra, an index R consists of N disjoint segments, R = R1 ⊎ R2 ⊎ · · · ⊎ RN ; within segment Ri , a document is identified by an ordinal (virtual docid) document number d ∈ [0, maxDoc i ), borrowing Lucene’s own maxDoc() [4] terminology — written |Ri | in the set-based notation of Section 6, which extends this scheme to the child relation S. In the remainder of this paper, we use the term docid to refer to these segment-scoped virtual IDs. Note that docids differ from physical record offsets: surrogates [25] and RID [22] share a property of immutability and internal assignment, but might be processed efficiently as ordinals. For now, we set aside the deletion marks as not significant to the core ideas. There are two consequences of using virtual IDs (docids): • Since docids are assigned sequentially, they are dense and narrow, and compress better than the wide, sparse external IDs [1]. Compression is, in fact, a cornerstone of Lucene’s performance [8]. • Since segments are immutable once written (deletions aside), segment-scoped docids remain stable for the segment’s lifetime.

4.3

Value Ordinals and Dictionary Compression

Dictionary compression is a technique commonly used in columnar stores [1]. When storing a value by docid, values[docid], we encounter two issues: variable-length values are harder to look up, and repeating values waste storage and impact processing time. Instead, we assign dense, narrow, fixed-width ordinals to values and map each docid to its ordinal, hence obtaining a value by docid becomes values[ordinals[docid]]. We can say that dictionary compression introduces virtual IDs for values. Also, see a note in § A.1. However, when there are many segments, the same values are assigned different ordinals in different segments. Thus, value ordinals can’t be compared across segments, which causes a challenge for join implementation, since joins work on value equality. That can be addressed with two distinct measures: • avoid dictionary compression by limiting users to fixed-width numerics, which can simplify query-time join (e.g. using integers for FK and PK) — but we consider it too restrictive and do not adopt this workaround in this paper; • restrict join sides to a single index and single field and correlate them via global ordinals (see §5.2) — again, we put it aside as too restrictive for this paper. 3

OpenSearch is a registered trademark of Amazon Web Services, Inc.

3

4.4

Dynamic pruning

There are many optimizations applied to top-k retrieval, such as: • adaptive (“leapfrog”/galloping) intersection for conjunctive queries [11], which skips runs of non-matching entries between two sorted posting lists by exploiting the gaps between their current positions, rather than merging them element by element; • the two-phase iteration algorithm [6], where a cheap approximation first narrows the candidate set with false-positives, and the expensive exact match — e.g. confirming a phrase’s term positions — is evaluated only on candidate documents that satisfy the cheaper checks first; • MaxScore [24], later refined into block-max variants such as Block-Max WAND [12], which use a per-block upper bound on relevance to skip entire runs of documents that provably cannot outscore the current threshold, as implemented in Apache Lucene and borrowed by search servers based on it, such as Elasticsearch4 [14], Apache Solr, etc. Our task is an efficient semijoin: an algorithm shaped as a segmented iterator over docids that takes another segmented iterator as input. This is what a semijoin implementation needs. For dynamic pruning, we design this algorithm to compose with arbitrary engine queries and their optimizations.

5

Related Work and Design Space

5.1

The classic query-time join

The existing implementation of query-time join [5] in Apache Lucene is, in relational terms, a block index join [15]. We do not use that name in the remainder of the paper: block would collide with Lucene’s own Block Join (§5.2), which is an entirely different algorithm. We refer to it throughout as the classic query-time join, always with a pointer to this section. Consider the following sample semijoin query: SELECT * FROM R WHERE EXISTS (SELECT 1 FROM S WHERE S.fk = R.id) It is executed in two stages: 1. loop through child (S) records, collecting foreign keys (FKs) into a set; 2. bulk-search that FK set against the primary key field R.id. We say stages rather than phases deliberately: phase is reserved in this paper for Lucene’s twophase iteration (§4.4, §6.3), the approximation/confirmation contract that our own algorithm implements in §8.2. The two notions are unrelated, and the collision is easy to make. Given that the indexes are partitioned across segments (§4.1), both stages can exploit persegment parallelism, but in the middle we need to merge the set of {F K} sequentially. That limits the scalability according to Amdahl’s law [2]. The motivation for this two-stage design is that Lucene has an optimized bulk search operation; avoiding the sequential merge would lead to multiple sub-search operations that are expected to be slow — but this has not been evaluated.

5.2

Other join algorithms in Apache Lucene

We mention them briefly for completeness, although they are not directly related to our work: 4

Elasticsearch is a trademark of Elasticsearch B.V., registered in the U.S. and in other countries.

4

• Index-time join [16] — a rather fast algorithm, since parents and their children are indexed together as a contiguous block of adjacent docids. That physical clustering is exactly what makes it prone to update amplification: touching a single child forces the whole block to be reindexed, which rules the approach out for many real-life scenarios we want to pursue. Its closest analog we can come up with is the hierarchical storage of IBM IMS [17] — a design that goes back to 1968, predating the relational model [9] itself, and is still shipping today — where dependent segments are stored beneath their parent and traversed in hierarchical sequential order. It is also unfortunate that Lucene calls this a Block Join, which clashes with the relational-database terminology we have just used above. • Global-ordinals join – it’s an optimization of the base algorithm above, but it has a limitation that both relations must be stored in a single index and the join keys must be stored in a single field5 . This is not always possible in real-life scenarios. In this paper we’d rather keep entities in two separate flush-produced indices with externally provided ID, F K arbitrary values. • The initial join in Apache Solr [19] implemented against inverted indices has some potential, but hardly able to compete in runtime with other ones. There is also much research on distributed joins, which spread the computation across a cluster of machines. We consider it out of scope, and complementary rather than competing: a distributed algorithm still has to join locally on each node, and the single-machine algorithm described in this paper can serve as exactly that building block.

5.3

The join-index lineage

Join indices were discussed in the relational-database field long ago: • Valduriez [25] introduced the idea of a join index, which is a precomputed binary relation of surrogate pairs, with a read/write cost model showing when materialization beats querytime joining; • O’Neil [22] introduced bitmap join indexes, which are industrial descendants of Valduriez’s idea. This paper adopts this idea for LSM-tree storages, where search engines based on inverted index can be considered as an instance of it §4.1. The key challenge is to make join indices work in append-only flush-based storage, where the values ordinals are segment scope and hard to correlate between segment and joining indices. As the final note: we need to disambiguate join index (materialized structure, this paper) from index join — index nested-loops, using an index during the join’s inner loop §5.1.

6

Problem Statement, Terminology, and Notation

6.1

Data Model

Let R be the parent relation (the returned side, primary key R.id) and S the child relation (the filtered side, foreign key S.f k), in a 1:M relationship. Let’s call them just parent and child; and depict them as R and S in formal notation and pseudocode. (In Apache Solr terminology, child is the from side and parent the to side.) Each relation is stored as immutable, append-only segments: R = R1 ⊎ · · · ⊎ RN , S = S1 ⊎ · · · ⊎ SM ; subscript i always ranges over parent segments, j over child segments. Inside a segment a document is identified by its docid: p ∈ [0, |Ri |), c ∈ [0, |Sj |). 5

https://www.elastic.co/docs/reference/elasticsearch/mapping-reference/parent-join#_parent_ join_restrictions

5

6.2

Filtered Semijoin

Definition 1 (Filtered semijoin). Given arbitrary engine queries qR over R and qS over S, compute Answer = σqR (R) ⋉ σqS (S) = { r ∈ R | r |= qR ∧ ∃s ∈ S : s.f k = r.id ∧ s |= qS }. Here qR , qS denote arbitrary predicates over R, S respectively; in SQL, SELECT * FROM R WHERE qR AND EXISTS ( SELECT 1 FROM S WHERE S.fk = R.id AND qS ). Where qR is evaluated. The two predicates are not handled symmetrically, and it is worth saying so before the algorithms, since qR appears in none of them. The algorithms of §8 compute only the ⋉ operand — the parents having at least one child that matches qS — and expose it as an ordinary query over R. The engine then evaluates σqR (R) ⋉ σqS (S) as the conjunction of qR with that query, exactly as it would intersect any two leaf queries; qR is a sibling conjunct, never an input to the semijoin. Nothing is lost by this split, and something is gained: because the semijoin is a conjunct rather than a pipeline stage, qR can steer it — restricting which parent segments are visited at all (§9.1) and which parent docids are ever offered for confirmation (§8.3).

6.3

Columns and Query Execution

A column (SortedDocValues field6 ) f is a column of value ordinals, positionally indexed by docid: Ri .f [p] yields the value ordinal for docid p, not the value itself. Since each field’s dictionary is private to its own segment, we annotate the value dereference with segment (superscript) and field (subscript): the value is obtained by a separate positional lookup on that ordinal, i valuesR f [Ri .f [p]] (§4.3). Square brackets denote a positional column lookup. Besides columns, a segment also exposes indexed fields (postings fields), searchable by value rather than by position. Given a set of values V , a single bulk search operation search(Ri .g, V ) = { p ∈ [0, |Ri |) | Ri .g[p] ∈ V } returns all matching docids at once, rather than one search per value. For instance, searching a collected FK set against the primary key field yields search(Ri .id, {F K}), the set of parent docids p whose id matches some collected key — this is stage 2 of the classic query-time join (§5.1). Executing a query against a segment yields a match iterator M(q, Sj ) ⊆ [0, |Sj |) supporting next(), advance(t), and the two-phase pair approximation()/matches(d). Both next() and advance(t) return docids in ascending order, and report exhaustion by returning the sentinel EXHAUSTED. We take EXHAUSTED to be greater than every docid, so that a bound test such as c ≤ cij max fails of its own accord once the iterator is spent and needs no separate exhaustion check; Lucene realizes the sentinel as NO_MORE_DOCS = Integer.MAX_VALUE, which has exactly this property.

6.4

Requirements and Result Sets

Requirements, as set by Sections 1–5: R1. performance: no query-time translation of external variable-length keys; R2. composability with arbitrary engine queries and their computation-skipping optimizations; 6

https://lucene.apache.org/core/10_1_0/core/org/apache/lucene/document/SortedDocValuesField. html

6

R3. parallelism via the existing segment mechanism; Result sets of the algorithm (all per parent segment): the exact semijoin set Pi , which the confirmation phase computes in full; the false-positive approximation Âi ⊇ Pi ; and the half-read union Hi ⊆ Pi , a false-negative set: p ∈ Hi ⇒ p ∈ Pi , while p ∈ / Hi decides nothing until Hi has converged to Pi .

7

The Join Index

7.1

Formal Definition

The classic query-time join (§5.1) can be depicted formally as a two-stage function from a set of child docids to, for each parent segment, a set of matching parent docids. Given a set of child docids C ⊆ [0, |Sj |), QTJ (C) = (P1 , . . . , PN ), V (C) =

 |

S

valuesf kj [Sj .f k[c]] {z

c∈C ,

stage 1: collect FK values

}

Pi = search Ri .id, V (C) .

|

{z

stage 2: bulk search

}

We instead introduce, for every segment pair (Ri , Sj ), a join-index column Jij mapping child docid directly to parent docid, Jij [c] = p: Definition 2 (Join-index column). For every pair (Ri , Sj ) we materialize an integer array Jij of length |Sj |, indexed by child docid (on when it is written, see §7.2):

Jij [c] =

  p,   

if the parent of c lives in Ri , i.e. p is the unique docid of [0, |Ri |) with

   ⊥,

otherwise: no such p — the parent lives in another segment, or is absent.

S

j i valuesR id [Ri .id[p]] = valuesf k [Sj .f k[c]],

The index to join S.f k = R.id is thus a column of parent docid indexed by child docid: Jij [c] = p. Well-definedness. Writing Jij [c] = p presupposes that p is unique: a given foreign-key value must select at most one parent docid, and in at most one parent segment. That is stronger than R.id being a primary key of Ri alone — it has to be a primary key of R as a whole. Search engines do not enforce it the way a relational system does: in Apache Lucene an update is a deletion followed by an append, so the same id value is routinely present in two segments at once, and duplicate ids are not rejected at all. Two properties rescue the definition: • immutability: a segment never changes once written, so Jij is a pure function of the pair (Ri , Sj ) — once built it can never go stale, and the fresh copy of an updated parent simply lands in a new segment Rk with its own column Jkj ; • deletion marks: the obsolete copy is tombstoned, and is therefore excluded either when the column is built (§7.2) or by the engine’s live-docs filter when Pi is scored. So uniqueness is only required among live documents, which is the same condition the classic query-time join of §5.1 already relies on. Where even that fails — genuinely duplicated live ids — Jij degenerates from a function into a relation, and the algorithms of §8 would report only one of the duplicated parents per child, i.e. produce false negatives. We assume unique live ids throughout. 7

7.2

Implementation Notes

Here, indexed by child docid means array access. In the Apache Lucene implementation, we realize this as an auxiliary index: a set of segments holding join-index columns as NumericDocValues7 , one column per segment pair (Ri , Sj ), named accordingly. The docids of this auxiliary index coincide with the docids of the child segment: writing Uj = [0, |Sj |) for that docid space, an auxiliary segment holding a column for Sj is addressed over Uj . (Uj is the full address space of Sj , not to be confused with the child docid set C of §7.1, which ranges over it.) Join-index columns may be stored one per auxiliary index segment, or several to a segment, since their names disambiguate them. Packing multiple columns per segment reduces number of files open, but complicates sweeping columns whose parent or child segment has since been deleted. This use of Lucene is unconventional: as a rule in the single segment same docid across different fields refers to the same document. But if we put several columns of different sizes into the single auxiliary index segment the columns of the different j (child segments) are projected onto one docid space although their Uj differ, so a docid from one join-index column means nothing in another column. We accept this because we are piggybacking on existing Lucene machinery rather than building bespoke storage. When columns are materialized. Join-index columns are not written when the parent and child indices are built. They are materialized on demand, by the first query that needs them, and persisted thereafter: a segment pair is immutable (§7.1), so a column, once written, is valid for as long as both its segments live, and every later query reads it rather than rebuilding it. Within a query, the work happens in bulk and up front rather than segment by segment. When the join query builds its weight, it determines the full set of pairs (Ri , Sj ) it will need, and writes every one of them that is not yet present in a single batch, before scoring begins. Only pairs that this pass misses are built lazily, per parent segment, inside the algorithm of §8. We describe both because the fallback is what makes the algorithm total — it never has to fail on a missing column — but it is the bulk pass that does the work in a steady system, and the cost reported in §11 is that pass, paid once, on the query path. Building up front rather than on first access is a deliberate trade. It forfeits the chance to skip columns that pruning would have made unnecessary — a pair whose column is never read still gets written — in exchange for one batched write per query instead of a write per parent segment, and for a complete view of the join index at scoring time. Deferring the write to the point of use, so that segment-level and a-priori pruning can suppress it entirely, is left for future work (§13). We omit the algorithm for creating join-index columns: it is straightforward, and the details may vary. The one we use can be seen in the actual implementation (§10). It is worth noting that building a join-index column honours the deletion marks on both sides, which makes the column smaller, since fewer values enter it. Each join index column additionally receives approximation ranges: the min/max child docid it is defined at, and the min/max parent docid it maps onto, cij min = min{ c | Jij [c] ̸= ⊥ },

cij max = max{ c | Jij [c] ̸= ⊥ },

pij min = min{ p | ∃ c : Jij [c] = p },

pij max = max{ p | ∃ c : Jij [c] = p }.

7

https://lucene.apache.org/core/10_1_0/core/org/apache/lucene/document/NumericDocValuesField. html

8

Empty columns. A segment pair may have no join at all: if no child of Sj has its parent in Ri , then Jij is ⊥ everywhere, the four sets above are empty, and the bounds are undefined as written. This is not a corner case to be waved away. It is the common case exactly when the two sides’ insertion orders are correlated — a bulk load ordered so that a parent lands near its children leaves most of the N × M pairs disjoint — which is the regime in which the ranges are worth anything at all (§11.3). We therefore take the conventional extrema over the empty set, ij cij min = pmin = +∞,

ij cij max = pmax = −∞,

realized as EXHAUSTED and −1 respectively. Every guard in §8 then bypasses such a column of its own accord, in the same way and for the same reason that the sentinel handles a spent iterator (§6.3): advance(+∞) returns EXHAUSTED, the bound test c ≤ cij max fails for every c, ij ij and [pmin , pmax ] is the empty interval, contributing nothing to Âi . No algorithm needs a case for it. An empty column consequently need not be materialized: its metadata alone answers every query that would have read it. The prototype detects the case before building, by testing whether the R.id and S.f k term ranges of (Ri , Sj ) are disjoint — a sufficient, not necessary, condition — and in that case writes the metadata only. What this does not do is reduce the N × M column count to address and sweep (§11.2); it removes the bytes, not the bookkeeping. Note: below we approximate the set of docids by a range with false-positive entries. In future work we may extend this to n-range approximation. There is a merge policy for the auxiliary join index which marks a whole segment (all its columns) for deletion once every segment pair (Ri , Sj ) it holds a column for has been deleted from the parent index R and the child index S.

8

The Semijoin Algorithm

8.1

Base algorithm: eager per-segment semijoin

We reuse Lucene’s built-in parallel segment search, giving parent-segment concurrency for free. For every parent segment we read the join-index columns of all child segments: Pi =

M [ 

Jij [c]

c ∈ M(qS , Sj ), Jij [c] ̸= ⊥ .

j=1

Thus we calculate the semijoin of a parent segment from child predicate matches, in parallel across parent segments, with no barrier between stages at which all parent tasks must have arrived.

9

Algorithm 1 Eager per-segment semijoin (base algorithm) Require: parent segments R1 ..RN , child segments S1 ..SM , join-index columns {Jij }, child ij query qS , cij min , cmax - ranges of child docids for each join-index column Require: cursor(j): a fresh cursor over Bj , the shared cached bitset of M(qS , Sj ). The first caller for a given j — whichever parent task that is — evaluates qS over Sj to exhaustion and publishes Bj under a per-j latch; every later caller receives a cursor over it. Shared across all parent tasks; see the cost discussion below Ensure: per-segment semijoin sets Pi , emitted as sorted docids iterators over Ri 1: for each parent segment Ri in parallel do 2: Pi ← ∅ {e.g. a bitset of |Ri | bits} 3: for j ← 1 to M {parallelizable too, but kept sequential; see below} do 4: it ← cursor(j) {sorted match cursor; qS is retrieved over Sj at most once overall} 5: c ← it.advance(cij min ) {skip below child range} 6: if c > cij then max 7: continue {a-priori column bypass, §9.2} 8: end if 9: while c ̸= EXHAUSTED and c ≤ cij max do 10: p ← Jij [c] {single array lookup} 11: if p ̸= ⊥ then 12: Pi ← Pi ∪ {p} 13: end if 14: c ← it.next() 15: end while 16: end for 17: end for Note that the inner loop over child segments is parallelizable as well: every iteration reads its own join-index column Jij and its own child segment, so the iterations are independent except for the accumulator Pi they share. We deliberately do not pursue this opportunity. The outer loop already yields N independent tasks — for free, via Lucene’s parallel segment search — which is normally enough to saturate the available cores, whereas a second, nested level of concurrency would have several threads updating a single Pi . That would demand either synchronized updates or per-thread bitsets merged afterwards, reintroducing exactly the sequential merge step whose cost we criticize in the classic query-time join (§5.1). We therefore keep child segments sequential within each parent segment. Cost: the child query is evaluated N × M times. The match iterator M(qS , Sj ) is constructed inside the parent-segment loop, so the child query is evaluated once per segment pair: N × M evaluations in total, or N times over each child segment Sj . The classic query-time join (§5.1) evaluates it M times — once per child segment — and this redundancy is precisely the price we pay for dropping its synchronization point. We trade one sequential merge of {F K} for N independent re-enumerations that need not coordinate at all. Two things make that trade favourable. First, the child query is cheap relative to what the classic algorithm does with its matches. There, every child match yields an external, variable-length FK value, all such values are deduplicated into one global set across all child segments — the sequential step — and that set is then bulk-searched against Ri .id. Here, a child match costs a single array lookup Jij [c] (§7.1), with no key materialization and no dictionary lookups on either side; and the pruning hierarchy of §9 removes much of even that, since a column whose child range does not intersect the matches is bypassed without being loaded at all, while the lazy variant of §8.3 stops as soon as the parent docid under confirmation is found. 10

Second, the repetition is enumeration, not retrieval. The child matches of a segment are materialized once, globally, and then shared — this is the cursor(j) of Algorithm 1, and it is load-bearing enough for the cost argument that we make it an explicit input rather than leaving it to the implementation. The first parent task to touch Sj — whichever one that happens to be — evaluates M(qS , Sj ) to exhaustion and publishes the resulting bitset Bj = { c ∈ M(qS , Sj ) }; every later toucher receives a cursor over Bj . The cache is thus triggered lazily but filled eagerly, and the persisted itj of Algorithm 3 are N independent cursors over one shared bitset rather than N independent executions of qS . Retrieval — postings decoding, skipping, and the evaluation of qS ’s own subqueries — therefore happens at most M times in total, once per child segment, and it is only the enumeration of an already-materialized bitset that is repeated up to N times per segment. Note that this cache does not reinstate the synchronization point of the classic query-time join (§5.1). Two tasks that reach an uncached Sj at the same moment resolve it as any concurrent memoization does: one fills, the other waits on that single fill. The parent tasks never wait on each other’s results — there is nothing to merge, and no point at which all N of them must have arrived — only, at worst, on the first materialization of a scan they both need anyway. What this leaves for the pruning hierarchy to save. It follows that the levels of §9 save on the N × M side of the computation rather than on the M side, and it is worth being exact about which reads they eliminate. An early exit in Algorithm 3, and an a-priori bypass in any of the three variants, avoid reading the join-index column Jij — one of N × M objects, each of which has to be located, loaded and decoded — but they do not avoid the child scan underneath it, which a sibling parent task may have paid for already, or will pay for later. When the R1 trace of §C.5 reports that J13 is never read, the claim is about that column and that parent segment: S3 ’s matches are materialized as soon as any parent task reaches S3 . This is the side worth saving on, because it is the side that grows with N .

8.2

Two-phase semijoin: approximate, then confirm

Here two-phase carries its Lucene meaning throughout: the approximation/confirmation iterator contract of §4.4, exposed as the approximation()/matches(d) pair of §6.3. It is unrelated to the two stages of the classic query-time join (§5.1); what follows is our algorithm implementing that contract, not a variant of that one. ij Every join-index column additionally has parent docids range: pij min , pmax ; leaping over all child segments (those that passed segment-level pruning, §9.1) and unioning all parent docid ranges, we get a false-positive match approximation: Âi =

M [  ij

pmin , pij max



⊇ Pi .

j=1

The advantage is that it yields parents approximation (with false positives) even without reading join-index column, thus such candidates might be withdrawn by §4.4 or, for example, intersecting with highly restrictive parents filter. This idea can be extended to n range edges, approximating {p} as a union of ranges, although it has not been evaluated. Then, to confirm a potential parent docid match, we need to union all confirmations {p} per child segment: for each child segment, the corresponding index column is read at the child matches, collecting {p}, and then unioned per child segment; thus we get the true-positive parent matches for the current parent segment — which is the exact semijoin set Pi of §8.1 again, now computed on demand rather than eagerly.

11

Algorithm 2 Two-phase semijoin (approximate, then confirm) ij ij j [pmin , pmax ] {metadata only; no column reads} S ij Pi ← j {Jij [c] : c ∈ M(qS , Sj ) ∩ [cij min , cmax ]} \ {⊥} {full read, as in Algo-

1: approximation(Ri ): return Âi = 2: matches(Ri ):

rithm 1}

S

3: answer membership of p ∈ Âi by p ∈ Pi

Implementation detail: this refined parent doc set Pi may replace the approximation docset for following processing, although it might not be fully compatible with possible Lucene optimizations.

8.3

Lazy confirmation: the half-read union

Then, we can make it even lazier. Let us run only a few per-child-segment steps of Algorithm 2, until we confirm the single given parent docid — and break. Such a half-read union is called a false-negative doc set Hi : a one in it is a match for sure, while a zero is uncertain, since it is a half-read union. For the next parent docid arriving for confirmation, we can check the false-negative set first. Note that only false-positive documents arrive for confirmation; and only if the false-negative check does not confirm the match do we proceed with the following step of the lazy variant, dumping the next {p} into the false-negative set, until it processes all child segments and converges to the two-phase algorithm above, updating the underlying match approximations with only true matches.

12

Algorithm 3 Lazy confirmation via the half-read union ij Require: parent segment Ri ; child query qS ; join-index columns Jij with metadata cij min , cmax , j = 1..M ; cursor(j) as in Algorithm 1 Require: step(j) ≡ on the first use of Sj : itj ← cursor(j), then itj .advance(cij min ); itj .next() thereafter {a-priori lower bound, §9.2} Ensure: matches(p) decides p ∈ Pi for each candidate p offered by Âi 1: initialize once per parent segment Ri , then persist across calls: 2: Hi ← ∅ 3: unread ← queue of child segments 1..M 4: itj ← undefined for each j {cursors are created by step, on first touch} 5: function matches(p): 6: if p ∈ Hi then 7: return true{false-negative check first — free} 8: end if 9: while unread ̸= ∅ do 10: j ← unread.head 11: while (c ← step(j)) ̸= EXHAUSTED and c ≤ cij max do ′ 12: p ← Jij [c] {first read of Jij loads the column} 13: if p′ ̸= ⊥ then 14: Hi ← Hi ∪ {p′ } 15: if p′ = p then 16: return true{confirmed — break early} 17: end if 18: end if 19: end while 20: unread.pop() {Sj drained, or past cij max } 21: end while 22: return false{Hi has converged: Hi = Pi }

The two guards on the inner loop are the a-priori level of §9.2 composed into the document level, not an alternative to it: step skips the child matches below cij min on the first touch of bound retires the segment as soon as its matches run past the column’s Sj , and the c ≤ cij max range. They subsume the column bypass as a degenerate case — if the first stepped match already exceeds cij max , the loop body never executes, Sj is popped, and Jij is never loaded — so a column outside the child query’s range costs one advance and no column read at all. Algorithm 1 and the matches line of Algorithm 2 apply the same restriction, the latter by ij intersecting the child matches with [cij min , cmax ]; the three levels of §9 are therefore stacked in every variant, not distributed among them. An all-⊥ column needs no case of its own here either: under the conventions of §7.2 its cij min is +∞, so the first step returns EXHAUSTED, Sj is popped unread, and the column — which was never materialized — is never asked for. Note that step is also what creates itj , on first touch, rather than the initialization block doing so for all j at once. The distinction is not cosmetic: constructing a cursor is what triggers the materialization of Bj (§8.1), so creating all M of them up front would make every parent segment pay for every child segment’s scan before its first matches call, and would leave the early exits of this algorithm saving column reads only. Deferring creation to first touch is what lets a parent segment that converges early — the R1 trace of §C.5 — avoid S3 entirely when no sibling parent task has reached it. When laziness pays, and when it does not. The asymmetry of Hi has a sharp consequence that we state plainly, since it bounds what document-level pruning can deliver. A confirmation is cheap: the loop stops at the first c with Jij [c] = p. A refutation is not: Hi is a false-negative 13

set, so p ∈ / Hi decides nothing, and Algorithm 3 may only answer false once unread is empty — that is, once Hi has converged to Pi . The first parent docid that is not a match therefore pays the full cost of the eager algorithm, and the lazy variant degenerates to Algorithm 1 at that moment. Everything after it is free, as the R2 trace of §C.5 shows, but nothing before it was saved. Whether that moment arrives early depends on how tight Âi is, and with a single range per column it is typically not tight at all. Any join-index column whose parents are spread over Ri ij has pij min near 0 and pmax near |Ri | − 1, so the union in §8.2 covers almost the whole segment — as it does for both segments of the worked example (§C.3). Every non-matching parent docid that the sibling conjunction admits is then a false positive, and the first of them triggers convergence. Document-level pruning consequently pays off in the regime where the parent-side filter is restrictive and the candidates surviving it are mostly true matches: there, confirmations dominate, refutations are rare, and whole child segments are never touched. It pays off least when candidates are drawn from a broad Âi , which is precisely when the approximation was uninformative to begin with. This is the strongest argument for the n-range extension sketched in §8.2 and §9.2: approximating {p} by a union of disjoint ranges rather than a single interval shrinks Âi , which suppresses exactly the false positives that force early convergence. We therefore regard it not as an optional refinement but as what makes the document level robust across data distributions; it remains unevaluated. Ordering the child segments. The order in which unread is consumed matters for the same reason. Ordering child segments by descending cardinality of their join-index column, { c | Jij [c] ̸= ⊥ } , visits first the columns that cover the most parents and are hence the likeliest to contain the docid being confirmed, so a confirmation is expected to be reached after fewer reads. The qualification is the one just made: this is a heuristic for the confirmation path alone. A refutation drains every column whatever the order, and costs the same under every permutation — reordering redistributes work inside the early-exit case and leaves the worst case exactly where it was. Two practical notes. The cardinality has to be recorded per column, alongside the bounding ranges of §7.2; the prototype stores the ranges but not yet the cardinality, so this ordering is left for future work and has not been evaluated. And because the order is a per-task heuristic, parent tasks running concurrently may reach the child segments in different orders, which leaves it undetermined in advance which task pays a given child segment’s first-touch materialization (§8.1). That cost is paid once either way, so the indeterminacy is one of accounting rather than of total work.

9

Pruning Hierarchy

We now summarize the pruning hierarchy of the semijoin algorithm described above.

9.1

Segment-level pruning

If the semijoin query is intersected (AND) with another query which does not have matches in a certain parent segment, that segment will be completely skipped from processing — which is more efficient than the classic query-time join (§5.1), which calculates FKs that can be dropped by the parent-level filter. This level is worth stating precisely, because we do not implement it: it falls out of the algorithm’s shape. Because the semijoin is an ordinary per-segment query rather than a global two-stage pipeline, segment-level skipping comes for free — the engine simply never asks Ri for a scorer when a sibling conjunct has no matches there, exactly as it would for any other leaf 14

query. Algorithm 1 has no line corresponding to it. The contrast with the classic query-time join (§5.1) is therefore structural rather than a matter of a cleverer test: its stage 1 collects FKs from all child segments before any parent-side filter is consulted, so work spent on children whose parents a sibling filter will discard has already been spent by the time the filter applies. Being per-segment is what makes the saving available; the two levels below are what the algorithm does with it.

9.2

A-priori (min/max) pruning

Another optimization is a-priori pruning: in addition to the index column, we also write a kind ij ij ij of bounding box over join-index column pij min , pmax and cmin , cmax . ij ij The child docid range cmin , cmax lets us: • skip the first child matches with c < cij min , then • prune at the first child filter match: if c(first match) > cij max , loading this column can be bypassed completely. Then, • when we loop through child matches, it can exit earlier when c > cij max ij The parent docid ranges pij min , pmax lets us build an approximation of the parent matches without reading the index column at all, which is used in the two-phase algorithm §8.2. These ideas might be extended over n even edge values approximating the set of docids by disjoint ranges (interval sketches) and allowing leapfrogging of child matches when calculating the semijoin, and narrow down parents approximation — although the efficiency of this optimization depends on the actual data and has not been evaluated.

9.3

Document-level pruning

Document-level pruning is the lazy two-phase machinery of Section 8.3: it defers loading index columns until it’s inevitable, and even more, it can confirm the given parent docid by reading only part of the join-index column. That returns control over the iteration to potentially faster sibling queries and advances overall search faster. See §4.4. Unlike the two levels above, this one is not unconditional: it saves work on confirmations only, and the first candidate it cannot confirm costs a full read of every remaining column. Its benefit is therefore distributiondependent, and is largest when the parent-side filter is restrictive enough that most surviving candidates are true matches — see the discussion at the end of §8.3.

10

Implementation Notes

Thus we get an algorithm joining two flush-based tables with external string variable-length keys. It does it concurrently: it employs the built-in Lucene mechanism. It implements the a-priori and document-level pruning of §9.2 and §9.3, and inherits segment-level skipping from being an ordinary per-segment query (§9.1), which together allow combining it with all Lucene queries efficiently, without wasting computation on matches which would later be thrown away by another filter. It uses Lucene data structures, which are compact, efficient, and flexible: for example, we can trade off memory instead of disk writes by switching to a memory buffer directory implementation. The code is published as early draft at https://github.com/apache/solr/compare/main. ..mkhludnev:solr:aijoin-qparser under ASLv2. It requires no changes to Lucene itself, being client code that merely uses the library. Any authors of custom search servers may adopt this code by copying it. 15

It also provides an Apache Solr query parser integration, which makes it readily adoptable by Solr users. For the codename of this query parser we use aijoin (“AI” stands for “auxiliary index”). We defer Elasticsearch and OpenSearch integrations since they don’t favor cross-index joins; however, it should be easy to integrate into a single-index join flow.

11

Experimental Evaluation

11.1

Existing Benchmark

The benchmark is published at https://github.com/mkhludnev/aijoin-benchmark. Sample benchmark results are reproduced in Table 1. The benchmark runs against bare Solr setup extended with the query parser §10. It runs on cloud VM with 4 vCPUs, 8G RAM, 2G heap, and SSD storage. Also, segment-level parallelism was set to 4 as described in README.md. The indexer creates segmented index of 1M parent documents (products) and 10M child documents (skus) in a single shard (horizontal partition in Solr terms). The flush produced N = 6 parent segments and M = 9 child segments, hence N × M = 54 join-index columns; segment sizes are uneven, as flush-produced runs are, the largest child segment holding 3,909,575 docs. Every figure below scales with these two counts, so we state them once here. The searcher then sends semijoin queries joining skus to products, with random filters applied on both sides. Three properties of the harness make the two parsers comparable, and all three are deliberate. First, each arm runs a fixed number of queries — 500 — rather than for a fixed duration, and the query list is generated up front from a fixed seed, so query k is the same query in every arm and at every concurrency. Second, each arm runs at fixed concurrency rather than at a fixed request rate: a rate above what the server can absorb makes the queue grow without bound, so the run would report queueing rather than joining, and whether a given rate is sustainable differs between the two parsers by roughly the factor we are trying to measure. A closed loop cannot diverge; we report the rate each arm achieved as a result rather than imposing one. Third, we sweep the concurrency, because a single operating point cannot distinguish a cheaper query from one that scales better. QTime, ms (concurrency 1)

{!join score=none} (baseline)

{!aijoin} (join index)

speedup

min median p90 p95 p99 mean

1273 1953 2585 2640 2716 1934.6

187 345 492 496 502 359.8

6.8× 5.7× 5.3× 5.3× 5.4× 5.4×

max

3006

12188†

Table 1: Per-query latency at concurrency one, 500 queries per arm, same query set in both. † the join-index arm ran against a cold auxiliary index: its slowest query is query 1 of 500, which paid the whole materialization of §11.2; the next slowest is 571 ms, and excluding it the mean is 336.1 ms.

16

Concurrency

1

2

4

8

{!join score=none} (baseline) mean QTime, ms 1934.6 p99 QTime, ms 2716 throughput, queries/s 0.48 gain over previous —

1962.0 2710 0.95 1.97×

3249.2 4456 1.18 1.24×

7027.7 9576 1.11 0.94×

{!aijoin} (join index) mean QTime, ms p99 QTime, ms throughput, queries/s gain over previous

359.8† 502 2.03† —

325.7 523 4.43 2.18×

438.6 711 7.09 1.60×

845.9 1478 8.04 1.13×

Speedup, mean QTime Throughput ratio numFound mismatches

5.4× 4.2× 0/500

6.0× 4.7× 0/500

7.4× 6.0× 0/500

8.3× 7.2× 0/500

Table 2: Concurrency sweep on 4 vCPUs, 500 queries per cell. † cold auxiliary index, see Table 1. The baseline peaks at concurrency 4 and loses throughput at 8; the join index is still gaining there, at 6.8× the baseline’s best figure at any concurrency (the 7.2× in the row above is the two arms compared at concurrency 8). Result-set equivalence. Because both arms execute the same 500 queries, they can be compared query by query rather than in aggregate. They agree on numFound for every one of the 500 — zero mismatches — which is what establishes that the pruning of §9 trades no correctness for speed. Matching aggregate distributions would not have established it: two runs of different lengths execute different query sets, so agreement between their summary statistics is neither necessary nor sufficient. The gain is distributional, not an artifact of the mean. At concurrency one the join index is faster at every quantile we measured, by between 5.3× and 6.8× from the minimum through the 99th percentile. Its tail is also tighter in absolute terms: the spread from median to p99 is 157 ms against the baseline’s 763 ms. The advantage widens with load, and that is the more informative result. Table 2 sweeps the concurrency on the same 4 vCPUs. The baseline converts the first doubling into throughput almost perfectly (0.48 → 0.95 queries/s, 1.97×), then falters (1.24×), then regresses: at concurrency 8 it serves 1.11 queries/s, fewer than the 1.18 it managed at 4, while its mean latency more than doubles to 7027.7 ms and its p99 reaches 9576 ms. Its peak is at concurrency 4, and past that point added load costs throughput rather than buying it. The join index does not turn over anywhere in the range we measured. It gains 1.60× from 2 to 4 and is still gaining at 8, where it serves 8.04 queries/s — 6.8× the baseline’s best figure at any concurrency, which is the sterner comparison than the 7.2× separating the two arms at concurrency 8. Its returns are diminishing there (1.13× for a doubling), so its own ceiling is nearby; we simply did not reach it. Normalizing removes the objection that a cheaper query would reach a higher ceiling anyway. Over the identical step from concurrency 2 to 4 the join index converts 80% of the added concurrency into throughput against the baseline’s 62%; over the step from 4 to 8 it converts 56% while the baseline converts none. The two are not separated by a constant factor: they scale differently, and the measured speedup rises monotonically with load — 5.4×, 6.0×, 7.4×, 8.3×. 17

A saturated system should hold its throughput, not shed it, so the baseline’s 6% decline from 4 to 8 is contention rather than mere saturation. We did not instrument it, but the shape of the classic algorithm suggests where to look: it materializes a global {F K} set per query (§5.1), sized by the number of matching child documents, so eight in-flight queries hold eight such sets at once on a 2 GB heap. The join-index algorithm allocates per-segment bitsets instead, whose size depends on segment length rather than on match count. Confirming that this is what collapses the baseline needs allocation and GC instrumentation we have not added. This is the first direct evidence for requirement R3 (§6.4) and for the Amdahl argument of §5.1: an algorithm with a sequential merge between its two stages should reach its ceiling sooner than one without a synchronization point, and it does — at half the concurrency and at 1/6 the throughput. We state the limit of that inference too. The classic join also costs more CPU per query — at saturation the throughput ratio is essentially the ratio of CPU work per query — and a CPU-heavier query saturates a fixed core count earlier whether or not it contains a serial section. The measurement is consistent with the sequential merge being the cause; it does not isolate it. Doing so would need the {F K} merge instrumented separately, which we have not done. Throughput ratios are smaller than latency ratios, for a client-side reason. Each query carries a client and network cost of roughly 120 ms (median client latency exceeds median QTime by 116 ms in the join-index arm and 123 ms in the baseline). Being constant in absolute terms, it dilutes a ratio far more when the server-side figure is 345 ms than when it is 1953 ms, which is why the throughput ratios in Table 2 run below the QTime speedups. The speedups are server-side results; what an application sees depends on what else is in its request path. The materialization cost is one query, and it is visible. The concurrency-one join-index run started from a cold auxiliary index, and the whole build lands on query 1 of 500: a QTime of 12188 ms, against 571 ms for the next slowest. That figure agrees with the 11325 ms measured inside the builder (§11.2), which confirms that QTime accounts for the build rather than hiding it. Spread over 500 queries it raises the arm’s mean by 23.7 ms, from 336.1 to 359.8; every other cell of Table 2 ran warm. Moving that one query’s cost into searcher warming is future work (§13).

11.2

The cost of materialization

A join index is a materialized structure, so the question Valduriez’s cost model asks of it (§5.3) is when materializing beats joining at query time. This benchmark answers it directly. Building the auxiliary index from cold produced the single event in Table 3; both figures it needs — what the structure costs and what it saves per query — are now measured on the same workload. Parent segments N / child segments M Join-index columns Jij built Largest child segment |Sj | Non-⊥ entries over all columns Auxiliary index on disk Build time (one batch, one thread)

6/9 54 3,909,575 10,000,000 ≈30 MB 11,325 ms

Latency saved per query (§11) Queries to break even

1,574.8 ms 7.2

Table 3: Materialization cost, from a cold auxiliary index, against the per-query saving of Table 1.

18

Break-even is seven queries. The build costs 11.3 s once; each query thereafter is 1,574.8 ms cheaper than the classic query-time join at concurrency one, and more than that under load. The structure has repaid itself after seven queries and is pure gain from the eighth. For an index that serves any sustained query load this is not a trade-off so much as a rounding error, and it is the concrete instance of the read/write balance [25] frames in the abstract. The N × M column count does not become N × M storage. Materializing one column per segment pair suggests N · |S| = 6 × 107 slots, six copies of the child collection. It does not cost that, because a column is ⊥ wherever the child’s parent lives in another parent segment, and ⊥ is stored as an absent value rather than a present one: Lucene’s NumericDocValues are sparse (§7.2). Every child docid is non-⊥ in exactly one of the N columns covering its segment — its parent lives in exactly one parent segment — so the non-⊥ entries over the whole join index number |S|, not N ·|S|. The measured total, 10,000,000, is exactly the child collection size, and the auxiliary index occupies about 30 MB, i.e. some 3 bytes per child document. Storage grows with the data, not with the segment count; what grows with N · M is the number of columns to address and sweep, not the bytes they hold. The build is serial, and need not be. All 54 columns were computed one after another on a single thread, in one batch; no pair was awaited from a concurrent builder. The pairs are independent, so the 11.3 s is an artifact of the prototype rather than of the design — with the caveat that the write itself must remain a single batch, since a batch begins at doc 0 of its sidecar segment, which is what makes a column’s docid coincide with the child docid. Parallelizing the computation is §13; so is moving the whole cost off the query path into searcher warming, after which break-even ceases to be a query-latency question at all.

11.3

Where the speedup comes from: instrumenting the pruning hierarchy

The latency figure above says the join index is faster; it does not say which part of the design earns that. To find out, the prototype counts, per parent segment, how many join-index columns each level of §9 eliminates, and how tight the approximation Âi actually is. Table 4 reports those counters over 3,000 parent-segment scorings of the same benchmark, covering 27,000 candidate segment pairs. Measurement

Value

Share

Candidate pairs (Ri , Sj ) with a child-side match dropped a-priori, before any column was opened surviving into confirmation

27,000 423 26,577

1.6% 98.4%

Âi as a share of the parent segment (median)
P ij ij Range overlap factor j |[pmin , pmax ]| /|Âi | Parent segments where Hi never converged Parent segments forced to full convergence Columns drained Columns never opened Drains ending in an early confirmation Child docids walked (column-read work)

100.0% 8.77 86 2,914 26,175 402 3,550 4.34×109

2.9% 97.1% 98.5% 1.5% 13.6%

Table 4: Pruning effectiveness on the benchmark of §11, over 3,000 parent-segment scorings. Three readings, and they point the same way.

19

The approximation is vacuous, exactly as predicted. The median Âi covers 100.0% of its parent segment — so does the 90th percentile. The approximation never excludes a single parent docid. This is the prediction of §8.3 confirmed quantitatively: with one range per ij column, any column whose parents are spread over Ri has pij min at 0 and pmax at |Ri | − 1, and the union of nine such ranges is the whole segment. The overlap factor of 8.77 says as much directly: the nine per-column ranges sum to 8.77 times the size of their union, i.e. each covers essentially all of it. Document-level pruning therefore collapses. Since every non-matching parent that survives the sibling filter is a false positive, the first one forces convergence: 97.1% of parent segments drained every column, and only 1.5% of columns went unopened. The 13.6% of drains that ended in an early confirmation did not save those reads — they deferred them, and the segment converged later anyway. The lazy variant of Algorithm 3 thus executed, on this workload, as Algorithm 1: 4.34 × 109 child docids walked is approximately every matching child docid, once per parent segment. A-priori pruning fires rarely, for the same reason on the child side. Only 1.6% of ij candidate pairs were bypassed. A column’s child range [cij min , cmax ] is as wide as its parent range for the same reason, so the bypass has nothing to bite on. The benchmark is the worst case for range-based pruning, by construction. This is not a neutral measurement, and reporting it as one would overstate it in the other direction. The indexer assigns each sku a foreign key drawn uniformly at random from all 106 products. Every child segment therefore references parents spread uniformly across every parent segment, ij ij ij which is precisely the distribution that flattens both [pij min , pmax ] and [cmin , cmax ] to the full range. Any correlation between insertion order on the two sides — a product indexed near its skus, a bulk load ordered by supplier, anything that puts related documents in nearby docids — would tighten both. The numbers above are a lower bound on what the two range-based levels can do, not an estimate of the typical case, and quantifying that gap needs a benchmark with a tunable correlation between the two sides, which §11.4 does not yet include. What this means for the result. The 5.4–8.3× speedup of §11 was obtained with the a-priori level firing on 1.6% of pairs and the document level saving 1.5% of column reads. It is therefore not attributable to the pruning hierarchy: it comes from the join index itself — the ordinal-to-ordinal column that removes query-time translation of external keys (R1), and the per-parent-segment execution that removes the synchronization point of §5.1 (R3). That is a sharper claim than the one we set out to make, and a more robust one: the structure delivers the speedup on a workload engineered, however unintentionally, to defeat its optimizations. It also makes the n-range extension (§8.2, §9.2) the highest-value item in §13 rather than a refinement. A single interval per column cannot describe a uniformly scattered key distribution; a union of disjoint ranges can, and it is the only one of the proposed changes that attacks the measured cause. Two caveats bound what Table 4 settles. Segment-level pruning (§9.1) is invisible to it, since a segment skipped by the engine never constructs the context that would report it; and the 50.6% of confirmations answered from Hi alone is dominated by lookups made after convergence, when Hi = Pi and the question is no longer being pruned but merely answered.

11.4

Future Evaluation Plan

• vary the correlation between the two sides’ insertion orders. The current generator assigns foreign keys uniformly at random, which flattens every column’s parent and child ranges 20

and reduces both range-based pruning levels to noise (§11.3); a tunable locality parameter would measure them across the range from that worst case to the co-located case, and would tell us what the n-range extension has to beat; • benchmark under a moderate stream of concurrent updates; • add a global-ordinals baseline arm — Lucene’s global-ordinals join (§5.2), reachable in Apache Solr as method=topLevelDV. This is the comparison the paper most needs and does not have. Global ordinals attack the same cost that R1 (§6.4) identifies in the classic query-time join — they correlate the two sides’ value ordinals once, up front, instead of translating external keys per query — so they are the strongest same-system baseline for the central claim, and measuring against {!join score=none} alone leaves that claim weaker than it needs to be. We expect the comparison to split by workload rather than to settle. A global ordinal map is built per top-level reader and invalidated on every commit, so its advantage should be largest on a static index and should erode as the update rate rises, while a join-index column is scoped to an immutable segment pair and survives commits that do not delete either segment. The two arms should therefore be swept against the update stream of the item above rather than measured at a single, static operating point — and the same sweep bounds what the global-ordinals restriction to one index and one field (§5.2) costs in exchange; • compare with memory buffer directory and soft-commits (NRT-search); • compare with joins over numeric fields; • compare against a state-of-the-art RDBMS join.

12

Discussion

This approach might be applicable to other LSM-tree storage engines and/or those which are based on virtual IDs.

13

Future Work

We group the outstanding work by how much of it is already decided, rather than by topic: what remains to be built on the current prototype, what is a charted extension of it, and what is still an open question. Engineering on the current prototype. §10:

Bounded work whose shape is already clear from

• cache the column-to-auxiliary-index-segment assignment (so far it searches columns by scanning segments linearly); • offload the join-index build onto searcher warmup, which should remove the tail latency observed in §11; • explore parallelism when writing join-index columns. The bulk pass of §7.2 computes each pair’s column on the calling thread, one pair after another, although the pairs are independent: each merges the term dictionaries of its own (Ri , Sj ) and touches no shared state but the scratch buffer, which can be made per-thread. The constraint is that the write itself must stay a single batch — a batch begins at doc 0 of its sidecar segment, which is what makes a column’s docid coincide with the child docid — so the parallelism belongs in computing the mappings, not in writing them; 21

• add join-index column cardinality to the metadata alongside the bounding ranges, and use it to order child segments in lazy confirmation (§8.3); • improve the sweeping and merging scheme for auxiliary index columns. Charted extensions.

Larger, but the direction is settled:

• extend bounding ranges to a union of n disjoint ranges, to tighten the parent docid approximation and allow leapfrogging of child matches (§8.2, §9.2). The measurements of §11.3 make this the first item to attempt rather than one among several: it is the only proposed change that addresses why both range-based levels currently fire so rarely; • extend the current 1:M onto a generic N:M relation; • semijoin in the reverse direction — return children of certain parents via the same joinindex columns; • prototype a real join operation returning the children side as well; • apply the join index to generic graph traversal8 ; • introduce joins in the existing SQL parser9 . Open questions.

Where the aim itself is still to be established:

• complexity analysis, and with it a read/write cost model in Valduriez’s sense [25] — when materializing N × M columns pays for itself against joining at query time; • following from that, whether the choice can be made adaptively, falling back to the classic query-time join (§5.1) as the segment count N grows and the redundant child-query evaluations of §8.1 come to dominate; • explore indexing multiple relation joins; • research compatibility with vector search (HNSW10 ); • introduce specialized data structures for a faster join; • research a file format allowing the join index to be kept on one side, without an auxiliary index.

14

Conclusion

We have shown how Valduriez’s join-index idea, originally developed for relational systems, carries over to the flush-produced, unmerged segments of an inverted index, using Apache Lucene as a concrete implementation target. On top of this structure we built a semijoin algorithm that runs per parent segment in parallel, without a global barrier between stages, and prunes at three levels — segment-level, which comes free from per-segment execution; apriori min/max; and document-level two-phase confirmation — so that it composes with the dynamic pruning already present in search engines rather than fighting it. On a benchmark of 1M products and 10M skus (§11), this join index cut average query latency 5.4× (359.8 ms vs. 1934.6 ms) against Solr’s built-in query-time join, and 8.3× once eight queries run at once — 8

https://solr.apache.org/guide/solr/latest/query-guide/other-parsers.html#graph-query-parser https://solr.apache.org/guide/solr/latest/query-guide/sql-query.html 10 https://solr.apache.org/guide/solr/latest/query-guide/dense-vector-search.html#query-time 9

22

a point at which the baseline has passed its own throughput peak and begun to decline, while the join index is still gaining — all while returning an identical result count on all 500 queries of every run. Instrumenting that run (§11.3) places the credit more precisely than we first expected. On a workload whose foreign keys are uniformly random — and therefore flatten every column’s bounding ranges to the full segment — the a-priori level bypassed 1.6% of segment pairs and the document level spared 1.5% of column reads, so the speedup is the join index’s own, not its pruning’s. We regard that as the stronger outcome: the ordinal-to-ordinal column and the synchronization-free per-segment execution carry the result unaided, and the pruning hierarchy remains available for the correlated key distributions where its single-interval approximation has something to exclude.

A

Appendix

A.1

Inverted Index as Dictionary Compression

If we precisely look into the first point of §4.3, we can recognize the dictionary compression [1] scheme in inverted index. To keep the argument in its simplest form, we restrict it to a primary-key field — exactly the case of R.id in this paper — and assume throughout this subsection that • f is single-valued: every docid has exactly one value ordinal; • values are unique: every ordinal occurs in exactly one document, so a posting list is a single docid; • the term dictionary is a collision-free in-memory hash table, so the ordinal of a value v is i ordsR f [v] = ordinals[ hash(v) mod tableSize ]. For sure, real implementations are much more complex than that. Under these assumptions, keeping the notation of §6.3, the two access paths are: Ri i • searching, i.e. obtaining a docid by a value, is docidsR f ordsf [v] ;





i • getting a value by docid is valuesR f Ri .f [p] .





The two are not merely symmetric, they are mutually inverse bijections between docids and ordinals:     i i docidsR and Ri .f docidsR f Ri .f [p] = p f [o] = o. In words: the inverted index is the column read backwards. The column Ri .f maps docids to Ri i ordinals, the inverted index maps ordinals back to docids, and valuesR f , ordsf are likewise inverse to each other between ordinals and values. So the inverted index and the dictionarycompressed column are two indexings of one and the same correspondence between docids and values: the column stores it indexed by docid, the inverted index stores it indexed by value. Dropping the assumptions does not change the picture, only weakens the one-to-one correspondence into a many-to-one one: if values repeat, the inverted index becomes the setvalued inverse of the column — the posting list of an ordinal is the preimage (Ri .f )−1 (o), and posting-list length is exactly the redundancy that dictionary compression exploits; if the field is multi-valued, the column becomes set-valued in the same way. The following observations demonstrate tight coupling of inverted index and data columns, which are formally distinct entities in Lucene right now:

23

• long ago Lucene obtained the data column at runtime via uninverting 11 meaning the process of reversing inversion (of inverted index). Note: nowadays it’s replaced by indextime data columns called by DocValues, where SortedDocValues introduce dictionary compression explicitly; • there’s a proposal12 about merging inverted index’s term dictionary and data column’s dictionary into a single one; • pulsing codec [10] is exact mapping of value to docid; • possible contra argument about a posting list arity can be debated with examples of multi-valued data columns (SortedSetDocValues13 ) and from other side, the pulsing codec emphasizes the importance of the singular case. Overall, this observation does not bring much to practice, but it may give us a clue in designing new data structures and indices formats.

11

https://lucene.apache.org/core/6_3_0/misc/org/apache/lucene/uninverting/UninvertingReader. html 12 https://issues.apache.org/jira/browse/LUCENE-5832 - Explore a combined DocValues/PostingsFormat that shares a single terms dict 13 https://lucene.apache.org/core/10_1_0/core/org/apache/lucene/document/ SortedSetDocValuesField.html

24

B

Symbol Table Table 5: Notation used throughout the paper. Symbol

Reads as

R R.id S S.f k qR , q S ⋉ Ri , Sj ; N , M p, c

parent (outer side) relation, "to" side parent side primary key child, inner relation, "from" side child side foreign key parent / child query semijoin segments and their counts parent / child docids (document ordinal numbers) a set of child docids; the docid space [0, |Sj |) positional column access f field value ordinal by p docid obtaining f field value by ordinal term-dictionary lookup: ordinal by value posting list: docids by ordinal (§A.1, inverse of Ri .f ) sorted match set / iterator iterator contract (approx./confirm. phases) join-index column; absent-parent sentinel column parent/child, min/max metadata exact / approximate / half-read set

C, Uj Ri .f [p] i valuesR f [v_ordinal] i ordsR f [v] i docidsR f [o]

M(q, Sj ) next/advance approximation/matches Jij , ⊥ ij ij ij pij min , pmax , cmin , cmax Pi , Âi , Hi

C

Worked Example

We trace the algorithms of §8 end-to-end on a tiny instance with N =2 parent segments and M =3 child segments. The instance is small but not degenerate: it exercises the a-priori level of §9.2 in all three of its uses (§C.4), and it contains a false positive that puts the lazy variant into both of its regimes — early confirmation for R1 , forced convergence for R2 (§C.5).

C.1

Setup

Parent segment R1 holds three docs, local docids p = 0, 1, 2, with ids A, B, C; parent segment R2 holds three docs, local docids p = 0, 1, 2, with ids D, E, F . Three child segments S1 , S2 , S3 hold, respectively, 4, 3, 4 docs, each carrying a foreign key pointing at one of A..F : S1 , c : 0 1 2 3 B D A F fk :

S2 , c : 0 1 2 E A C fk :

S3 , c : 0 F fk :

1 2 3 B D E

A single child query qS matches M(qS , S1 ) = {0, 2, 3}, M(qS , S2 ) = {1, 2}, M(qS , S3 ) = {0, 1, 3} (sorted iterators, in this order).

25

C.2

Join-index columns

By Definition 2, each of the N ×M = 6 columns Jij maps a child docid of Sj to a local parent docid of Ri , or ⊥ if the fk target does not live in Ri : J11 = (1, ⊥, 0, ⊥),

J12 = (⊥, 0, 2),

J13 = (⊥, 1, ⊥, ⊥),

J21 = (⊥, 0, ⊥, 2),

J22 = (1, ⊥, ⊥),

J23 = (2, ⊥, 0, 1).

The associated metadata (over non-⊥ entries only) is

C.3

column

cmin

cmax

pmin

pmax

J11 J12 J13 J21 J22 J23

0 1 1 1 0 0

2 2 1 3 0 3

0 0 1 0 1 0

1 2 1 2 1 2

Approximation phase

Unioning the per-column [pmin , pmax ] ranges over j = 1..3 (Algorithm 2, line 1) gives Â1 = [0, 1] ∪ [0, 2] ∪ [1, 1] = {0, 1, 2},

Â2 = [0, 2] ∪ [1, 1] ∪ [0, 2] = {0, 1, 2}.

Both approximations cover all of their segment (R1 and R2 have only 3 docs each), so no candidate is pruned yet by §9.2 at this granularity — but Â2 already contains a false positive, p=0 (D), that the confirm phase below must rule out.

C.4

Ground truth via the base algorithm

For reference, Algorithm 1 gives the exact semijoin sets directly (writing only the non-⊥ entries that each column contributes): P1 = {J11 [0], J11 [2]} ∪ {J12 [1], J12 [2]} ∪ {J13 [1]} = {1, 0} ∪ {0, 2} ∪ {1} = {0, 1, 2}, P2 = {J21 [3]} ∪ {} ∪ {J23 [0], J23 [3]} = {2} ∪ {2, 1} = {1, 2}. So every doc of R1 matches (A, B, C), while R2 matches only E, F — D is a match for no child in M (qS , ·), despite sitting inside Â2 . The a-priori guards of §9.2 are already in force here, and each of their three uses fires at least once. The advance(cij min ) entry skips a child match before any read: J21 is entered at c=1 and never sees the match c=0, as is J13 . The c > cij max exit abandons a column early: J11 stops at c=3 and J13 , defined only at c ∈ [1, 1], contributes its single entry and retires, reading one of the three matches of S3 . Finally, the empty term of P2 is the bypass: J22 is defined only at c=0, which qS does not match, so advance(0) returns c=1 > c22 max =0 and the column is never opened — that empty set costs one advance and no column read.

C.5

Lazy confirmation trace (Algorithm 3)

Each parent segment keeps its own Hi and its own persisted iterators itj over M(qS , Sj ), j = 1, 2, 3; matches(p) is invoked once for each local docid of Ri inside Âi , in ascending order. We apply the a-priori guards of Algorithm 3: the first step on a child segment is advance(cij min ), and the inner loop retires the segment once c passes cij , using the metadata tabulated in §C.2. max 26

R1 : early breaks pay off.

Start with H1 = ∅, unread = [1, 2, 3].

• matches(0): 0 ∈ / H1 . Read it1 , entered at advance(c11 min =0): c=0 ⇒ J11 [0]=1, H1 ← {1} (no match yet); c=2 ⇒ J11 [2]=0, H1 ← {0, 1} — 0=0, return true. it1 is left paused at c=2 consumed, c=3 still unread; S2 , S3 untouched. • matches(1): 1 ∈ H1 already — return true for free, no column read at all. • matches(2): 2 ∈ / H1 = {0, 1}. Resume it1 at c=3, which exceeds c11 max =2: S1 retires without J11 [3] ever being read, pop, unread = [2, 3]. Move to j=2, entered at advance(c12 min =1): c=1 ⇒ J12 [1]=0 (already in H1 , no match); c=2 ⇒ J12 [2]=2, H1 ← {0, 1, 2} — 2=2, return true. J13 (S3 ) is never read. H1 converges to {0, 1, 2} = P1 , matching §C.4, after touching only 4 of the 3+2+3=8 available child matches — three saved by the early returns, one by the c11 max bound. R2 : a false positive forces a full drain.

Start with H2 = ∅, unread = [1, 2, 3].

• matches(0) (the false positive D from Â2 ): 0 ∈ / H2 , and no read of any column can ever confirm it, so the loop must retire all three child segments before giving up. j=1, entered at advance(c21 min =1), which skips the match c=0 outright: c=2 ⇒ J21 [2]=⊥; c=3 ⇒ J21 [3]=2, H2 ← {2} (2 ̸= 0); it1 exhausted, pop. j=2: advance(c22 min =0) yields c=1, already past c22 =0, so the column is bypassed and J is never loaded at all — though S2 ’s 22 max child matches are materialized regardless (§8.1); pop. j=3, entered at advance(c23 min =0): c=0 ⇒ J23 [0]=2 (H2 unchanged); c=1 ⇒ J23 [1]=⊥; c=3 ⇒ J23 [3]=1, H2 ← {1, 2} (1 ̸= 0); it3 exhausted, pop. unread = ∅ — return false. • matches(1): 1 ∈ H2 = {1, 2} — return true for free. • matches(2): 2 ∈ H2 — return true for free. Here the single false positive forces convergence up front (the worst case of §8.3), and the apriori level is all that stands between it and a full read: of the eight child matches it costs five column lookups, and J22 — whose single defined entry lies outside the child query’s matches — is bypassed without being opened. That cost is paid exactly once per segment: H2 has now fully converged to P2 = {1, 2}, and the two remaining confirmations are free lookups.

References [1] Daniel Abadi, Peter Boncz, and Stavros Harizopoulos. The Design and Implementation of Modern Column-Oriented Database Systems. Now Publishers Inc., Hanover, MA, United States, 2013. [2] Gene M. Amdahl. Validity of the single processor approach to achieving large scale computing capabilities. In Proceedings of the April 18–20, 1967, Spring Joint Computer Conference (AFIPS), pages 483–485, 1967. [3] Apache Software Foundation. Apache lucene. https://lucene.apache.org/. Accessed July 2026. [4] Apache Software Foundation. Apache lucene 10.2.2 core API: org.apache.lucene.index (segments and document IDs). https://lucene.apache.org/core/10_2_2/core/org/ apache/lucene/index/package-summary.html#segments-and-docids-heading. Accessed July 2026.

27

[5] Apache Software Foundation. Apache lucene 10.2.2 join module: org.apache.lucene.search.join (query-time joins). https://lucene.apache.org/ core/10_2_2/join/org/apache/lucene/search/join/package-summary.html# query-time-joins-heading. Accessed July 2026. [6] Apache Software Foundation. LUCENE-6198: Speed up conjunctions with a highcardinality clause by using two-phase iterators. https://issues.apache.org/jira/ browse/LUCENE-6198. Accessed July 2026. [7] Philip A. Bernstein and Dah-Ming W. Chiu. Using semi-joins to solve relational queries. Journal of the ACM, 28(1):25–40, 1981. [8] Andrzej Białecki, Robert Muir, and Grant Ingersoll. Apache lucene 4. In Proceedings of the SIGIR 2012 Workshop on Open Source Information Retrieval (OSIR@SIGIR), pages 17–24, Portland, OR, 2012. [9] E. F. Codd. A relational model of data for large shared data banks. Communications of the ACM, 13(6):377–387, 1970. [10] Douglass R. Cutting and Jan O. Pedersen. Optimization for dynamic inverted index maintenance. In Jean-Luc Vidick, editor, Proceedings of the 13th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR ’90), pages 405–411, New York, NY, USA, 1990. ACM. [11] Erik D. Demaine, Alejandro López-Ortiz, and J. Ian Munro. Adaptive set intersections, unions, and differences. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 743–752, 2000. [12] Shuai Ding and Torsten Suel. Faster top-k document retrieval using block-max indexes. In Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 993–1002, 2011. [13] Siying Dong, Mark Callaghan, Leonidas Galanis, Dhruba Borthakur, Tony Savor, and Michael Strum. Optimizing space amplification in RocksDB. In Proceedings of the 8th Biennial Conference on Innovative Data Systems Research (CIDR), 2017. [14] Elastic. Faster retrieval of top hits in Elasticsearch with Block-Max WAND. https://www.elastic.co/blog/ faster-retrieval-of-top-hits-in-elasticsearch-with-block-max-wand. Accessed July 2026. [15] Goetz Graefe. Query evaluation techniques for large databases. ACM Computing Surveys, 25(2):73–169, 1993. [16] Mark Harwood. Proposal for nested document support in Lucene. http://www. slideshare.net/MarkHarwood/proposal-for-nested-document-support-in-lucene. Accessed July 2026. [17] IBM Corporation. Sequential access. IMS 15.4 Product Documentation, Application Programming — Analyzing Data Access, 2026. [18] Xin Liang, Qing Yang, Wenru Qiu, Wenjie Mao, Tianyu Ma, Minghui Zhu, and Nan Wang. Write-read decoupling in modern large-scale search engines: Architectures, techniques, and emerging approaches, 2026. [19] Lucidworks. Solr and joins. https://lucidworks.com/blog/solr-and-joins. Accessed July 2026. 28

[20] Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze. Introduction to Information Retrieval. Cambridge University Press, 2008. [21] Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil. The log-structured merge-tree (LSM-tree). Acta Informatica, 33(4):351–385, 1996. [22] Patrick O’Neil and Dallan Quass. Improved query performance with variant indexes. In Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data, pages 38–49, 1997. [23] OpenSearch Project. Concurrent segment search. https://docs.opensearch.org/ latest/search-plugins/concurrent-segment-search/. Accessed July 2026. [24] Howard Turtle and James Flood. Query evaluation: Strategies and optimizations. Information Processing & Management, 31(6):831–850, 1995. [25] Patrick Valduriez. Join indices. ACM Transactions on Database Systems, 12(2):218–246, 1987.

29

Related documents

• Q-TIE: A Lightweight and Generalizable Re-ranking Framework for Temporal Information Retrieval#1050071
• Aristóteles no século XX#116881
• Beyond Similarity Search: A Unified Data Layer for Production RAG Systems#155410
• House price index - Item weights#815172
• SELF-ADJOINT EXTENSION SELECTION UNDER QUADRATIC FORM ORDER IN QUANTUM MECHANICS#713452