mikemccand commented on code in PR #11888:
URL: https://github.com/apache/lucene/pull/11888#discussion_r1541971598
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene90/blocktree/SegmentTermsEnumFrame.java:
##########
@@ -642,6 +651,99 @@ public SeekStatus scanToTermLeaf(BytesRef target, boolean
exactOnly) throws IOEx
return SeekStatus.END;
}
+ // Target's prefix matches this block's prefix;
+ // And all suffixes have the same length in this block,
+ // we binary search the entries check if the suffix matches.
+ public SeekStatus binarySearchTermLeaf(BytesRef target, boolean exactOnly)
throws IOException {
+ // if (DEBUG) System.out.println(" binarySearchTermLeaf: block fp=" +
fp + " prefix=" +
+ // prefix + "
+ // nextEnt=" + nextEnt + " (of " + entCount + ") target=" +
brToString(target) + " term=" +
+ // brToString(term));
+
+ assert nextEnt != -1;
+
+ ste.termExists = true;
+ subCode = 0;
+
+ if (nextEnt == entCount) {
+ if (exactOnly) {
+ fillTerm();
+ }
+ return SeekStatus.END;
+ }
+
+ assert prefixMatches(target);
+
+ suffix = suffixLengthsReader.readVInt();
+ // TODO early terminate when target length unequals suffix + prefix.
+ // But we need to keep the same status with scanToTermLeaf.
+ int start = nextEnt;
+ int end = entCount - 1;
+ // Binary search the entries (terms) in this leaf block:
+ int cmp = 0;
+ while (start <= end) {
+ int mid = (start + end) / 2;
Review Comment:
It surely won't matter for this particular binary search but can we replace
the division by 2 with logical right shift `>>> 1` instead, to avoid even the
appearance of the [classic binary search overflow
bug](https://thebittheories.com/the-curious-case-of-binary-search-the-famous-bug-that-remained-undetected-for-20-years-973e89fc212)?
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene90/blocktree/SegmentTermsEnumFrame.java:
##########
@@ -642,6 +651,99 @@ public SeekStatus scanToTermLeaf(BytesRef target, boolean
exactOnly) throws IOEx
return SeekStatus.END;
}
+ // Target's prefix matches this block's prefix;
+ // And all suffixes have the same length in this block,
+ // we binary search the entries check if the suffix matches.
+ public SeekStatus binarySearchTermLeaf(BytesRef target, boolean exactOnly)
throws IOException {
+ // if (DEBUG) System.out.println(" binarySearchTermLeaf: block fp=" +
fp + " prefix=" +
+ // prefix + "
+ // nextEnt=" + nextEnt + " (of " + entCount + ") target=" +
brToString(target) + " term=" +
+ // brToString(term));
+
+ assert nextEnt != -1;
+
+ ste.termExists = true;
+ subCode = 0;
+
+ if (nextEnt == entCount) {
+ if (exactOnly) {
+ fillTerm();
+ }
+ return SeekStatus.END;
+ }
+
+ assert prefixMatches(target);
+
+ suffix = suffixLengthsReader.readVInt();
+ // TODO early terminate when target length unequals suffix + prefix.
+ // But we need to keep the same status with scanToTermLeaf.
+ int start = nextEnt;
+ int end = entCount - 1;
+ // Binary search the entries (terms) in this leaf block:
+ int cmp = 0;
+ while (start <= end) {
+ int mid = (start + end) / 2;
+ nextEnt = mid + 1;
+ startBytePos = mid * suffix;
+
+ // Binary search bytes in the suffix, comparing to the target
+ cmp =
+ Arrays.compareUnsigned(
+ suffixBytes,
+ startBytePos,
+ startBytePos + suffix,
+ target.bytes,
+ target.offset + prefix,
+ target.offset + target.length);
+ if (cmp < 0) {
+ start = mid + 1;
+ } else if (cmp > 0) {
+ end = mid - 1;
+ } else {
+ // Exact match!
+ suffixesReader.setPosition(startBytePos + suffix);
+ // This cannot be a sub-block because we
+ // would have followed the index to this
+ // sub-block from the start:
+ assert ste.termExists;
+ fillTerm();
+ // if (DEBUG) System.out.println(" found!");
+ return SeekStatus.FOUND;
+ }
+ }
+
+ // It is possible (and OK) that terms index pointed us
+ // at this block, but, we searched the entire block and
+ // did not find the term to position to. This happens
+ // when the target is after the last term in the block
+ // (but, before the next term in the index). EG
+ // target could be foozzz, and terms index pointed us
+ // to the foo* block, but the last term in this block
+ // was fooz (and, eg, first term in the next block will
+ // bee fop).
+ // if (DEBUG) System.out.println(" block end");
+ SeekStatus seekStatus = end < entCount - 1 ? SeekStatus.NOT_FOUND :
SeekStatus.END;
+ if (seekStatus == SeekStatus.NOT_FOUND) {
+ // If binary search ended at the less term, and greater term exists.
+ // We need to advance to the greater term.
+ if (cmp < 0) {
+ startBytePos += suffix;
+ nextEnt++;
+ }
+ suffixesReader.setPosition(startBytePos + suffix);
+ fillTerm();
+ } else {
+ suffixesReader.setPosition(startBytePos + suffix);
+ if (exactOnly) {
+ fillTerm();
+ }
+ }
+ // TODO: not consistent that in the
+ // not-exact case we don't next() into the next
+ // frame here
+ return seekStatus;
Review Comment:
I'm confused why `SeekStatus.END` is OK to return here? Just because the
term is beyond the end of our block, and before the start term of the next
block, doesn't mean it will be `END`?
Oh nevermind: I see this is pre-existing, and, the `END` here (at the Frame
level) is re-interpreted up above in the `Intersect/SegmentTermsEnum` up above
to translate it into a `NOT_FOUND` when we are not in fact at the end of the
terms, phew.
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene90/blocktree/SegmentTermsEnumFrame.java:
##########
@@ -642,6 +651,99 @@ public SeekStatus scanToTermLeaf(BytesRef target, boolean
exactOnly) throws IOEx
return SeekStatus.END;
}
+ // Target's prefix matches this block's prefix;
+ // And all suffixes have the same length in this block,
+ // we binary search the entries check if the suffix matches.
+ public SeekStatus binarySearchTermLeaf(BytesRef target, boolean exactOnly)
throws IOException {
+ // if (DEBUG) System.out.println(" binarySearchTermLeaf: block fp=" +
fp + " prefix=" +
+ // prefix + "
+ // nextEnt=" + nextEnt + " (of " + entCount + ") target=" +
brToString(target) + " term=" +
+ // brToString(term));
+
+ assert nextEnt != -1;
+
+ ste.termExists = true;
+ subCode = 0;
+
+ if (nextEnt == entCount) {
+ if (exactOnly) {
+ fillTerm();
+ }
+ return SeekStatus.END;
+ }
+
+ assert prefixMatches(target);
+
+ suffix = suffixLengthsReader.readVInt();
+ // TODO early terminate when target length unequals suffix + prefix.
+ // But we need to keep the same status with scanToTermLeaf.
+ int start = nextEnt;
+ int end = entCount - 1;
+ // Binary search the entries (terms) in this leaf block:
+ int cmp = 0;
+ while (start <= end) {
+ int mid = (start + end) / 2;
+ nextEnt = mid + 1;
+ startBytePos = mid * suffix;
+
+ // Binary search bytes in the suffix, comparing to the target
+ cmp =
+ Arrays.compareUnsigned(
+ suffixBytes,
+ startBytePos,
+ startBytePos + suffix,
+ target.bytes,
+ target.offset + prefix,
+ target.offset + target.length);
+ if (cmp < 0) {
+ start = mid + 1;
+ } else if (cmp > 0) {
+ end = mid - 1;
+ } else {
+ // Exact match!
+ suffixesReader.setPosition(startBytePos + suffix);
+ // This cannot be a sub-block because we
+ // would have followed the index to this
+ // sub-block from the start:
+ assert ste.termExists;
+ fillTerm();
+ // if (DEBUG) System.out.println(" found!");
+ return SeekStatus.FOUND;
+ }
+ }
+
+ // It is possible (and OK) that terms index pointed us
+ // at this block, but, we searched the entire block and
+ // did not find the term to position to. This happens
+ // when the target is after the last term in the block
+ // (but, before the next term in the index). EG
+ // target could be foozzz, and terms index pointed us
+ // to the foo* block, but the last term in this block
+ // was fooz (and, eg, first term in the next block will
+ // bee fop).
+ // if (DEBUG) System.out.println(" block end");
+ SeekStatus seekStatus = end < entCount - 1 ? SeekStatus.NOT_FOUND :
SeekStatus.END;
Review Comment:
Could we make a normal `if` for this instead of ternary operator?
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene90/blocktree/SegmentTermsEnumFrame.java:
##########
@@ -642,6 +651,99 @@ public SeekStatus scanToTermLeaf(BytesRef target, boolean
exactOnly) throws IOEx
return SeekStatus.END;
}
+ // Target's prefix matches this block's prefix;
+ // And all suffixes have the same length in this block,
+ // we binary search the entries check if the suffix matches.
+ public SeekStatus binarySearchTermLeaf(BytesRef target, boolean exactOnly)
throws IOException {
+ // if (DEBUG) System.out.println(" binarySearchTermLeaf: block fp=" +
fp + " prefix=" +
+ // prefix + "
+ // nextEnt=" + nextEnt + " (of " + entCount + ") target=" +
brToString(target) + " term=" +
+ // brToString(term));
+
+ assert nextEnt != -1;
+
+ ste.termExists = true;
+ subCode = 0;
+
+ if (nextEnt == entCount) {
+ if (exactOnly) {
+ fillTerm();
+ }
+ return SeekStatus.END;
+ }
+
+ assert prefixMatches(target);
+
+ suffix = suffixLengthsReader.readVInt();
+ // TODO early terminate when target length unequals suffix + prefix.
+ // But we need to keep the same status with scanToTermLeaf.
+ int start = nextEnt;
+ int end = entCount - 1;
+ // Binary search the entries (terms) in this leaf block:
+ int cmp = 0;
+ while (start <= end) {
+ int mid = (start + end) / 2;
+ nextEnt = mid + 1;
+ startBytePos = mid * suffix;
+
+ // Binary search bytes in the suffix, comparing to the target
+ cmp =
+ Arrays.compareUnsigned(
+ suffixBytes,
+ startBytePos,
+ startBytePos + suffix,
+ target.bytes,
+ target.offset + prefix,
+ target.offset + target.length);
+ if (cmp < 0) {
+ start = mid + 1;
+ } else if (cmp > 0) {
+ end = mid - 1;
+ } else {
+ // Exact match!
+ suffixesReader.setPosition(startBytePos + suffix);
+ // This cannot be a sub-block because we
+ // would have followed the index to this
+ // sub-block from the start:
+ assert ste.termExists;
+ fillTerm();
+ // if (DEBUG) System.out.println(" found!");
+ return SeekStatus.FOUND;
+ }
+ }
+
+ // It is possible (and OK) that terms index pointed us
+ // at this block, but, we searched the entire block and
+ // did not find the term to position to. This happens
+ // when the target is after the last term in the block
+ // (but, before the next term in the index). EG
+ // target could be foozzz, and terms index pointed us
+ // to the foo* block, but the last term in this block
+ // was fooz (and, eg, first term in the next block will
+ // bee fop).
+ // if (DEBUG) System.out.println(" block end");
+ SeekStatus seekStatus = end < entCount - 1 ? SeekStatus.NOT_FOUND :
SeekStatus.END;
+ if (seekStatus == SeekStatus.NOT_FOUND) {
Review Comment:
Hmm instead of assigning `seekStatus` separately above, could we just make
this:
```
if (end < entCount - 1) {
seekStatus = SeekStatus.NOT_FOUND;
....
} else {
seekStatus = SeekStatus.END;
...
}
```
?
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene90/blocktree/SegmentTermsEnumFrame.java:
##########
@@ -642,6 +651,99 @@ public SeekStatus scanToTermLeaf(BytesRef target, boolean
exactOnly) throws IOEx
return SeekStatus.END;
}
+ // Target's prefix matches this block's prefix;
+ // And all suffixes have the same length in this block,
+ // we binary search the entries check if the suffix matches.
+ public SeekStatus binarySearchTermLeaf(BytesRef target, boolean exactOnly)
throws IOException {
+ // if (DEBUG) System.out.println(" binarySearchTermLeaf: block fp=" +
fp + " prefix=" +
+ // prefix + "
+ // nextEnt=" + nextEnt + " (of " + entCount + ") target=" +
brToString(target) + " term=" +
+ // brToString(term));
+
+ assert nextEnt != -1;
+
+ ste.termExists = true;
+ subCode = 0;
+
+ if (nextEnt == entCount) {
+ if (exactOnly) {
+ fillTerm();
+ }
+ return SeekStatus.END;
+ }
+
+ assert prefixMatches(target);
+
+ suffix = suffixLengthsReader.readVInt();
+ // TODO early terminate when target length unequals suffix + prefix.
+ // But we need to keep the same status with scanToTermLeaf.
+ int start = nextEnt;
+ int end = entCount - 1;
+ // Binary search the entries (terms) in this leaf block:
+ int cmp = 0;
+ while (start <= end) {
+ int mid = (start + end) / 2;
+ nextEnt = mid + 1;
+ startBytePos = mid * suffix;
+
+ // Binary search bytes in the suffix, comparing to the target
+ cmp =
+ Arrays.compareUnsigned(
+ suffixBytes,
+ startBytePos,
+ startBytePos + suffix,
+ target.bytes,
+ target.offset + prefix,
+ target.offset + target.length);
+ if (cmp < 0) {
+ start = mid + 1;
+ } else if (cmp > 0) {
+ end = mid - 1;
+ } else {
+ // Exact match!
+ suffixesReader.setPosition(startBytePos + suffix);
+ // This cannot be a sub-block because we
+ // would have followed the index to this
+ // sub-block from the start:
+ assert ste.termExists;
Review Comment:
Fix this comment? `This cannot be a sub-block because we only do this
binary search on leaf blocks` or so?
Also, we set `ste.termExists` above so we could just remove this comment and
the assert instead?
--
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-unsubscr...@lucene.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
