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/03/07 21:45:34 UTC
[GitHub] [druid] clintropolis opened a new pull request #12315: push value range and set index get operations into BitmapIndex
clintropolis opened a new pull request #12315:
URL: https://github.com/apache/druid/pull/12315
### Description
This PR updates the `BitmapIndex` interface to add several "value" based bitmap retrieval methods, to push the logic of how these are collected into the `BitmapIndex` implementation, instead of leaking details about the underlying dictionaries (such as GenericIndexed.indexOf returning position or -insertion point).
```
ImmutableBitmap getBitmapForValue(@Nullable String value);
default Iterable<ImmutableBitmap> getBitmapsInRange(
@Nullable String startValue,
boolean startStrict,
@Nullable String endValue,
boolean endStrict
)
{
return getBitmapsInRange(startValue, startStrict, endValue, endStrict, (index) -> true);
}
Iterable<ImmutableBitmap> getBitmapsInRange(
@Nullable String startValue,
boolean startStrict,
@Nullable String endValue,
boolean endStrict,
IntPredicate matcher
);
Iterable<ImmutableBitmap> getBitmapsForValues(Set<String> values);
```
I consider this the first step of some work I'd like to do on allowing indexes on other types of values, such as numbers and complex types.
<hr>
##### Key changed/added classes in this PR
* `BitmapIndex`
* `BitmapIndexSelector`
* `StringBitmapIndexColumnPartSupplier`
* `InDimFilter`
* `BoundFilter`
* `LikeFilter`
<hr>
This PR has:
- [ ] been self-reviewed.
- [ ] using the [concurrency checklist](https://github.com/apache/druid/blob/master/dev/code-review/concurrency.md) (Remove this item if the PR doesn't have any relation to concurrency.)
- [ ] added documentation for new or modified features or behaviors.
- [ ] added Javadocs for most classes and all non-trivial methods. Linked related entities via Javadoc links.
- [ ] added or updated version, license, or notice information in [licenses.yaml](https://github.com/apache/druid/blob/master/dev/license.md)
- [ ] added comments explaining the "why" and the intent of the code wherever would not be obvious for an unfamiliar reader.
- [ ] added unit tests or modified existing tests to cover new code paths, ensuring the threshold for [code coverage](https://github.com/apache/druid/blob/master/dev/code-review/code-coverage.md) is met.
- [ ] added integration tests.
- [ ] been tested in a test Druid cluster.
--
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
[GitHub] [druid] gianm commented on a change in pull request #12315: push value range and set index get operations into BitmapIndex
Posted by GitBox <gi...@apache.org>.
gianm commented on a change in pull request #12315:
URL: https://github.com/apache/druid/pull/12315#discussion_r822098147
##########
File path: processing/src/main/java/org/apache/druid/segment/ColumnSelectorBitmapIndexSelector.java
##########
@@ -264,6 +265,78 @@ public ImmutableBitmap getBitmap(int idx)
return bitmapFactory.makeEmptyImmutableBitmap();
}
}
+
+ @Override
+ public ImmutableBitmap getBitmapForValue(@Nullable String value)
+ {
+ if (NullHandling.isNullOrEquivalent(value)) {
+ return bitmapFactory.complement(bitmapFactory.makeEmptyImmutableBitmap(), getNumRows());
+ } else {
+ return bitmapFactory.makeEmptyImmutableBitmap();
+ }
+ }
+
+ @Override
+ public Iterable<ImmutableBitmap> getBitmapsInRange(
Review comment:
This code block is for a bitmap selector on an all-null column, right? It looks overly complex for that. Shouldn't it check if `matcher` matches `null` and then either return a single `getBitmap(0)`, or no bitmaps, appropriately?
##########
File path: processing/src/main/java/org/apache/druid/query/dimension/PredicateFilteredDimensionSelector.java
##########
@@ -97,7 +97,7 @@ public void inspectRuntimeShape(RuntimeShapeInspector inspector)
@Override
public ValueMatcher makeValueMatcher(final Predicate<String> matcherPredicate)
{
- final boolean matchNull = predicate.apply(null);
+ final boolean matchNull = predicate.apply(null) && matcherPredicate.apply(null);
Review comment:
Also a cool bug.
##########
File path: processing/src/main/java/org/apache/druid/segment/serde/StringBitmapIndexColumnPartSupplier.java
##########
@@ -94,6 +101,179 @@ public ImmutableBitmap getBitmap(int idx)
final ImmutableBitmap bitmap = bitmaps.get(idx);
return bitmap == null ? bitmapFactory.makeEmptyImmutableBitmap() : bitmap;
}
+
+ @Override
+ public ImmutableBitmap getBitmapForValue(@Nullable String value)
+ {
+ final int idx = dictionary.indexOf(value);
+ return getBitmap(idx);
+ }
+
+ @Override
+ public Iterable<ImmutableBitmap> getBitmapsInRange(
+ @Nullable String startValue,
+ boolean startStrict,
+ @Nullable String endValue,
+ boolean endStrict
+ )
+ {
+ int startIndex, endIndex;
+ if (startValue == null) {
+ startIndex = 0;
+ } else {
+ final int found = dictionary.indexOf(NullHandling.emptyToNullIfNeeded(startValue));
+ if (found >= 0) {
+ startIndex = startStrict ? found + 1 : found;
+ } else {
+ startIndex = -(found + 1);
+ }
+ }
+
+ if (endValue == null) {
+ endIndex = dictionary.size();
+ } else {
+ final int found = dictionary.indexOf(NullHandling.emptyToNullIfNeeded(endValue));
+ if (found >= 0) {
+ endIndex = endStrict ? found : found + 1;
+ } else {
+ endIndex = -(found + 1);
+ }
+ }
+
+ endIndex = startIndex > endIndex ? startIndex : endIndex;
+ final IntIterator rangeIterator = IntListUtils.fromTo(startIndex, endIndex).iterator();
+ return () -> new Iterator<ImmutableBitmap>()
Review comment:
This isn't really a proper Iterable. It will only be iterable once; a proper Iterable should be re-iterable. If it doesn't need to be re-iterable, it may be simpler to return an Iterator instead of an Iterable.
##########
File path: processing/src/main/java/org/apache/druid/query/dimension/PredicateFilteredDimensionSelector.java
##########
@@ -81,8 +81,8 @@ public boolean matches()
nullRow = false;
}
}
- // null should match empty rows in multi-value columns
- return nullRow && value == null;
+ // null should match empty rows in multi-value columns if predicate matches null
+ return nullRow && value == null && predicate.apply(null);
Review comment:
Cache `predicate.apply(null)`?
(Cool bug, btw.)
--
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
[GitHub] [druid] clintropolis commented on pull request #12315: push value range and set index get operations into BitmapIndex
Posted by GitBox <gi...@apache.org>.
clintropolis commented on pull request #12315:
URL: https://github.com/apache/druid/pull/12315#issuecomment-1061334506
turns out there were still a few users of `BitmapIndexSelector.getDimensionValues`, so can't remove yet, however I went ahead and re-arranged the "like" filter as discussed, which I think seems nicer
--
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
[GitHub] [druid] clintropolis commented on pull request #12315: push value range and set index get operations into BitmapIndex
Posted by GitBox <gi...@apache.org>.
clintropolis commented on pull request #12315:
URL: https://github.com/apache/druid/pull/12315#issuecomment-1061310060
I actually think the "like" filter here could be done a bit differently and could eliminate the need for `BitmapIndex.getIndex` which is now only used to power `BitmapIndexSelector.getDimensionValues`, which itself is only used by the `LikeFilter` to call `(index) -> likeMatcher.matchesSuffixOnly(dimValues, index)` to filter the values of `BitmapIndex.getBitmapsInRange`, the version of which is only called by the "like" filter.... I will see if I can further simplify things
--
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
[GitHub] [druid] clintropolis commented on a change in pull request #12315: push value range and set index get operations into BitmapIndex
Posted by GitBox <gi...@apache.org>.
clintropolis commented on a change in pull request #12315:
URL: https://github.com/apache/druid/pull/12315#discussion_r822448662
##########
File path: processing/src/main/java/org/apache/druid/segment/data/Indexed.java
##########
@@ -55,8 +55,8 @@
int indexOf(@Nullable T value);
/**
- * Returns the index of "value" in some object whose values are accessible by index some {@link IndexedGetter}, or
- * (-(insertion point) - 1) if the value is not present, in the manner of Arrays.binarySearch.
+ * Returns the index of "value" in some object in the {@link Indexed}, or (-(insertion point) - 1) if the value is
+ * not present, in the manner of Arrays.binarySearch.
Review comment:
i just killed this method and moved this logic into `GenericIndexed` which was the only caller again after the changes in this PR. I think it is ok for `GenericIndexed.indexOf` to mention that it has this contract for `indexOf`, since it is an implementation detail that the `BitmapIndex` implementation of `StringBitmapIndexColumnPartSupplier` cares about.
--
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
[GitHub] [druid] clintropolis commented on pull request #12315: push value range and set index get operations into BitmapIndex
Posted by GitBox <gi...@apache.org>.
clintropolis commented on pull request #12315:
URL: https://github.com/apache/druid/pull/12315#issuecomment-1061169076
marked WIP because some tests I added for `ListFilteredVirtualColumn` are failing for "deny" lists. However, these tests also fail when not using the bitmap index at all, so I think there is some underlying bug unrelated to the changes in this PR, which I'm still looking into.
--
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
[GitHub] [druid] lgtm-com[bot] commented on pull request #12315: push value range and set index get operations into BitmapIndex
Posted by GitBox <gi...@apache.org>.
lgtm-com[bot] commented on pull request #12315:
URL: https://github.com/apache/druid/pull/12315#issuecomment-1061227533
This pull request **introduces 1 alert** when merging 21a35071ac44373d00a30f73ba6afd1cd4ad12a3 into 28f8bcce9b304fd123126073619ffd5f60f59f20 - [view on LGTM.com](https://lgtm.com/projects/g/apache/druid/rev/pr-7f723cb678494efbe8c7810b5b95e0b3373367d0)
**new alerts:**
* 1 for Spurious Javadoc @param tags
--
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
[GitHub] [druid] clintropolis commented on a change in pull request #12315: push value range and set index get operations into BitmapIndex
Posted by GitBox <gi...@apache.org>.
clintropolis commented on a change in pull request #12315:
URL: https://github.com/apache/druid/pull/12315#discussion_r822452684
##########
File path: processing/src/main/java/org/apache/druid/segment/virtual/ListFilteredVirtualColumn.java
##########
@@ -252,22 +256,172 @@ public BitmapFactory getBitmapFactory()
return delegate.getBitmapFactory();
}
+ @Override
+ public int getCardinality()
+ {
+ return idMapping.getValueCardinality();
+ }
+
+ @Override
+ public int getIndex(@Nullable String value)
+ {
+ return getReverseIndex(value);
+ }
+
@Override
public ImmutableBitmap getBitmap(int idx)
{
return delegate.getBitmap(idMapping.getReverseId(idx));
}
@Override
- public int getCardinality()
+ public ImmutableBitmap getBitmapForValue(@Nullable String value)
{
- return idMapping.getValueCardinality();
+ if (getReverseIndex(value) < 0) {
+ return delegate.getBitmap(-1);
+ }
+ return delegate.getBitmapForValue(value);
}
@Override
- public int getIndex(@Nullable String value)
+ public Iterable<ImmutableBitmap> getBitmapsInRange(
Review comment:
>For the "include" case, the implementations of these methods seem like they should be able to be a lot simpler. The normal use case provides a much smaller list of things to show, it seems like we could quite rapidly filter through that list and then delegate to something that uses that list.
I _think_ this is already doing this, the range iterated over here is the cardinality of the idLookup, not the dictionary of the delegate column, so it only considers ranges of the filtered values. There might be room for improvement, especially in the deny case, though I think it probably would need bigger changes to `ListFilteredVirtualColumn` and maybe best to do as a follow-up.
--
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
[GitHub] [druid] imply-cheddar commented on a change in pull request #12315: push value range and set index get operations into BitmapIndex
Posted by GitBox <gi...@apache.org>.
imply-cheddar commented on a change in pull request #12315:
URL: https://github.com/apache/druid/pull/12315#discussion_r822353278
##########
File path: processing/src/main/java/org/apache/druid/segment/column/BitmapIndex.java
##########
@@ -23,28 +23,85 @@
import org.apache.druid.collections.bitmap.ImmutableBitmap;
import javax.annotation.Nullable;
+import java.util.Set;
+import java.util.function.Predicate;
/**
+ * Provides a mechanism to get {@link ImmutableBitmap} for a value, or {@link Iterable} of {@link ImmutableBitmap}
+ * for a range or exact set of values, the set bits of which correspond to which rows contain the matching values.
+ *
+ * Used to power {@link org.apache.druid.segment.BitmapOffset} and
+ * {@link org.apache.druid.segment.vector.BitmapVectorOffset} which are used with column cursors for fast filtering
+ * of indexed values.
+ *
+ * The column must be ingested with a bitmap index for filters to use them and to participate in this "pre-filtering"
+ * step when scanning segments
+ *
+ * @see org.apache.druid.segment.QueryableIndexStorageAdapter#analyzeFilter
*/
public interface BitmapIndex
{
+ /**
+ * Get the cardinality of the underlying value dictionary
+ */
int getCardinality();
+ /**
+ * Get the value in the underlying value dictionary of the specified dictionary id
+ */
@Nullable
String getValue(int index);
+ /**
+ * Returns true if the underlying value dictionary has nulls
+ */
boolean hasNulls();
BitmapFactory getBitmapFactory();
/**
- * Returns the index of "value" in this BitmapIndex, or (-(insertion point) - 1) if the value is not
- * present, in the manner of Arrays.binarySearch.
- *
- * @param value value to search for
- * @return index of value, or negative number equal to (-(insertion point) - 1).
+ * Returns the index of "value" in this BitmapIndex, or a negative value, if not present in the underlying dictionary
*/
int getIndex(@Nullable String value);
+ /**
+ * Get the {@link ImmutableBitmap} for dictionary id of the underlying dictionary
+ */
ImmutableBitmap getBitmap(int idx);
+
+ /**
+ * Get the {@link ImmutableBitmap} corresponding to the supplied value
+ */
+ ImmutableBitmap getBitmapForValue(@Nullable String value);
+
+ /**
+ * Get an {@link Iterable} of {@link ImmutableBitmap} corresponding to the values supplied in the specified range
+ */
+ default Iterable<ImmutableBitmap> getBitmapsInRange(
Review comment:
I believe that these are always Union'd together and I'm not really seeing a great reason for why this shouldn't just return a single `ImmutableBitmap` that has already been unioned instead of an Iterable.
##########
File path: processing/src/main/java/org/apache/druid/segment/column/BitmapIndex.java
##########
@@ -23,28 +23,85 @@
import org.apache.druid.collections.bitmap.ImmutableBitmap;
import javax.annotation.Nullable;
+import java.util.Set;
+import java.util.function.Predicate;
/**
+ * Provides a mechanism to get {@link ImmutableBitmap} for a value, or {@link Iterable} of {@link ImmutableBitmap}
+ * for a range or exact set of values, the set bits of which correspond to which rows contain the matching values.
+ *
+ * Used to power {@link org.apache.druid.segment.BitmapOffset} and
+ * {@link org.apache.druid.segment.vector.BitmapVectorOffset} which are used with column cursors for fast filtering
+ * of indexed values.
+ *
+ * The column must be ingested with a bitmap index for filters to use them and to participate in this "pre-filtering"
+ * step when scanning segments
+ *
+ * @see org.apache.druid.segment.QueryableIndexStorageAdapter#analyzeFilter
*/
public interface BitmapIndex
{
+ /**
+ * Get the cardinality of the underlying value dictionary
+ */
int getCardinality();
+ /**
+ * Get the value in the underlying value dictionary of the specified dictionary id
+ */
@Nullable
String getValue(int index);
+ /**
+ * Returns true if the underlying value dictionary has nulls
+ */
boolean hasNulls();
BitmapFactory getBitmapFactory();
/**
- * Returns the index of "value" in this BitmapIndex, or (-(insertion point) - 1) if the value is not
- * present, in the manner of Arrays.binarySearch.
- *
- * @param value value to search for
- * @return index of value, or negative number equal to (-(insertion point) - 1).
+ * Returns the index of "value" in this BitmapIndex, or a negative value, if not present in the underlying dictionary
*/
int getIndex(@Nullable String value);
+ /**
+ * Get the {@link ImmutableBitmap} for dictionary id of the underlying dictionary
+ */
ImmutableBitmap getBitmap(int idx);
+
+ /**
+ * Get the {@link ImmutableBitmap} corresponding to the supplied value
+ */
+ ImmutableBitmap getBitmapForValue(@Nullable String value);
+
+ /**
+ * Get an {@link Iterable} of {@link ImmutableBitmap} corresponding to the values supplied in the specified range
+ */
+ default Iterable<ImmutableBitmap> getBitmapsInRange(
+ @Nullable String startValue,
+ boolean startStrict,
+ @Nullable String endValue,
+ boolean endStrict
Review comment:
It might be nice to package these things up into a holder Object of some sort so that it's a bit easier to adjust parameters if/when we need to. That could probably be done in a subsequent change though.
##########
File path: processing/src/main/java/org/apache/druid/segment/column/BitmapIndex.java
##########
@@ -23,28 +23,85 @@
import org.apache.druid.collections.bitmap.ImmutableBitmap;
import javax.annotation.Nullable;
+import java.util.Set;
+import java.util.function.Predicate;
/**
+ * Provides a mechanism to get {@link ImmutableBitmap} for a value, or {@link Iterable} of {@link ImmutableBitmap}
+ * for a range or exact set of values, the set bits of which correspond to which rows contain the matching values.
+ *
+ * Used to power {@link org.apache.druid.segment.BitmapOffset} and
+ * {@link org.apache.druid.segment.vector.BitmapVectorOffset} which are used with column cursors for fast filtering
+ * of indexed values.
+ *
+ * The column must be ingested with a bitmap index for filters to use them and to participate in this "pre-filtering"
+ * step when scanning segments
+ *
+ * @see org.apache.druid.segment.QueryableIndexStorageAdapter#analyzeFilter
*/
public interface BitmapIndex
{
+ /**
+ * Get the cardinality of the underlying value dictionary
+ */
int getCardinality();
+ /**
+ * Get the value in the underlying value dictionary of the specified dictionary id
+ */
@Nullable
String getValue(int index);
+ /**
+ * Returns true if the underlying value dictionary has nulls
+ */
boolean hasNulls();
BitmapFactory getBitmapFactory();
/**
- * Returns the index of "value" in this BitmapIndex, or (-(insertion point) - 1) if the value is not
- * present, in the manner of Arrays.binarySearch.
- *
- * @param value value to search for
- * @return index of value, or negative number equal to (-(insertion point) - 1).
+ * Returns the index of "value" in this BitmapIndex, or a negative value, if not present in the underlying dictionary
*/
int getIndex(@Nullable String value);
+ /**
+ * Get the {@link ImmutableBitmap} for dictionary id of the underlying dictionary
+ */
ImmutableBitmap getBitmap(int idx);
+
+ /**
+ * Get the {@link ImmutableBitmap} corresponding to the supplied value
+ */
+ ImmutableBitmap getBitmapForValue(@Nullable String value);
+
+ /**
+ * Get an {@link Iterable} of {@link ImmutableBitmap} corresponding to the values supplied in the specified range
+ */
+ default Iterable<ImmutableBitmap> getBitmapsInRange(
+ @Nullable String startValue,
+ boolean startStrict,
+ @Nullable String endValue,
+ boolean endStrict
+ )
+ {
+ return getBitmapsInRange(startValue, startStrict, endValue, endStrict, (index) -> true);
+ }
+
+ /**
+ * Get an {@link Iterable} of {@link ImmutableBitmap} corresponding to the values supplied in the specified range
+ * whose dictionary ids also match some predicate
+ */
+ Iterable<ImmutableBitmap> getBitmapsInRange(
+ @Nullable String startValue,
+ boolean startStrict,
+ @Nullable String endValue,
+ boolean endStrict,
+ Predicate<String> matcher
+ );
+
+ /**
+ * Get an {@link Iterable} of {@link ImmutableBitmap} corresponding to the specified set of values (if they are
+ * contained in the underlying column)
+ */
+ Iterable<ImmutableBitmap> getBitmapsForValues(Set<String> values);
Review comment:
And here on Iterable too
##########
File path: processing/src/main/java/org/apache/druid/segment/column/BitmapIndex.java
##########
@@ -23,28 +23,85 @@
import org.apache.druid.collections.bitmap.ImmutableBitmap;
import javax.annotation.Nullable;
+import java.util.Set;
+import java.util.function.Predicate;
/**
+ * Provides a mechanism to get {@link ImmutableBitmap} for a value, or {@link Iterable} of {@link ImmutableBitmap}
+ * for a range or exact set of values, the set bits of which correspond to which rows contain the matching values.
+ *
+ * Used to power {@link org.apache.druid.segment.BitmapOffset} and
+ * {@link org.apache.druid.segment.vector.BitmapVectorOffset} which are used with column cursors for fast filtering
+ * of indexed values.
+ *
+ * The column must be ingested with a bitmap index for filters to use them and to participate in this "pre-filtering"
+ * step when scanning segments
+ *
+ * @see org.apache.druid.segment.QueryableIndexStorageAdapter#analyzeFilter
*/
public interface BitmapIndex
{
+ /**
+ * Get the cardinality of the underlying value dictionary
+ */
int getCardinality();
+ /**
+ * Get the value in the underlying value dictionary of the specified dictionary id
+ */
@Nullable
String getValue(int index);
+ /**
+ * Returns true if the underlying value dictionary has nulls
+ */
boolean hasNulls();
BitmapFactory getBitmapFactory();
/**
- * Returns the index of "value" in this BitmapIndex, or (-(insertion point) - 1) if the value is not
- * present, in the manner of Arrays.binarySearch.
- *
- * @param value value to search for
- * @return index of value, or negative number equal to (-(insertion point) - 1).
+ * Returns the index of "value" in this BitmapIndex, or a negative value, if not present in the underlying dictionary
*/
int getIndex(@Nullable String value);
+ /**
+ * Get the {@link ImmutableBitmap} for dictionary id of the underlying dictionary
+ */
ImmutableBitmap getBitmap(int idx);
+
+ /**
+ * Get the {@link ImmutableBitmap} corresponding to the supplied value
+ */
+ ImmutableBitmap getBitmapForValue(@Nullable String value);
+
+ /**
+ * Get an {@link Iterable} of {@link ImmutableBitmap} corresponding to the values supplied in the specified range
+ */
+ default Iterable<ImmutableBitmap> getBitmapsInRange(
+ @Nullable String startValue,
+ boolean startStrict,
+ @Nullable String endValue,
+ boolean endStrict
+ )
+ {
+ return getBitmapsInRange(startValue, startStrict, endValue, endStrict, (index) -> true);
+ }
+
+ /**
+ * Get an {@link Iterable} of {@link ImmutableBitmap} corresponding to the values supplied in the specified range
+ * whose dictionary ids also match some predicate
+ */
+ Iterable<ImmutableBitmap> getBitmapsInRange(
Review comment:
Same comment here on Iterable
##########
File path: processing/src/main/java/org/apache/druid/segment/virtual/ListFilteredVirtualColumn.java
##########
@@ -252,22 +256,172 @@ public BitmapFactory getBitmapFactory()
return delegate.getBitmapFactory();
}
+ @Override
+ public int getCardinality()
+ {
+ return idMapping.getValueCardinality();
+ }
+
+ @Override
+ public int getIndex(@Nullable String value)
+ {
+ return getReverseIndex(value);
+ }
+
@Override
public ImmutableBitmap getBitmap(int idx)
{
return delegate.getBitmap(idMapping.getReverseId(idx));
}
@Override
- public int getCardinality()
+ public ImmutableBitmap getBitmapForValue(@Nullable String value)
{
- return idMapping.getValueCardinality();
+ if (getReverseIndex(value) < 0) {
+ return delegate.getBitmap(-1);
+ }
+ return delegate.getBitmapForValue(value);
}
@Override
- public int getIndex(@Nullable String value)
+ public Iterable<ImmutableBitmap> getBitmapsInRange(
Review comment:
For the "include" case, the implementations of these methods seem like they should be able to be a lot simpler. The normal use case provides a much smaller list of things to show, it seems like we could quite rapidly filter through that list and then delegate to something that uses that list.
The deny-list case requires different logic. But, then I wonder how important this actually is, or is the difference between the implementation that you have and this more direct implementation just a few milliseconds such that it doesn't actually matter...
##########
File path: processing/src/main/java/org/apache/druid/segment/serde/StringBitmapIndexColumnPartSupplier.java
##########
@@ -94,6 +101,179 @@ public ImmutableBitmap getBitmap(int idx)
final ImmutableBitmap bitmap = bitmaps.get(idx);
return bitmap == null ? bitmapFactory.makeEmptyImmutableBitmap() : bitmap;
}
+
+ @Override
+ public ImmutableBitmap getBitmapForValue(@Nullable String value)
+ {
+ final int idx = dictionary.indexOf(value);
+ return getBitmap(idx);
+ }
+
+ @Override
+ public Iterable<ImmutableBitmap> getBitmapsInRange(
+ @Nullable String startValue,
+ boolean startStrict,
+ @Nullable String endValue,
+ boolean endStrict
+ )
+ {
+ int startIndex, endIndex;
+ if (startValue == null) {
+ startIndex = 0;
+ } else {
+ final int found = dictionary.indexOf(NullHandling.emptyToNullIfNeeded(startValue));
+ if (found >= 0) {
+ startIndex = startStrict ? found + 1 : found;
+ } else {
+ startIndex = -(found + 1);
+ }
+ }
+
+ if (endValue == null) {
+ endIndex = dictionary.size();
+ } else {
+ final int found = dictionary.indexOf(NullHandling.emptyToNullIfNeeded(endValue));
+ if (found >= 0) {
+ endIndex = endStrict ? found : found + 1;
+ } else {
+ endIndex = -(found + 1);
+ }
+ }
+
+ endIndex = startIndex > endIndex ? startIndex : endIndex;
+ final IntIterator rangeIterator = IntListUtils.fromTo(startIndex, endIndex).iterator();
+ return () -> new Iterator<ImmutableBitmap>()
Review comment:
If you change this to only return a single Bitmap and union them here, then you don't need to worry about it ;)
##########
File path: processing/src/main/java/org/apache/druid/segment/data/Indexed.java
##########
@@ -55,8 +55,8 @@
int indexOf(@Nullable T value);
/**
- * Returns the index of "value" in some object whose values are accessible by index some {@link IndexedGetter}, or
- * (-(insertion point) - 1) if the value is not present, in the manner of Arrays.binarySearch.
+ * Returns the index of "value" in some object in the {@link Indexed}, or (-(insertion point) - 1) if the value is
+ * not present, in the manner of Arrays.binarySearch.
Review comment:
I'd personally prefer that we remove this bit of documentation. It's an implementation detail that I don't think we should try to enshrine in the docs anymore (especially after this PR)
##########
File path: processing/src/main/java/org/apache/druid/segment/data/Indexed.java
##########
@@ -65,7 +65,7 @@
*
* @return index of value, or negative number equal to (-(insertion point) - 1).
Review comment:
It's here too
--
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
[GitHub] [druid] clintropolis commented on a change in pull request #12315: push value range and set index get operations into BitmapIndex
Posted by GitBox <gi...@apache.org>.
clintropolis commented on a change in pull request #12315:
URL: https://github.com/apache/druid/pull/12315#discussion_r822286661
##########
File path: processing/src/main/java/org/apache/druid/segment/serde/StringBitmapIndexColumnPartSupplier.java
##########
@@ -94,6 +101,179 @@ public ImmutableBitmap getBitmap(int idx)
final ImmutableBitmap bitmap = bitmaps.get(idx);
return bitmap == null ? bitmapFactory.makeEmptyImmutableBitmap() : bitmap;
}
+
+ @Override
+ public ImmutableBitmap getBitmapForValue(@Nullable String value)
+ {
+ final int idx = dictionary.indexOf(value);
+ return getBitmap(idx);
+ }
+
+ @Override
+ public Iterable<ImmutableBitmap> getBitmapsInRange(
+ @Nullable String startValue,
+ boolean startStrict,
+ @Nullable String endValue,
+ boolean endStrict
+ )
+ {
+ int startIndex, endIndex;
+ if (startValue == null) {
+ startIndex = 0;
+ } else {
+ final int found = dictionary.indexOf(NullHandling.emptyToNullIfNeeded(startValue));
+ if (found >= 0) {
+ startIndex = startStrict ? found + 1 : found;
+ } else {
+ startIndex = -(found + 1);
+ }
+ }
+
+ if (endValue == null) {
+ endIndex = dictionary.size();
+ } else {
+ final int found = dictionary.indexOf(NullHandling.emptyToNullIfNeeded(endValue));
+ if (found >= 0) {
+ endIndex = endStrict ? found : found + 1;
+ } else {
+ endIndex = -(found + 1);
+ }
+ }
+
+ endIndex = startIndex > endIndex ? startIndex : endIndex;
+ final IntIterator rangeIterator = IntListUtils.fromTo(startIndex, endIndex).iterator();
+ return () -> new Iterator<ImmutableBitmap>()
Review comment:
good catch. I'm not really sure they need to be `Iterable`, I was just matching the pattern being used externally on top of `BitmapIndex`, so I just fixed it instead of changing them to `Iterator` for now, but will revisit this later.
--
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
[GitHub] [druid] clintropolis commented on a change in pull request #12315: push value range and set index get operations into BitmapIndex
Posted by GitBox <gi...@apache.org>.
clintropolis commented on a change in pull request #12315:
URL: https://github.com/apache/druid/pull/12315#discussion_r822440348
##########
File path: processing/src/main/java/org/apache/druid/segment/column/BitmapIndex.java
##########
@@ -23,28 +23,85 @@
import org.apache.druid.collections.bitmap.ImmutableBitmap;
import javax.annotation.Nullable;
+import java.util.Set;
+import java.util.function.Predicate;
/**
+ * Provides a mechanism to get {@link ImmutableBitmap} for a value, or {@link Iterable} of {@link ImmutableBitmap}
+ * for a range or exact set of values, the set bits of which correspond to which rows contain the matching values.
+ *
+ * Used to power {@link org.apache.druid.segment.BitmapOffset} and
+ * {@link org.apache.druid.segment.vector.BitmapVectorOffset} which are used with column cursors for fast filtering
+ * of indexed values.
+ *
+ * The column must be ingested with a bitmap index for filters to use them and to participate in this "pre-filtering"
+ * step when scanning segments
+ *
+ * @see org.apache.druid.segment.QueryableIndexStorageAdapter#analyzeFilter
*/
public interface BitmapIndex
{
+ /**
+ * Get the cardinality of the underlying value dictionary
+ */
int getCardinality();
+ /**
+ * Get the value in the underlying value dictionary of the specified dictionary id
+ */
@Nullable
String getValue(int index);
+ /**
+ * Returns true if the underlying value dictionary has nulls
+ */
boolean hasNulls();
BitmapFactory getBitmapFactory();
/**
- * Returns the index of "value" in this BitmapIndex, or (-(insertion point) - 1) if the value is not
- * present, in the manner of Arrays.binarySearch.
- *
- * @param value value to search for
- * @return index of value, or negative number equal to (-(insertion point) - 1).
+ * Returns the index of "value" in this BitmapIndex, or a negative value, if not present in the underlying dictionary
*/
int getIndex(@Nullable String value);
+ /**
+ * Get the {@link ImmutableBitmap} for dictionary id of the underlying dictionary
+ */
ImmutableBitmap getBitmap(int idx);
+
+ /**
+ * Get the {@link ImmutableBitmap} corresponding to the supplied value
+ */
+ ImmutableBitmap getBitmapForValue(@Nullable String value);
+
+ /**
+ * Get an {@link Iterable} of {@link ImmutableBitmap} corresponding to the values supplied in the specified range
+ */
+ default Iterable<ImmutableBitmap> getBitmapsInRange(
Review comment:
I considered this, but it was a bigger pattern change than I was hoping to deal with right now, so I'd like to save this for a follow-up.
The other thing that I'm unsure of is that currently those bitmap union operations aren't really subject to query timeout or any other sort of limiting, so it might be worth thinking on how we might add some limits to prevent a very large number of bitmap operations from running until completion. The answer may still be to push that enforcement into `BitmapIndex`, just need to think a bit more about it first.
--
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
[GitHub] [druid] gianm commented on pull request #12315: push value range and set index get operations into BitmapIndex
Posted by GitBox <gi...@apache.org>.
gianm commented on pull request #12315:
URL: https://github.com/apache/druid/pull/12315#issuecomment-1062988309
> Leaving a green checkmark instead of the gray one.
😱
--
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
[GitHub] [druid] clintropolis merged pull request #12315: push value range and set index get operations into BitmapIndex
Posted by GitBox <gi...@apache.org>.
clintropolis merged pull request #12315:
URL: https://github.com/apache/druid/pull/12315
--
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
[GitHub] [druid] clintropolis commented on a change in pull request #12315: push value range and set index get operations into BitmapIndex
Posted by GitBox <gi...@apache.org>.
clintropolis commented on a change in pull request #12315:
URL: https://github.com/apache/druid/pull/12315#discussion_r822286062
##########
File path: processing/src/main/java/org/apache/druid/segment/ColumnSelectorBitmapIndexSelector.java
##########
@@ -264,6 +265,78 @@ public ImmutableBitmap getBitmap(int idx)
return bitmapFactory.makeEmptyImmutableBitmap();
}
}
+
+ @Override
+ public ImmutableBitmap getBitmapForValue(@Nullable String value)
+ {
+ if (NullHandling.isNullOrEquivalent(value)) {
+ return bitmapFactory.complement(bitmapFactory.makeEmptyImmutableBitmap(), getNumRows());
+ } else {
+ return bitmapFactory.makeEmptyImmutableBitmap();
+ }
+ }
+
+ @Override
+ public Iterable<ImmutableBitmap> getBitmapsInRange(
Review comment:
oops yes, I meant to revisit this one. I started with copying the existing path it was taking but forgot about it; it should be better now
--
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