You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "javanna (via GitHub)" <gi...@apache.org> on 2024/09/09 18:27:52 UTC
[I] Stop duplicate per-segment work across segment partitions [lucene]
javanna opened a new issue, #13745:
URL: https://github.com/apache/lucene/issues/13745
With the introduction of intra-segment concurrency support (see #13542), the `IndexSearcher` is able to parallelize search across partitions of segments. Some of our queries, like `PointRangeQuery`, perform per-segment computation ahead of time, that is currently not shared across segment partitions, but rather duplicated. This makes intra-segment concurrency not appealing for those queries, which we should look at addressing. If we can share such computation across segment partitions, we can likely enable intra-segment slicing by default and ensure that intra-segment concurrency is beneficial for all queries.
--
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] Stop duplicating per-segment work across segment partitions [lucene]
Posted by "scampi (via GitHub)" <gi...@apache.org>.
scampi commented on issue #13745:
URL: https://github.com/apache/lucene/issues/13745#issuecomment-3303389628
Jumping in as this interests me, sorry if I get some points wrong!
It seems that `PointInSetIncludingScoreQuery` creates also a bitset from the scan of `PointValues` in `createWeight`.
https://github.com/apache/lucene/blob/085a0ae054b1df9623afce47e28b65c52184ce48/lucene/join/src/java/org/apache/lucene/search/join/PointInSetIncludingScoreQuery.java#L203-L205
Several queries like `LatLonPointDistanceQuery` also access `PointValues` but do not create upfront a bitset (as far as I can tell).
https://github.com/apache/lucene/blob/085a0ae054b1df9623afce47e28b65c52184ce48/lucene/core/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java#L138-L139
However, it looks like a bitset for the whole segment is computed nonetheless.
https://github.com/apache/lucene/blob/085a0ae054b1df9623afce47e28b65c52184ce48/lucene/core/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java#L153-L156
--
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
Re: [I] Stop duplicating per-segment work across segment partitions [lucene]
Posted by "expani (via GitHub)" <gi...@apache.org>.
expani commented on issue #13745:
URL: https://github.com/apache/lucene/issues/13745#issuecomment-3060066462
Will go over all types of queries to check ( other than PointRangeQuery ) that needs special handling by sharing the docId space unless someone has already covered 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
Re: [I] Stop duplicating per-segment work across segment partitions [lucene]
Posted by "javanna (via GitHub)" <gi...@apache.org>.
javanna commented on issue #13745:
URL: https://github.com/apache/lucene/issues/13745#issuecomment-2682478759
This is a heads up that I started working on this. My focus is currently on `PointRangeQuery`. The overall goal is to share the bitset computation across scorer suppliers for the same leaf context. We would still create one scorer supplier per segment partition, and a new doc id set iterator, but all the rest would be shared across different partitions of the same segment.
Focusing on a single query is quite a simplification, which allows me to better understand the problem I am trying to solve. I do wonder how many other queries need this kind of treatment. I know there have been talks in the past about cloning scorers and such, but I wonder if that can be avoided by adapting the queries / weight impls that require attention instead.
Could anyone help me come up with a list of queries that need to be modified to de-duplicate per-segment work in order to optimize their support for intra-segment concurrency? Do we actually need a very generic approach for this problem, or is it reasonable to go case by case perhaps?
--
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
Re: [I] Stop duplicating per-segment work across segment partitions [lucene]
Posted by "prudhvigodithi (via GitHub)" <gi...@apache.org>.
prudhvigodithi commented on issue #13745:
URL: https://github.com/apache/lucene/issues/13745#issuecomment-3680554964
> Also correct me if I'm wrong, but I believe we may be duplicating allocations in `TopFieldCollectorManager` as we allocate a queue of size `numHits` for every collector, but we may be calling a collector multiple times on the same segment right?
> https://github.com/apache/lucene/blob/branch_10_2/lucene/core/src/java/org/apache/lucene/search/TopFieldCollectorManager.java#L137-L173. Specifically through `FieldValueHitQueue#create` which mentions "NOTE: The instances returned by this method pre-allocate a full array of length numHits."
I went through the `TotalHitCountCollectorManager` which uses putIfAbsent in intra-segment mode (https://github.com/apache/lucene/pull/13542) which says it’s already been done and skip or reuse the cached result since its pure count. But for `TopFieldCollectorManager` the only duplication is memory (for example with 4 partitions 4 queues instead of 1) which is the necessary cost for lock free parallelism. Each partition independently finds its local top-K then reduce() should merges them, IMO the latency improvement from parallelism could outweigh the memory cost, let me conclude this with some tests on my local.
--
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
Re: [I] Stop duplicating per-segment work across segment partitions [lucene]
Posted by "prudhvigodithi (via GitHub)" <gi...@apache.org>.
prudhvigodithi commented on issue #13745:
URL: https://github.com/apache/lucene/issues/13745#issuecomment-3683310820
> let me conclude this with some tests on my local.
From my local tests using Lucene benchmark-jmh I can see the `TopFieldCollectorManager` performed well with intra segment.
```
Benchmark (numDocs) (numHits) Mode Cnt Score Error Units
TopFieldCollectorBenchmark.noIntraSegment 1000000 100 avgt 20 3870.629 ± 102.246 us/op
TopFieldCollectorBenchmark.noIntraSegment 1000000 1000 avgt 20 4838.287 ± 535.474 us/op
TopFieldCollectorBenchmark.withIntraSegment 1000000 100 avgt 20 1552.220 ± 25.915 us/op
TopFieldCollectorBenchmark.withIntraSegment 1000000 1000 avgt 20 1885.688 ± 33.323 us/op
Benchmark (numDocs) (numHits) Mode Cnt Score Error Units
TopFieldCollectorBenchmark.noIntraSegment 1000000 100 thrpt 20 249.435 ± 13.173 ops/s
TopFieldCollectorBenchmark.noIntraSegment 1000000 1000 thrpt 20 208.132 ± 22.701 ops/s
TopFieldCollectorBenchmark.withIntraSegment 1000000 100 thrpt 20 674.382 ± 29.088 ops/s
TopFieldCollectorBenchmark.withIntraSegment 1000000 1000 thrpt 20 477.343 ± 39.071 ops/s
```
--
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
Re: [I] Stop duplicating per-segment work across segment partitions [lucene]
Posted by "javanna (via GitHub)" <gi...@apache.org>.
javanna commented on issue #13745:
URL: https://github.com/apache/lucene/issues/13745#issuecomment-3062037144
For reference, this is the ahead of time work that currently gets duplicated in PointRangeQuery across partitions of the same segments: https://github.com/apache/lucene/blob/main/lucene/core/src/java/org/apache/lucene/search/PointRangeQuery.java#L313 . We create a bitset of the size of the entire segment. We should look into doing this once per segment and reusing it across partitions of the same segment instead.
Something similar happens in `PointInSetQuery` too, when pulling the scorer from the scorer supplier.
--
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
Re: [I] Stop duplicating per-segment work across segment partitions [lucene]
Posted by "javanna (via GitHub)" <gi...@apache.org>.
javanna commented on issue #13745:
URL: https://github.com/apache/lucene/issues/13745#issuecomment-2699189350
> HNSW vector search heavy lifting is done in rewrite, so out of scope for this, right?
I believe so, mostly because query rewrite does not parallelize on slices, but across segments directly. See #13952 .
> Maybe multi-term queries would need to do some work. What about join queries? TermInSet query?
Yep, TermInSet was on my radar. The others you mentioned, I will take a look at. Thanks!
--
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
Re: [I] Stop duplicating per-segment work across segment partitions [lucene]
Posted by "expani (via GitHub)" <gi...@apache.org>.
expani commented on issue #13745:
URL: https://github.com/apache/lucene/issues/13745#issuecomment-3058268142
I was looking to integrate Intra Segment Concurrent Search and found that this same problem also applies to downstream consumers of Lucene like OpenSearch/ElasticSearch/Solr who use Collectors to build out their Aggregation framework.
Since, we have to make a Query/Collector aware that they are participating in an Intra Segment Concurrent Search via Constructor like the [initial PR did for TotalHitCountCollectorManager ](https://github.com/apache/lucene/blob/main/lucene/core/src/java/org/apache/lucene/search/TotalHitCountCollectorManager.java#L48-L62) the changes required would increase unless we go case by case basis.
Recording the call flow for my own understanding
```
IndexSearcher#search(Query query, CollectorManager<C, T> collectorManager)
--- calls ---
IndexSearcher#search(Weight weight, CollectorManager<C, T> collectorManager, C firstCollector)
--- calls from a Runnable per Slice ---
IndexSearcher#search(LeafReaderContextPartition[] partitions, Weight weight, Collector collector)
--- calls ---
IndexSearcher#searchLeaf(LeafReaderContext ctx, int minDocId, int maxDocId, Weight weight, Collector collector)
```
Two threads can invoke `searchLeaf` with the same LeafReaderContext but for different partitions of the segment.
Things inside `searchLeaf` that need to be done only once even during intra segment concurrent search
```
Collector#getLeafCollector()
Weight#scorerSupplier()
ScorerSupplier#bulkScorer()
LeafReaderContext#reader()#getLiveDocs()
LeafCollector#finish()
```
Other downstream users do some extra operations when profiling the queries.
My proposal is to handle the de-duplication at the IndexSearcher and ensure the above listed steps are only done once per LeafSlice.
@javanna I would like to pick this up unless you are almost done with PointRangeQuery.
--
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
Re: [I] Stop duplicating per-segment work across segment partitions [lucene]
Posted by "smuching202 (via GitHub)" <gi...@apache.org>.
smuching202 commented on issue #13745:
URL: https://github.com/apache/lucene/issues/13745#issuecomment-3363606550
Also correct me if I'm wrong, but I believe we may be duplicating allocations in `TopFieldCollectorManager` as we allocate a queue of size `numHits` for every collector, but we may be calling a collector multiple times on the same segment right?
https://github.com/apache/lucene/blob/branch_10_2/lucene/core/src/java/org/apache/lucene/search/TopFieldCollectorManager.java#L137-L173
--
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
Re: [I] Stop duplicating per-segment work across segment partitions [lucene]
Posted by "javanna (via GitHub)" <gi...@apache.org>.
javanna commented on issue #13745:
URL: https://github.com/apache/lucene/issues/13745#issuecomment-2838255713
> Does using intra-segment partitioning negatively impact these queries (TermInSet/MultiTerm) or is there still some benefit from using the feature?
I guess it depends on data and query, but it may be that the per-segment computation is heavier than running the query, hence duplicating it would make the query overall slower even if executed across multiple threads.
--
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
Re: [I] Stop duplicating per-segment work across segment partitions [lucene]
Posted by "smuching202 (via GitHub)" <gi...@apache.org>.
smuching202 commented on issue #13745:
URL: https://github.com/apache/lucene/issues/13745#issuecomment-3272662016
Hi @javanna, is there a known list of the queries that have duplicated per-segment computation?
I reviewed the benchmarks you ran in PR [#13542](https://github.com/apache/lucene/pull/13542#issuecomment-2332114836) with intra-segment parallelism enabled. Based off those results, it looks like these queries showed regressions:
- `CommonTermsQuery` (i.e. HighTerm)
- `TermQuery` (i.e. CountTerm)
- `BooleanQuery` (i.e. OrHighLow)
- `PrefixQuery` (i.e. Prefix3)
- `WildcardQuery` (i.e. Wildcard)
- `FuzzyQuery` (i.e. Fuzzy1)
- `MatchAllDocsQuery` (i.e. BrowseDateSSDVFacets)
Granted, it's possible that the regressions stem from underlying issues rather than the top-level query itself. For example:
- The regression in `OrHighLow` might be due to problems in `CommonTermsQuery`
- `PrefixQuery`, `WildCardQuery`, and `FuzzyQuery` all rely on `MultiTermQuery`, so the root cause could be from `MultiTermQuery#CONSTANT_SCORE_BLENDED_REWRITE` (see https://github.com/apache/lucene/blob/main/lucene/core/src/java/org/apache/lucene/search/MultiTermQueryConstantScoreBlendedWrapper.java#L60)
Does this generally align with your findings so far?
--
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
Re: [I] Stop duplicating per-segment work across segment partitions [lucene]
Posted by "Shibi-bala (via GitHub)" <gi...@apache.org>.
Shibi-bala commented on issue #13745:
URL: https://github.com/apache/lucene/issues/13745#issuecomment-2822481473
@javanna not sure about the underlying implementation of these queries. Does using intra-segment partitioning negatively impact these queries (TermInSet/MultiTerm) or is there still some benefit from using the feature?
--
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
Re: [I] Stop duplicating per-segment work across segment partitions [lucene]
Posted by "msokolov (via GitHub)" <gi...@apache.org>.
msokolov commented on issue #13745:
URL: https://github.com/apache/lucene/issues/13745#issuecomment-2698550635
HNSW vector search heavy lifting is done in `rewrite`, so out of scope for this, right? Maybe multi-term queries would need to do some work. What about join queries? TermInSet query?
--
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
Re: [I] Stop duplicating per-segment work across segment partitions [lucene]
Posted by "javanna (via GitHub)" <gi...@apache.org>.
javanna commented on issue #13745:
URL: https://github.com/apache/lucene/issues/13745#issuecomment-3291991178
@smuching202 the two I remember clearly about are `PointRangeQuery` and `PointInSetQuery`. These build a bitset ahead of time of the size of the entire segments. There may be others but I'd need to look closely at the code. It feels like once we solved one we have a solution for all potentially.
--
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