You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "jpountz (via GitHub)" <gi...@apache.org> on 2023/07/05 11:49:09 UTC
[GitHub] [lucene] jpountz opened a new pull request, #12415: Optimize disjunction counts.
jpountz opened a new pull request, #12415:
URL: https://github.com/apache/lucene/pull/12415
This introduces `LeafCollector#collect(DocIdStream)` to enable collectors to collect batches of doc IDs at once. `BooleanScorer` takes advantage of this by creating a `DocIdStream` whose `count()` method counts the number of bits that are set in the bit set of matches in the current window, instead of naively iterating over all matches.
On wikimedium10m, this yields a ~20% speedup when counting hits for the `title OR 12` query (2.9M hits).
Relates #12358
--
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] mikemccand commented on pull request #12415: Optimize disjunction counts.
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on PR #12415:
URL: https://github.com/apache/lucene/pull/12415#issuecomment-1657104392
> It might help to have a `nextClearBit` on `Bits` to be able to still apply this optimization. E.g. `MatchAllDocsQuery` could use `Bits#nextClearBit` on live docs to create a `DocIdStream` for every sequence of adjacent non-deleted doc IDs to speed up counting under sparse deletions.
+1, this is a neat idea! Often deletes are sparse (apps try hard to merge them away) ... at Amazon product search we have insanely aggressively asked `TieredMP` to merge away deletions now, at tremendous increase of indexing cost and wee bit faster searching, the right tradeoff when using NRT segment replication to efficiently/incrementally index once and distribute the copy to many replicas for searching. Maybe open a follow-on issue for this?
--
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 pull request #12415: Optimize disjunction counts.
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #12415:
URL: https://github.com/apache/lucene/pull/12415#issuecomment-1666224165
After merging a subset of this PR in #12475, there remains a ~25% speedup when counting hits on `title OR 12` (same query as mentioned earlier).
--
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 a diff in pull request #12415: Optimize disjunction counts.
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #12415:
URL: https://github.com/apache/lucene/pull/12415#discussion_r1276556323
##########
lucene/core/src/java/org/apache/lucene/search/CheckedIntConsumer.java:
##########
@@ -0,0 +1,31 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.search;
+
+import java.util.function.IntConsumer;
+
+/** Like {@link IntConsumer}, but may throw checked exceptions. */
+@FunctionalInterface
+public interface CheckedIntConsumer<T extends Exception> {
Review Comment:
It's viral!
--
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 pull request #12415: Optimize disjunction counts.
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #12415:
URL: https://github.com/apache/lucene/pull/12415#issuecomment-1654029579
> I'd love to start benchmarking charts for these before we land this opto so we can fully appreciate / document the "pop"
+1 I'll wait for a few data point before merging
> I wonder what other queries could (later) benefit from DocIdStream bulk collection ...
I tried to think about this too.
`MatchAllDocsQuery` is an obvious candidate, but it's already optimized differently using `Weight#count`. It's probably still a good idea to implement this API on `MatchAllDocsQuery` so that it would help pure negations (a `MatchAllDocsQuery` in a MUST/FILTER/SHOULD clause, and one or more MUST_NOT clauses), as this will trigger usage of `ReqExclBulkScorer` which will delegate to the `MatchAllDocsQuery` `BulkScorer`.
Queries that produce bitsets could also implement a similar optimization, e.g. (numeric) `range`, `prefix`, `wildcard` or `geo` queries. I expect the cost of building the bitset to dominate the overall execution time, but it will probably still yield a noticeable speedup. A question I'm wondering there is whether we should pass the entire BitSet as a single `DocIdStream` or if there are reasons why we should split it anyway.
Term queries could theoretically return a DocIdStream per block of 128 doc IDs, where decoding would happen lazily at the beginning of `DocIdStream#forEach` and `DocIdStream#count` would return 128 without even decoding postings. This would require more intimate integration with the codec as we don't have the right APIs to do this at the moment.
And like you already suggested, we could handle some conjunctions if we ran them through BS1.
In general, deletions will tend to disable this optimization. (BS1 is a notable case when deletions would not disable this optimization) It might help to have a `nextClearBit` on `Bits` to be able to still apply this optimization. E.g. `MatchAllDocsQuery` could use `Bits#nextClearBit` on live docs to create a `DocIdStream` for every sequence of adjacent non-deleted doc IDs to speed up counting under sparse deletions.
--
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 a diff in pull request #12415: Optimize disjunction counts.
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #12415:
URL: https://github.com/apache/lucene/pull/12415#discussion_r1278368477
##########
lucene/core/src/java/org/apache/lucene/search/CheckedIntConsumer.java:
##########
@@ -0,0 +1,31 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.search;
+
+import java.util.function.IntConsumer;
+
+/** Like {@link IntConsumer}, but may throw checked exceptions. */
+@FunctionalInterface
+public interface CheckedIntConsumer<T extends Exception> {
Review Comment:
I would like `LeafCollector#collect` to be a valid method reference that implements this functional interface, and I don't want to change the signature of `LeafCollector#collect`. If we remove the exception here, it would force the default implementation of `LeafCollector#collect(DocIdStream)` to change from this:
```java
default void collect(DocIdStream stream) throws IOException {
stream.forEach(this::collect);
}
```
to that
```java
default void collect(DocIdStream stream) throws IOException {
stream.forEach(doc -> {
try {
collect(doc);
} catch (IOException e) {
throw new UncheckedIOException(e);
}
});
}
```
which I like less than introducing this functional interface.
--
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 a diff in pull request #12415: Optimize disjunction counts.
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #12415:
URL: https://github.com/apache/lucene/pull/12415#discussion_r1276544244
##########
lucene/core/src/java/org/apache/lucene/search/BooleanScorer.java:
##########
@@ -109,7 +109,9 @@ public BulkScorerAndDoc get(int i) {
}
}
- final Bucket[] buckets = new Bucket[SIZE];
+ // One bucket per doc ID in the window, non-null if scores are needed or if frequencies need to be
+ // counted
+ final Bucket[] buckets;
Review Comment:
It's been this way for a very (very very very) long time, but I agree it would probably perform better with parallel arrays!
--
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 a diff in pull request #12415: Optimize disjunction counts.
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #12415:
URL: https://github.com/apache/lucene/pull/12415#discussion_r1276566623
##########
lucene/test-framework/src/java/org/apache/lucene/tests/search/QueryUtils.java:
##########
@@ -738,4 +740,66 @@ public void collect(int doc) throws IOException {
}
}
}
+
+ /**
+ * Check that counting hits through {@link DocIdStream#count()} yield the same result as counting
+ * naively.
+ */
+ public static void checkCount(Query query, final IndexSearcher searcher) throws IOException {
+ query = searcher.rewrite(query);
+ Weight weight = searcher.createWeight(query, ScoreMode.COMPLETE_NO_SCORES, 1);
+ for (LeafReaderContext context : searcher.getIndexReader().leaves()) {
+ BulkScorer scorer = weight.bulkScorer(context);
+ if (scorer == null) {
+ continue;
+ }
+ int[] expectedCount = {0};
+ boolean[] docIdStream = {false};
+ scorer.score(
+ new LeafCollector() {
+ @Override
+ public void collect(DocIdStream stream) throws IOException {
+ docIdStream[0] = true;
+ LeafCollector.super.collect(stream);
Review Comment:
Correct
--
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] msokolov commented on a diff in pull request #12415: Optimize disjunction counts.
Posted by "msokolov (via GitHub)" <gi...@apache.org>.
msokolov commented on code in PR #12415:
URL: https://github.com/apache/lucene/pull/12415#discussion_r1278450910
##########
lucene/core/src/java/org/apache/lucene/search/CheckedIntConsumer.java:
##########
@@ -0,0 +1,31 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.search;
+
+import java.util.function.IntConsumer;
+
+/** Like {@link IntConsumer}, but may throw checked exceptions. */
+@FunctionalInterface
+public interface CheckedIntConsumer<T extends Exception> {
Review Comment:
My suggestion was global search and replace throughout Lucene, only half-serious
--
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] mikemccand commented on a diff in pull request #12415: Optimize disjunction counts.
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on code in PR #12415:
URL: https://github.com/apache/lucene/pull/12415#discussion_r1278545744
##########
lucene/core/src/java/org/apache/lucene/search/BooleanScorer.java:
##########
@@ -154,19 +207,20 @@ public void collect(int doc) throws IOException {
throw new IllegalArgumentException(
"This scorer can only be used with two scorers or more, got " + scorers.size());
}
- for (int i = 0; i < buckets.length; i++) {
- buckets[i] = new Bucket();
+ if (needsScores || minShouldMatch > 1) {
Review Comment:
OK. Maybe if the `FILTER` clause is high enough cardinality, at some point BS1 becomes worth it. Restrictive (low cardinality) filters is where BS2 should win.
--
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] mikemccand commented on a diff in pull request #12415: Optimize disjunction counts.
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on code in PR #12415:
URL: https://github.com/apache/lucene/pull/12415#discussion_r1278546051
##########
lucene/core/src/java/org/apache/lucene/search/BooleanScorer.java:
##########
@@ -119,6 +121,7 @@ public BulkScorerAndDoc get(int i) {
final Score score = new Score();
final int minShouldMatch;
final long cost;
+ final boolean needsScores;
final class OrCollector implements LeafCollector {
Review Comment:
Query optimization is so tricky!
--
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 merged pull request #12415: Optimize disjunction counts.
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz merged PR #12415:
URL: https://github.com/apache/lucene/pull/12415
--
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 pull request #12415: Optimize disjunction counts.
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #12415:
URL: https://github.com/apache/lucene/pull/12415#issuecomment-1625654158
I added documentation and tests, it's ready for review. I settled on making consumption of `DocIdStream`s terminal, on the basis that it wouldn't add much value to use this optimization in a `MultiCollector` anyway. I also removed some overhead that is mostly unrelated to this change, and counting `title OR 12` is now 80% faster compared to `main`.
--
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] mikemccand commented on a diff in pull request #12415: Optimize disjunction counts.
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on code in PR #12415:
URL: https://github.com/apache/lucene/pull/12415#discussion_r1278546012
##########
lucene/core/src/java/org/apache/lucene/search/CheckedIntConsumer.java:
##########
@@ -0,0 +1,31 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.search;
+
+import java.util.function.IntConsumer;
+
+/** Like {@link IntConsumer}, but may throw checked exceptions. */
+@FunctionalInterface
+public interface CheckedIntConsumer<T extends Exception> {
Review Comment:
Sooooo tempting. This `IOExcption` pollution has been so irritating over the years ... we could maybe make all the entry points (`IndexSearcher#search`, `#count`, etc.) throw `IOException` so callers know "yes you are searching an on-disk index still so stuff could go badly wrong with those transistors", but internally use the unchecked form maybe. Though, that just pushes the virus "up" to our users ...
--
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] mikemccand commented on a diff in pull request #12415: Optimize disjunction counts.
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on code in PR #12415:
URL: https://github.com/apache/lucene/pull/12415#discussion_r1278545621
##########
lucene/core/src/java/org/apache/lucene/search/BooleanScorer.java:
##########
@@ -109,7 +109,9 @@ public BulkScorerAndDoc get(int i) {
}
}
- final Bucket[] buckets = new Bucket[SIZE];
+ // One bucket per doc ID in the window, non-null if scores are needed or if frequencies need to be
+ // counted
+ final Bucket[] buckets;
Review Comment:
LOL +1 to the extra `very` instances above!
--
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 pull request #12415: Optimize disjunction counts.
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #12415:
URL: https://github.com/apache/lucene/pull/12415#issuecomment-1623101984
To me a big question with this API is whether we should consider methods on the `DocIdStream` terminal or not. If we do this, then this may enable more optimizations later on, e.g. it would be legal to create such objects that are backed by an iterator. But on the other hand, you wouldn't be able to propage this optimization in a `MultiLeafCollector` since it would be illegal for each sub `LeafCollector` to consume the `DocIdStream` independently.
--
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 pull request #12415: Optimize disjunction counts.
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #12415:
URL: https://github.com/apache/lucene/pull/12415#issuecomment-1621604501
Note: this is just a proof of concept to discuss the idea of integrating at the collector level, more work is needed to add more tests, integrating in the test framework (`AssertingLeafCollector`), etc.
--
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] mikemccand commented on a diff in pull request #12415: Optimize disjunction counts.
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on code in PR #12415:
URL: https://github.com/apache/lucene/pull/12415#discussion_r1276073917
##########
lucene/core/src/java/org/apache/lucene/search/BooleanScorer.java:
##########
@@ -154,19 +207,20 @@ public void collect(int doc) throws IOException {
throw new IllegalArgumentException(
"This scorer can only be used with two scorers or more, got " + scorers.size());
}
- for (int i = 0; i < buckets.length; i++) {
- buckets[i] = new Bucket();
+ if (needsScores || minShouldMatch > 1) {
Review Comment:
Might this also optimize other cases, where we are using `BooleanScorer` in non-scoring cases (`MUST_NOT` or `FILTER`)? Or do we never use `BooleanScorer` for these clauses and it's really just the `count` API that we are accelerating here?
##########
lucene/core/src/java/org/apache/lucene/search/BooleanScorer.java:
##########
@@ -109,7 +109,9 @@ public BulkScorerAndDoc get(int i) {
}
}
- final Bucket[] buckets = new Bucket[SIZE];
+ // One bucket per doc ID in the window, non-null if scores are needed or if frequencies need to be
+ // counted
+ final Bucket[] buckets;
Review Comment:
I wonder if switching this to parallel arrays, for maybe better CPU cache locality, would show any speedup (separate issue!). Or maybe "structs" (value objects) when Java finally gets them.
Though, the inlined `matching` bitset is sort of already a parallel array and maybe gets most of the gains.
##########
lucene/core/src/java/org/apache/lucene/search/DocIdStream.java:
##########
@@ -0,0 +1,45 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.search;
+
+import java.io.IOException;
+
+/**
+ * A stream of doc IDs. Most methods on {@link DocIdStream}s are terminal, meaning that the {@link
+ * DocIdStream} may not be further used.
+ *
+ * @see LeafCollector#collect(DocIdStream)
+ * @lucene.experimental
+ */
+public abstract class DocIdStream {
Review Comment:
I'm not sure where to document this, but this stream is not in general (though could be) holding ALL matching hits for a given collection situation (query) right? As used from `BooleanScorer` it is just one window's worth of hits (a 2048 chunk of docid space) at once? I guess the right place to make this clear is in the new `collect(DocIdStream)` method?
##########
lucene/core/src/java/org/apache/lucene/search/BooleanScorer.java:
##########
@@ -154,19 +207,20 @@ public void collect(int doc) throws IOException {
throw new IllegalArgumentException(
"This scorer can only be used with two scorers or more, got " + scorers.size());
}
- for (int i = 0; i < buckets.length; i++) {
- buckets[i] = new Bucket();
+ if (needsScores || minShouldMatch > 1) {
+ buckets = new Bucket[SIZE];
+ for (int i = 0; i < buckets.length; i++) {
+ buckets[i] = new Bucket();
+ }
+ } else {
+ buckets = null;
}
this.leads = new BulkScorerAndDoc[scorers.size()];
this.head = new HeadPriorityQueue(scorers.size() - minShouldMatch + 1);
this.tail = new TailPriorityQueue(minShouldMatch - 1);
this.minShouldMatch = minShouldMatch;
+ this.needsScores = needsScores;
for (BulkScorer scorer : scorers) {
- if (needsScores == false) {
- // OrCollector calls score() all the time so we have to explicitly
- // disable scoring in order to avoid decoding useless norms
- scorer = BooleanWeight.disableScoring(scorer);
Review Comment:
Nice -- this change is a more effective way to disable scoring than wrapping in a no-op / fake scorer!
##########
lucene/core/src/java/org/apache/lucene/search/CheckedIntConsumer.java:
##########
@@ -0,0 +1,31 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.search;
+
+import java.util.function.IntConsumer;
+
+/** Like {@link IntConsumer}, but may throw checked exceptions. */
+@FunctionalInterface
+public interface CheckedIntConsumer<T extends Exception> {
Review Comment:
Darned ubiquitous `IOException` all throughout Lucene!!
##########
lucene/core/src/java/org/apache/lucene/search/LeafCollector.java:
##########
@@ -83,6 +83,13 @@ public interface LeafCollector {
*/
void collect(int doc) throws IOException;
+ /**
+ * Bulk-collect doc IDs. The default implementation calls {@code stream.forEach(this::collect)}.
Review Comment:
Can we note that this might be a chunk/window of docids, and it's always sequential/in-order with respect to other calls to collect (e.g. `collect(int doc)`). Is it valid for a caller to mix & match calls to both `collect` methods here? I would think so, but we are not yet doing that since this change will always collect with one or the other.
##########
lucene/core/src/java/org/apache/lucene/search/BooleanScorer.java:
##########
@@ -133,14 +136,64 @@ public void collect(int doc) throws IOException {
final int i = doc & MASK;
final int idx = i >>> 6;
matching[idx] |= 1L << i;
- final Bucket bucket = buckets[i];
- bucket.freq++;
- bucket.score += scorer.score();
+ if (buckets != null) {
+ final Bucket bucket = buckets[i];
+ bucket.freq++;
+ if (needsScores) {
+ bucket.score += scorer.score();
+ }
+ }
}
}
final OrCollector orCollector = new OrCollector();
+ final class DocIdStreamView extends DocIdStream {
+
+ int base;
+
+ @Override
+ public void forEach(CheckedIntConsumer<IOException> consumer) throws IOException {
+ long[] matching = BooleanScorer.this.matching;
+ Bucket[] buckets = BooleanScorer.this.buckets;
Review Comment:
We should (later!) maybe rename `Bucket` to `OneHit` or `DocHit` or so, to make it clear it represents details of a single doc hit.
##########
lucene/test-framework/src/java/org/apache/lucene/tests/search/QueryUtils.java:
##########
@@ -738,4 +740,66 @@ public void collect(int doc) throws IOException {
}
}
}
+
+ /**
+ * Check that counting hits through {@link DocIdStream#count()} yield the same result as counting
+ * naively.
+ */
+ public static void checkCount(Query query, final IndexSearcher searcher) throws IOException {
+ query = searcher.rewrite(query);
+ Weight weight = searcher.createWeight(query, ScoreMode.COMPLETE_NO_SCORES, 1);
+ for (LeafReaderContext context : searcher.getIndexReader().leaves()) {
+ BulkScorer scorer = weight.bulkScorer(context);
+ if (scorer == null) {
+ continue;
+ }
+ int[] expectedCount = {0};
+ boolean[] docIdStream = {false};
+ scorer.score(
+ new LeafCollector() {
+ @Override
+ public void collect(DocIdStream stream) throws IOException {
+ docIdStream[0] = true;
+ LeafCollector.super.collect(stream);
Review Comment:
This then forwards to our `collect(int doc)` method below right? So we are forcing counting "the slow way" (one by one).
##########
lucene/test-framework/src/java/org/apache/lucene/tests/search/QueryUtils.java:
##########
@@ -738,4 +740,66 @@ public void collect(int doc) throws IOException {
}
}
}
+
+ /**
+ * Check that counting hits through {@link DocIdStream#count()} yield the same result as counting
+ * naively.
+ */
+ public static void checkCount(Query query, final IndexSearcher searcher) throws IOException {
+ query = searcher.rewrite(query);
+ Weight weight = searcher.createWeight(query, ScoreMode.COMPLETE_NO_SCORES, 1);
+ for (LeafReaderContext context : searcher.getIndexReader().leaves()) {
+ BulkScorer scorer = weight.bulkScorer(context);
+ if (scorer == null) {
+ continue;
+ }
+ int[] expectedCount = {0};
+ boolean[] docIdStream = {false};
+ scorer.score(
+ new LeafCollector() {
+ @Override
+ public void collect(DocIdStream stream) throws IOException {
+ docIdStream[0] = true;
+ LeafCollector.super.collect(stream);
+ }
+
+ @Override
+ public void collect(int doc) throws IOException {
+ expectedCount[0]++;
+ }
+
+ @Override
+ public void setScorer(Scorable scorer) throws IOException {}
+ },
+ context.reader().getLiveDocs(),
+ 0,
+ DocIdSetIterator.NO_MORE_DOCS);
+ if (docIdStream[0] == false) {
+ // Don't spend cycles running the query one more time, it doesn't use the DocIdStream
+ // optimization.
+ continue;
+ }
+ scorer = weight.bulkScorer(context);
+ int[] actualCount = {0};
+ scorer.score(
+ new LeafCollector() {
+ @Override
+ public void collect(DocIdStream stream) throws IOException {
+ actualCount[0] += stream.count();
+ }
+
+ @Override
+ public void collect(int doc) throws IOException {
+ actualCount[0]++;
+ }
+
+ @Override
+ public void setScorer(Scorable scorer) throws IOException {}
+ },
+ context.reader().getLiveDocs(),
+ 0,
+ DocIdSetIterator.NO_MORE_DOCS);
+ assertEquals(expectedCount[0], actualCount[0]);
Review Comment:
Nice! So we count both fast (`DocIdStream#count`) and slow (one by one) way and confirm they agree.
##########
lucene/core/src/java/org/apache/lucene/search/BooleanScorer.java:
##########
@@ -119,6 +121,7 @@ public BulkScorerAndDoc get(int i) {
final Score score = new Score();
final int minShouldMatch;
final long cost;
+ final boolean needsScores;
final class OrCollector implements LeafCollector {
Review Comment:
Do we really only use this `BooleanScorer` for pure disjunctive cases now? I wonder if it might be faster than BS2 for certain conjunctive cases, e.g. if the clauses all have "similar" cost. (Separate issue).
--
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 a diff in pull request #12415: Optimize disjunction counts.
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #12415:
URL: https://github.com/apache/lucene/pull/12415#discussion_r1276555327
##########
lucene/core/src/java/org/apache/lucene/search/BooleanScorer.java:
##########
@@ -154,19 +207,20 @@ public void collect(int doc) throws IOException {
throw new IllegalArgumentException(
"This scorer can only be used with two scorers or more, got " + scorers.size());
}
- for (int i = 0; i < buckets.length; i++) {
- buckets[i] = new Bucket();
+ if (needsScores || minShouldMatch > 1) {
Review Comment:
Yes, we also use `BooleanScorer` when there is a mix of SHOULD and MUST_NOT clauses. But not when there are FILTER clauses.
--
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 a diff in pull request #12415: Optimize disjunction counts.
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #12415:
URL: https://github.com/apache/lucene/pull/12415#discussion_r1276558624
##########
lucene/core/src/java/org/apache/lucene/search/BooleanScorer.java:
##########
@@ -119,6 +121,7 @@ public BulkScorerAndDoc get(int i) {
final Score score = new Score();
final int minShouldMatch;
final long cost;
+ final boolean needsScores;
final class OrCollector implements LeafCollector {
Review Comment:
Indeed, we never use it for conjunctions. It's probably faster than BS2 for conjunctions at times, it would be interesting to find a good heuristic.
--
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] msokolov commented on a diff in pull request #12415: Optimize disjunction counts.
Posted by "msokolov (via GitHub)" <gi...@apache.org>.
msokolov commented on code in PR #12415:
URL: https://github.com/apache/lucene/pull/12415#discussion_r1278351078
##########
lucene/core/src/java/org/apache/lucene/search/CheckedIntConsumer.java:
##########
@@ -0,0 +1,31 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.search;
+
+import java.util.function.IntConsumer;
+
+/** Like {@link IntConsumer}, but may throw checked exceptions. */
+@FunctionalInterface
+public interface CheckedIntConsumer<T extends Exception> {
Review Comment:
How about `s/throws IOException//g` and `s/IOException/IOExceptionUnchecked/g` ?
--
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 pull request #12415: Optimize disjunction counts.
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #12415:
URL: https://github.com/apache/lucene/pull/12415#issuecomment-1666458827
Counting tasks after integrating #12488:
```
TaskQPS baseline StdDevQPS my_modified_version StdDev Pct diff p-value
CountPhrase 12.47 (3.2%) 12.49 (3.9%) 0.1% ( -6% - 7%) 0.909
PKLookup 240.85 (4.1%) 241.22 (3.6%) 0.2% ( -7% - 8%) 0.897
CountTerm 9110.81 (3.9%) 9163.88 (2.8%) 0.6% ( -5% - 7%) 0.586
CountAndHighHigh 51.81 (3.5%) 52.36 (2.5%) 1.1% ( -4% - 7%) 0.274
CountAndHighMed 196.28 (3.8%) 198.66 (2.3%) 1.2% ( -4% - 7%) 0.222
CountOrHighHigh 50.41 (9.3%) 64.37 (16.3%) 27.7% ( 1% - 58%) 0.000
CountOrHighMed 79.16 (8.7%) 105.40 (16.4%) 33.2% ( 7% - 63%) 0.000
```
--
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] mikemccand commented on pull request #12415: Optimize disjunction counts.
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on PR #12415:
URL: https://github.com/apache/lucene/pull/12415#issuecomment-1645462761
> counting title OR 12 is now 80% faster compared to main.
Wow! I'll try to review soon. Thanks @jpountz!
--
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