clintropolis commented on code in PR #12277: URL: https://github.com/apache/druid/pull/12277#discussion_r995575465
########## 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)); Review Comment: the only place we seem to truly throw it away is in `QueryableIndexStorageAdapater.canVectorize`, which calls `Filter.getBitmapColumnIndex` (which for `SelectorFilter` and `LikeFilter` ends up calling `forValue`) to see if the filter supports bitmap indexes (which means it can be vectorized even if the value matcher hasn't been vectorized), and a place in the native 'search' query that is doing a similar check in the `UseIndexesStrategy` - though for this one it could probably be re-used, since its making `ColumnIndexSelector` twice and calling `Filter.getBitmapColumnIndex` twice (this one should be fixed, but I don't really want to do in this PR, maybe later when I move index supplier to `BaseColumn`). In most cases I think `computeBitmapResult` is only going to be called once when building a cursor, and `estimateSelectivity` is only used by search queries, so i'm not sure it makes a huge difference either way? -- 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]
