Re: TermInSetQuery storage: PrefixCodedTerms vs sorted BytesRef[]

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

Hi Greg,

Thanks for looking into this. PR here with the new impl + JMH benchmark:
https://github.com/apache/lucene/pull/16051. The JMH numbers are in the PR
description.

Regards,
Govind Balaji S

On Fri, May 8, 2026 at 9:30=E2=80=AFPM Greg Miller <[email protected]> wro=
te:

> 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-case=
s
> would prefer the memory efficient query representation. But that's just o=
ne
> 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]> wrote:
>
>> Hello Lucene devs,
>>
>> I'd like to surface a benchmark observation about TermInSetQuery's choic=
e
>> 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, an=
d
>> 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 ~9=
0%
>> 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 a=
s
>> 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 b=
y
>> random access into a BytesRef[] instead of a streaming TermIterator.
>> Conceptually this is closer to the pre-LUCENE-6350 storage layout. We
>> also 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
>> being 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 ter=
m
>> that we chose to have indexed. Reported as speedup =3D TermInSetQuery ti=
me /
>> 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
>> the number of terms in TermInSetQuery > 30K. (Decreased by ~2% for queri=
es
>> with 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
>> of interest.
>>
>> Thanks,
>> Govind Balaji S
>>
>>

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

<div dir=3D"ltr">Hi Greg,<br><div><br></div><div>Thanks for looking into th=
is. PR here with the new impl=C2=A0+ JMH benchmark:=C2=A0<a href=3D"https:/=
/github.com/apache/lucene/pull/16051">https://github.com/apache/lucene/pull=
/16051</a>. The JMH numbers are in the PR description.</div><div><br></div>=
<div>Regards,</div><div>Govind Balaji S</div></div><br><div class=3D"gmail_=
quote gmail_quote_container"><div dir=3D"ltr" class=3D"gmail_attr">On Fri, =
May 8, 2026 at 9:30=E2=80=AFPM Greg Miller &lt;<a href=3D"mailto:gsmiller@g=
mail.com">[email protected]</a>&gt; wrote:<br></div><blockquote class=3D"g=
mail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204=
,204,204);padding-left:1ex"><div dir=3D"ltr"><div dir=3D"ltr">Thanks for sh=
aring this work Govind. This is interesting stuff!</div><div dir=3D"ltr"><b=
r></div><div>My brief 2 cents: I suspect it&#39;s a somewhat atypical patte=
rn 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 majorit=
y 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 b=
e great to publish your benchmarking in a PR! Let&#39;s capture this testin=
g and have a discussion. Even if the community decides to stay with the cur=
rent approach, you might want to consider adding your version of this query=
 in the sandbox module. That could provide a nice, community-supported opti=
on for a more CPU efficient version of this query that users could opt into=
.</div><div><br></div><div>Cheers,</div><div>-Greg</div><br><div class=3D"g=
mail_quote"><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]=
.org" target=3D"_blank">[email protected]</a>&gt; wrote:<br></div><bloc=
kquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:=
1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr">Hello Lucene =
devs,<br><br>I&#39;d like to surface a benchmark observation about TermInSe=
tQuery&#39;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 numb=
er of terms, and the reasoning behind.<div><div><br>## Background<br>Before=
 LUCENE-6350 (May 2015), TermsQuery (the predecessor of TermInSetQuery) sto=
red its terms as a sorted byte[] with a parallel int[] of offsets, plus a c=
ached int hashCode.=C2=A0<div>LUCENE-6350 replaced this shape with PrefixCo=
dedTerms. The rationale recorded in the issue was &quot;This will save ram =
and cleanup a lot of the code.&quot;<br><br>## The workload where this show=
s up<br>=C2=A0 - We run TermInSetQuery with a tens of thousands terms per q=
uery.<br>=C2=A0 - The LRUQueryCache skips caching the query on most segment=
s because they are below its per-leaf size threshold. In our workloads, thi=
s is ~90% of segments (cumulatively a small fraction of docs). <br>=C2=A0 =
=C2=A0 On those segments the query pays its full per-segment cost of unpack=
ing and iterating the same prefix coded terms on every request.</div><div>=
=C2=A0 - Our workloads are CPU-bound than memory-bound.<br><br>In this setu=
p, the work that is independent of segment size becomes the dominant CPU co=
st of the query on all those many small segments.=C2=A0</div><div>PrefixCod=
edTerms.TermIterator.next loading delta-encoded bytes show up as hot in pro=
files.<br><br>## What we tried<br>A reimplementation of TermInSetQuery whos=
e only change is the storage shape of the term list.</div><div>Same Filtere=
dTermsEnum ping-pong (accept / nextSeekTerm) - just driven by random access=
 into a BytesRef[] instead of a streaming TermIterator.=C2=A0</div><div>Con=
ceptually this is closer to the pre-LUCENE-6350 storage layout. We also avo=
id the packTerms() cost in the constructor with this.<br><br>We additionall=
y 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[].</div><div>That is how the pre-6350 implement=
ation got its fast equals as well. BytesRef[] is still redundant, but did n=
ot want to mess around with the interfacing types too much and seemed okay.=
<br><br>## Results<br>JMH microbenchmarks against Lucene&#39;s TermInSetQue=
ry (Query construction + IndexSearcher.count(query)), on an in-memory index=
 with the query cache disabled.<br>We try a few different N terms in the Te=
rmInSetQuery, with each term being a random 16 char hex. <br>For the benchm=
ark, the index contains 50 segments and we vary what terms are indexed in e=
ach segment too as follows.=C2=A0</div><div>Each indexed term is also a 16 =
char hex, and we index 1 doc for each term that we chose to have indexed. R=
eported as speedup =3D TermInSetQuery time / our impl time; &gt;1 means our=
 impl is faster.<br><br><font face=3D"monospace">=C2=A0 Index 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<b=
r>=C2=A0 each segment has exactly the same terms in the random 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 production (opensear=
ch indexes with multiple shards per index), where this TermInSetQuery is on=
ly 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 Term=
InSetQuery &gt; 30K. (Decreased by ~2% for queries with number of terms bet=
ween 1k to 5k).<br><br>## What I&#39;d like to ask</div><div>Is this patter=
n of queries considered atypical and not worth the CPU at the cost of memor=
y? Is this also a guiding principle in other parts of lucene?</div><div>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.<br><br>Happy to put a PR up with the JMH benc=
hmark/the impl we tried if that&#39;s of interest.</div><div><br></div><div=
>Thanks,</div><div>Govind Balaji S<br><br></div></div></div></div>
</blockquote></div></div>
</blockquote></div>

--000000000000839f7006519bd5d4--