Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper adapts Valduriez's join-index technique to enhance query-time joins in Lucene's segment storage, addressing the limitations of existing implementations that either sacrifice performance or capability. By materializing an append-only join-index for parent and child segments and employing a parallel semijoin algorithm that prunes at multiple levels, the authors achieve significant performance improvements. The prototype, tested on a dataset of 1M products against 10M SKUs, demonstrates a reduction in average query latency by 5.4 times compared to Solr's built-in join, with performance gains increasing under higher loads.
Achieving an 8.3x performance boost in query latency for joins in search engines could redefine how we approach data retrieval efficiency.
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 J[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 times (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 times 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.8times the baseline's best.