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 2021/12/03 07:31:40 UTC
[GitHub] [lucene] gf2121 opened a new pull request #510: LUCENE-10280: Store BKD blocks with continuous ids more efficiently
gf2121 opened a new pull request #510:
URL: https://github.com/apache/lucene/pull/510
For scenes that index is sorted on the field, blocks with continuous ids may be a common situation. In this case we can handle this situation more efficiently. We just need to check
```
stritylysorted && (docIds[start+count-1] - docids[start] + 1) == count
```
to check if ids is continuous. If so, we can only write the first id of this block.
--
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] gf2121 edited a comment on pull request #510: LUCENE-10280: Store BKD blocks with continuous ids more efficiently
Posted by GitBox <gi...@apache.org>.
gf2121 edited a comment on pull request #510:
URL: https://github.com/apache/lucene/pull/510#issuecomment-989104054
@iverase Thanks for your explanation!
> I worked on the PR about using #readLELongs but never get a meaningful speed up that justify the added complexity.
I find that we were trying to use #readLELongs to speed up 24/32 bit situation in the `DocIdsWriter`, which means the ids in the block are unsorted, typically happening in high cardinarlity fields. I think queries on high cardinality fields spend most of their time on `visitDocValues` but not `readDocIds`, so maybe this is the reason that we can not see a obvious gain on E2E took?
My current thoughts are about using readLELongs to speed up the **sorted** ids situation (means low or medium cardinality fields), whose bottleneck is reading docIds. For sorted arrays, we can compute the delta of the sorted ids and encode/decode them like what we do in `StoredFieldsInts`.
I raised an [ISSUE](https://issues.apache.org/jira/browse/LUCENE-10297) based on this idea. The benchmark result i post in the issue looks promising. Would you like to help take a look when you are free? 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
[GitHub] [lucene] gf2121 commented on a change in pull request #510: LUCENE-10280: Store BKD blocks with continuous ids more efficiently
Posted by GitBox <gi...@apache.org>.
gf2121 commented on a change in pull request #510:
URL: https://github.com/apache/lucene/pull/510#discussion_r762940276
##########
File path: lucene/core/src/java/org/apache/lucene/util/bkd/DocIdsWriter.java
##########
@@ -44,13 +44,21 @@ static void writeDocIds(int[] docIds, int start, int count, DataOutput out) thro
}
}
- if (strictlySorted && (docIds[start + count - 1] - docIds[start] + 1) <= (count << 4)) {
- // Only trigger this optimization when max - min + 1 <= 16 * count in order to avoid expanding
- // too much storage.
- // A field with lower cardinality will have higher probability to trigger this optimization.
- out.writeByte((byte) -1);
- writeIdsAsBitSet(docIds, start, count, out);
- return;
+ int min2max = docIds[start + count - 1] - docIds[start] + 1;
+ if (strictlySorted) {
+ if (min2max == count) {
+ // continuous ids, typically happens when segment is sorted
+ out.writeByte((byte) -2);
+ out.writeVInt(docIds[start]);
+ return;
+ } else if (min2max <= (count << 4)) {
+ // Only trigger bitset optimization when max - min + 1 <= 16 * count in order to avoid
Review comment:
+1
--
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] gf2121 commented on pull request #510: LUCENE-10280: Store BKD blocks with continuous ids more efficiently
Posted by GitBox <gi...@apache.org>.
gf2121 commented on pull request #510:
URL: https://github.com/apache/lucene/pull/510#issuecomment-986952205
Hi @jpountz ! Just to remind, maybe we can merge this now? :)
By the way, I found that there is a PR about using readLELongs in BKD https://github.com/apache/lucene-solr/pull/1538. The discussion of this issue has stopped since last Year. This looks promising to me and I'd like to play with this but i wonder the reason it stopped, if there are some problems with this idea or if there has already been someone doing 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] gf2121 edited a comment on pull request #510: LUCENE-10280: Store BKD blocks with continuous ids more efficiently
Posted by GitBox <gi...@apache.org>.
gf2121 edited a comment on pull request #510:
URL: https://github.com/apache/lucene/pull/510#issuecomment-989104054
@iverase Thanks for your explanation!
> I worked on the PR about using #readLELongs but never get a meaningful speed up that justify the added complexity.
I find that we were trying to use #readLELongs to speed up 24/32 bit situation in the `DocIdsWriter`, which means the ids in the block are unsorted, typically happening in high cardinarlity fields. I think queries on high cardinality fields spend most of their time on `visitDocValues` but not `readDocIds`, so maybe this is the reason that we can not see a obvious gain on E2E took?
My current thoughts are about using readLELongs to speed up the **sorted** ids situation (means low or medium cardinality fields), whose bottleneck is reading docIds. For sorted arrays, we can compute the delta of the sorted ids and encode/decode them like what we do in `StoredFieldsInts`.
I raised an [ISSUE](https://issues.apache.org/jira/browse/LUCENE-10297) based on this idea. The benchmark result i post in the issue looks promising. Would you like to help take a look when you have free time? 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
[GitHub] [lucene] gf2121 edited a comment on pull request #510: LUCENE-10280: Store BKD blocks with continuous ids more efficiently
Posted by GitBox <gi...@apache.org>.
gf2121 edited a comment on pull request #510:
URL: https://github.com/apache/lucene/pull/510#issuecomment-986952205
Hi @jpountz @iverase ! Just to remind, maybe we can merge this now? :)
By the way, I found that there is a PR about using readLELongs in BKD https://github.com/apache/lucene-solr/pull/1538. The discussion of this issue has stopped since last Year. This looks promising and I'd like to play with this but i wonder why it stopped, if there are some problems with this idea or if there has already been someone working on 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] sonatype-lift[bot] commented on a change in pull request #510: LUCENE-10280: Store BKD blocks with continuous ids more efficiently
Posted by GitBox <gi...@apache.org>.
sonatype-lift[bot] commented on a change in pull request #510:
URL: https://github.com/apache/lucene/pull/510#discussion_r761853692
##########
File path: lucene/core/src/java/org/apache/lucene/search/DocIdSetIterator.java
##########
@@ -101,36 +101,57 @@ public static final DocIdSetIterator range(int minDoc, int maxDoc) {
if (minDoc < 0) {
throw new IllegalArgumentException("minDoc must be >= 0 but got minDoc=" + minDoc);
}
- return new DocIdSetIterator() {
- private int doc = -1;
+ return new RangeDocIdSetIterator(minDoc, maxDoc);
+ }
- @Override
- public int docID() {
- return doc;
- }
+ /**
+ * A {@link DocIdSetIterator} that matches a range documents from minDocID (inclusive) to maxDocID
+ * (exclusive).
+ */
+ public static class RangeDocIdSetIterator extends DocIdSetIterator {
+ private final int minDoc;
+ private final int maxDoc;
+ private int doc = -1;
+
+ public RangeDocIdSetIterator(int minDoc, int maxDoc) {
+ this.minDoc = minDoc;
+ this.maxDoc = maxDoc;
+ }
- @Override
- public int nextDoc() throws IOException {
- return advance(doc + 1);
- }
+ @Override
+ public int docID() {
+ return doc;
+ }
- @Override
- public int advance(int target) throws IOException {
- if (target < minDoc) {
- doc = minDoc;
- } else if (target >= maxDoc) {
- doc = NO_MORE_DOCS;
- } else {
- doc = target;
- }
- return doc;
- }
+ @Override
+ public int nextDoc() throws IOException {
+ return advance(doc + 1);
+ }
- @Override
- public long cost() {
- return maxDoc - minDoc;
+ @Override
+ public int advance(int target) throws IOException {
+ if (target < minDoc) {
+ doc = minDoc;
+ } else if (target >= maxDoc) {
+ doc = NO_MORE_DOCS;
+ } else {
+ doc = target;
}
- };
+ return doc;
+ }
+
+ public int getMinDoc() {
+ return minDoc;
+ }
+
+ public int getMaxDoc() {
+ return maxDoc;
+ }
+
+ @Override
+ public long cost() {
+ return maxDoc - minDoc;
Review comment:
*IntLongMath:* Expression of type int may overflow before being assigned to a long [(details)](https://errorprone.info/bugpattern/IntLongMath)
(at-me [in a reply](https://help.sonatype.com/lift/talking-to-lift) with `help` or `ignore`)
--
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 change in pull request #510: LUCENE-10280: Store BKD blocks with continuous ids more efficiently
Posted by GitBox <gi...@apache.org>.
jpountz commented on a change in pull request #510:
URL: https://github.com/apache/lucene/pull/510#discussion_r761974115
##########
File path: lucene/core/src/java/org/apache/lucene/util/bkd/DocIdsWriter.java
##########
@@ -44,13 +44,21 @@ static void writeDocIds(int[] docIds, int start, int count, DataOutput out) thro
}
}
- if (strictlySorted && (docIds[start + count - 1] - docIds[start] + 1) <= (count << 4)) {
- // Only trigger this optimization when max - min + 1 <= 16 * count in order to avoid expanding
- // too much storage.
- // A field with lower cardinality will have higher probability to trigger this optimization.
- out.writeByte((byte) -1);
- writeIdsAsBitSet(docIds, start, count, out);
- return;
+ int min2max = docIds[start + count - 1] - docIds[start] + 1;
+ if (strictlySorted) {
+ if (min2max == count) {
+ // continuous ids, typically happens when segment is sorted
+ out.writeByte((byte) -2);
+ out.writeVInt(docIds[start]);
+ return;
+ } else if (min2max <= (count << 4)) {
+ // Only trigger bitset optimization when max - min + 1 <= 16 * count in order to avoid
Review comment:
maybe assert that min2max > count?
--
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] gf2121 edited a comment on pull request #510: LUCENE-10280: Store BKD blocks with continuous ids more efficiently
Posted by GitBox <gi...@apache.org>.
gf2121 edited a comment on pull request #510:
URL: https://github.com/apache/lucene/pull/510#issuecomment-986952205
Hi @jpountz ! Just to remind, maybe we can merge this now? :)
By the way, I found that there is a PR about using readLELongs in BKD https://github.com/apache/lucene-solr/pull/1538. The discussion of this issue has stopped since last Year. This looks promising and I'd like to play with it but i wonder why it stopped, if there are some problems with this idea or if there has already been someone working on 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] gf2121 edited a comment on pull request #510: LUCENE-10280: Store BKD blocks with continuous ids more efficiently
Posted by GitBox <gi...@apache.org>.
gf2121 edited a comment on pull request #510:
URL: https://github.com/apache/lucene/pull/510#issuecomment-986952205
Hi @jpountz ! Just to remind, maybe we can merge this now? :)
By the way, I found that there is a PR about using readLELongs in BKD https://github.com/apache/lucene-solr/pull/1538. The discussion of this issue has stopped since last Year. This looks promising and I'd like to play with this but i wonder why it stopped, if there are some problems with this idea or if there has already been someone working on 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] gf2121 commented on pull request #510: LUCENE-10280: Store BKD blocks with continuous ids more efficiently
Posted by GitBox <gi...@apache.org>.
gf2121 commented on pull request #510:
URL: https://github.com/apache/lucene/pull/510#issuecomment-989104054
@iverase Thanks for your explanation!
> I worked on the PR about using #readLELongs but never get a meaningful speed up that justify the added complexity.
I find that we were trying to use #readLELongs to speed up 24/32 bit situation in the `DocIdsWriter`, which means the ids in the block are unsorted, typically happening in high cardinarlity fields. I think queries on high cardinality fields spend most of their time on `visitDocValues` but not `readDocIds`, so maybe this is the reason that we can not see a obvious gain on E2E side?
My current thoughts are about using readLELongs to speed up the **sorted** ids situation (means low or medium cardinality fields), whose bottleneck is reading docIds. For sorted arrays, we can compute the delta of the sorted ids and encode/decode them like what we do in `StoredFieldsInts`.
I raised an [ISSUE](https://issues.apache.org/jira/browse/LUCENE-10297) based this idea. The benchmark result i post in the issue looks promising. Would you like to help take a look when you are free? 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
[GitHub] [lucene] iverase merged pull request #510: LUCENE-10280: Store BKD blocks with continuous ids more efficiently
Posted by GitBox <gi...@apache.org>.
iverase merged pull request #510:
URL: https://github.com/apache/lucene/pull/510
--
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] gf2121 commented on a change in pull request #510: LUCENE-10280: Store BKD blocks with continuous ids more efficiently
Posted by GitBox <gi...@apache.org>.
gf2121 commented on a change in pull request #510:
URL: https://github.com/apache/lucene/pull/510#discussion_r762940276
##########
File path: lucene/core/src/java/org/apache/lucene/util/bkd/DocIdsWriter.java
##########
@@ -44,13 +44,21 @@ static void writeDocIds(int[] docIds, int start, int count, DataOutput out) thro
}
}
- if (strictlySorted && (docIds[start + count - 1] - docIds[start] + 1) <= (count << 4)) {
- // Only trigger this optimization when max - min + 1 <= 16 * count in order to avoid expanding
- // too much storage.
- // A field with lower cardinality will have higher probability to trigger this optimization.
- out.writeByte((byte) -1);
- writeIdsAsBitSet(docIds, start, count, out);
- return;
+ int min2max = docIds[start + count - 1] - docIds[start] + 1;
+ if (strictlySorted) {
+ if (min2max == count) {
+ // continuous ids, typically happens when segment is sorted
+ out.writeByte((byte) -2);
+ out.writeVInt(docIds[start]);
+ return;
+ } else if (min2max <= (count << 4)) {
+ // Only trigger bitset optimization when max - min + 1 <= 16 * count in order to avoid
Review comment:
+1, fixed
--
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] iverase commented on pull request #510: LUCENE-10280: Store BKD blocks with continuous ids more efficiently
Posted by GitBox <gi...@apache.org>.
iverase commented on pull request #510:
URL: https://github.com/apache/lucene/pull/510#issuecomment-987036814
I will merge soon if Adrien does not beat me up.
I worked on the PR about using #readLELongs but never get a meaningful speed up that justify the added complexity. Maybe now that we have little endian codecs might make more sense. I am not planing to continue that work so please feel free to have a go.
--
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