Re: TermInSetQuery storage: PrefixCodedTerms vs sorted BytesRef[]

--000000000000996af706515080d5
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Thanks for sharing this work Govind. This is interesting stuff!

My brief 2 cents: I suspect it's a somewhat atypical pattern to have
queries that are dominated by large cardinality term-in-set disjunctions.
So my initial reaction to this is that I suspect the majority of use-cases
would prefer the memory efficient query representation. But that's just one
opinion.

That said, it would be great to publish your benchmarking in a PR! Let's
capture this testing and have a discussion. Even if the community decides
to stay with the current approach, you might want to consider adding your
version of this query in the sandbox module. That could provide a nice,
community-supported option for a more CPU efficient version of this query
that users could opt into.

Cheers,
-Greg

On Thu, May 7, 2026 at 3:20=E2=80=AFAM Govind Balaji via dev <[email protected]=
ache.org>
wrote:

> Hello Lucene devs,
>
> I'd like to surface a benchmark observation about TermInSetQuery's choice
> of PrefixCodedTerms as the in-memory term storage, and am curious if the
> community is aware of this RAM-CPU tradeoff at large number of terms, and
> the reasoning behind.
>
> ## Background
> Before LUCENE-6350 (May 2015), TermsQuery (the predecessor of
> TermInSetQuery) stored its terms as a sorted byte[] with a parallel int[]
> of offsets, plus a cached int hashCode.
> LUCENE-6350 replaced this shape with PrefixCodedTerms. The rationale
> recorded in the issue was "This will save ram and cleanup a lot of the
> code."
>
> ## The workload where this shows up
>   - We run TermInSetQuery with a tens of thousands terms per query.
>   - The LRUQueryCache skips caching the query on most segments because
> they are below its per-leaf size threshold. In our workloads, this is ~90=
%
> of segments (cumulatively a small fraction of docs).
>     On those segments the query pays its full per-segment cost of
> unpacking and iterating the same prefix coded terms on every request.
>   - Our workloads are CPU-bound than memory-bound.
>
> In this setup, the work that is independent of segment size becomes the
> dominant CPU cost of the query on all those many small segments.
> PrefixCodedTerms.TermIterator.next loading delta-encoded bytes show up as
> hot in profiles.
>
> ## What we tried
> A reimplementation of TermInSetQuery whose only change is the storage
> shape of the term list.
> Same FilteredTermsEnum ping-pong (accept / nextSeekTerm) - just driven by
> random access into a BytesRef[] instead of a streaming TermIterator.
> Conceptually this is closer to the pre-LUCENE-6350 storage layout. We als=
o
> avoid the packTerms() cost in the constructor with this.
>
> We additionally keep the term bytes in a single contiguous byte[]
> (length-prefixed VInts, BytesRef[] entries are zero-copy views into it),
> and have equals/hashCode operate solely on that byte[].
> That is how the pre-6350 implementation got its fast equals as well.
> BytesRef[] is still redundant, but did not want to mess around with the
> interfacing types too much and seemed okay.
>
> ## Results
> JMH microbenchmarks against Lucene's TermInSetQuery (Query construction +
> IndexSearcher.count(query)), on an in-memory index with the query cache
> disabled.
> We try a few different N terms in the TermInSetQuery, with each term bein=
g
> a random 16 char hex.
> For the benchmark, the index contains 50 segments and we vary what terms
> are indexed in each segment too as follows.
> Each indexed term is also a 16 char hex, and we index 1 doc for each term
> that we chose to have indexed. Reported as speedup =3D TermInSetQuery tim=
e /
> our impl time; >1 means our impl is faster.
>
>   Index content                                                   | N =3D
> 300 | N =3D 3k |  N =3D 30k
>   each segment has exactly the same terms in the random query     | 1.30x
>  | 1.31x  |  1.22x
>   Only 2 of N query terms in each segment, most seeks miss        | 2.11x
>  | 3.41x  |  3.74x
>   50k random (independent of the query) terms in each segment     | 1.05x
>  | 1.15x  |  1.32x
>
> In production (opensearch indexes with multiple shards per index), where
> this TermInSetQuery is only a subquery of our typical query,
> we saw the overall mean latency decrease by ~22% with this change when th=
e
> number of terms in TermInSetQuery > 30K. (Decreased by ~2% for queries wi=
th
> number of terms between 1k to 5k).
>
> ## What I'd like to ask
> Is this pattern of queries considered atypical and not worth the CPU at
> the cost of memory? Is this also a guiding principle in other parts of
> lucene?
> Or is there a quantified typical values for CPU-memory tradeoff? Asking
> out of curiousity whether we should be tweaking more stuff similarly,
> internally, for our CPU-bound workloads.
>
> Happy to put a PR up with the JMH benchmark/the impl we tried if that's o=
f
> interest.
>
> Thanks,
> Govind Balaji S
>
>

--000000000000996af706515080d5
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div dir=3D"ltr">Thanks for sharing this work Govind. This=
 is interesting stuff!</div><div dir=3D"ltr"><br></div><div>My brief 2 cent=
s: I suspect it&#39;s a somewhat atypical pattern to have queries=C2=A0that=
 are dominated by large cardinality term-in-set disjunctions. So my initial=
 reaction to this is that I suspect the majority of use-cases would prefer =
the memory efficient query representation. But that&#39;s just one opinion.=
</div><div><br></div><div>That said, it would be great to publish your benc=
hmarking in a PR! Let&#39;s capture this testing and have a discussion. Eve=
n if the community decides to stay with the current approach, you might wan=
t to consider adding your version of this query in the sandbox module. That=
 could provide a nice, community-supported option for a more CPU efficient =
version of this query that users could opt into.</div><div><br></div><div>C=
heers,</div><div>-Greg</div><br><div class=3D"gmail_quote gmail_quote_conta=
iner"><div dir=3D"ltr" class=3D"gmail_attr">On Thu, May 7, 2026 at 3:20=E2=
=80=AFAM Govind Balaji via dev &lt;<a href=3D"mailto:[email protected]"=
>[email protected]</a>&gt; wrote:<br></div><blockquote class=3D"gmail_q=
uote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-s=
tyle:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir=3D=
"ltr">Hello Lucene devs,<br><br>I&#39;d like to surface a benchmark observa=
tion about TermInSetQuery&#39;s choice of PrefixCodedTerms as the in-memory=
 term storage, and am curious if the community is aware of this RAM-CPU tra=
deoff at large number of terms, and the reasoning behind.<div><div><br>## B=
ackground<br>Before LUCENE-6350 (May 2015), TermsQuery (the predecessor of =
TermInSetQuery) stored its terms as a sorted byte[] with a parallel int[] o=
f offsets, plus a cached int hashCode.=C2=A0<div>LUCENE-6350 replaced this =
shape with PrefixCodedTerms. The rationale recorded in the issue was &quot;=
This will save ram and cleanup a lot of the code.&quot;<br><br>## The workl=
oad where this shows up<br>=C2=A0 - We run TermInSetQuery with a tens of th=
ousands terms per query.<br>=C2=A0 - The LRUQueryCache skips caching the qu=
ery on most segments because they are below its per-leaf size threshold. In=
 our workloads, this is ~90% of segments (cumulatively a small fraction of =
docs). <br>=C2=A0 =C2=A0 On those segments the query pays its full per-segm=
ent cost of unpacking and iterating the same prefix coded terms on every re=
quest.</div><div>=C2=A0 - Our workloads are CPU-bound than memory-bound.<br=
><br>In this setup, the work that is independent of segment size becomes th=
e dominant CPU cost of the query on all those many small segments.=C2=A0</d=
iv><div>PrefixCodedTerms.TermIterator.next loading delta-encoded bytes show=
 up as hot in profiles.<br><br>## What we tried<br>A reimplementation of Te=
rmInSetQuery whose only change is the storage shape of the term list.</div>=
<div>Same FilteredTermsEnum ping-pong (accept / nextSeekTerm) - just driven=
 by random access into a BytesRef[] instead of a streaming TermIterator.=C2=
=A0</div><div>Conceptually this is closer to the pre-LUCENE-6350 storage la=
yout. We also avoid the packTerms() cost in the constructor with this.<br><=
br>We additionally keep the term bytes in a single contiguous byte[] (lengt=
h-prefixed VInts, BytesRef[] entries are zero-copy views into it), and have=
 equals/hashCode operate solely on that byte[].</div><div>That is how the p=
re-6350 implementation got its fast equals as well. BytesRef[] is still red=
undant, but did not want to mess around with the interfacing types too much=
 and seemed okay.<br><br>## Results<br>JMH microbenchmarks against Lucene&#=
39;s TermInSetQuery (Query construction + IndexSearcher.count(query)), on a=
n in-memory index with the query cache disabled.<br>We try a few different =
N terms in the TermInSetQuery, with each term being a random 16 char hex. <=
br>For the benchmark, the index contains 50 segments and we vary what terms=
 are indexed in each segment too as follows.=C2=A0</div><div>Each indexed t=
erm is also a 16 char hex, and we index 1 doc for each term that we chose t=
o have indexed. Reported as speedup =3D TermInSetQuery time / our impl time=
; &gt;1 means our impl is faster.<br><br><font face=3D"monospace">=C2=A0 In=
dex content=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0| N =3D 300 | N =3D 3k |=C2=A0=
 N =3D 30k=C2=A0<br>=C2=A0 each segment has exactly the same terms in the r=
andom query=C2=A0 =C2=A0 =C2=A0| 1.30x=C2=A0 =C2=A0| 1.31x=C2=A0 | =C2=A01.=
22x<br>=C2=A0 Only 2 of N query terms in each segment, most seeks miss=C2=
=A0 =C2=A0 =C2=A0 =C2=A0 | 2.11x=C2=A0 =C2=A0| 3.41x=C2=A0 | =C2=A03.74x<br=
>=C2=A0 50k random (independent of the query) terms in each segment =C2=A0 =
=C2=A0 | 1.05x=C2=A0 =C2=A0| 1.15x=C2=A0 | =C2=A01.32x</font><br><br>In pro=
duction (opensearch indexes with multiple shards per index), where this Ter=
mInSetQuery is only a subquery of our typical query,=C2=A0</div><div>we saw=
 the overall mean latency decrease by ~22% with this change when the number=
 of terms in TermInSetQuery &gt; 30K. (Decreased by ~2% for queries with nu=
mber of terms between 1k to 5k).<br><br>## What I&#39;d like to ask</div><d=
iv>Is this pattern of queries considered atypical and not worth the CPU at =
the cost of memory? Is this also a guiding principle in other parts of luce=
ne?</div><div>Or is there a quantified typical values for CPU-memory tradeo=
ff? Asking out of curiousity whether we should be tweaking more stuff simil=
arly, internally, for our CPU-bound workloads.<br><br>Happy to put a PR up =
with the JMH benchmark/the impl we tried if that&#39;s of interest.</div><d=
iv><br></div><div>Thanks,</div><div>Govind Balaji S<br><br></div></div></di=
v></div>
</blockquote></div></div>

--000000000000996af706515080d5--