vsop-479 commented on code in PR #11888: URL: https://github.com/apache/lucene/pull/11888#discussion_r1542363416
########## 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: Done. -- 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