xiangfu0 commented on code in PR #19906:
URL: https://github.com/apache/pinot/pull/19906#discussion_r4296688465
##########
pinot-segment-spi/src/main/java/org/apache/pinot/segment/spi/memory/CompoundDataBuffer.java:
##########
@@ -112,21 +113,19 @@ private static DataBuffer[]
asDataBufferArray(List<ByteBuffer> buffers) {
}
private int getBufferIndex(long offset) {
- // this optimistically assumes that lookups are going to be in ascending
order
- // we don't care about concurrency here given that this is only used to
speed up the lookup
+ // Most lookups land in the same buffer as the previous one, so check it
first. Otherwise use a binary search,
+ // which keeps random and backward access at O(log n) instead of a scan
from the first buffer.
+ // We don't care about concurrency here given that this is only used to
speed up the lookup.
int lastBufferIndex = _lastBufferIndex;
- if (_bufferOffsets[lastBufferIndex] > offset) {
- lastBufferIndex = 0;
- }
-
- for (int i = lastBufferIndex; i < _bufferOffsets.length; i++) {
- if (offset < _bufferOffsets[i]) {
- int result = i - 1;
- _lastBufferIndex = result;
- return result;
- }
- }
- int result = _bufferOffsets.length - 1;
+ int nextBufferIndex = lastBufferIndex + 1;
+ if (_bufferOffsets[lastBufferIndex] <= offset
+ && (nextBufferIndex == _bufferOffsets.length || offset <
_bufferOffsets[nextBufferIndex])) {
+ return lastBufferIndex;
+ }
+ // Offsets are strictly ascending because empty buffers are rejected. On a
miss, binarySearch returns
+ // (-insertionPoint - 1), and the buffer that contains the offset is the
one before the insertion point.
+ int index = Arrays.binarySearch(_bufferOffsets, offset);
+ int result = index >= 0 ? index : -index - 2;
Review Comment:
This fixes a real quadratic: before, a backward lookup reset to index 0 and
rescanned, which the DataTable merge path hit hard with thousands of pages read
in column/random order. The `-index - 2` decode is correct since offset 0 is
always present. Minor: the test exercises backward and random access well, but
none of the buffer sizes exceed one entry boundary enough to make the old scan
visibly quadratic — that is fine for a correctness test, just noting the perf
win itself is not directly asserted.
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
