Hey Michael,
You are right, iterating all deletes with nextClearBit() would
run in O(maxDoc). I am coming from the other direction, where I'm
expecting the number of deletes to be more in the order of 1%-5%
of the doc ID space, so a separate int[] would use lots of heap
and probably not help that much compared with nextClearBit(). My
mental model is that the two most common use-cases are
append-only workloads, where there are no deletes at all, and
update workloads, which would commonly have several percents of
deleted docs. It's not clear to me how common it is to have very
few deletes.
On Tue, Feb 6, 2024 at 7:03 AM Michael Froh <msf...@gmail.com> wrote:
Thanks Adrien!
My thinking with a separate iterator was that nextClearBit()
is relatively expensive (O(maxDoc) to traverse everything, I
think). The solution I was imagining would involve an
index-time change to output, say, an int[] of deleted docIDs
if the number is sufficiently small (like maybe less than
1000). Then the livedocs interface could optionally return a
cheap deleted docs iterator (i.e. only if the number of
deleted docs is less than the threshold). Technically, the
cost would be O(1), since we set a constant bound on the
effort and fail otherwise. :)
I think 1000 doc value lookups would be cheap, but I don't
know if the guarantee is cheap enough to make it into
Weight#count.
That said, I'm going to see if iterating with nextClearBit()
is sufficiently cheap. Hmm... precomputing that int[] for
deleted docIDs on refresh could be an option too.
Thanks again,
Froh
On Fri, Feb 2, 2024 at 11:38 PM Adrien Grand
<jpou...@gmail.com> wrote:
Hi Michael,
Indeed, only MatchAllDocsQuery knows how to produce a
count when there are deletes.
Your idea sounds good to me, do you actually need a side
car iterator for deletes, or could you use a
nextClearBit() operation on the bit set?
I don't think we can fold it into Weight#count since
there is an expectation that it is negligible compared
with the cost of a naive count, but we may be able to do
it in IndexSearcher#count or on the OpenSearch side.
Le ven. 2 févr. 2024, 23:50, Michael Froh
<msf...@gmail.com> a écrit :
Hi,
On OpenSearch, we've been taking advantage of the
various O(1) Weight#count() implementations to
quickly compute various aggregations without needing
to iterate over all the matching documents (at least
when the top-level query is functionally a match-all
at the segment level). Of course, from what I've
seen, every clever Weight#count()
implementation falls apart (returns -1) in the face
of deletes.
I was thinking that we could still handle small
numbers of deletes efficiently if only we could get a
DocIdSetIterator for deleted docs.
Like suppose you're doing a date histogram
aggregation, you could get the counts for each bucket
from the points tree (ignoring deletes), then iterate
through the deleted docs and decrement their
contribution from the relevant bucket (determined
based on a docvalues lookup). Assuming the number of
deleted docs is small, it should be cheap, right?
The current LiveDocs implementation is just a
FixedBitSet, so AFAIK it's not great for iteration.
I'm imagining adding a supplementary "deleted docs
iterator" that could sit next to the FixedBitSet if
and only if the number of deletes is "small". Is
there a better way that I should be thinking about this?
Thanks,
Froh
--
Adrien
