You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@druid.apache.org by GitBox <gi...@apache.org> on 2022/10/22 15:22:21 UTC
[GitHub] [druid] abhishekagarwal87 commented on a diff in pull request #12277: add support for 'front coded' string dictionaries for smaller string columns
abhishekagarwal87 commented on code in PR #12277:
URL: https://github.com/apache/druid/pull/12277#discussion_r1002466260
##########
processing/src/main/java/org/apache/druid/segment/column/IndexedStringDruidPredicateIndex.java:
##########
@@ -0,0 +1,107 @@
+/*
+ * 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.druid.segment.column;
+
+import com.google.common.base.Predicate;
+import org.apache.druid.collections.bitmap.BitmapFactory;
+import org.apache.druid.collections.bitmap.ImmutableBitmap;
+import org.apache.druid.query.filter.DruidPredicateFactory;
+import org.apache.druid.segment.data.Indexed;
+
+import javax.annotation.Nullable;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+public final class IndexedStringDruidPredicateIndex<TDictionary extends Indexed<String>> implements DruidPredicateIndex
+{
+ private final BitmapFactory bitmapFactory;
+ private final TDictionary dictionary;
+ private final Indexed<ImmutableBitmap> bitmaps;
+
+ public IndexedStringDruidPredicateIndex(
+ BitmapFactory bitmapFactory,
+ TDictionary dictionary,
+ Indexed<ImmutableBitmap> bitmaps
+ )
+ {
+ this.bitmapFactory = bitmapFactory;
+ this.dictionary = dictionary;
+ this.bitmaps = bitmaps;
+ }
+
+ @Override
+ public BitmapColumnIndex forPredicate(DruidPredicateFactory matcherFactory)
+ {
+ return new SimpleImmutableBitmapIterableIndex()
+ {
+ @Override
+ public Iterable<ImmutableBitmap> getBitmapIterable()
+ {
+ return () -> new Iterator<ImmutableBitmap>()
Review Comment:
nit: The iterator impl could go into a private class for better readability.
##########
processing/src/main/java/org/apache/druid/segment/nested/NestedDataColumnSupplier.java:
##########
@@ -74,7 +79,32 @@ public NestedDataColumnSupplier(
mapper,
NestedDataColumnSerializer.STRING_DICTIONARY_FILE_NAME
);
- dictionary = GenericIndexed.read(stringDictionaryBuffer, GenericIndexed.STRING_STRATEGY, mapper);
+
+ final int dictionaryStartPosition = stringDictionaryBuffer.position();
+ final byte dictionaryVersion = stringDictionaryBuffer.get();
+
+ if (dictionaryVersion == EncodedStringDictionaryWriter.VERSION) {
+ final byte encodingId = stringDictionaryBuffer.get();
+ if (encodingId == StringEncodingStrategy.FRONT_CODED_ID) {
+ frontCodedDictionary = FrontCodedIndexed.read(stringDictionaryBuffer, metadata.getByteOrder());
+ dictionary = null;
+ } else if (encodingId == StringEncodingStrategy.UTF8_ID) {
+ // this cannot happen naturally right now since generic indexed is written in the 'legacy' format, but
+ // this provides backwards compatibility should we switch at some point in the future to always
+ // writing dictionaryVersion
+ dictionary = GenericIndexed.read(stringDictionaryBuffer, GenericIndexed.BYTE_BUFFER_STRATEGY, mapper);
+ frontCodedDictionary = null;
Review Comment:
the answer is probably somewhere in the code but I didn't find it. why is frontCodedDictionary a supplier when dictionary is not?
##########
processing/src/main/java/org/apache/druid/segment/column/IndexedStringDruidPredicateIndex.java:
##########
@@ -0,0 +1,107 @@
+/*
+ * 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.druid.segment.column;
+
+import com.google.common.base.Predicate;
+import org.apache.druid.collections.bitmap.BitmapFactory;
+import org.apache.druid.collections.bitmap.ImmutableBitmap;
+import org.apache.druid.query.filter.DruidPredicateFactory;
+import org.apache.druid.segment.data.Indexed;
+
+import javax.annotation.Nullable;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+public final class IndexedStringDruidPredicateIndex<TDictionary extends Indexed<String>> implements DruidPredicateIndex
+{
+ private final BitmapFactory bitmapFactory;
+ private final TDictionary dictionary;
+ private final Indexed<ImmutableBitmap> bitmaps;
+
+ public IndexedStringDruidPredicateIndex(
+ BitmapFactory bitmapFactory,
+ TDictionary dictionary,
+ Indexed<ImmutableBitmap> bitmaps
+ )
+ {
+ this.bitmapFactory = bitmapFactory;
+ this.dictionary = dictionary;
+ this.bitmaps = bitmaps;
+ }
+
+ @Override
+ public BitmapColumnIndex forPredicate(DruidPredicateFactory matcherFactory)
+ {
+ return new SimpleImmutableBitmapIterableIndex()
+ {
+ @Override
+ public Iterable<ImmutableBitmap> getBitmapIterable()
+ {
+ return () -> new Iterator<ImmutableBitmap>()
+ {
+ final Predicate<String> stringPredicate = matcherFactory.makeStringPredicate();
+ final Iterator<String> iterator = dictionary.iterator();
+ @Nullable
+ String next = null;
+ boolean nextSet = false;
+
+ @Override
+ public boolean hasNext()
+ {
+ if (!nextSet) {
+ findNext();
+ }
+ return nextSet;
+ }
+
+ @Override
+ public ImmutableBitmap next()
+ {
+ if (!nextSet) {
+ findNext();
+ if (!nextSet) {
+ throw new NoSuchElementException();
+ }
+ }
Review Comment:
```suggestion
if (!hasNext()) {
throw new NoSuchElementException();
}
```
##########
processing/src/main/java/org/apache/druid/segment/column/IndexedUtf8ValueSetIndex.java:
##########
@@ -0,0 +1,249 @@
+/*
+ * 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.druid.segment.column;
+
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Iterators;
+import com.google.common.collect.PeekingIterator;
+import org.apache.druid.collections.bitmap.BitmapFactory;
+import org.apache.druid.collections.bitmap.ImmutableBitmap;
+import org.apache.druid.java.util.common.ByteBufferUtils;
+import org.apache.druid.java.util.common.StringUtils;
+import org.apache.druid.query.BitmapResultFactory;
+import org.apache.druid.segment.data.Indexed;
+
+import javax.annotation.Nullable;
+import java.nio.ByteBuffer;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.SortedSet;
+
+public final class IndexedUtf8ValueSetIndex<TDictionary extends Indexed<ByteBuffer>>
+ implements StringValueSetIndex, Utf8ValueSetIndex
+{
+ // This determines the cut-off point to swtich the merging algorithm from doing binary-search per element in the value
+ // set to doing a sorted merge algorithm between value set and dictionary. The ratio here represents the ratio b/w
+ // the number of elements in value set and the number of elements in the dictionary. The number has been derived
+ // using benchmark in https://github.com/apache/druid/pull/13133. If the ratio is higher than the threshold, we use
+ // sorted merge instead of binary-search based algorithm.
+ private static final double SORTED_MERGE_RATIO_THRESHOLD = 0.12D;
+ private static final int SIZE_WORTH_CHECKING_MIN = 8;
+ private static final Comparator<ByteBuffer> COMPARATOR = ByteBufferUtils.unsignedComparator();
+
+ private final BitmapFactory bitmapFactory;
+ private final TDictionary dictionary;
+ private final Indexed<ImmutableBitmap> bitmaps;
+
+ public IndexedUtf8ValueSetIndex(
+ BitmapFactory bitmapFactory,
+ TDictionary dictionary,
+ Indexed<ImmutableBitmap> bitmaps
+ )
+ {
+ this.bitmapFactory = bitmapFactory;
+ this.dictionary = dictionary;
+ this.bitmaps = bitmaps;
+ }
+
+ @Override
+ public BitmapColumnIndex forValue(@Nullable String value)
+ {
+ return new SimpleBitmapColumnIndex()
+ {
+ @Override
+ public double estimateSelectivity(int totalRows)
+ {
+ return Math.min(1, (double) getBitmapForValue().size() / totalRows);
+ }
+
+ @Override
+ public <T> T computeBitmapResult(BitmapResultFactory<T> bitmapResultFactory)
+ {
+
+ return bitmapResultFactory.wrapDimensionValue(getBitmapForValue());
+ }
+
+ private ImmutableBitmap getBitmapForValue()
+ {
+ final ByteBuffer valueUtf8 = value == null ? null : ByteBuffer.wrap(StringUtils.toUtf8(value));
+ final int idx = dictionary.indexOf(valueUtf8);
+ return getBitmap(idx);
+ }
+ };
+ }
+
+ @Override
+ public BitmapColumnIndex forSortedValues(SortedSet<String> values)
+ {
+ return getBitmapColumnIndexForSortedIterableUtf8(
+ Iterables.transform(
+ values,
+ input -> input != null ? ByteBuffer.wrap(StringUtils.toUtf8(input)) : null
+ ),
+ values.size()
+ );
+ }
+
+ @Override
+ public BitmapColumnIndex forSortedValuesUtf8(SortedSet<ByteBuffer> valuesUtf8)
+ {
+ final SortedSet<ByteBuffer> tailSet;
+
+ if (valuesUtf8.size() >= SIZE_WORTH_CHECKING_MIN) {
+ final ByteBuffer minValueInColumn = dictionary.get(0);
+ tailSet = valuesUtf8.tailSet(minValueInColumn);
+ } else {
+ tailSet = valuesUtf8;
+ }
+
+ return getBitmapColumnIndexForSortedIterableUtf8(tailSet, tailSet.size());
+ }
+
+ private ImmutableBitmap getBitmap(int idx)
+ {
+ if (idx < 0) {
+ return bitmapFactory.makeEmptyImmutableBitmap();
+ }
+
+ final ImmutableBitmap bitmap = bitmaps.get(idx);
+ return bitmap == null ? bitmapFactory.makeEmptyImmutableBitmap() : bitmap;
+ }
+
+ /**
+ * Helper used by {@link #forSortedValues} and {@link #forSortedValuesUtf8}.
+ */
+ private BitmapColumnIndex getBitmapColumnIndexForSortedIterableUtf8(Iterable<ByteBuffer> valuesUtf8, int size)
+ {
+ // for large number of in-filter values in comparison to the dictionary size, use the sorted merge algorithm.
+ if (size > SORTED_MERGE_RATIO_THRESHOLD * dictionary.size()) {
+ return new SimpleImmutableBitmapIterableIndex()
+ {
+ @Override
+ public Iterable<ImmutableBitmap> getBitmapIterable()
+ {
+ return () -> new Iterator<ImmutableBitmap>()
+ {
+ final PeekingIterator<ByteBuffer> valuesIterator = Iterators.peekingIterator(valuesUtf8.iterator());
+ final PeekingIterator<ByteBuffer> dictionaryIterator = Iterators.peekingIterator(dictionary.iterator());
+ int next = -1;
+ int idx = 0;
+
+ @Override
+ public boolean hasNext()
+ {
+ if (next < 0) {
+ findNext();
+ }
+ return next >= 0;
+ }
+
+ @Override
+ public ImmutableBitmap next()
+ {
+ if (next < 0) {
+ findNext();
+ if (next < 0) {
+ throw new NoSuchElementException();
+ }
+ }
+ final int swap = next;
+ next = -1;
+ return getBitmap(swap);
+ }
+
+ private void findNext()
+ {
+ while (next < 0 && valuesIterator.hasNext() && dictionaryIterator.hasNext()) {
+ final ByteBuffer nextValue = valuesIterator.peek();
+ final ByteBuffer nextDictionaryKey = dictionaryIterator.peek();
+ final int comparison = COMPARATOR.compare(nextValue, nextDictionaryKey);
+ if (comparison == 0) {
+ next = idx;
+ valuesIterator.next();
+ break;
+ } else if (comparison < 0) {
+ valuesIterator.next();
+ } else {
+ dictionaryIterator.next();
+ idx++;
+ }
+ }
+ }
+ };
+ }
+ };
+ }
+
+ // if the size of in-filter values is less than the threshold percentage of dictionary size, then use binary search
+ // based lookup per value. The algorithm works well for smaller number of values.
+ return new SimpleImmutableBitmapIterableIndex()
+ {
+ @Override
+ public Iterable<ImmutableBitmap> getBitmapIterable()
+ {
+ return () -> new Iterator<ImmutableBitmap>()
+ {
+ final int dictionarySize = dictionary.size();
+ final Iterator<ByteBuffer> iterator = valuesUtf8.iterator();
+ int next = -1;
+
+ @Override
+ public boolean hasNext()
+ {
+ if (next < 0) {
+ findNext();
+ }
+ return next >= 0;
+ }
+
+ @Override
+ public ImmutableBitmap next()
+ {
+ if (next < 0) {
+ findNext();
+ if (next < 0) {
+ throw new NoSuchElementException();
+ }
+ }
+ final int swap = next;
+ next = -1;
+ return getBitmap(swap);
+ }
+
+ private void findNext()
+ {
+ while (next < 0 && iterator.hasNext()) {
+ ByteBuffer nextValue = iterator.next();
+ next = dictionary.indexOf(nextValue);
+
+ if (next == -dictionarySize - 1) {
+ // nextValue is past the end of the dictionary.
Review Comment:
```suggestion
// nextValue is past the end of the dictionary and we can break early instead of going through all values in iterator
```
I know that it might be obvious but took me a bit of time to connect the dots :)
##########
processing/src/main/java/org/apache/druid/segment/data/FrontCodedIndexed.java:
##########
@@ -0,0 +1,491 @@
+/*
+ * 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.druid.segment.data;
+
+import com.google.common.base.Preconditions;
+import com.google.common.base.Supplier;
+import org.apache.druid.common.config.NullHandling;
+import org.apache.druid.java.util.common.ISE;
+import org.apache.druid.query.monomorphicprocessing.RuntimeShapeInspector;
+
+import javax.annotation.Nullable;
+import java.nio.ByteBuffer;
+import java.nio.ByteOrder;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+/**
+ * {@link Indexed} specialized for storing variable-width binary values (such as utf8 encoded strings), which must be
+ * sorted and unique, using 'front coding'. Front coding is a type of delta encoding for byte arrays, where sorted
+ * values are grouped into buckets. The first value of the bucket is written entirely, and remaining values are stored
+ * as a pair of an integer which indicates how much of the first byte array of the bucket to use as a prefix, followed
+ * by the remaining bytes after the prefix to complete the value.
+ *
+ * Getting a value first picks the appropriate bucket, finds its offset in the underlying buffer, then scans the bucket
+ * values to seek to the correct position of the value within the bucket in order to reconstruct it using the prefix
+ * length.
+ *
+ * Finding the index of a value involves binary searching the first values of each bucket to find the correct bucket,
+ * then a linear scan within the bucket to find the matching value (or negative insertion point -1 for values that
+ * are not present).
+ *
+ * The value iterator reads an entire bucket at a time, reconstructing the values into an array to iterate within the
+ * bucket before moving onto the next bucket as the iterator is consumed.
Review Comment:
> copy the layout description from the PR description into Javadoc here.
+1. GenericIndexed has a similar description.
##########
processing/src/main/java/org/apache/druid/segment/data/FrontCodedIndexed.java:
##########
@@ -0,0 +1,491 @@
+/*
+ * 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.druid.segment.data;
+
+import com.google.common.base.Preconditions;
+import com.google.common.base.Supplier;
+import org.apache.druid.common.config.NullHandling;
+import org.apache.druid.java.util.common.ISE;
+import org.apache.druid.query.monomorphicprocessing.RuntimeShapeInspector;
+
+import javax.annotation.Nullable;
+import java.nio.ByteBuffer;
+import java.nio.ByteOrder;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+/**
+ * {@link Indexed} specialized for storing variable-width binary values (such as utf8 encoded strings), which must be
+ * sorted and unique, using 'front coding'. Front coding is a type of delta encoding for byte arrays, where sorted
+ * values are grouped into buckets. The first value of the bucket is written entirely, and remaining values are stored
+ * as a pair of an integer which indicates how much of the first byte array of the bucket to use as a prefix, followed
+ * by the remaining bytes after the prefix to complete the value.
+ *
+ * Getting a value first picks the appropriate bucket, finds its offset in the underlying buffer, then scans the bucket
+ * values to seek to the correct position of the value within the bucket in order to reconstruct it using the prefix
+ * length.
+ *
+ * Finding the index of a value involves binary searching the first values of each bucket to find the correct bucket,
+ * then a linear scan within the bucket to find the matching value (or negative insertion point -1 for values that
+ * are not present).
+ *
+ * The value iterator reads an entire bucket at a time, reconstructing the values into an array to iterate within the
+ * bucket before moving onto the next bucket as the iterator is consumed.
+ */
+public final class FrontCodedIndexed implements Indexed<ByteBuffer>
+{
+ public static Supplier<FrontCodedIndexed> read(ByteBuffer buffer, ByteOrder ordering)
+ {
+ final ByteBuffer orderedBuffer = buffer.asReadOnlyBuffer().order(ordering);
+ final byte version = orderedBuffer.get();
+ Preconditions.checkArgument(version == 0, "only V0 exists, encountered " + version);
+ final int bucketSize = orderedBuffer.get();
+ final boolean hasNull = NullHandling.IS_NULL_BYTE == orderedBuffer.get();
+ final int numValues = VByte.readInt(orderedBuffer);
+ // size of offsets + values
+ final int size = VByte.readInt(orderedBuffer);
+ final int offsetsPosition = orderedBuffer.position();
+ // move position to end of buffer
+ buffer.position(offsetsPosition + size);
+
+ final int numBuckets = (int) Math.ceil((double) numValues / (double) bucketSize);
+ final int adjustIndex = hasNull ? 1 : 0;
+ final int div = Integer.numberOfTrailingZeros(bucketSize);
+ final int rem = bucketSize - 1;
+ return () -> new FrontCodedIndexed(
+ orderedBuffer,
+ bucketSize,
+ numBuckets,
+ (numValues & rem) == 0 ? bucketSize : numValues & rem,
+ hasNull,
+ numValues + adjustIndex,
+ adjustIndex,
+ div,
+ rem,
+ offsetsPosition,
+ offsetsPosition + ((numBuckets - 1) * Integer.BYTES)
+ );
+ }
+
+ private final ByteBuffer buffer;
+ private final int adjustedNumValues;
+ private final int adjustIndex;
+ private final int bucketSize;
+ private final int numBuckets;
+ private final int div;
+ private final int rem;
+ private final int offsetsPosition;
+ private final int bucketsPosition;
+ private final boolean hasNull;
+ private final int lastBucketNumValues;
+
+ private FrontCodedIndexed(
+ ByteBuffer buffer,
+ int bucketSize,
+ int numBuckets,
+ int lastBucketNumValues,
+ boolean hasNull,
+ int adjustedNumValues,
+ int adjustIndex,
+ int div,
+ int rem,
+ int offsetsPosition,
+ int bucketsPosition
+ )
+ {
+ if (Integer.bitCount(bucketSize) != 1) {
+ throw new ISE("bucketSize must be a power of two but was[%,d]", bucketSize);
+ }
+ this.buffer = buffer.asReadOnlyBuffer().order(buffer.order());
+ this.bucketSize = bucketSize;
+ this.hasNull = hasNull;
+ this.adjustedNumValues = adjustedNumValues;
+ this.adjustIndex = adjustIndex;
+ this.div = div;
+ this.rem = rem;
+ this.numBuckets = numBuckets;
+ this.offsetsPosition = offsetsPosition;
+ this.bucketsPosition = bucketsPosition;
+ this.lastBucketNumValues = lastBucketNumValues;
+ }
+
+ @Override
+ public int size()
+ {
+ return adjustedNumValues;
+ }
+
+ @Nullable
+ @Override
+ public ByteBuffer get(int index)
+ {
+ if (hasNull && index == 0) {
+ return null;
+ }
+
+ // due to vbyte encoding, the null value is not actually stored in the bucket (no negative values), so we adjust
+ // the index
+ final int adjustedIndex = index - adjustIndex;
+ // find the bucket which contains the value with maths
+ final int bucket = adjustedIndex >> div;
+ final int bucketIndex = adjustedIndex & rem;
+ final int offset = getBucketOffset(bucket);
+ buffer.position(offset);
+ return getFromBucket(buffer, bucketIndex);
+ }
+
+ @Override
+ public int indexOf(@Nullable ByteBuffer value)
+ {
+ // performs binary search using the first values of each bucket to locate the appropriate bucket, and then does
+ // a linear scan to find the value within the bucket
+ if (value == null) {
+ return hasNull ? 0 : -1;
+ }
+
+ int minBucketIndex = 0;
+ int maxBucketIndex = numBuckets - 1;
+ while (minBucketIndex < maxBucketIndex) {
+ int currentBucket = (minBucketIndex + maxBucketIndex) >>> 1;
+ int currBucketFirstValueIndex = currentBucket * bucketSize;
+
+ // compare against first value in "current" bucket
+ final int offset = getBucketOffset(currentBucket);
+ buffer.position(offset);
+ final int firstLength = VByte.readInt(buffer);
+ final int firstOffset = buffer.position();
+ int comparison = compareBucketFirstValue(buffer, firstLength, value);
+ // save the length of the shared prefix with the first value of the bucket and the value to match so we
+ // can use it later to skip over all values in the bucket that share a longer prefix with the first value
+ // (the bucket is sorted, so the prefix length gets smaller as values increase)
+ final int sharedPrefix = buffer.position() - firstOffset;
+ if (comparison == 0) {
+ if (firstLength == value.remaining()) {
+ // it turns out that the first value in current bucket is what we are looking for, short circuit
+ return currBucketFirstValueIndex + adjustIndex;
+ } else {
+ comparison = Integer.compare(firstLength, value.remaining());
+ }
+ }
+
+ // we also compare against the adjacent bucket to determine if the value is actually in this bucket or
+ // if we need to keep searching buckets
+ final int nextOffset = getBucketOffset(currentBucket + 1);
Review Comment:
that wouldn't happen since `maxBucketIndex` has to be greater than `minBucketIndex` otherwise code won't enter this loop. and currentBucketIndex would come out to be less than maxBucketIndex, based on the calculation.
--
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: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org