You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by GitBox <gi...@apache.org> on 2022/11/10 08:54:41 UTC
[GitHub] [lucene] jpountz opened a new issue, #11915: Make Lucene smarter about long runs of matches
jpountz opened a new issue, #11915:
URL: https://github.com/apache/lucene/issues/11915
### Description
Lucene's abstractions are good at dealing with long runs of documents that do not match a query, but much less at dealing with long runs of documents that match a query. In such cases, Lucene still needs to linearly scan these matches and do some amount of work for each of the matches.
Is it actually common to have long runs of matches? For full-text indexes, maybe not so much, only stop words may have runs of adjacent matches. For string fields, this may happen if the field has a default value that is the value of most documents in the collection. Also it's possible for users to use index sorting in order to cluster similar documents together, which increases the likelihood to have long runs of adjacent matches.
One idea would be to augment the `DocIdSetIterator` API to add a new `peekNextNonMatchingDocID` method, which would return the next doc ID that may not be a match. The default implementation could return `docID() + 1`. We'd need to implement this API in postings, doc-value iterators and a few other important `DocIdSetIterators` like `BitSetIterator` and `DocIdSetIterator#all`. And propagate this information in disjunctions and conjunctions. Then we could leverage this API in a number of places:
- `ReqExclScorer` could ask the prohibited clause for the next doc ID that is worth evaluating on the required clause.
- Conjunctions could ignore non-scoring clauses over ranges of doc IDs that all match.
- `FixedBitSet#or` could set ranges of doc IDs at once, which would in-turn speed up `DocIdSetBuilder`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Make Lucene smarter about long runs of matches [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz closed issue #11915: Make Lucene smarter about long runs of matches
URL: https://github.com/apache/lucene/issues/11915
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] zacharymorn commented on issue #11915: Make Lucene smarter about long runs of matches
Posted by "zacharymorn (via GitHub)" <gi...@apache.org>.
zacharymorn commented on issue #11915:
URL: https://github.com/apache/lucene/issues/11915#issuecomment-1426607516
This is an interesting idea @jpountz ! From my understanding of your description, this new API may need to provide these two guarantees:
1. It returns the next doc ID that may not be a match, so the returned doc ID requires further check to confirm if it's actually a match or not (I'm guessing this from the propose default implementation of the API to return `docID() + 1` )
2. `peekNextNonMatchingDocID() - 1` is guaranteed to not be a match.
But I'm wondering if it will be better for the API to just return the next, furthest out doc ID that we know is not going to be a match?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] zacharymorn commented on issue #11915: Make Lucene smarter about long runs of matches
Posted by "zacharymorn (via GitHub)" <gi...@apache.org>.
zacharymorn commented on issue #11915:
URL: https://github.com/apache/lucene/issues/11915#issuecomment-1459261207
Thanks @jpountz for the clarification! I was under a different assumption / understanding earlier actually, hence the additional questions. Your comment makes sense to me.
I just published a draft PR https://github.com/apache/lucene/pull/12194 with some initial (potentially buggy) implementations, primarily focusing on adding the new API to DISI, implementing it in a few DISI subclasses, and using it in `ReqExclScorer`. So far this implementation seems to have around -10% impact to benchmark boolean negation queries such as `OrHighNotHigh`, but I feel that's expected since those test query clauses do not necessarily provide long running matches. Could you please take a look and let me know if if's heading to the right direction?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] jpountz commented on issue #11915: Make Lucene smarter about long runs of matches
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on issue #11915:
URL: https://github.com/apache/lucene/issues/11915#issuecomment-1433171306
Thanks for looking!
> peekNextNonMatchingDocID() - 1 is guaranteed to not be a match.
`peekNextNonMatchingDocID() - 1` would either be the current doc ID, or a match. (did you make a typo when writing that it's guaranteed *not* to be a match?)
> But I'm wondering if it will be better for the API to just return the next, furthest out doc ID that we know is not going to be a match?
Ideally our queries that can compute this information cheaply would do this. I wanted to make it an optional API so that all queries like doc-values-based queries wouldn't have to linearly scan until they find a non-match, which could often be more costly than asking other clauses to advance.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] zacharymorn commented on issue #11915: Make Lucene smarter about long runs of matches
Posted by "zacharymorn (via GitHub)" <gi...@apache.org>.
zacharymorn commented on issue #11915:
URL: https://github.com/apache/lucene/issues/11915#issuecomment-1459711628
Yes please go ahead @mdmarshmallow !
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] zacharymorn commented on issue #11915: Make Lucene smarter about long runs of matches
Posted by "zacharymorn (via GitHub)" <gi...@apache.org>.
zacharymorn commented on issue #11915:
URL: https://github.com/apache/lucene/issues/11915#issuecomment-1459282541
Oh hi @mdmarshmallow , thanks for looking into this issue as well!
I actually worked on it a bit in the last few days and just published a draft PR for it, but the PR is potentially buggy and does not cover some areas like ConjunctionScorers and `FixedBitSet#or` that @jpountz mentioned. Also, from my experimentation and benchmarking, it appears that we may need to add some additional benchmarking tasks for this as well. Maybe we could collaborate on this issue? On the other hand, I'm typically slow, so please feel free to take over if you could implement this faster. :)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] mdmarshmallow commented on issue #11915: Make Lucene smarter about long runs of matches
Posted by "mdmarshmallow (via GitHub)" <gi...@apache.org>.
mdmarshmallow commented on issue #11915:
URL: https://github.com/apache/lucene/issues/11915#issuecomment-1459502217
I actually wanted to work on this cause I think the `FixedBitSet#or` optimization could be nice for my use case. I can go ahead and maybe work on that section/add it to your draft PR if you don't mind?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] mdmarshmallow commented on issue #11915: Make Lucene smarter about long runs of matches
Posted by "mdmarshmallow (via GitHub)" <gi...@apache.org>.
mdmarshmallow commented on issue #11915:
URL: https://github.com/apache/lucene/issues/11915#issuecomment-1459150300
If no one else is working on this issue, I would like to take a stab at it.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org