TermInSetQuery storage: PrefixCodedTerms vs sorted BytesRef[]

--00000000000062b66f0651379d06
Content-Type: text/plain; charset="UTF-8"

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 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 term
that we chose to have indexed. Reported as speedup = TermInSetQuery time /
our impl time; >1 means our impl is faster.

  Index content                                                   | N = 300
| N = 3k |  N = 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 queries 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

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

<div dir=3D"ltr">Hello Lucene devs,<br><br>I&#39;d like to surface a benchm=
ark observation about TermInSetQuery&#39;s choice of PrefixCodedTerms as th=
e 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.<div><d=
iv><br>## Background<br>Before LUCENE-6350 (May 2015), TermsQuery (the pred=
ecessor of TermInSetQuery) stored its terms as a sorted byte[] with a paral=
lel int[] of offsets, plus a cached int hashCode.=C2=A0<div>LUCENE-6350 rep=
laced 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 workload where this shows up<br>=C2=A0 - We run TermInSetQuery with a=
 tens of thousands terms per query.<br>=C2=A0 - The LRUQueryCache skips cac=
hing the query on most segments because they are below its per-leaf size th=
reshold. In our workloads, this is ~90% of segments (cumulatively a small f=
raction of docs). <br>=C2=A0 =C2=A0 On those segments the query pays its fu=
ll per-segment cost of unpacking and iterating the same prefix coded terms =
on every request.</div><div>=C2=A0 - Our workloads are CPU-bound than memor=
y-bound.<br><br>In this setup, the work that is independent of segment size=
 becomes the dominant CPU cost of the query on all those many small segment=
s.=C2=A0</div><div>PrefixCodedTerms.TermIterator.next loading delta-encoded=
 bytes show up as hot in profiles.<br><br>## What we tried<br>A reimplement=
ation of TermInSetQuery 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 TermI=
terator.=C2=A0</div><div>Conceptually this is closer to the pre-LUCENE-6350=
 storage layout. We also avoid the packTerms() cost in the constructor with=
 this.<br><br>We additionally keep the term bytes in a single contiguous by=
te[] (length-prefixed VInts, BytesRef[] entries are zero-copy views into it=
), and have equals/hashCode operate solely on that byte[].</div><div>That i=
s how the pre-6350 implementation got its fast equals as well. BytesRef[] i=
s still redundant, but did not want to mess around with the interfacing typ=
es too much and seemed okay.<br><br>## Results<br>JMH microbenchmarks again=
st Lucene&#39;s TermInSetQuery (Query construction + IndexSearcher.count(qu=
ery)), on an 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>Eac=
h 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 time / ou=
r 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<br>=C2=A0 each segment has exactly the same term=
s 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=A0=
3.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><b=
r>In production (opensearch indexes with multiple shards per index), where =
this TermInSetQuery is only a subquery of our typical query,=C2=A0</div><di=
v>we saw the overall mean latency decrease by ~22% with this change when th=
e number of terms in TermInSetQuery &gt; 30K. (Decreased by ~2% for queries=
 with number of terms between 1k to 5k).<br><br>## What I&#39;d like to ask=
</div><div>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?</div><div>Or is there a quantified typical values for CPU-memor=
y tradeoff? Asking out of curiousity whether we should be tweaking more stu=
ff similarly, 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><div><br></div><div>Thanks,</div><div>Govind Balaji S<br><br></div></=
div></div></div>

--00000000000062b66f0651379d06--