You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@druid.apache.org by "LakshSingla (via GitHub)" <gi...@apache.org> on 2024/03/07 13:04:53 UTC
[PR] Unifying GroupBy strategies and grouping on complex columns (druid)
LakshSingla opened a new pull request, #16068:
URL: https://github.com/apache/druid/pull/16068
### Description
(DRAFT)
#### Release note
<!-- Give your best effort to summarize your changes in a couple of sentences aimed toward Druid users.
If your change doesn't have end user impact, you can skip this section.
For tips about how to write a good release note, see [Release notes](https://github.com/apache/druid/blob/master/CONTRIBUTING.md#release-notes).
-->
<hr>
##### Key changed/added classes in this PR
* `MyFoo`
* `OurBar`
* `TheirBaz`
<hr>
<!-- Check the items by putting "x" in the brackets for the done things. Not all of these items apply to every PR. Remove the items which are not done or not relevant to the PR. None of the items from the checklist below are strictly necessary, but it would be very helpful if you at least self-review the PR. -->
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.
- [ ] a release note entry in the PR description.
- [ ] 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
Re: [PR] Grouping on complex columns aka unifying GroupBy strategies (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on PR #16068:
URL: https://github.com/apache/druid/pull/16068#issuecomment-2068949371
I am cleaning up the dead todos, and adding a few tests soon! Should be good to go then.
--
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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1538847396
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/DimensionToIdConverter.java:
##########
@@ -0,0 +1,77 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import org.apache.druid.segment.ColumnValueSelector;
+
+import javax.annotation.Nullable;
+
+/**
+ * Interface for converters of dimension to dictionary id.
+ *
+ * This is a slightly convoluted interface because it also encapsulates the additional logic for handling multi-value
+ * dimensions. It has an additional step that converts the given dimensions to "dimension holders", which represent the
+ * multi-value holders for a given dimension.
+ * Therefore, the conversion goes from ColumnValueSelector -> DimensionHolder -> DictionaryID (for each dimension in the holder)
+ *
+ * The dimension holder is only applicable for multi-value strings.
+ * For other dimensions that cannot have multi-values the dimension holder is identical to the dimension. They can be
+ * defensively cast or homogenised, for example doubles to floats for float selectors or Long[] to Object[] for array
+ * selectors, so that the upstream callers can assume the class of the dimensions. The size of these dimensions is always 1,
+ * and only contain a value at index 0.
+ *
+ * Converting a value to its dictionary id might require building dictionaries on the fly while computing the id. The
+ * return type of the methods, except {@link #multiValueSize}, takes that into account.
+ *
+ * The implementations can pre-convert the value to the dictionaryId while extracting the dimensionHolder. Extracting
+ * dictionary id for a specific value from the (potentially multi-value dimension holder) can be done by calling
+ * {@link #getIndividualValueDictId} and passing the index to the multi-value.
+ *
+ * @see IdToDimensionConverter for converting the dictionary values back to dimensions
+ *
+ * @param <DimensionHolderType> Type of the dimension holder
+ */
+public interface DimensionToIdConverter<DimensionHolderType>
Review Comment:
👍
Currently, I am going ahead with refactoring the keymapping strategy to
a. KeyMappingGroupByColumnSelectorStrategy - For arrays, and complex types
b. KeyMappingMultiValueGroupByColumnSelectorStrategy - This would handle only strings. Upon thinking about it, it should be exactly same as the StringGroupByColumnSelectorStrategy
--
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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1540703651
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/IdToDimensionConverter.java:
##########
@@ -0,0 +1,56 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+/**
+ * Converts back the dictionaryId to the dimension value. The implementations might or might not handle
+ * {@link GroupByColumnSelectorStrategy#GROUP_BY_MISSING_VALUE}. The callers should handle those values appropriately on
+ * their own, and filter those out before trying to convert the dictionary id back to value.
+ *
+ * The encoding - decoding workflow looks like:
+ *
+ * Encoding
+ * 1. {@link DimensionToIdConverter} extracts the multi-value holder for the given row, which get's stored somewhere
+ * 2. For each entry in the multi-value object, the value gets encoded into a dictionaryId, using {@link DimensionToIdConverter#getIndividualValueDictId}
+ * 3. The callers can use this integer dictionaryID to materialize the results somewhere
+ *
+ * Decoding
+ * 1. The materialized dictionary id is deserialized back to an int, and then decoded into value using {@link #idToKey}
+ *
+ * @see DimensionToIdConverter for converting the dimensions to dictionary ids
+ *
+ * @param <DimensionType> Type of the dimension's values
+ */
+public interface IdToDimensionConverter<DimensionType>
Review Comment:
https://github.com/apache/druid/pull/16068#discussion_r1533110863 After completing this refactoring, I realized that now we only have a single implementation of Id->Dimension and Dimension->Id converters. Keeping this abstraction or removing it completely now lies on how whether or not we want to keep the stuff extendible for future dimensions having prebuilt dictionaries.
Also, I think we can't replace `DimensionToIdConverter` with `IdLookup` because the former requires tracking memory estimates as well.
--
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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1533317817
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/DimensionToIdConverter.java:
##########
@@ -0,0 +1,77 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import org.apache.druid.segment.ColumnValueSelector;
+
+import javax.annotation.Nullable;
+
+/**
+ * Interface for converters of dimension to dictionary id.
+ *
+ * This is a slightly convoluted interface because it also encapsulates the additional logic for handling multi-value
+ * dimensions. It has an additional step that converts the given dimensions to "dimension holders", which represent the
+ * multi-value holders for a given dimension.
+ * Therefore, the conversion goes from ColumnValueSelector -> DimensionHolder -> DictionaryID (for each dimension in the holder)
+ *
+ * The dimension holder is only applicable for multi-value strings.
+ * For other dimensions that cannot have multi-values the dimension holder is identical to the dimension. They can be
+ * defensively cast or homogenised, for example doubles to floats for float selectors or Long[] to Object[] for array
+ * selectors, so that the upstream callers can assume the class of the dimensions. The size of these dimensions is always 1,
+ * and only contain a value at index 0.
+ *
+ * Converting a value to its dictionary id might require building dictionaries on the fly while computing the id. The
+ * return type of the methods, except {@link #multiValueSize}, takes that into account.
+ *
+ * The implementations can pre-convert the value to the dictionaryId while extracting the dimensionHolder. Extracting
+ * dictionary id for a specific value from the (potentially multi-value dimension holder) can be done by calling
+ * {@link #getIndividualValueDictId} and passing the index to the multi-value.
+ *
+ * @see IdToDimensionConverter for converting the dictionary values back to dimensions
+ *
+ * @param <DimensionHolderType> Type of the dimension holder
+ */
+public interface DimensionToIdConverter<DimensionHolderType>
Review Comment:
> In fact, I almost wonder if we should dump all of the multi-value grouping stuff and just rewrite in GroupingEngine.process to wrap the storage adapter in an unnest if we detect any multi-value dimensions...
I think that would work, we'd need something like `UNNEST(MV_TO_ARRAY(...)))`. However, that would perhaps alter the results which equated `null` to `[]`. Also, we might not be able to use the dictionaries (if present) on top of the multi-value dimensions.
--
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
Re: [PR] Grouping on complex columns aka unifying GroupBy strategies (druid)
Posted by "cryptoe (via GitHub)" <gi...@apache.org>.
cryptoe commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1568682683
##########
sql/src/test/java/org/apache/druid/sql/calcite/CalciteGroupByQueryTest.java:
##########
@@ -0,0 +1,24 @@
+/*
+ * 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.sql.calcite;
Review Comment:
Why is this class required ?
##########
processing/src/main/java/org/apache/druid/query/dimension/ColumnSelectorStrategyFactory.java:
##########
@@ -24,5 +24,8 @@
public interface ColumnSelectorStrategyFactory<ColumnSelectorStrategyClass extends ColumnSelectorStrategy>
{
- ColumnSelectorStrategyClass makeColumnSelectorStrategy(ColumnCapabilities capabilities, ColumnValueSelector selector);
+ ColumnSelectorStrategyClass makeColumnSelectorStrategy(ColumnCapabilities capabilities, ColumnValueSelector selector, String dimension);
+
+ // TODO(laksh): Javadoc
Review Comment:
Looks like we need java docs here.
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/DictionaryBuildingGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,203 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import it.unimi.dsi.fastutil.objects.Object2IntMap;
+import org.apache.druid.error.DruidException;
+import org.apache.druid.query.groupby.epinephelinae.DictionaryBuildingUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.column.NullableTypeStrategy;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.List;
+
+/**
+ * Strategy for grouping dimensions which can have variable-width objects, and aren't backed by prebuilt dictionaries. It
+ * encapsulates the dictionary building logic, along with providing the implementations for dimension to dictionary id
+ * encoding-decoding.
+ * <p>
+ * This strategy can handle any dimension that can be addressed on a reverse-dictionary. Reverse dictionary uses
+ * a sorted map, rather than a hashmap.
+ * <p>
+ * This is the most expensive of all the strategies, and hence must be used only when other strategies aren't valid.
+ */
+@NotThreadSafe
+public class DictionaryBuildingGroupByColumnSelectorStrategy<DimensionType>
+ extends KeyMappingGroupByColumnSelectorStrategy<DimensionType>
+{
+
+ /**
+ * Dictionary for mapping the dimension value to an index. i-th position in the dictionary holds the value represented
+ * by the dictionaryId "i".
+ * Therefore, if a value has a dictionary id "i", dictionary.get(i) = value
Review Comment:
Can you add an example for this as well.
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/MemoryEstimate.java:
##########
@@ -0,0 +1,46 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+/**
+ * Holder for a value and the memory increase in the internal dictionary associated with the increase
+ */
+public class MemoryEstimate<T>
+{
+ private final T value;
+ private final int memoryIncrease;
+
+ // Reduced visibility
+ MemoryEstimate(T value, int memoryIncrease)
+ {
+ this.value = value;
+ this.memoryIncrease = memoryIncrease;
Review Comment:
lets cal it memory footprint.
##########
processing/src/main/java/org/apache/druid/segment/column/TypeStrategies.java:
##########
@@ -544,5 +622,47 @@ public int compare(@Nullable Object o1Obj, @Nullable Object o2Obj)
}
return Integer.compare(o1.length, o2.length);
}
+
+ /**
+ * Implements {@link Arrays#hashCode(Object[])} but the element hashing uses the element's type strategy
+ */
+ @Override
+ public int hashCode(Object[] o)
+ {
+ if (o == null) {
+ return 0;
+ } else {
+ int result = 1;
+ for (Object element : o) {
+ result = 31 * result + (element == null ? 0 : elementStrategy.hashCode(element));
+ }
+ return result;
+ }
+ }
+ /**
+ * Implements {@link Arrays#equals} but the element equality uses the element's type strategy
+ */
+ @Override
+ public boolean equals(@Nullable Object[] a, @Nullable Object[] b)
Review Comment:
Lets have Ut's for this.
##########
processing/src/main/java/org/apache/druid/segment/column/TypeStrategy.java:
##########
@@ -170,4 +172,30 @@ default T fromBytes(byte[] value)
{
throw new IllegalStateException("Not supported");
}
+
+ /**
+ * Whether the type is groupable or not. This is always true for all the primitive types, arrays, and nested arrays
+ * therefore the SQL and the native layer might ignore this flag for those types. For complex types, this flag can be
+ * true or false, depending on whether the semantics and implementation of the type naturally leads to groupability
+ * or not. For example, it makes sense for JSON columns to be groupable, however there is little sense in grouping
+ * sketches (before finalizing).
+ *
+ * If a type is groupable, it MUST implement the {@link #hashCode} and {@link #equals} correctly
+ */
+ default boolean groupable()
+ {
+ return false;
+ }
+
+ @Override
+ default int hashCode(T o)
Review Comment:
Lets add java doc mentioning that most implementation have groupable=true while overriding this method.
##########
processing/src/main/java/org/apache/druid/query/filter/ArrayContainsElementFilter.java:
##########
@@ -108,7 +109,10 @@ public byte[] getCacheKey()
final NullableTypeStrategy<Object> typeStrategy = elementMatchValueEval.type().getNullableStrategy();
final int size = typeStrategy.estimateSizeBytes(elementMatchValueEval.value());
final ByteBuffer valueBuffer = ByteBuffer.allocate(size);
- typeStrategy.write(valueBuffer, elementMatchValueEval.value(), size);
+ if (typeStrategy.write(valueBuffer, elementMatchValueEval.value(), size) < 0) {
+ // Defensive check, since the size had already been estimated from the same type strategy
+ throw DruidException.defensive("Unable to write the value");
Review Comment:
We should also add the the colName and the size. The reason I say this is because colValue can have sensitive data .
##########
.github/workflows/static-checks.yml:
##########
@@ -163,9 +163,17 @@ jobs:
${MVN} install -q -ff -pl 'distribution' ${MAVEN_SKIP} ${MAVEN_SKIP_TESTS}
- name: rewrite:dryRun
+ id: rewrite-dryRun
run: |
${MVN} rewrite:dryRun ${MAVEN_SKIP}
+ - name: Upload open rewrite patch
Review Comment:
I think this is not related to this PR :)
##########
processing/src/main/java/org/apache/druid/query/dimension/ColumnSelectorStrategyFactory.java:
##########
@@ -24,5 +24,8 @@
public interface ColumnSelectorStrategyFactory<ColumnSelectorStrategyClass extends ColumnSelectorStrategy>
{
- ColumnSelectorStrategyClass makeColumnSelectorStrategy(ColumnCapabilities capabilities, ColumnValueSelector selector);
+ ColumnSelectorStrategyClass makeColumnSelectorStrategy(ColumnCapabilities capabilities, ColumnValueSelector selector, String dimension);
+
+ // TODO(laksh): Javadoc
+ boolean supportsNestedArraysAndComplexTypes();
Review Comment:
This shoudl be renamed supportsComplexTypes() or should return a list of columns types to suppport .
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/DictionaryBuildingGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,203 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import it.unimi.dsi.fastutil.objects.Object2IntMap;
+import org.apache.druid.error.DruidException;
+import org.apache.druid.query.groupby.epinephelinae.DictionaryBuildingUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.column.NullableTypeStrategy;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.List;
+
+/**
+ * Strategy for grouping dimensions which can have variable-width objects, and aren't backed by prebuilt dictionaries. It
+ * encapsulates the dictionary building logic, along with providing the implementations for dimension to dictionary id
+ * encoding-decoding.
+ * <p>
+ * This strategy can handle any dimension that can be addressed on a reverse-dictionary. Reverse dictionary uses
+ * a sorted map, rather than a hashmap.
+ * <p>
+ * This is the most expensive of all the strategies, and hence must be used only when other strategies aren't valid.
+ */
+@NotThreadSafe
+public class DictionaryBuildingGroupByColumnSelectorStrategy<DimensionType>
+ extends KeyMappingGroupByColumnSelectorStrategy<DimensionType>
+{
+
+ /**
+ * Dictionary for mapping the dimension value to an index. i-th position in the dictionary holds the value represented
+ * by the dictionaryId "i".
+ * Therefore, if a value has a dictionary id "i", dictionary.get(i) = value
+ */
+ private final List<DimensionType> dictionary;
+
+ /**
+ * Reverse dictionary for faster lookup into the dictionary, and reusing pre-existing dictionary ids.
+ * <p>
+ * An entry of form (value, i) in the reverse dictionary represents that "value" is present at the i-th location in the
+ * {@link #dictionary}.
+ * Absence of mapping of a "value" (denoted by returning {@link GroupByColumnSelectorStrategy#GROUP_BY_MISSING_VALUE})
+ * represents that the value is absent in the dictionary
+ */
+ private final Object2IntMap<DimensionType> reverseDictionary;
+
+ private DictionaryBuildingGroupByColumnSelectorStrategy(
+ DimensionToIdConverter<DimensionType> dimensionToIdConverter,
+ ColumnType columnType,
+ NullableTypeStrategy<DimensionType> nullableTypeStrategy,
+ DimensionType defaultValue,
+ IdToDimensionConverter<DimensionType> idToDimensionConverter,
+ List<DimensionType> dictionary,
+ Object2IntMap<DimensionType> reverseDictionary
+ )
+ {
+ super(dimensionToIdConverter, columnType, nullableTypeStrategy, defaultValue, idToDimensionConverter);
+ this.dictionary = dictionary;
+ this.reverseDictionary = reverseDictionary;
+ }
+
+ /**
+ * Creates an implementation of the strategy for the given type
+ */
+ public static GroupByColumnSelectorStrategy forType(final ColumnType columnType)
+ {
+ if (columnType.equals(ColumnType.STRING)) {
+ // String types are handled specially because they can have multi-value dimensions
+ throw DruidException.defensive("Should use special variant which handles multi-value dimensions");
+ } else if (
+ // Defensive check, primitives should be using a faster fixed-width strategy
+ columnType.equals(ColumnType.DOUBLE)
+ || columnType.equals(ColumnType.FLOAT)
+ || columnType.equals(ColumnType.LONG)) {
+ throw DruidException.defensive("Could used a fixed width strategy");
+ }
+
+ // Catch-all for all other types, that can only have single-valued dimensions
+ return forArrayAndComplexTypes(columnType);
+ }
+
+ /**
+ * Implemenatation of dictionary building strategy for types other than strings (since they can be multi-valued and need
+ * to be handled separately) and numeric primitives (since they can be handled by fixed-width strategy).
+ * This also means that we handle array and complex types here, which simplifies the generics a lot, as everything can be
+ * treated as Object in this class.
+ * <p>
+ * Also, there isn't any concept of multi-values here, therefore Dimension == DimensionHolderType == Object. We still
+ * homogenize rogue selectors which can return non-standard implementation of arrays (like Long[] for long arrays instead of
+ * Object[]) to what the callers would expect (i.e. Object[] in this case).
+ */
+ private static GroupByColumnSelectorStrategy forArrayAndComplexTypes(final ColumnType columnType)
+ {
+ final List<Object> dictionary = DictionaryBuildingUtils.createDictionary();
+ final Object2IntMap<Object> reverseDictionary =
+ DictionaryBuildingUtils.createReverseDictionary(columnType.getNullableStrategy());
+ return new DictionaryBuildingGroupByColumnSelectorStrategy<>(
Review Comment:
Also what would happen in Array<Strings> earlier we had an optimization where each string element of the array of dictionary encoded and the whole array was made of of Array<dictionaryInts> which gave us best compression. In your case we would have only one level of dictionary.
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/DictionaryBuildingGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,203 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import it.unimi.dsi.fastutil.objects.Object2IntMap;
+import org.apache.druid.error.DruidException;
+import org.apache.druid.query.groupby.epinephelinae.DictionaryBuildingUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.column.NullableTypeStrategy;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.List;
+
+/**
+ * Strategy for grouping dimensions which can have variable-width objects, and aren't backed by prebuilt dictionaries. It
+ * encapsulates the dictionary building logic, along with providing the implementations for dimension to dictionary id
+ * encoding-decoding.
+ * <p>
+ * This strategy can handle any dimension that can be addressed on a reverse-dictionary. Reverse dictionary uses
+ * a sorted map, rather than a hashmap.
+ * <p>
+ * This is the most expensive of all the strategies, and hence must be used only when other strategies aren't valid.
+ */
+@NotThreadSafe
+public class DictionaryBuildingGroupByColumnSelectorStrategy<DimensionType>
+ extends KeyMappingGroupByColumnSelectorStrategy<DimensionType>
+{
+
+ /**
+ * Dictionary for mapping the dimension value to an index. i-th position in the dictionary holds the value represented
+ * by the dictionaryId "i".
+ * Therefore, if a value has a dictionary id "i", dictionary.get(i) = value
+ */
+ private final List<DimensionType> dictionary;
+
+ /**
+ * Reverse dictionary for faster lookup into the dictionary, and reusing pre-existing dictionary ids.
+ * <p>
+ * An entry of form (value, i) in the reverse dictionary represents that "value" is present at the i-th location in the
+ * {@link #dictionary}.
+ * Absence of mapping of a "value" (denoted by returning {@link GroupByColumnSelectorStrategy#GROUP_BY_MISSING_VALUE})
+ * represents that the value is absent in the dictionary
+ */
+ private final Object2IntMap<DimensionType> reverseDictionary;
+
+ private DictionaryBuildingGroupByColumnSelectorStrategy(
+ DimensionToIdConverter<DimensionType> dimensionToIdConverter,
+ ColumnType columnType,
+ NullableTypeStrategy<DimensionType> nullableTypeStrategy,
+ DimensionType defaultValue,
+ IdToDimensionConverter<DimensionType> idToDimensionConverter,
+ List<DimensionType> dictionary,
+ Object2IntMap<DimensionType> reverseDictionary
+ )
+ {
+ super(dimensionToIdConverter, columnType, nullableTypeStrategy, defaultValue, idToDimensionConverter);
+ this.dictionary = dictionary;
+ this.reverseDictionary = reverseDictionary;
+ }
+
+ /**
+ * Creates an implementation of the strategy for the given type
+ */
+ public static GroupByColumnSelectorStrategy forType(final ColumnType columnType)
+ {
+ if (columnType.equals(ColumnType.STRING)) {
+ // String types are handled specially because they can have multi-value dimensions
+ throw DruidException.defensive("Should use special variant which handles multi-value dimensions");
+ } else if (
+ // Defensive check, primitives should be using a faster fixed-width strategy
+ columnType.equals(ColumnType.DOUBLE)
+ || columnType.equals(ColumnType.FLOAT)
+ || columnType.equals(ColumnType.LONG)) {
+ throw DruidException.defensive("Could used a fixed width strategy");
+ }
+
+ // Catch-all for all other types, that can only have single-valued dimensions
+ return forArrayAndComplexTypes(columnType);
+ }
+
+ /**
+ * Implemenatation of dictionary building strategy for types other than strings (since they can be multi-valued and need
+ * to be handled separately) and numeric primitives (since they can be handled by fixed-width strategy).
+ * This also means that we handle array and complex types here, which simplifies the generics a lot, as everything can be
+ * treated as Object in this class.
+ * <p>
+ * Also, there isn't any concept of multi-values here, therefore Dimension == DimensionHolderType == Object. We still
+ * homogenize rogue selectors which can return non-standard implementation of arrays (like Long[] for long arrays instead of
+ * Object[]) to what the callers would expect (i.e. Object[] in this case).
+ */
+ private static GroupByColumnSelectorStrategy forArrayAndComplexTypes(final ColumnType columnType)
+ {
+ final List<Object> dictionary = DictionaryBuildingUtils.createDictionary();
+ final Object2IntMap<Object> reverseDictionary =
+ DictionaryBuildingUtils.createReverseDictionary(columnType.getNullableStrategy());
Review Comment:
You are always passing a Object dictionar where as on line 51 : ` private final List<DimensionType> dictionary;` we have a templated dictionary. Seems odd to me.
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/vector/DictionaryBuildingSingleValueStringGroupByVectorColumnSelector.java:
##########
@@ -82,7 +83,7 @@ public int writeKeys(
// Use same ROUGH_OVERHEAD_PER_DICTIONARY_ENTRY as the nonvectorized version; dictionary structure is the same.
stateFootprintIncrease +=
- DictionaryBuilding.estimateEntryFootprint((value == null ? 0 : value.length()) * Character.BYTES);
+ DictionaryBuildingUtils.estimateEntryFootprint((value == null ? 0 : value.length()) * Character.BYTES);
Review Comment:
Should we push this stringLogic inside the footPrintMethod or maybe have a wrapper string method inside the same class ?
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/MemoryEstimate.java:
##########
@@ -0,0 +1,46 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+/**
+ * Holder for a value and the memory increase in the internal dictionary associated with the increase
+ */
+public class MemoryEstimate<T>
Review Comment:
This is more like memoryFootprint. Lets rename it to such.
##########
processing/src/main/java/org/apache/druid/segment/nested/NestedDataComplexTypeSerde.java:
##########
@@ -157,6 +160,34 @@ public byte[] toBytes(@Nullable Object val)
};
}
+ @Override
+ public <T extends Comparable<T>> TypeStrategy<T> getTypeStrategy()
+ {
+ return new ObjectStrategyComplexTypeStrategy<>(
+ getObjectStrategy(),
+ ColumnType.ofComplex(TYPE_NAME),
+ true,
+ new Hash.Strategy<Object>()
+ {
+ @Override
+ public int hashCode(Object o)
+ {
+ // TODO(laksh): VET, Check if StructuredData.wrap(o).hashCode() makes sense, given that most of the objects inside
Review Comment:
Is this todo still there ?
cc @clintropolis I think this is not a blocker for this PR. We can always improve the implementation of the StructuredData
##########
processing/src/main/java/org/apache/druid/segment/column/ObjectStrategyComplexTypeStrategy.java:
##########
@@ -27,19 +29,35 @@
/**
* Default implementation of {@link TypeStrategy} for all {@link org.apache.druid.segment.serde.ComplexMetricSerde}
* implementations that just wraps the {@link ObjectStrategy} they are required to implement.
- *
+ * <p>
* This is not likely to be the most efficient way to do things, especially since writing must first produce a byte
* array before it can be written to the buffer, but it is cheap and should work correctly, which is important.
*/
public class ObjectStrategyComplexTypeStrategy<T> implements TypeStrategy<T>
{
private final ObjectStrategy<T> objectStrategy;
private final TypeSignature<?> typeSignature;
+ private final boolean groupable;
Review Comment:
We should just store hashStrategy here.
and just do hashStrategey.groupable()
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/DictionaryBuildingGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,203 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import it.unimi.dsi.fastutil.objects.Object2IntMap;
+import org.apache.druid.error.DruidException;
+import org.apache.druid.query.groupby.epinephelinae.DictionaryBuildingUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.column.NullableTypeStrategy;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.List;
+
+/**
+ * Strategy for grouping dimensions which can have variable-width objects, and aren't backed by prebuilt dictionaries. It
+ * encapsulates the dictionary building logic, along with providing the implementations for dimension to dictionary id
+ * encoding-decoding.
+ * <p>
+ * This strategy can handle any dimension that can be addressed on a reverse-dictionary. Reverse dictionary uses
+ * a sorted map, rather than a hashmap.
+ * <p>
+ * This is the most expensive of all the strategies, and hence must be used only when other strategies aren't valid.
+ */
+@NotThreadSafe
+public class DictionaryBuildingGroupByColumnSelectorStrategy<DimensionType>
+ extends KeyMappingGroupByColumnSelectorStrategy<DimensionType>
Review Comment:
I also think the abstraction is an overkill since we only have one impl for now.
##########
processing/src/main/java/org/apache/druid/segment/nested/StructuredData.java:
##########
@@ -185,6 +186,13 @@ public int hashCode()
return Objects.hash(value);
}
+ // hashCode that relies on the object equality. Translates the hashcode to an integer as well
+ // TODO(laksh): better name
Review Comment:
Lets remove the todo we can always make this better 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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1533320463
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/KeyMappingGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,243 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import com.google.common.base.Preconditions;
+import org.apache.druid.query.DimensionComparisonUtils;
+import org.apache.druid.query.groupby.ResultRow;
+import org.apache.druid.query.groupby.epinephelinae.Grouper;
+import org.apache.druid.query.ordering.StringComparator;
+import org.apache.druid.segment.ColumnValueSelector;
+import org.apache.druid.segment.DimensionHandlerUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.column.NullableTypeStrategy;
+
+import javax.annotation.Nullable;
+import javax.annotation.concurrent.NotThreadSafe;
+import java.nio.ByteBuffer;
+
+/**
+ * Strategy for grouping dimensions which can have variable-width objects. Materializing such objects on the buffer
+ * require an additional step of mapping them to an integer index. The integer index can be materialized on the buffer within
+ * a fixed width, and is often backed by a dictionary representing the actual dimension object. It is used for arrays,
+ * strings, and complex types.
+ * <p>
+ * The visibility of the class is limited, and the callers must use one of the two variants of the mapping strategy:
+ * 1. {@link PrebuiltDictionaryStringGroupByColumnSelectorStrategy}
+ * 2. {@link DictionaryBuildingGroupByColumnSelectorStrategy}
+ * <p>
+ * TODO(laksh): Vet this change
+ * {@code null} can be represented by either -1 or the position of null in the dictionary it was stored when it was
+ * encountered. This is fine, because most of the time, the dictionary id has no value of its own, and is converted back to
+ * the value it represents, before doing further operations. The only place where it would matter would be when
+ * {@link IdToDimensionConverter#canCompareIds()} is true, and we compare directly on the dictionary ids for prebuilt
+ * dictionaries (we can't compare ids for the dictionaries built on the fly in the grouping strategy). However, in that case,
+ * it is guaranteed that the dictionaryId of null represented by the pre-built dictionary would be the lowest (most likely 0)
+ * and therefore nulls (-1) would be adjacent to nulls (represented by the lowest non-negative dictionary id), and would get
+ * grouped in the later merge stages.
+ *
+ * @param <DimensionType>> Class of the dimension
+ * @param <DimensionHolderType> Class of the "dimension holder". For single-value dimensions, the holder's type and the
+ * holder's object are equivalent to the dimension. For multi-value dimensions (only strings),
+ * the holder's type and the object are different, where the type would be {@link org.apache.druid.segment.data.IndexedInts}
+ * representing all the values in the multi-valued string, while the dimension type would be
+ * String
+ * @see DimensionToIdConverter encoding logic for converting value to dictionary
+ * @see IdToDimensionConverter decoding logic for converting back dictionary to value
+ */
+@NotThreadSafe
+class KeyMappingGroupByColumnSelectorStrategy<DimensionType, DimensionHolderType>
Review Comment:
This makes more sense. It'll introduce some redundancy, but it should make the code a lot cleaner (especially when we handle single values)
--
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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1538787941
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/FixedWidthGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,214 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import org.apache.druid.error.DruidException;
+import org.apache.druid.query.DimensionComparisonUtils;
+import org.apache.druid.query.groupby.ResultRow;
+import org.apache.druid.query.groupby.epinephelinae.Grouper;
+import org.apache.druid.query.ordering.StringComparator;
+import org.apache.druid.segment.ColumnValueSelector;
+import org.apache.druid.segment.DimensionHandlerUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.column.NullableTypeStrategy;
+
+import javax.annotation.Nullable;
+import javax.annotation.concurrent.NotThreadSafe;
+import java.nio.ByteBuffer;
+
+/**
+ * Strategy for grouping dimensions which have fixed-width objects. It is only used for numeric primitive types,
+ * however complex types can reuse this strategy if they can hint the engine that they are always fixed width
+ * (for e.g. IP types). Such types donot need to be backed by a dictionary, and hence are faster to group by.
+ *
+ * @param <T> Class of the dimension
+ */
+@NotThreadSafe
+public class FixedWidthGroupByColumnSelectorStrategy<T> implements GroupByColumnSelectorStrategy
+{
+ /**
+ * Size of the key when materialized as bytes
+ */
+ final int keySizeBytes;
+
+ /**
+ * Indicates whether the type is primitive or not
+ */
+ final boolean isPrimitive;
+
+ /**
+ * Type of the dimension on which the grouping strategy is being used
+ */
+ final ColumnType columnType;
+
+ /**
+ * Nullable type strategy of the dimension
+ */
+ final NullableTypeStrategy<T> nullableTypeStrategy;
+
+ public FixedWidthGroupByColumnSelectorStrategy(
+ int keySizeBytes,
+ boolean isPrimitive,
+ ColumnType columnType
+ )
+ {
+ this.keySizeBytes = keySizeBytes;
+ this.isPrimitive = isPrimitive;
+ this.columnType = columnType;
+ this.nullableTypeStrategy = columnType.getNullableStrategy();
+ }
+
+ @Override
+ public int getGroupingKeySizeBytes()
+ {
+ return keySizeBytes;
+ }
+
+ @Override
+ public void processValueFromGroupingKey(
+ GroupByColumnSelectorPlus selectorPlus,
+ ByteBuffer key,
+ ResultRow resultRow,
+ int keyBufferPosition
+ )
+ {
+ resultRow.set(
+ selectorPlus.getResultRowPosition(),
+ nullableTypeStrategy.read(key, keyBufferPosition)
+ );
+ }
+
+ @Override
+ public int initColumnValues(ColumnValueSelector selector, int columnIndex, Object[] valuess)
+ {
+ valuess[columnIndex] = getValue(selector);
+ return 0;
+ }
+
+ @Override
+ public void initGroupingKeyColumnValue(
+ int keyBufferPosition,
+ int dimensionIndex,
+ Object rowObj,
+ ByteBuffer keyBuffer,
+ int[] stack
+ )
+ {
+ int written;
+ if (rowObj == null) {
+ written = nullableTypeStrategy.write(keyBuffer, keyBufferPosition, null, keySizeBytes);
+ stack[dimensionIndex] = 0;
+ } else {
+ written = nullableTypeStrategy.write(keyBuffer, keyBufferPosition, (T) rowObj, keySizeBytes);
+ stack[dimensionIndex] = 1;
+ }
+ // Since this is a fixed width strategy, the caller should already have allocated enough space to materialize the
+ // key object, and the type strategy should always be able to write to the buffer
+ if (written < 0) {
+ throw DruidException.defensive("Unable to serialize the value [%s] to buffer", rowObj);
+ }
+ }
+
+ /**
+ * This is used for multi-valued dimensions, for values after the first one. None of the current types supported by
+ * this strategy handle multi-valued dimensions, therefore this short circuits and returns false
+ */
+ @Override
+ public boolean checkRowIndexAndAddValueToGroupingKey(
+ int keyBufferPosition,
+ Object rowObj,
+ int rowValIdx,
+ ByteBuffer keyBuffer
+ )
+ {
+ return false;
+ }
+
+ @Override
+ public int writeToKeyBuffer(
+ int keyBufferPosition,
+ ColumnValueSelector selector,
+ ByteBuffer keyBuffer
+ )
+ {
+ T value = getValue(selector);
+ int written = nullableTypeStrategy.write(keyBuffer, keyBufferPosition, value, keySizeBytes);
+ if (written < 0) {
+ throw DruidException.defensive("Unable to serialize the value [%s] to buffer", value);
+ }
+ // This strategy doesn't use dictionary building and doesn't hold any internal state, therefore size increase is nil.
+ return 0;
+ }
+
+ @Override
+ public Grouper.BufferComparator bufferComparator(
+ int keyBufferPosition,
+ @Nullable StringComparator stringComparator
+ )
+ {
+ return (lhsBuffer, rhsBuffer, lhsPosition, rhsPosition) -> {
+ T lhs = nullableTypeStrategy.read(lhsBuffer, lhsPosition + keyBufferPosition);
+ T rhs = nullableTypeStrategy.read(rhsBuffer, rhsPosition + keyBufferPosition);
+ if (stringComparator != null
+ && !DimensionComparisonUtils.isNaturalComparator(columnType.getType(), stringComparator)) {
+ return stringComparator.compare(String.valueOf(lhs), String.valueOf(rhs));
+ }
+ // Nulls are allowed while comparing
+ //noinspection ConstantConditions
+ return nullableTypeStrategy.compare(lhs, rhs);
+ };
+ }
+
+
+ @Override
+ public void reset()
+ {
+ // Nothing to reset
+ }
+
+ /**
+ * Returns true if the value at the selector is null. It unifies the null handling of primitive numeric types and the
+ * other types
+ */
+ private boolean selectorIsNull(ColumnValueSelector columnValueSelector)
+ {
+ if (isPrimitive && columnValueSelector.isNull()) {
+ return true;
+ }
+ return !isPrimitive && (columnValueSelector.getObject() == null);
+ }
+
+ /**
+ * Returns the value of the selector. It handles nullity of the value and casts it to the proper type so that the
+ * upstream callers donot need to worry about handling incorrect types (for example, if a double column value selector
+ * returns a long)
+ */
+ @Nullable
+ private T getValue(ColumnValueSelector columnValueSelector)
+ {
+ if (selectorIsNull(columnValueSelector)) {
+ return null;
+ }
+ // TODO(laksh): Check if calling .getObject() on primitive selectors be problematic??
+ // Convert the object to the desired type
+ //noinspection unchecked
+ return (T) DimensionHandlerUtils.convertObjectToType(columnValueSelector.getObject(), columnType);
Review Comment:
I think it makes sense given that either we'd be having numeric primitives, or complex (future work) types, since in that case, DimensionHandlerUtils.convertObjectToType() would be a no-op, and we can remove that call.
--
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
Re: [PR] Grouping on complex columns aka unifying GroupBy strategies (druid)
Posted by "github-advanced-security[bot] (via GitHub)" <gi...@apache.org>.
github-advanced-security[bot] commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1557531355
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/KeyMappingGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,232 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import org.apache.druid.query.DimensionComparisonUtils;
+import org.apache.druid.query.groupby.ResultRow;
+import org.apache.druid.query.groupby.epinephelinae.Grouper;
+import org.apache.druid.query.ordering.StringComparator;
+import org.apache.druid.segment.ColumnValueSelector;
+import org.apache.druid.segment.DimensionHandlerUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.column.NullableTypeStrategy;
+
+import javax.annotation.Nullable;
+import javax.annotation.concurrent.NotThreadSafe;
+import java.nio.ByteBuffer;
+
+/**
+ * Strategy for grouping single value dimensions which can have variable-width objects. Materializing such objects on the buffer
+ * require an additional step of mapping them to an integer index. The integer index can be materialized on the buffer within
+ * a fixed width, and is often backed by a dictionary representing the actual dimension object. It is used for arrays,
+ * and complex types.
+ * <p>
+ * The visibility of the class is limited, and the callers must use one of the two variants of the mapping strategy:
+ * 1. {@link PrebuiltDictionaryGroupByColumnSelectorStrategy}
+ * 2. {@link DictionaryBuildingGroupByColumnSelectorStrategy}
+ * <p>
+ * {@code null} can be represented by either -1 or the position of null in the dictionary it was stored when it was
+ * encountered. This is fine, because most of the time, the dictionary id has no value of its own, and is converted back to
+ * the value it represents, before doing further operations. The only place where it would matter would be when
+ * {@link IdToDimensionConverter#canCompareIds()} is true, and we compare directly on the dictionary ids for prebuilt
+ * dictionaries (we can't compare ids for the dictionaries built on the fly in the grouping strategy). However, in that case,
+ * it is guaranteed that the dictionaryId of null represented by the pre-built dictionary would be the lowest (most likely 0)
+ * and therefore nulls (-1) would be adjacent to nulls (represented by the lowest non-negative dictionary id), and would get
+ * grouped in the later merge stages.
+ * <p>
+ * It only handles single value dimensions, i.e. every type except for strings. Strings are handled by the implementations
+ * of {@link KeyMappingMultiValueGroupByColumnSelectorStrategy}
+ * <p>
+ * It only handles non-primitive types, because numeric primitives are handled by the {@link FixedWidthGroupByColumnSelectorStrategy}
+ * and the string primitives are handled by the {@link KeyMappingMultiValueGroupByColumnSelectorStrategy}
+ *
+ * @param <DimensionType>> Class of the dimension
Review Comment:
## Spurious Javadoc @param tags
@param tag "<DimensionType>>" does not match any actual type parameter of type "KeyMappingGroupByColumnSelectorStrategy".
[Show more details](https://github.com/apache/druid/security/code-scanning/7236)
##########
benchmarks/src/test/java/org/apache/druid/benchmark/query/SqlGroupByBenchmark.java:
##########
@@ -0,0 +1,385 @@
+/*
+ * 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.benchmark.query;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import org.apache.druid.common.config.NullHandling;
+import org.apache.druid.data.input.impl.DimensionSchema;
+import org.apache.druid.data.input.impl.DimensionsSpec;
+import org.apache.druid.guice.NestedDataModule;
+import org.apache.druid.java.util.common.StringUtils;
+import org.apache.druid.java.util.common.granularity.Granularities;
+import org.apache.druid.java.util.common.guava.Sequence;
+import org.apache.druid.java.util.common.io.Closer;
+import org.apache.druid.math.expr.ExpressionProcessing;
+import org.apache.druid.query.DruidProcessingConfig;
+import org.apache.druid.query.QueryRunnerFactoryConglomerate;
+import org.apache.druid.query.expression.TestExprMacroTable;
+import org.apache.druid.segment.AutoTypeColumnSchema;
+import org.apache.druid.segment.IndexSpec;
+import org.apache.druid.segment.QueryableIndex;
+import org.apache.druid.segment.column.StringEncodingStrategy;
+import org.apache.druid.segment.generator.GeneratorBasicSchemas;
+import org.apache.druid.segment.generator.GeneratorSchemaInfo;
+import org.apache.druid.segment.generator.SegmentGenerator;
+import org.apache.druid.segment.transform.ExpressionTransform;
+import org.apache.druid.segment.transform.TransformSpec;
+import org.apache.druid.server.QueryStackTests;
+import org.apache.druid.server.SpecificSegmentsQuerySegmentWalker;
+import org.apache.druid.server.security.AuthConfig;
+import org.apache.druid.server.security.AuthTestUtils;
+import org.apache.druid.sql.calcite.SqlVectorizedExpressionSanityTest;
+import org.apache.druid.sql.calcite.planner.CalciteRulesManager;
+import org.apache.druid.sql.calcite.planner.CatalogResolver;
+import org.apache.druid.sql.calcite.planner.DruidPlanner;
+import org.apache.druid.sql.calcite.planner.PlannerConfig;
+import org.apache.druid.sql.calcite.planner.PlannerFactory;
+import org.apache.druid.sql.calcite.planner.PlannerResult;
+import org.apache.druid.sql.calcite.run.SqlEngine;
+import org.apache.druid.sql.calcite.schema.DruidSchemaCatalog;
+import org.apache.druid.sql.calcite.util.CalciteTests;
+import org.apache.druid.timeline.DataSegment;
+import org.apache.druid.timeline.partition.LinearShardSpec;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Param;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.TearDown;
+import org.openjdk.jmh.annotations.Warmup;
+import org.openjdk.jmh.infra.Blackhole;
+
+import javax.annotation.Nullable;
+import java.util.Collections;
+import java.util.List;
+import java.util.concurrent.TimeUnit;
+import java.util.stream.Collectors;
+
+@State(Scope.Benchmark)
+@Fork(value = 1)
+@Warmup(iterations = 3)
+@Measurement(iterations = 5)
+public class SqlGroupByBenchmark
+{
+ static {
+ NullHandling.initializeForTests();
+ ExpressionProcessing.initializeForTests();
+ NestedDataModule.registerHandlersAndSerde();
+ }
+
+ private static final DruidProcessingConfig PROCESSING_CONFIG = new DruidProcessingConfig()
+ {
+ @Override
+ public int intermediateComputeSizeBytes()
+ {
+ return 512 * 1024 * 1024;
+ }
+
+ @Override
+ public int getNumMergeBuffers()
+ {
+ return 3;
+ }
+
+ @Override
+ public int getNumThreads()
+ {
+ return 1;
+ }
+
+ @Override
+ public String getFormatString()
+ {
+ return "benchmarks-processing-%s";
+ }
+ };
+
+ @Param({
+ "string-Sequential-100_000",
+ "string-Sequential-10_000_000",
+ // "string-Sequential-1_000_000_000",
+ "string-ZipF-1_000_000",
+ "string-Uniform-1_000_000",
+
+ "multi-string-Sequential-100_000",
+ "multi-string-Sequential-10_000_000",
+ // "multi-string-Sequential-1_000_000_000",
+ "multi-string-ZipF-1_000_000",
+ "multi-string-Uniform-1_000_000",
+
+ "long-Sequential-100_000",
+ "long-Sequential-10_000_000",
+ // "long-Sequential-1_000_000_000",
+ "long-ZipF-1_000_000",
+ "long-Uniform-1_000_000",
+
+ "double-ZipF-1_000_000",
+ "double-Uniform-1_000_000",
+
+ "float-ZipF-1_000_000",
+ "float-Uniform-1_000_000",
+
+ "stringArray-Sequential-100_000",
+ "stringArray-Sequential-3_000_000",
+ // "stringArray-Sequential-1_000_000_000",
+ "stringArray-ZipF-1_000_000",
+ "stringArray-Uniform-1_000_000",
+
+ "longArray-Sequential-100_000",
+ "longArray-Sequential-3_000_000",
+ // "longArray-Sequential-1_000_000_000",
+ "longArray-ZipF-1_000_000",
+ "longArray-Uniform-1_000_000",
+
+ "nested-Sequential-100_000",
+ "nested-Sequential-3_000_000",
+ // "nested-Sequential-1_000_000_000",
+ "nested-ZipF-1_000_000",
+ "nested-Uniform-1_000_000",
+ })
+ private String groupingDimension;
+
+ private SqlEngine engine;
+ @Nullable
+ private PlannerFactory plannerFactory;
+ private Closer closer = Closer.create();
+
+ @Setup(Level.Trial)
+ public void setup()
+ {
+ final GeneratorSchemaInfo schemaInfo = GeneratorBasicSchemas.SCHEMA_MAP.get("groupBy-testbench");
+
+ final DataSegment dataSegment = DataSegment.builder()
+ .dataSource("foo")
+ .interval(schemaInfo.getDataInterval())
+ .version("1")
+ .shardSpec(new LinearShardSpec(0))
+ .size(0)
+ .build();
+ final DataSegment dataSegment2 = DataSegment.builder()
+ .dataSource("foo")
+ .interval(schemaInfo.getDataInterval())
+ .version("1")
+ .shardSpec(new LinearShardSpec(1))
+ .size(0)
+ .build();
+
+
+ final PlannerConfig plannerConfig = new PlannerConfig();
+
+ String columnCardinalityWithUnderscores = groupingDimension.substring(groupingDimension.lastIndexOf('-') + 1);
+ int rowsPerSegment = Integer.parseInt(StringUtils.replace(columnCardinalityWithUnderscores, "_", ""));
Review Comment:
## Missing catch of NumberFormatException
Potential uncaught 'java.lang.NumberFormatException'.
[Show more details](https://github.com/apache/druid/security/code-scanning/7235)
--
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
Re: [PR] Grouping on complex columns aka unifying GroupBy strategies (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1570502719
##########
processing/src/main/java/org/apache/druid/query/filter/ArrayContainsElementFilter.java:
##########
@@ -108,7 +109,10 @@ public byte[] getCacheKey()
final NullableTypeStrategy<Object> typeStrategy = elementMatchValueEval.type().getNullableStrategy();
final int size = typeStrategy.estimateSizeBytes(elementMatchValueEval.value());
final ByteBuffer valueBuffer = ByteBuffer.allocate(size);
- typeStrategy.write(valueBuffer, elementMatchValueEval.value(), size);
+ if (typeStrategy.write(valueBuffer, elementMatchValueEval.value(), size) < 0) {
+ // Defensive check, since the size had already been estimated from the same type strategy
+ throw DruidException.defensive("Unable to write the value");
Review Comment:
value is the one provided in the filter, which the user provides. Therefore printing the value as well. LMK if that poses any risk that I haven't considered.
--
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
Re: [PR] Grouping on complex columns aka unifying GroupBy strategies (druid)
Posted by "cryptoe (via GitHub)" <gi...@apache.org>.
cryptoe merged PR #16068:
URL: https://github.com/apache/druid/pull/16068
--
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
Re: [PR] Grouping on complex columns aka unifying GroupBy strategies (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1571365472
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/DictionaryBuildingGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,203 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import it.unimi.dsi.fastutil.objects.Object2IntMap;
+import org.apache.druid.error.DruidException;
+import org.apache.druid.query.groupby.epinephelinae.DictionaryBuildingUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.column.NullableTypeStrategy;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.List;
+
+/**
+ * Strategy for grouping dimensions which can have variable-width objects, and aren't backed by prebuilt dictionaries. It
+ * encapsulates the dictionary building logic, along with providing the implementations for dimension to dictionary id
+ * encoding-decoding.
+ * <p>
+ * This strategy can handle any dimension that can be addressed on a reverse-dictionary. Reverse dictionary uses
+ * a sorted map, rather than a hashmap.
+ * <p>
+ * This is the most expensive of all the strategies, and hence must be used only when other strategies aren't valid.
+ */
+@NotThreadSafe
+public class DictionaryBuildingGroupByColumnSelectorStrategy<DimensionType>
+ extends KeyMappingGroupByColumnSelectorStrategy<DimensionType>
+{
+
+ /**
+ * Dictionary for mapping the dimension value to an index. i-th position in the dictionary holds the value represented
+ * by the dictionaryId "i".
+ * Therefore, if a value has a dictionary id "i", dictionary.get(i) = value
+ */
+ private final List<DimensionType> dictionary;
+
+ /**
+ * Reverse dictionary for faster lookup into the dictionary, and reusing pre-existing dictionary ids.
+ * <p>
+ * An entry of form (value, i) in the reverse dictionary represents that "value" is present at the i-th location in the
+ * {@link #dictionary}.
+ * Absence of mapping of a "value" (denoted by returning {@link GroupByColumnSelectorStrategy#GROUP_BY_MISSING_VALUE})
+ * represents that the value is absent in the dictionary
+ */
+ private final Object2IntMap<DimensionType> reverseDictionary;
+
+ private DictionaryBuildingGroupByColumnSelectorStrategy(
+ DimensionToIdConverter<DimensionType> dimensionToIdConverter,
+ ColumnType columnType,
+ NullableTypeStrategy<DimensionType> nullableTypeStrategy,
+ DimensionType defaultValue,
+ IdToDimensionConverter<DimensionType> idToDimensionConverter,
+ List<DimensionType> dictionary,
+ Object2IntMap<DimensionType> reverseDictionary
+ )
+ {
+ super(dimensionToIdConverter, columnType, nullableTypeStrategy, defaultValue, idToDimensionConverter);
+ this.dictionary = dictionary;
+ this.reverseDictionary = reverseDictionary;
+ }
+
+ /**
+ * Creates an implementation of the strategy for the given type
+ */
+ public static GroupByColumnSelectorStrategy forType(final ColumnType columnType)
+ {
+ if (columnType.equals(ColumnType.STRING)) {
+ // String types are handled specially because they can have multi-value dimensions
+ throw DruidException.defensive("Should use special variant which handles multi-value dimensions");
+ } else if (
+ // Defensive check, primitives should be using a faster fixed-width strategy
+ columnType.equals(ColumnType.DOUBLE)
+ || columnType.equals(ColumnType.FLOAT)
+ || columnType.equals(ColumnType.LONG)) {
+ throw DruidException.defensive("Could used a fixed width strategy");
+ }
+
+ // Catch-all for all other types, that can only have single-valued dimensions
+ return forArrayAndComplexTypes(columnType);
+ }
+
+ /**
+ * Implemenatation of dictionary building strategy for types other than strings (since they can be multi-valued and need
+ * to be handled separately) and numeric primitives (since they can be handled by fixed-width strategy).
+ * This also means that we handle array and complex types here, which simplifies the generics a lot, as everything can be
+ * treated as Object in this class.
+ * <p>
+ * Also, there isn't any concept of multi-values here, therefore Dimension == DimensionHolderType == Object. We still
+ * homogenize rogue selectors which can return non-standard implementation of arrays (like Long[] for long arrays instead of
+ * Object[]) to what the callers would expect (i.e. Object[] in this case).
+ */
+ private static GroupByColumnSelectorStrategy forArrayAndComplexTypes(final ColumnType columnType)
+ {
+ final List<Object> dictionary = DictionaryBuildingUtils.createDictionary();
+ final Object2IntMap<Object> reverseDictionary =
+ DictionaryBuildingUtils.createReverseDictionary(columnType.getNullableStrategy());
+ return new DictionaryBuildingGroupByColumnSelectorStrategy<>(
Review Comment:
Great catch! I have corrected the code to use a multi-level dictionary in the case of array<string>. I'd assume that the changed code might be better in low-cardinality use case, or when the memory is abundant (due to single lookup), while the earlier code would have performed better in high cardinality use case, and/or when the memory is constrained (due to less frequent spills).
The benchmarks suggest that the new approach might be better, but the data was skewed (["1"], ["2"], ...) and the strings within the columns weren't reused. I haven't tested it with the real-world data, and with different configurations, which might be required to vet this change.
Since the purpose of this patch is to enable grouping on complex columns, I have modified the code to be inline with the original code, and I can do the benchmarking for this change 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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "clintropolis (via GitHub)" <gi...@apache.org>.
clintropolis commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1526860696
##########
processing/src/main/java/org/apache/druid/segment/DimensionHandlerUtils.java:
##########
@@ -413,9 +414,12 @@ public static Object convertObjectToType(
case DOUBLE:
return coerceToObjectArrayWithElementCoercionFunction(obj, DimensionHandlerUtils::convertObjectToDouble);
Review Comment:
we probably want to add a case here for other array types to just recursively call this method on the element type for nested and non-primitive arrays
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/GroupByColumnSelectorStrategyFactory.java:
##########
@@ -0,0 +1,96 @@
+/*
+ * 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.query.groupby.epinephelinae;
+
+import org.apache.druid.error.DruidException;
+import org.apache.druid.java.util.common.IAE;
+import org.apache.druid.query.dimension.ColumnSelectorStrategyFactory;
+import org.apache.druid.query.groupby.epinephelinae.column.DictionaryBuildingGroupByColumnSelectorStrategy;
+import org.apache.druid.query.groupby.epinephelinae.column.FixedWidthGroupByColumnSelectorStrategy;
+import org.apache.druid.query.groupby.epinephelinae.column.GroupByColumnSelectorStrategy;
+import org.apache.druid.query.groupby.epinephelinae.column.PrebuiltDictionaryStringGroupByColumnSelectorStrategy;
+import org.apache.druid.segment.ColumnValueSelector;
+import org.apache.druid.segment.DimensionSelector;
+import org.apache.druid.segment.column.ColumnCapabilities;
+import org.apache.druid.segment.column.ColumnType;
+
+/**
+ * Creates {@link org.apache.druid.query.dimension.ColumnSelectorStrategy}s for grouping dimensions
+ */
+public class GroupByColumnSelectorStrategyFactory implements ColumnSelectorStrategyFactory<GroupByColumnSelectorStrategy>
+{
+ @Override
+ public GroupByColumnSelectorStrategy makeColumnSelectorStrategy(
+ ColumnCapabilities capabilities,
+ ColumnValueSelector selector
+ )
+ {
+ if (capabilities == null || capabilities.getType() == null) {
+ throw DruidException.defensive("Unable to deduce type for the grouping dimension");
+ }
+ switch (capabilities.getType()) {
+ case STRING:
+ DimensionSelector dimSelector = (DimensionSelector) selector;
+ if (dimSelector.getValueCardinality() >= 0 && dimSelector.nameLookupPossibleInAdvance()) {
+ return PrebuiltDictionaryStringGroupByColumnSelectorStrategy.forType(
+ ColumnType.STRING,
+ selector,
+ capabilities
+ );
+ } else {
+ return DictionaryBuildingGroupByColumnSelectorStrategy.forType(ColumnType.STRING);
+ }
+ case LONG:
+ return new FixedWidthGroupByColumnSelectorStrategy<Long>(
+ Byte.BYTES + Long.BYTES,
Review Comment:
i wonder if we should check for default value mode? we can leave out the extra byte per value in that case and just use the regular type strategy for numbers instead of nullable strategy. This would i guess require splitting fixed width into nullable fixed width and not null fixed width though, which i guess wouldn't be the worst thing. alternatively maybe `TypeStrategy` and `NullableTypeStrategy` could have a common interface since they are pretty close otherwise
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/GroupByColumnSelectorStrategyFactory.java:
##########
@@ -0,0 +1,96 @@
+/*
+ * 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.query.groupby.epinephelinae;
+
+import org.apache.druid.error.DruidException;
+import org.apache.druid.java.util.common.IAE;
+import org.apache.druid.query.dimension.ColumnSelectorStrategyFactory;
+import org.apache.druid.query.groupby.epinephelinae.column.DictionaryBuildingGroupByColumnSelectorStrategy;
+import org.apache.druid.query.groupby.epinephelinae.column.FixedWidthGroupByColumnSelectorStrategy;
+import org.apache.druid.query.groupby.epinephelinae.column.GroupByColumnSelectorStrategy;
+import org.apache.druid.query.groupby.epinephelinae.column.PrebuiltDictionaryStringGroupByColumnSelectorStrategy;
+import org.apache.druid.segment.ColumnValueSelector;
+import org.apache.druid.segment.DimensionSelector;
+import org.apache.druid.segment.column.ColumnCapabilities;
+import org.apache.druid.segment.column.ColumnType;
+
+/**
+ * Creates {@link org.apache.druid.query.dimension.ColumnSelectorStrategy}s for grouping dimensions
+ */
+public class GroupByColumnSelectorStrategyFactory implements ColumnSelectorStrategyFactory<GroupByColumnSelectorStrategy>
Review Comment:
i know this isn't new, and definitely doesn't need done in this PR, but i wonder if worth considering switching to using `ColumnProcessors` instead of `ColumnSelectorStrategyFactory`
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/GroupByColumnSelectorStrategyFactory.java:
##########
@@ -0,0 +1,96 @@
+/*
+ * 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.query.groupby.epinephelinae;
+
+import org.apache.druid.error.DruidException;
+import org.apache.druid.java.util.common.IAE;
+import org.apache.druid.query.dimension.ColumnSelectorStrategyFactory;
+import org.apache.druid.query.groupby.epinephelinae.column.DictionaryBuildingGroupByColumnSelectorStrategy;
+import org.apache.druid.query.groupby.epinephelinae.column.FixedWidthGroupByColumnSelectorStrategy;
+import org.apache.druid.query.groupby.epinephelinae.column.GroupByColumnSelectorStrategy;
+import org.apache.druid.query.groupby.epinephelinae.column.PrebuiltDictionaryStringGroupByColumnSelectorStrategy;
+import org.apache.druid.segment.ColumnValueSelector;
+import org.apache.druid.segment.DimensionSelector;
+import org.apache.druid.segment.column.ColumnCapabilities;
+import org.apache.druid.segment.column.ColumnType;
+
+/**
+ * Creates {@link org.apache.druid.query.dimension.ColumnSelectorStrategy}s for grouping dimensions
+ */
+public class GroupByColumnSelectorStrategyFactory implements ColumnSelectorStrategyFactory<GroupByColumnSelectorStrategy>
+{
+ @Override
+ public GroupByColumnSelectorStrategy makeColumnSelectorStrategy(
+ ColumnCapabilities capabilities,
+ ColumnValueSelector selector
+ )
+ {
+ if (capabilities == null || capabilities.getType() == null) {
+ throw DruidException.defensive("Unable to deduce type for the grouping dimension");
+ }
+ switch (capabilities.getType()) {
+ case STRING:
+ DimensionSelector dimSelector = (DimensionSelector) selector;
+ if (dimSelector.getValueCardinality() >= 0 && dimSelector.nameLookupPossibleInAdvance()) {
+ return PrebuiltDictionaryStringGroupByColumnSelectorStrategy.forType(
+ ColumnType.STRING,
+ selector,
+ capabilities
+ );
+ } else {
+ return DictionaryBuildingGroupByColumnSelectorStrategy.forType(ColumnType.STRING);
+ }
+ case LONG:
+ return new FixedWidthGroupByColumnSelectorStrategy<Long>(
+ Byte.BYTES + Long.BYTES,
+ true,
+ ColumnType.LONG
+ );
+ case FLOAT:
+ return new FixedWidthGroupByColumnSelectorStrategy<Float>(
+ Byte.BYTES + Float.BYTES,
+ true,
+ ColumnType.FLOAT
+ );
+ case DOUBLE:
+ return new FixedWidthGroupByColumnSelectorStrategy<Double>(
+ Byte.BYTES + Double.BYTES,
+ true,
+ ColumnType.DOUBLE
+ );
+ case ARRAY:
+ switch (capabilities.getElementType().getType()) {
+ case LONG:
+ case STRING:
+ case DOUBLE:
+ return DictionaryBuildingGroupByColumnSelectorStrategy.forType(capabilities.toColumnType());
+ case FLOAT:
+ // Array<Float> not supported in expressions, ingestion
+ default:
+ throw new IAE("Cannot create query type helper from invalid type [%s]", capabilities.asTypeString());
+
+ }
+ case COMPLEX:
+ return DictionaryBuildingGroupByColumnSelectorStrategy.forType(capabilities.toColumnType());
+ default:
+ throw new IAE("Cannot create query type helper from invalid type [%s]", capabilities.asTypeString());
Review Comment:
there is no reason other array types cannot group in the same way, so I think we can just do this
```suggestion
case ARRAY:
case COMPLEX:
default:
return DictionaryBuildingGroupByColumnSelectorStrategy.forType(capabilities.toColumnType());
```
##########
sql/src/test/java/org/apache/druid/sql/calcite/QueryTestRunner.java:
##########
@@ -380,7 +380,7 @@ public VerifyNativeQueries(BaseExecuteQuery execStep)
public void verify()
{
for (QueryResults queryResults : execStep.results()) {
- verifyQuery(queryResults);
+// verifyQuery(queryResults);
Review Comment:
this i assume was for testing some stuff and needs to go away
##########
processing/src/main/java/org/apache/druid/segment/column/TypeStrategies.java:
##########
@@ -47,6 +49,9 @@ public class TypeStrategies
public static final StringTypeStrategy STRING = new StringTypeStrategy();
public static final ConcurrentHashMap<String, TypeStrategy<?>> COMPLEX_STRATEGIES = new ConcurrentHashMap<>();
+ static {
+ ComplexMetrics.registerSerde(ColumnType.NESTED_DATA.getComplexTypeName(), new NestedDataComplexTypeSerde());
+ }
Review Comment:
this should not be here, it happens in [the module](https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/guice/NestedDataModule.java), if a test is needing this then just register manually for the test
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/FixedWidthGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,214 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import org.apache.druid.error.DruidException;
+import org.apache.druid.query.DimensionComparisonUtils;
+import org.apache.druid.query.groupby.ResultRow;
+import org.apache.druid.query.groupby.epinephelinae.Grouper;
+import org.apache.druid.query.ordering.StringComparator;
+import org.apache.druid.segment.ColumnValueSelector;
+import org.apache.druid.segment.DimensionHandlerUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.column.NullableTypeStrategy;
+
+import javax.annotation.Nullable;
+import javax.annotation.concurrent.NotThreadSafe;
+import java.nio.ByteBuffer;
+
+/**
+ * Strategy for grouping dimensions which have fixed-width objects. It is only used for numeric primitive types,
+ * however complex types can reuse this strategy if they can hint the engine that they are always fixed width
+ * (for e.g. IP types). Such types donot need to be backed by a dictionary, and hence are faster to group by.
+ *
+ * @param <T> Class of the dimension
+ */
+@NotThreadSafe
+public class FixedWidthGroupByColumnSelectorStrategy<T> implements GroupByColumnSelectorStrategy
+{
+ /**
+ * Size of the key when materialized as bytes
+ */
+ final int keySizeBytes;
+
+ /**
+ * Indicates whether the type is primitive or not
+ */
+ final boolean isPrimitive;
+
+ /**
+ * Type of the dimension on which the grouping strategy is being used
+ */
+ final ColumnType columnType;
+
+ /**
+ * Nullable type strategy of the dimension
+ */
+ final NullableTypeStrategy<T> nullableTypeStrategy;
+
+ public FixedWidthGroupByColumnSelectorStrategy(
+ int keySizeBytes,
+ boolean isPrimitive,
+ ColumnType columnType
+ )
+ {
+ this.keySizeBytes = keySizeBytes;
+ this.isPrimitive = isPrimitive;
+ this.columnType = columnType;
+ this.nullableTypeStrategy = columnType.getNullableStrategy();
+ }
+
+ @Override
+ public int getGroupingKeySizeBytes()
+ {
+ return keySizeBytes;
+ }
+
+ @Override
+ public void processValueFromGroupingKey(
+ GroupByColumnSelectorPlus selectorPlus,
+ ByteBuffer key,
+ ResultRow resultRow,
+ int keyBufferPosition
+ )
+ {
+ resultRow.set(
+ selectorPlus.getResultRowPosition(),
+ nullableTypeStrategy.read(key, keyBufferPosition)
+ );
+ }
+
+ @Override
+ public int initColumnValues(ColumnValueSelector selector, int columnIndex, Object[] valuess)
+ {
+ valuess[columnIndex] = getValue(selector);
+ return 0;
+ }
+
+ @Override
+ public void initGroupingKeyColumnValue(
+ int keyBufferPosition,
+ int dimensionIndex,
+ Object rowObj,
+ ByteBuffer keyBuffer,
+ int[] stack
+ )
+ {
+ int written;
+ if (rowObj == null) {
+ written = nullableTypeStrategy.write(keyBuffer, keyBufferPosition, null, keySizeBytes);
+ stack[dimensionIndex] = 0;
+ } else {
+ written = nullableTypeStrategy.write(keyBuffer, keyBufferPosition, (T) rowObj, keySizeBytes);
+ stack[dimensionIndex] = 1;
+ }
+ // Since this is a fixed width strategy, the caller should already have allocated enough space to materialize the
+ // key object, and the type strategy should always be able to write to the buffer
+ if (written < 0) {
+ throw DruidException.defensive("Unable to serialize the value [%s] to buffer", rowObj);
+ }
+ }
+
+ /**
+ * This is used for multi-valued dimensions, for values after the first one. None of the current types supported by
+ * this strategy handle multi-valued dimensions, therefore this short circuits and returns false
+ */
+ @Override
+ public boolean checkRowIndexAndAddValueToGroupingKey(
+ int keyBufferPosition,
+ Object rowObj,
+ int rowValIdx,
+ ByteBuffer keyBuffer
+ )
+ {
+ return false;
+ }
+
+ @Override
+ public int writeToKeyBuffer(
+ int keyBufferPosition,
+ ColumnValueSelector selector,
+ ByteBuffer keyBuffer
+ )
+ {
+ T value = getValue(selector);
+ int written = nullableTypeStrategy.write(keyBuffer, keyBufferPosition, value, keySizeBytes);
+ if (written < 0) {
+ throw DruidException.defensive("Unable to serialize the value [%s] to buffer", value);
+ }
+ // This strategy doesn't use dictionary building and doesn't hold any internal state, therefore size increase is nil.
+ return 0;
+ }
+
+ @Override
+ public Grouper.BufferComparator bufferComparator(
+ int keyBufferPosition,
+ @Nullable StringComparator stringComparator
+ )
+ {
+ return (lhsBuffer, rhsBuffer, lhsPosition, rhsPosition) -> {
+ T lhs = nullableTypeStrategy.read(lhsBuffer, lhsPosition + keyBufferPosition);
+ T rhs = nullableTypeStrategy.read(rhsBuffer, rhsPosition + keyBufferPosition);
+ if (stringComparator != null
+ && !DimensionComparisonUtils.isNaturalComparator(columnType.getType(), stringComparator)) {
+ return stringComparator.compare(String.valueOf(lhs), String.valueOf(rhs));
+ }
+ // Nulls are allowed while comparing
+ //noinspection ConstantConditions
+ return nullableTypeStrategy.compare(lhs, rhs);
+ };
+ }
+
+
+ @Override
+ public void reset()
+ {
+ // Nothing to reset
+ }
+
+ /**
+ * Returns true if the value at the selector is null. It unifies the null handling of primitive numeric types and the
+ * other types
+ */
+ private boolean selectorIsNull(ColumnValueSelector columnValueSelector)
+ {
+ if (isPrimitive && columnValueSelector.isNull()) {
+ return true;
+ }
+ return !isPrimitive && (columnValueSelector.getObject() == null);
Review Comment:
nit:
```suggestion
if (isPrimitive) {
return columnValueSelector.isNull();
}
return columnValueSelector.getObject() == null;
```
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/DimensionToIdConverter.java:
##########
@@ -0,0 +1,77 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import org.apache.druid.segment.ColumnValueSelector;
+
+import javax.annotation.Nullable;
+
+/**
+ * Interface for converters of dimension to dictionary id.
+ *
+ * This is a slightly convoluted interface because it also encapsulates the additional logic for handling multi-value
+ * dimensions. It has an additional step that converts the given dimensions to "dimension holders", which represent the
+ * multi-value holders for a given dimension.
+ * Therefore, the conversion goes from ColumnValueSelector -> DimensionHolder -> DictionaryID (for each dimension in the holder)
+ *
+ * The dimension holder is only applicable for multi-value strings.
+ * For other dimensions that cannot have multi-values the dimension holder is identical to the dimension. They can be
+ * defensively cast or homogenised, for example doubles to floats for float selectors or Long[] to Object[] for array
+ * selectors, so that the upstream callers can assume the class of the dimensions. The size of these dimensions is always 1,
+ * and only contain a value at index 0.
+ *
+ * Converting a value to its dictionary id might require building dictionaries on the fly while computing the id. The
+ * return type of the methods, except {@link #multiValueSize}, takes that into account.
+ *
+ * The implementations can pre-convert the value to the dictionaryId while extracting the dimensionHolder. Extracting
+ * dictionary id for a specific value from the (potentially multi-value dimension holder) can be done by calling
+ * {@link #getIndividualValueDictId} and passing the index to the multi-value.
+ *
+ * @see IdToDimensionConverter for converting the dictionary values back to dimensions
+ *
+ * @param <DimensionHolderType> Type of the dimension holder
+ */
+public interface DimensionToIdConverter<DimensionHolderType>
Review Comment:
i feel like we should special handle multi-value dimensions instead of making new interfaces to accommodate them, though I'm still considering exactly how we should do this... maybe just making a dedicate multi-value string grouping strategy that doesn't fit any of the common patterns would be best.
Everything else should be grouping a single value and that is what we should always do going forwards. Things with multiple values like arrays should instead explicitly use UNNEST to aggregate individual elements of multiple values.
In fact, I almost wonder if we should dump all of the multi-value grouping stuff and just rewrite in `GroupingEngine.process` to wrap the storage adapter in an unnest if we detect any multi-value dimensions...
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/RowBasedGrouperHelper.java:
##########
@@ -1531,32 +1548,136 @@ private RowBasedKeySerdeHelper makeNumericSerdeHelper(
}
}
- private class ArrayNumericRowBasedKeySerdeHelper implements RowBasedKeySerdeHelper
+ private abstract class DictionaryBuildingSingleValuedRowBasedKeySerdeHelper implements RowBasedKeySerdeHelper
+ {
+ private final int keyBufferPosition;
+
+ public DictionaryBuildingSingleValuedRowBasedKeySerdeHelper(final int keyBufferPosition)
+ {
+ this.keyBufferPosition = keyBufferPosition;
+ }
+
+ @Override
+ public int getKeyBufferValueSize()
+ {
+ return Integer.BYTES;
+ }
+
+ @Override
+ public boolean putToKeyBuffer(RowBasedKey key, int idx)
+ {
+ final Object obj = key.getKey()[idx];
+ int id = getReverseDictionary().getInt(obj);
+ if (id == DimensionDictionary.ABSENT_VALUE_ID) {
+ id = getDictionary().size();
+ getReverseDictionary().put(obj, id);
+ getDictionary().add(obj);
+ }
+ keyBuffer.putInt(id);
+ return true;
+ }
+
+ @Override
+ public void getFromByteBuffer(ByteBuffer buffer, int initialOffset, int dimValIdx, Object[] dimValues)
+ {
+ dimValues[dimValIdx] = getDictionary().get(buffer.getInt(initialOffset + keyBufferPosition));
+ }
+
+ /**
+ * Raw type used because arrays and object dictionaries differ
+ */
+ @SuppressWarnings("rawtypes")
+ public abstract List getDictionary();
+
+ /**
+ * Raw types used because arrays and object dictionaries differ
+ */
+ @SuppressWarnings("rawtypes")
+ public abstract Object2IntMap getReverseDictionary();
+ }
+
+ private class ComplexRowBasedKeySerdeHelper extends DictionaryBuildingSingleValuedRowBasedKeySerdeHelper
{
final int keyBufferPosition;
final BufferComparator bufferComparator;
- final TypeSignature<ValueType> elementType;
+ final ColumnType complexType;
+ final String complexTypeName;
+
+ final List<Object> complexTypeDictionary;
+ final Object2IntMap<Object> complexTypeReverseDictionary;
+
+ public ComplexRowBasedKeySerdeHelper(
+ int keyBufferPosition,
+ ColumnType complexType
+ )
+ {
+ super(keyBufferPosition);
+ this.keyBufferPosition = keyBufferPosition;
+ this.complexType = complexType;
+ this.complexTypeName = Preconditions.checkNotNull(complexType.getComplexTypeName(), "complex type name expected");
Review Comment:
if instead of `complexType.getComplexTypeName()` we just use `complexType.asTypeString()` we can re-use this strategy generically for things like nested arrays or arrays of complex types too. Suggest renaming to `GenericDictionaryBuildingRowBasedKeySerdeHelper` or something.
I suppose we could pack dictionaries for all types into this since they are all basically the same, to have less stuff to track... but it also seems ok to leave the strings and primitive arrays handled separately in case we want to further optimize stuff
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/IdToDimensionConverter.java:
##########
@@ -0,0 +1,56 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+/**
+ * Converts back the dictionaryId to the dimension value. The implementations might or might not handle
+ * {@link GroupByColumnSelectorStrategy#GROUP_BY_MISSING_VALUE}. The callers should handle those values appropriately on
+ * their own, and filter those out before trying to convert the dictionary id back to value.
+ *
+ * The encoding - decoding workflow looks like:
+ *
+ * Encoding
+ * 1. {@link DimensionToIdConverter} extracts the multi-value holder for the given row, which get's stored somewhere
+ * 2. For each entry in the multi-value object, the value gets encoded into a dictionaryId, using {@link DimensionToIdConverter#getIndividualValueDictId}
+ * 3. The callers can use this integer dictionaryID to materialize the results somewhere
+ *
+ * Decoding
+ * 1. The materialized dictionary id is deserialized back to an int, and then decoded into value using {@link #idToKey}
+ *
+ * @see DimensionToIdConverter for converting the dimensions to dictionary ids
+ *
+ * @param <DimensionType> Type of the dimension's values
+ */
+public interface IdToDimensionConverter<DimensionType>
Review Comment:
hmm, this seems basically like `IdLookup` except generic, and the latter method is only used internally to the class where this thing is also used.
I wonder if we can just drop this interface, make `IdLookup` generic, and just define `canCompareIds` directly on `KeyMappingGroupByColumnSelectorStrategy` and let stuff override it
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/KeyMappingGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,243 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import com.google.common.base.Preconditions;
+import org.apache.druid.query.DimensionComparisonUtils;
+import org.apache.druid.query.groupby.ResultRow;
+import org.apache.druid.query.groupby.epinephelinae.Grouper;
+import org.apache.druid.query.ordering.StringComparator;
+import org.apache.druid.segment.ColumnValueSelector;
+import org.apache.druid.segment.DimensionHandlerUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.column.NullableTypeStrategy;
+
+import javax.annotation.Nullable;
+import javax.annotation.concurrent.NotThreadSafe;
+import java.nio.ByteBuffer;
+
+/**
+ * Strategy for grouping dimensions which can have variable-width objects. Materializing such objects on the buffer
+ * require an additional step of mapping them to an integer index. The integer index can be materialized on the buffer within
+ * a fixed width, and is often backed by a dictionary representing the actual dimension object. It is used for arrays,
+ * strings, and complex types.
+ * <p>
+ * The visibility of the class is limited, and the callers must use one of the two variants of the mapping strategy:
+ * 1. {@link PrebuiltDictionaryStringGroupByColumnSelectorStrategy}
+ * 2. {@link DictionaryBuildingGroupByColumnSelectorStrategy}
+ * <p>
+ * TODO(laksh): Vet this change
+ * {@code null} can be represented by either -1 or the position of null in the dictionary it was stored when it was
+ * encountered. This is fine, because most of the time, the dictionary id has no value of its own, and is converted back to
+ * the value it represents, before doing further operations. The only place where it would matter would be when
+ * {@link IdToDimensionConverter#canCompareIds()} is true, and we compare directly on the dictionary ids for prebuilt
+ * dictionaries (we can't compare ids for the dictionaries built on the fly in the grouping strategy). However, in that case,
+ * it is guaranteed that the dictionaryId of null represented by the pre-built dictionary would be the lowest (most likely 0)
+ * and therefore nulls (-1) would be adjacent to nulls (represented by the lowest non-negative dictionary id), and would get
+ * grouped in the later merge stages.
+ *
+ * @param <DimensionType>> Class of the dimension
+ * @param <DimensionHolderType> Class of the "dimension holder". For single-value dimensions, the holder's type and the
+ * holder's object are equivalent to the dimension. For multi-value dimensions (only strings),
+ * the holder's type and the object are different, where the type would be {@link org.apache.druid.segment.data.IndexedInts}
+ * representing all the values in the multi-valued string, while the dimension type would be
+ * String
+ * @see DimensionToIdConverter encoding logic for converting value to dictionary
+ * @see IdToDimensionConverter decoding logic for converting back dictionary to value
+ */
+@NotThreadSafe
+class KeyMappingGroupByColumnSelectorStrategy<DimensionType, DimensionHolderType>
Review Comment:
yea, after looking more at this i really starting to feel like we should either split out multi-value string grouping into its own strategy (or do the other thing and dump it completely in favor of unnest adapter).
Everything except for mvds will spend time doing pointless stuff when there is ever only 1 dictionary id per row, so it doesn't feel worth the complexity/cost to have this odd strategy unified with the rest of the sane ones.
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/FixedWidthGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,214 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import org.apache.druid.error.DruidException;
+import org.apache.druid.query.DimensionComparisonUtils;
+import org.apache.druid.query.groupby.ResultRow;
+import org.apache.druid.query.groupby.epinephelinae.Grouper;
+import org.apache.druid.query.ordering.StringComparator;
+import org.apache.druid.segment.ColumnValueSelector;
+import org.apache.druid.segment.DimensionHandlerUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.column.NullableTypeStrategy;
+
+import javax.annotation.Nullable;
+import javax.annotation.concurrent.NotThreadSafe;
+import java.nio.ByteBuffer;
+
+/**
+ * Strategy for grouping dimensions which have fixed-width objects. It is only used for numeric primitive types,
+ * however complex types can reuse this strategy if they can hint the engine that they are always fixed width
+ * (for e.g. IP types). Such types donot need to be backed by a dictionary, and hence are faster to group by.
+ *
+ * @param <T> Class of the dimension
+ */
+@NotThreadSafe
+public class FixedWidthGroupByColumnSelectorStrategy<T> implements GroupByColumnSelectorStrategy
+{
+ /**
+ * Size of the key when materialized as bytes
+ */
+ final int keySizeBytes;
+
+ /**
+ * Indicates whether the type is primitive or not
+ */
+ final boolean isPrimitive;
+
+ /**
+ * Type of the dimension on which the grouping strategy is being used
+ */
+ final ColumnType columnType;
+
+ /**
+ * Nullable type strategy of the dimension
+ */
+ final NullableTypeStrategy<T> nullableTypeStrategy;
+
+ public FixedWidthGroupByColumnSelectorStrategy(
+ int keySizeBytes,
+ boolean isPrimitive,
+ ColumnType columnType
+ )
+ {
+ this.keySizeBytes = keySizeBytes;
+ this.isPrimitive = isPrimitive;
+ this.columnType = columnType;
+ this.nullableTypeStrategy = columnType.getNullableStrategy();
+ }
+
+ @Override
+ public int getGroupingKeySizeBytes()
+ {
+ return keySizeBytes;
+ }
+
+ @Override
+ public void processValueFromGroupingKey(
+ GroupByColumnSelectorPlus selectorPlus,
+ ByteBuffer key,
+ ResultRow resultRow,
+ int keyBufferPosition
+ )
+ {
+ resultRow.set(
+ selectorPlus.getResultRowPosition(),
+ nullableTypeStrategy.read(key, keyBufferPosition)
+ );
+ }
+
+ @Override
+ public int initColumnValues(ColumnValueSelector selector, int columnIndex, Object[] valuess)
+ {
+ valuess[columnIndex] = getValue(selector);
+ return 0;
+ }
+
+ @Override
+ public void initGroupingKeyColumnValue(
+ int keyBufferPosition,
+ int dimensionIndex,
+ Object rowObj,
+ ByteBuffer keyBuffer,
+ int[] stack
+ )
+ {
+ int written;
+ if (rowObj == null) {
+ written = nullableTypeStrategy.write(keyBuffer, keyBufferPosition, null, keySizeBytes);
+ stack[dimensionIndex] = 0;
+ } else {
+ written = nullableTypeStrategy.write(keyBuffer, keyBufferPosition, (T) rowObj, keySizeBytes);
+ stack[dimensionIndex] = 1;
+ }
+ // Since this is a fixed width strategy, the caller should already have allocated enough space to materialize the
+ // key object, and the type strategy should always be able to write to the buffer
+ if (written < 0) {
+ throw DruidException.defensive("Unable to serialize the value [%s] to buffer", rowObj);
+ }
+ }
+
+ /**
+ * This is used for multi-valued dimensions, for values after the first one. None of the current types supported by
+ * this strategy handle multi-valued dimensions, therefore this short circuits and returns false
+ */
+ @Override
+ public boolean checkRowIndexAndAddValueToGroupingKey(
+ int keyBufferPosition,
+ Object rowObj,
+ int rowValIdx,
+ ByteBuffer keyBuffer
+ )
+ {
+ return false;
+ }
+
+ @Override
+ public int writeToKeyBuffer(
+ int keyBufferPosition,
+ ColumnValueSelector selector,
+ ByteBuffer keyBuffer
+ )
+ {
+ T value = getValue(selector);
+ int written = nullableTypeStrategy.write(keyBuffer, keyBufferPosition, value, keySizeBytes);
+ if (written < 0) {
+ throw DruidException.defensive("Unable to serialize the value [%s] to buffer", value);
+ }
+ // This strategy doesn't use dictionary building and doesn't hold any internal state, therefore size increase is nil.
+ return 0;
+ }
+
+ @Override
+ public Grouper.BufferComparator bufferComparator(
+ int keyBufferPosition,
+ @Nullable StringComparator stringComparator
+ )
+ {
+ return (lhsBuffer, rhsBuffer, lhsPosition, rhsPosition) -> {
+ T lhs = nullableTypeStrategy.read(lhsBuffer, lhsPosition + keyBufferPosition);
+ T rhs = nullableTypeStrategy.read(rhsBuffer, rhsPosition + keyBufferPosition);
+ if (stringComparator != null
+ && !DimensionComparisonUtils.isNaturalComparator(columnType.getType(), stringComparator)) {
+ return stringComparator.compare(String.valueOf(lhs), String.valueOf(rhs));
+ }
+ // Nulls are allowed while comparing
+ //noinspection ConstantConditions
+ return nullableTypeStrategy.compare(lhs, rhs);
+ };
+ }
+
+
+ @Override
+ public void reset()
+ {
+ // Nothing to reset
+ }
+
+ /**
+ * Returns true if the value at the selector is null. It unifies the null handling of primitive numeric types and the
+ * other types
+ */
+ private boolean selectorIsNull(ColumnValueSelector columnValueSelector)
+ {
+ if (isPrimitive && columnValueSelector.isNull()) {
+ return true;
+ }
+ return !isPrimitive && (columnValueSelector.getObject() == null);
+ }
+
+ /**
+ * Returns the value of the selector. It handles nullity of the value and casts it to the proper type so that the
+ * upstream callers donot need to worry about handling incorrect types (for example, if a double column value selector
+ * returns a long)
+ */
+ @Nullable
+ private T getValue(ColumnValueSelector columnValueSelector)
+ {
+ if (selectorIsNull(columnValueSelector)) {
+ return null;
+ }
+ // TODO(laksh): Check if calling .getObject() on primitive selectors be problematic??
+ // Convert the object to the desired type
+ //noinspection unchecked
+ return (T) DimensionHandlerUtils.convertObjectToType(columnValueSelector.getObject(), columnType);
Review Comment:
i wonder if there is a nicer way we could do this by letting the thing that creates this supply a value supplier method that could be backed by whatever makes sense for the selector type, e.g. something like
```
public FixedWidthGroupByColumnSelectorStrategy(
int keySizeBytes,
boolean isPrimitive,
ColumnType columnType,
Function<ColumnValueSelector<?>, T> getterFn
)
```
and then
```
case LONG:
return new FixedWidthGroupByColumnSelectorStrategy<>(
Byte.BYTES + Long.BYTES,
true,
ColumnType.LONG,
ColumnValueSelector::getLong
);
```
and so on. It seems to work afaict and doesn't seem like it should be any worse than going through getObject and dimension handler utils conversion methods
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/PrebuiltDictionaryStringGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,138 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import org.apache.druid.common.config.NullHandling;
+import org.apache.druid.error.DruidException;
+import org.apache.druid.segment.ColumnValueSelector;
+import org.apache.druid.segment.DimensionSelector;
+import org.apache.druid.segment.column.ColumnCapabilities;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.data.IndexedInts;
+
+import javax.annotation.Nullable;
+
+/**
+ * Implementation of {@link KeyMappingGroupByColumnSelectorStrategy} that relies on a prebuilt dictionary to map the
+ * dimension to the dictionaryId. It is more like a helper class, that handles the different ways that dictionaries can be
+ * provided for different types. Currently, it only handles String dimensions. Array dimensions are also backed by dictionaries,
+ * but not exposed via the ColumnValueSelector interface, hence this strategy cannot handle array dimensions.
+ */
+public class PrebuiltDictionaryStringGroupByColumnSelectorStrategy
+{
+
+ /**
+ * Create the strategy for the provided column type
+ */
+ public static GroupByColumnSelectorStrategy forType(
+ final ColumnType columnType,
+ final ColumnValueSelector columnValueSelector,
+ final ColumnCapabilities columnCapabilities
+ )
+ {
+ if (columnType.equals(ColumnType.STRING)) {
+ return forString(columnValueSelector, columnCapabilities);
+ } else {
+ // This will change with array columns
+ throw DruidException.defensive("Only string columns expose prebuilt dictionaries");
+ }
+ }
+
+ private static GroupByColumnSelectorStrategy forString(
+ final ColumnValueSelector columnValueSelector,
+ final ColumnCapabilities columnCapabilities
+ )
+ {
+ return new KeyMappingGroupByColumnSelectorStrategy<>(
+ new StringDimensionToIdConverter(),
+ ColumnType.STRING,
+ ColumnType.STRING.getNullableStrategy(),
+ NullHandling.defaultStringValue(),
+ new StringIdToDimensionConverter((DimensionSelector) columnValueSelector, columnCapabilities)
+ );
+ }
+
+ /**
+ * Dimension to id converter for string dimensions and {@link DimensionSelector}, where the dictionaries are prebuilt.
+ * The callers must ensure that's the case by checking that {@link DimensionSelector#getValueCardinality()} is known
+ * and {@link DimensionSelector#nameLookupPossibleInAdvance()} is true.
+ */
+ private static class StringDimensionToIdConverter implements DimensionToIdConverter<IndexedInts>
+ {
+ @Override
+ public MemoryEstimate<IndexedInts> getMultiValueHolder(
+ final ColumnValueSelector selector,
+ final IndexedInts reusableValue
+ )
+ {
+ return new MemoryEstimate<>(((DimensionSelector) selector).getRow(), 0);
+ }
+
+ @Override
+ public int multiValueSize(IndexedInts multiValueHolder)
+ {
+ return multiValueHolder.size();
+ }
+
+ @Override
+ public MemoryEstimate<Integer> getIndividualValueDictId(IndexedInts multiValueHolder, int index)
+ {
+ // dictId is already encoded in the indexedInt supplied by the column value selector
+ return new MemoryEstimate<>(multiValueHolder.get(index), 0);
+ }
+ }
+
+ /**
+ * ID to dimension converter for {@link DimensionSelector} with prebuilt dictionary
+ */
+ private static class StringIdToDimensionConverter implements IdToDimensionConverter<String>
+ {
+
+ final DimensionSelector dimensionSelector;
+
+ @Nullable
+ final ColumnCapabilities columnCapabilities;
+
+ public StringIdToDimensionConverter(
+ final DimensionSelector dimensionSelector,
+ @Nullable final ColumnCapabilities columnCapabilities
+ )
+ {
+ this.dimensionSelector = dimensionSelector;
+ this.columnCapabilities = columnCapabilities;
+ }
+
+ @Override
+ public String idToKey(int id)
+ {
+ // Converting back to the value is as simple as looking up the value in the prebuilt dictionary
+ return dimensionSelector.lookupName(id);
+ }
+
+ @Override
+ public boolean canCompareIds()
+ {
+ return columnCapabilities != null
+ && columnCapabilities.hasBitmapIndexes()
+ && (columnCapabilities.areDictionaryValuesSorted()
+ .and(columnCapabilities.areDictionaryValuesUnique())).isTrue();
Review Comment:
this isn't correct, we should be checking `isDictionaryEncoded` not `hasBitmapIndexes`
```suggestion
return columnCapabilities != null
&& columnCapabilities.isDictionaryEncoded()
.and(columnCapabilities.areDictionaryValuesSorted())
.and(columnCapabilities.areDictionaryValuesUnique())
.isTrue();
```
--
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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1540703651
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/IdToDimensionConverter.java:
##########
@@ -0,0 +1,56 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+/**
+ * Converts back the dictionaryId to the dimension value. The implementations might or might not handle
+ * {@link GroupByColumnSelectorStrategy#GROUP_BY_MISSING_VALUE}. The callers should handle those values appropriately on
+ * their own, and filter those out before trying to convert the dictionary id back to value.
+ *
+ * The encoding - decoding workflow looks like:
+ *
+ * Encoding
+ * 1. {@link DimensionToIdConverter} extracts the multi-value holder for the given row, which get's stored somewhere
+ * 2. For each entry in the multi-value object, the value gets encoded into a dictionaryId, using {@link DimensionToIdConverter#getIndividualValueDictId}
+ * 3. The callers can use this integer dictionaryID to materialize the results somewhere
+ *
+ * Decoding
+ * 1. The materialized dictionary id is deserialized back to an int, and then decoded into value using {@link #idToKey}
+ *
+ * @see DimensionToIdConverter for converting the dimensions to dictionary ids
+ *
+ * @param <DimensionType> Type of the dimension's values
+ */
+public interface IdToDimensionConverter<DimensionType>
Review Comment:
https://github.com/apache/druid/pull/16068#discussion_r1533110863 After completing this refactoring, I realized that now we only have a single implementation of Id->Dimension and Dimension->Id converters. Keeping this abstraction or removing it completely now lies on how whether or not we want to keep the stuff extendible for future dimensions having prebuilt dictionaries.
--
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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "cryptoe (via GitHub)" <gi...@apache.org>.
cryptoe commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1553254590
##########
sql/src/main/java/org/apache/druid/sql/calcite/rel/DruidQuery.java:
##########
@@ -1250,8 +1249,8 @@ private TopNQuery toTopNQuery()
}
final DimensionSpec dimensionSpec = Iterables.getOnlyElement(grouping.getDimensions()).toDimensionSpec();
- // grouping col cannot be type array
- if (dimensionSpec.getOutputType().isArray()) {
+ // grouping col cannot be arrays or complex types
Review Comment:
i think we should also mention that grouping complex col is not supported for topn query.
##########
sql/src/main/java/org/apache/druid/sql/calcite/rel/DruidQuery.java:
##########
@@ -486,15 +484,16 @@ private static List<DimensionExpression> computeDimensions(
final RelDataType dataType = rexNode.getType();
final ColumnType outputType = Calcites.getColumnTypeForRelDataType(dataType);
- if (Types.isNullOr(outputType, ValueType.COMPLEX)) {
- // Can't group on unknown or COMPLEX types.
- plannerContext.setPlanningError(
- "SQL requires a group-by on a column of type %s that is unsupported.",
- outputType
- );
+ if (outputType == null) {
+ // Can't group on unknown types.
+ plannerContext.setPlanningError("SQL requires a group-by on a column with unknown type that is unsupported.");
+ throw new CannotBuildQueryException(aggregate, rexNode);
+ }
+ if (!outputType.getNullableStrategy().groupable()) {
+ // Can't group on 'ungroupable' types.
+ plannerContext.setPlanningError("SQL requires a group-by column with ungroupable type [%s].", outputType);
Review Comment:
This should be SQL cannot group by a ungroupable column.
--
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
Re: [PR] Grouping on complex columns aka unifying GroupBy strategies (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1572098882
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/DictionaryBuildingGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,203 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import it.unimi.dsi.fastutil.objects.Object2IntMap;
+import org.apache.druid.error.DruidException;
+import org.apache.druid.query.groupby.epinephelinae.DictionaryBuildingUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.column.NullableTypeStrategy;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.List;
+
+/**
+ * Strategy for grouping dimensions which can have variable-width objects, and aren't backed by prebuilt dictionaries. It
+ * encapsulates the dictionary building logic, along with providing the implementations for dimension to dictionary id
+ * encoding-decoding.
+ * <p>
+ * This strategy can handle any dimension that can be addressed on a reverse-dictionary. Reverse dictionary uses
+ * a sorted map, rather than a hashmap.
+ * <p>
+ * This is the most expensive of all the strategies, and hence must be used only when other strategies aren't valid.
+ */
+@NotThreadSafe
+public class DictionaryBuildingGroupByColumnSelectorStrategy<DimensionType>
+ extends KeyMappingGroupByColumnSelectorStrategy<DimensionType>
Review Comment:
I think it's cool to keep it as is, since the class houses a decent amount of code, even though the class itself doesn't do anything. Without this class, we'd have to have separate classes for the inner static classes inside and another class for the static methods, which will be similar in complexity, if not more.
--
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
Re: [PR] Grouping on complex columns aka unifying GroupBy strategies (druid)
Posted by "cryptoe (via GitHub)" <gi...@apache.org>.
cryptoe commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1572162264
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/DictionaryBuildingGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,280 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import com.google.common.collect.BiMap;
+import com.google.common.collect.HashBiMap;
+import it.unimi.dsi.fastutil.objects.Object2IntMap;
+import org.apache.druid.error.DruidException;
+import org.apache.druid.query.groupby.epinephelinae.DictionaryBuildingUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.column.NullableTypeStrategy;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Strategy for grouping dimensions which can have variable-width objects, and aren't backed by prebuilt dictionaries. It
+ * encapsulates the dictionary building logic, along with providing the implementations for dimension to dictionary id
+ * encoding-decoding.
+ * <p>
+ * This strategy can handle any dimension that can be addressed on a reverse-dictionary. Reverse dictionary uses
+ * a sorted map, rather than a hashmap.
+ * <p>
+ * This is the most expensive of all the strategies, and hence must be used only when other strategies aren't valid.
+ */
+@NotThreadSafe
+public class DictionaryBuildingGroupByColumnSelectorStrategy<DimensionType>
+ extends KeyMappingGroupByColumnSelectorStrategy<DimensionType>
+{
+
+ private DictionaryBuildingGroupByColumnSelectorStrategy(
+ DimensionIdCodec<DimensionType> dimensionIdCodec,
+ ColumnType columnType,
+ NullableTypeStrategy<DimensionType> nullableTypeStrategy,
+ DimensionType defaultValue
+ )
+ {
+ super(dimensionIdCodec, columnType, nullableTypeStrategy, defaultValue);
+ }
+
+ /**
+ * Creates an implementation of the strategy for the given type
+ */
+ public static GroupByColumnSelectorStrategy forType(final ColumnType columnType)
+ {
+ if (columnType.equals(ColumnType.STRING)) {
+ // String types are handled specially because they can have multi-value dimensions
+ throw DruidException.defensive("Should use special variant which handles multi-value dimensions");
+ } else if (
+ // Defensive check, primitives should be using a faster fixed-width strategy
+ columnType.equals(ColumnType.DOUBLE)
+ || columnType.equals(ColumnType.FLOAT)
+ || columnType.equals(ColumnType.LONG)) {
+ throw DruidException.defensive("Could used a fixed width strategy");
+ }
+
+ if (ColumnType.STRING_ARRAY.equals(columnType)) {
+ forStringArrays();
+ }
+
+ // Catch-all for all other types, that can only have single-valued dimensions
+ return forArrayAndComplexTypes(columnType);
+ }
+
+ /**
+ * Implemenatation of dictionary building strategy for types other than strings (since they can be multi-valued and need
+ * to be handled separately) and numeric primitives (since they can be handled by fixed-width strategy).
+ * This also means that we handle array and complex types here, which simplifies the generics a lot, as everything can be
+ * treated as Object in this class.
+ * <p>
+ * Also, there isn't any concept of multi-values here, therefore Dimension == DimensionHolderType == Object. We still
+ * homogenize rogue selectors which can return non-standard implementation of arrays (like Long[] for long arrays instead of
+ * Object[]) to what the callers would expect (i.e. Object[] in this case).
+ */
+ private static GroupByColumnSelectorStrategy forArrayAndComplexTypes(final ColumnType columnType)
+ {
+ final List<Object> dictionary = DictionaryBuildingUtils.createDictionary();
+ final Object2IntMap<Object> reverseDictionary =
+ DictionaryBuildingUtils.createReverseDictionary(columnType.getNullableStrategy());
+ return new DictionaryBuildingGroupByColumnSelectorStrategy<>(
+ new UniValueDimensionIdCodec(dictionary, reverseDictionary, columnType.getNullableStrategy()),
+ columnType,
+ columnType.getNullableStrategy(),
+ null
+ );
+ }
+
+ private static GroupByColumnSelectorStrategy forStringArrays()
+ {
+ final BiMap<String, Integer> elementBiDictionary = HashBiMap.create();
+ final BiMap<ArrayList<Integer>, Integer> arrayBiDictionary = HashBiMap.create();
+ return new DictionaryBuildingGroupByColumnSelectorStrategy<>(
+ new StringArrayDimensionIdCodec(elementBiDictionary, arrayBiDictionary),
+ ColumnType.STRING_ARRAY,
+ ColumnType.STRING_ARRAY.getNullableStrategy(),
+ null
+ );
+ }
+
+ private static class UniValueDimensionIdCodec implements DimensionIdCodec<Object>
+ {
+ /**
+ * Dictionary for mapping the dimension value to an index. i-th position in the dictionary holds the value represented
+ * by the dictionaryId "i".
+ * Therefore, if a value has a dictionary id "i", dictionary.get(i) = value
+ * If a -> 0, b -> 1, c -> 2 (value -> dictionaryId), then the dictionary would be laid out like: [a, b, c]
+ */
+ private final List<Object> dictionary;
+
+ /**
+ * Reverse dictionary for faster lookup into the dictionary, and reusing pre-existing dictionary ids.
+ * <p>
+ * An entry of form (value, i) in the reverse dictionary represents that "value" is present at the i-th location in the
+ * {@link #dictionary}.
+ * Absence of mapping of a "value" (denoted by returning {@link GroupByColumnSelectorStrategy#GROUP_BY_MISSING_VALUE})
+ * represents that the value is absent in the dictionary
+ * If a -> 0, b -> 1, c -> 2 (value -> dictionaryId), then the reverse dictionary would have the entries (a, 0), (b, 1),
+ * (c, 2)
+ */
+ private final Object2IntMap<Object> reverseDictionary;
+
+ @SuppressWarnings("rawtypes")
+ private final NullableTypeStrategy nullableTypeStrategy;
+
+ public UniValueDimensionIdCodec(
+ final List<Object> dictionary,
+ final Object2IntMap<Object> reverseDictionary,
+ final NullableTypeStrategy nullableTypeStrategy
+ )
+ {
+ this.dictionary = dictionary;
+ this.reverseDictionary = reverseDictionary;
Review Comment:
I feel the objects should be owned by the code since we are resetting them.
--
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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1545980953
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/DictionaryBuildingGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,200 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import it.unimi.dsi.fastutil.objects.Object2IntMap;
+import org.apache.druid.error.DruidException;
+import org.apache.druid.query.groupby.epinephelinae.DictionaryBuildingUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.column.NullableTypeStrategy;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.List;
+
+/**
+ * Strategy for grouping dimensions which can have variable-width objects, and aren't backed by prebuilt dictionaries. It
+ * encapsulates the dictionary building logic, along with providing the implementations for dimension to dictionary id
+ * encoding-decoding.
+ * <p>
+ * This strategy can handle any dimension that can be addressed on a reverse-dictionary. Reverse dictionary uses
+ * a sorted map, rather than a hashmap.
+ * <p>
+ * This is the most expensive of all the strategies, and hence must be used only when other strategies aren't valid.
+ */
+@NotThreadSafe
+public class DictionaryBuildingGroupByColumnSelectorStrategy<DimensionType>
+ extends KeyMappingGroupByColumnSelectorStrategy<DimensionType>
+{
+
+ /**
+ * Dictionary for mapping the dimension value to an index. i-th position in the dictionary holds the value represented
+ * by the dictionaryId "i".
+ * Therefore, if a value has a dictionary id "i", dictionary.get(i) = value
+ */
+ private final List<DimensionType> dictionary;
+
+ /**
+ * Reverse dictionary for faster lookup into the dictionary, and reusing pre-existing dictionary ids.
+ * <p>
+ * An entry of form (value, i) in the reverse dictionary represents that "value" is present at the i-th location in the
+ * {@link #dictionary}.
+ * Absence of mapping of a "value" (denoted by returning {@link GroupByColumnSelectorStrategy#GROUP_BY_MISSING_VALUE})
+ * represents that the value is absent in the dictionary
+ */
+ private final Object2IntMap<DimensionType> reverseDictionary;
+
+ private DictionaryBuildingGroupByColumnSelectorStrategy(
+ DimensionToIdConverter<DimensionType> dimensionToIdConverter,
+ ColumnType columnType,
+ NullableTypeStrategy<DimensionType> nullableTypeStrategy,
+ DimensionType defaultValue,
+ IdToDimensionConverter<DimensionType> idToDimensionConverter,
+ List<DimensionType> dictionary,
+ Object2IntMap<DimensionType> reverseDictionary
+ )
+ {
+ super(dimensionToIdConverter, columnType, nullableTypeStrategy, defaultValue, idToDimensionConverter);
+ this.dictionary = dictionary;
+ this.reverseDictionary = reverseDictionary;
+ }
+
+ /**
+ * Creates an implementation of the strategy for the given type
+ */
+ public static GroupByColumnSelectorStrategy forType(final ColumnType columnType)
+ {
+ if (columnType.equals(ColumnType.STRING)) {
+ // String types are handled specially because they can have multi-value dimensions
+ throw DruidException.defensive("Should use special variant which handles multi-value dimensions");
Review Comment:
I haven't it out, but I suspect most of the work would happen while building the dictionary. On the flip side, it helped me get rid of the `PreBuiltGroupBySelectorStrategy` because there's no type at the moment that can exploit this, therefore this seemed lucrative.
I could add that back in, so adding stuff for the array dictionary becomes easier later. WDYT?
--
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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1533315580
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/PrebuiltDictionaryStringGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,138 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import org.apache.druid.common.config.NullHandling;
+import org.apache.druid.error.DruidException;
+import org.apache.druid.segment.ColumnValueSelector;
+import org.apache.druid.segment.DimensionSelector;
+import org.apache.druid.segment.column.ColumnCapabilities;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.data.IndexedInts;
+
+import javax.annotation.Nullable;
+
+/**
+ * Implementation of {@link KeyMappingGroupByColumnSelectorStrategy} that relies on a prebuilt dictionary to map the
+ * dimension to the dictionaryId. It is more like a helper class, that handles the different ways that dictionaries can be
+ * provided for different types. Currently, it only handles String dimensions. Array dimensions are also backed by dictionaries,
+ * but not exposed via the ColumnValueSelector interface, hence this strategy cannot handle array dimensions.
+ */
+public class PrebuiltDictionaryStringGroupByColumnSelectorStrategy
+{
+
+ /**
+ * Create the strategy for the provided column type
+ */
+ public static GroupByColumnSelectorStrategy forType(
+ final ColumnType columnType,
+ final ColumnValueSelector columnValueSelector,
+ final ColumnCapabilities columnCapabilities
+ )
+ {
+ if (columnType.equals(ColumnType.STRING)) {
+ return forString(columnValueSelector, columnCapabilities);
+ } else {
+ // This will change with array columns
+ throw DruidException.defensive("Only string columns expose prebuilt dictionaries");
+ }
+ }
+
+ private static GroupByColumnSelectorStrategy forString(
+ final ColumnValueSelector columnValueSelector,
+ final ColumnCapabilities columnCapabilities
+ )
+ {
+ return new KeyMappingGroupByColumnSelectorStrategy<>(
+ new StringDimensionToIdConverter(),
+ ColumnType.STRING,
+ ColumnType.STRING.getNullableStrategy(),
+ NullHandling.defaultStringValue(),
+ new StringIdToDimensionConverter((DimensionSelector) columnValueSelector, columnCapabilities)
+ );
+ }
+
+ /**
+ * Dimension to id converter for string dimensions and {@link DimensionSelector}, where the dictionaries are prebuilt.
+ * The callers must ensure that's the case by checking that {@link DimensionSelector#getValueCardinality()} is known
+ * and {@link DimensionSelector#nameLookupPossibleInAdvance()} is true.
+ */
+ private static class StringDimensionToIdConverter implements DimensionToIdConverter<IndexedInts>
+ {
+ @Override
+ public MemoryEstimate<IndexedInts> getMultiValueHolder(
+ final ColumnValueSelector selector,
+ final IndexedInts reusableValue
+ )
+ {
+ return new MemoryEstimate<>(((DimensionSelector) selector).getRow(), 0);
+ }
+
+ @Override
+ public int multiValueSize(IndexedInts multiValueHolder)
+ {
+ return multiValueHolder.size();
+ }
+
+ @Override
+ public MemoryEstimate<Integer> getIndividualValueDictId(IndexedInts multiValueHolder, int index)
+ {
+ // dictId is already encoded in the indexedInt supplied by the column value selector
+ return new MemoryEstimate<>(multiValueHolder.get(index), 0);
+ }
+ }
+
+ /**
+ * ID to dimension converter for {@link DimensionSelector} with prebuilt dictionary
+ */
+ private static class StringIdToDimensionConverter implements IdToDimensionConverter<String>
+ {
+
+ final DimensionSelector dimensionSelector;
+
+ @Nullable
+ final ColumnCapabilities columnCapabilities;
+
+ public StringIdToDimensionConverter(
+ final DimensionSelector dimensionSelector,
+ @Nullable final ColumnCapabilities columnCapabilities
+ )
+ {
+ this.dimensionSelector = dimensionSelector;
+ this.columnCapabilities = columnCapabilities;
+ }
+
+ @Override
+ public String idToKey(int id)
+ {
+ // Converting back to the value is as simple as looking up the value in the prebuilt dictionary
+ return dimensionSelector.lookupName(id);
+ }
+
+ @Override
+ public boolean canCompareIds()
+ {
+ return columnCapabilities != null
+ && columnCapabilities.hasBitmapIndexes()
+ && (columnCapabilities.areDictionaryValuesSorted()
+ .and(columnCapabilities.areDictionaryValuesUnique())).isTrue();
Review Comment:
Thanks for catching this. I was also confused about the condition, but then I chose to go ahead with the pre-existing code: https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/StringGroupByColumnSelectorStrategy.java#L165.
I'll correct this here.
--
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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1533344570
##########
sql/src/test/java/org/apache/druid/sql/calcite/QueryTestRunner.java:
##########
@@ -380,7 +380,7 @@ public VerifyNativeQueries(BaseExecuteQuery execStep)
public void verify()
{
for (QueryResults queryResults : execStep.results()) {
- verifyQuery(queryResults);
+// verifyQuery(queryResults);
Review Comment:
Yep, I didn't wanna write the query to verify that it was working. That's why I have also commented it out with Intellij style comment (s.t. it'd fail during checkstyle).
--
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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "github-advanced-security[bot] (via GitHub)" <gi...@apache.org>.
github-advanced-security[bot] commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1555687111
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/KeyMappingGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,238 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import org.apache.druid.query.DimensionComparisonUtils;
+import org.apache.druid.query.groupby.ResultRow;
+import org.apache.druid.query.groupby.epinephelinae.Grouper;
+import org.apache.druid.query.ordering.StringComparator;
+import org.apache.druid.segment.ColumnValueSelector;
+import org.apache.druid.segment.DimensionHandlerUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.column.NullableTypeStrategy;
+
+import javax.annotation.Nullable;
+import javax.annotation.concurrent.NotThreadSafe;
+import java.nio.ByteBuffer;
+
+/**
+ * Strategy for grouping dimensions which can have variable-width objects. Materializing such objects on the buffer
+ * require an additional step of mapping them to an integer index. The integer index can be materialized on the buffer within
+ * a fixed width, and is often backed by a dictionary representing the actual dimension object. It is used for arrays,
+ * strings, and complex types.
+ * <p>
+ * The visibility of the class is limited, and the callers must use one of the two variants of the mapping strategy:
+ * 1. {@link PrebuiltDictionaryGroupByColumnSelectorStrategy}
+ * 2. {@link DictionaryBuildingGroupByColumnSelectorStrategy}
+ * <p>
+ * {@code null} can be represented by either -1 or the position of null in the dictionary it was stored when it was
+ * encountered. This is fine, because most of the time, the dictionary id has no value of its own, and is converted back to
+ * the value it represents, before doing further operations. The only place where it would matter would be when
+ * {@link IdToDimensionConverter#canCompareIds()} is true, and we compare directly on the dictionary ids for prebuilt
+ * dictionaries (we can't compare ids for the dictionaries built on the fly in the grouping strategy). However, in that case,
+ * it is guaranteed that the dictionaryId of null represented by the pre-built dictionary would be the lowest (most likely 0)
+ * and therefore nulls (-1) would be adjacent to nulls (represented by the lowest non-negative dictionary id), and would get
+ * grouped in the later merge stages.
+ * <p>
+ * It only handles single value dimensions, i.e. all types except for strings. Strings are handled by the implementations
+ * of {@link KeyMappingMultiValueGroupByColumnSelectorStrategy}
+ * <p>
+ * It only handles non-primitive types, because numeric primitives are handled by the {@link FixedWidthGroupByColumnSelectorStrategy}
+ * and the string primitives are handled by the {@link KeyMappingMultiValueGroupByColumnSelectorStrategy}
+ *
+ * @param <DimensionType>> Class of the dimension
Review Comment:
## Spurious Javadoc @param tags
@param tag "<DimensionType>>" does not match any actual type parameter of type "KeyMappingGroupByColumnSelectorStrategy".
[Show more details](https://github.com/apache/druid/security/code-scanning/7229)
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/KeyMappingGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,238 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import org.apache.druid.query.DimensionComparisonUtils;
+import org.apache.druid.query.groupby.ResultRow;
+import org.apache.druid.query.groupby.epinephelinae.Grouper;
+import org.apache.druid.query.ordering.StringComparator;
+import org.apache.druid.segment.ColumnValueSelector;
+import org.apache.druid.segment.DimensionHandlerUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.column.NullableTypeStrategy;
+
+import javax.annotation.Nullable;
+import javax.annotation.concurrent.NotThreadSafe;
+import java.nio.ByteBuffer;
+
+/**
+ * Strategy for grouping dimensions which can have variable-width objects. Materializing such objects on the buffer
+ * require an additional step of mapping them to an integer index. The integer index can be materialized on the buffer within
+ * a fixed width, and is often backed by a dictionary representing the actual dimension object. It is used for arrays,
+ * strings, and complex types.
+ * <p>
+ * The visibility of the class is limited, and the callers must use one of the two variants of the mapping strategy:
+ * 1. {@link PrebuiltDictionaryGroupByColumnSelectorStrategy}
+ * 2. {@link DictionaryBuildingGroupByColumnSelectorStrategy}
+ * <p>
+ * {@code null} can be represented by either -1 or the position of null in the dictionary it was stored when it was
+ * encountered. This is fine, because most of the time, the dictionary id has no value of its own, and is converted back to
+ * the value it represents, before doing further operations. The only place where it would matter would be when
+ * {@link IdToDimensionConverter#canCompareIds()} is true, and we compare directly on the dictionary ids for prebuilt
+ * dictionaries (we can't compare ids for the dictionaries built on the fly in the grouping strategy). However, in that case,
+ * it is guaranteed that the dictionaryId of null represented by the pre-built dictionary would be the lowest (most likely 0)
+ * and therefore nulls (-1) would be adjacent to nulls (represented by the lowest non-negative dictionary id), and would get
+ * grouped in the later merge stages.
+ * <p>
+ * It only handles single value dimensions, i.e. all types except for strings. Strings are handled by the implementations
+ * of {@link KeyMappingMultiValueGroupByColumnSelectorStrategy}
+ * <p>
+ * It only handles non-primitive types, because numeric primitives are handled by the {@link FixedWidthGroupByColumnSelectorStrategy}
+ * and the string primitives are handled by the {@link KeyMappingMultiValueGroupByColumnSelectorStrategy}
+ *
+ * @param <DimensionType>> Class of the dimension
+ * @param <DimensionHolderType> Class of the "dimension holder". For single-value dimensions, the holder's type and the
Review Comment:
## Spurious Javadoc @param tags
@param tag "<DimensionHolderType>" does not match any actual type parameter of type "KeyMappingGroupByColumnSelectorStrategy".
[Show more details](https://github.com/apache/druid/security/code-scanning/7230)
--
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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1538847396
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/DimensionToIdConverter.java:
##########
@@ -0,0 +1,77 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import org.apache.druid.segment.ColumnValueSelector;
+
+import javax.annotation.Nullable;
+
+/**
+ * Interface for converters of dimension to dictionary id.
+ *
+ * This is a slightly convoluted interface because it also encapsulates the additional logic for handling multi-value
+ * dimensions. It has an additional step that converts the given dimensions to "dimension holders", which represent the
+ * multi-value holders for a given dimension.
+ * Therefore, the conversion goes from ColumnValueSelector -> DimensionHolder -> DictionaryID (for each dimension in the holder)
+ *
+ * The dimension holder is only applicable for multi-value strings.
+ * For other dimensions that cannot have multi-values the dimension holder is identical to the dimension. They can be
+ * defensively cast or homogenised, for example doubles to floats for float selectors or Long[] to Object[] for array
+ * selectors, so that the upstream callers can assume the class of the dimensions. The size of these dimensions is always 1,
+ * and only contain a value at index 0.
+ *
+ * Converting a value to its dictionary id might require building dictionaries on the fly while computing the id. The
+ * return type of the methods, except {@link #multiValueSize}, takes that into account.
+ *
+ * The implementations can pre-convert the value to the dictionaryId while extracting the dimensionHolder. Extracting
+ * dictionary id for a specific value from the (potentially multi-value dimension holder) can be done by calling
+ * {@link #getIndividualValueDictId} and passing the index to the multi-value.
+ *
+ * @see IdToDimensionConverter for converting the dictionary values back to dimensions
+ *
+ * @param <DimensionHolderType> Type of the dimension holder
+ */
+public interface DimensionToIdConverter<DimensionHolderType>
Review Comment:
👍
Currently, I am refactoring the keymapping strategy to
a. `KeyMappingGroupByColumnSelectorStrategy` - For arrays and complex types
b. `KeyMappingMultiValueGroupByColumnSelectorStrategy` - This would handle only strings. Upon thinking about it, it should be exactly the same as the `StringGroupByColumnSelectorStrategy`
--
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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1538847396
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/DimensionToIdConverter.java:
##########
@@ -0,0 +1,77 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import org.apache.druid.segment.ColumnValueSelector;
+
+import javax.annotation.Nullable;
+
+/**
+ * Interface for converters of dimension to dictionary id.
+ *
+ * This is a slightly convoluted interface because it also encapsulates the additional logic for handling multi-value
+ * dimensions. It has an additional step that converts the given dimensions to "dimension holders", which represent the
+ * multi-value holders for a given dimension.
+ * Therefore, the conversion goes from ColumnValueSelector -> DimensionHolder -> DictionaryID (for each dimension in the holder)
+ *
+ * The dimension holder is only applicable for multi-value strings.
+ * For other dimensions that cannot have multi-values the dimension holder is identical to the dimension. They can be
+ * defensively cast or homogenised, for example doubles to floats for float selectors or Long[] to Object[] for array
+ * selectors, so that the upstream callers can assume the class of the dimensions. The size of these dimensions is always 1,
+ * and only contain a value at index 0.
+ *
+ * Converting a value to its dictionary id might require building dictionaries on the fly while computing the id. The
+ * return type of the methods, except {@link #multiValueSize}, takes that into account.
+ *
+ * The implementations can pre-convert the value to the dictionaryId while extracting the dimensionHolder. Extracting
+ * dictionary id for a specific value from the (potentially multi-value dimension holder) can be done by calling
+ * {@link #getIndividualValueDictId} and passing the index to the multi-value.
+ *
+ * @see IdToDimensionConverter for converting the dictionary values back to dimensions
+ *
+ * @param <DimensionHolderType> Type of the dimension holder
+ */
+public interface DimensionToIdConverter<DimensionHolderType>
Review Comment:
👍
Currently, I am going ahead with refactoring the keymapping strategy to
a. KeyMappingGroupByColumnSelectorStrategy - For arrays, and complex types
b. KeyMappingMultiValueGroupByColumnSelectorStrategy - This would handle only strings
--
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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1540406635
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/IdToDimensionConverter.java:
##########
@@ -0,0 +1,56 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+/**
+ * Converts back the dictionaryId to the dimension value. The implementations might or might not handle
+ * {@link GroupByColumnSelectorStrategy#GROUP_BY_MISSING_VALUE}. The callers should handle those values appropriately on
+ * their own, and filter those out before trying to convert the dictionary id back to value.
+ *
+ * The encoding - decoding workflow looks like:
+ *
+ * Encoding
+ * 1. {@link DimensionToIdConverter} extracts the multi-value holder for the given row, which get's stored somewhere
+ * 2. For each entry in the multi-value object, the value gets encoded into a dictionaryId, using {@link DimensionToIdConverter#getIndividualValueDictId}
+ * 3. The callers can use this integer dictionaryID to materialize the results somewhere
+ *
+ * Decoding
+ * 1. The materialized dictionary id is deserialized back to an int, and then decoded into value using {@link #idToKey}
+ *
+ * @see DimensionToIdConverter for converting the dimensions to dictionary ids
+ *
+ * @param <DimensionType> Type of the dimension's values
+ */
+public interface IdToDimensionConverter<DimensionType>
Review Comment:
While refactoring, I realized that `IdLookup` is for the replacement of `DimensionToIdConvertor`. After separating out the strategy, it should be simple to replace `DimensionToIdConverter` with `IdLookup`
--
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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1545980953
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/DictionaryBuildingGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,200 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import it.unimi.dsi.fastutil.objects.Object2IntMap;
+import org.apache.druid.error.DruidException;
+import org.apache.druid.query.groupby.epinephelinae.DictionaryBuildingUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.column.NullableTypeStrategy;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.List;
+
+/**
+ * Strategy for grouping dimensions which can have variable-width objects, and aren't backed by prebuilt dictionaries. It
+ * encapsulates the dictionary building logic, along with providing the implementations for dimension to dictionary id
+ * encoding-decoding.
+ * <p>
+ * This strategy can handle any dimension that can be addressed on a reverse-dictionary. Reverse dictionary uses
+ * a sorted map, rather than a hashmap.
+ * <p>
+ * This is the most expensive of all the strategies, and hence must be used only when other strategies aren't valid.
+ */
+@NotThreadSafe
+public class DictionaryBuildingGroupByColumnSelectorStrategy<DimensionType>
+ extends KeyMappingGroupByColumnSelectorStrategy<DimensionType>
+{
+
+ /**
+ * Dictionary for mapping the dimension value to an index. i-th position in the dictionary holds the value represented
+ * by the dictionaryId "i".
+ * Therefore, if a value has a dictionary id "i", dictionary.get(i) = value
+ */
+ private final List<DimensionType> dictionary;
+
+ /**
+ * Reverse dictionary for faster lookup into the dictionary, and reusing pre-existing dictionary ids.
+ * <p>
+ * An entry of form (value, i) in the reverse dictionary represents that "value" is present at the i-th location in the
+ * {@link #dictionary}.
+ * Absence of mapping of a "value" (denoted by returning {@link GroupByColumnSelectorStrategy#GROUP_BY_MISSING_VALUE})
+ * represents that the value is absent in the dictionary
+ */
+ private final Object2IntMap<DimensionType> reverseDictionary;
+
+ private DictionaryBuildingGroupByColumnSelectorStrategy(
+ DimensionToIdConverter<DimensionType> dimensionToIdConverter,
+ ColumnType columnType,
+ NullableTypeStrategy<DimensionType> nullableTypeStrategy,
+ DimensionType defaultValue,
+ IdToDimensionConverter<DimensionType> idToDimensionConverter,
+ List<DimensionType> dictionary,
+ Object2IntMap<DimensionType> reverseDictionary
+ )
+ {
+ super(dimensionToIdConverter, columnType, nullableTypeStrategy, defaultValue, idToDimensionConverter);
+ this.dictionary = dictionary;
+ this.reverseDictionary = reverseDictionary;
+ }
+
+ /**
+ * Creates an implementation of the strategy for the given type
+ */
+ public static GroupByColumnSelectorStrategy forType(final ColumnType columnType)
+ {
+ if (columnType.equals(ColumnType.STRING)) {
+ // String types are handled specially because they can have multi-value dimensions
+ throw DruidException.defensive("Should use special variant which handles multi-value dimensions");
Review Comment:
I haven't it out, but I suspect most of the work would happen while building the dictionary. On the flip side, it helped me get rid of the `PreBuiltGroupBySelectorStrategy` because there's no type at the moment that can exploit this, therefore this seemed lucrative.
I could add that back in, so adding stuff for the array dictionary becomes easier 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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1553265926
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/GroupByColumnSelectorStrategyFactory.java:
##########
@@ -0,0 +1,96 @@
+/*
+ * 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.query.groupby.epinephelinae;
+
+import org.apache.druid.error.DruidException;
+import org.apache.druid.java.util.common.IAE;
+import org.apache.druid.query.dimension.ColumnSelectorStrategyFactory;
+import org.apache.druid.query.groupby.epinephelinae.column.DictionaryBuildingGroupByColumnSelectorStrategy;
+import org.apache.druid.query.groupby.epinephelinae.column.FixedWidthGroupByColumnSelectorStrategy;
+import org.apache.druid.query.groupby.epinephelinae.column.GroupByColumnSelectorStrategy;
+import org.apache.druid.query.groupby.epinephelinae.column.PrebuiltDictionaryStringGroupByColumnSelectorStrategy;
+import org.apache.druid.segment.ColumnValueSelector;
+import org.apache.druid.segment.DimensionSelector;
+import org.apache.druid.segment.column.ColumnCapabilities;
+import org.apache.druid.segment.column.ColumnType;
+
+/**
+ * Creates {@link org.apache.druid.query.dimension.ColumnSelectorStrategy}s for grouping dimensions
+ */
+public class GroupByColumnSelectorStrategyFactory implements ColumnSelectorStrategyFactory<GroupByColumnSelectorStrategy>
+{
+ @Override
+ public GroupByColumnSelectorStrategy makeColumnSelectorStrategy(
+ ColumnCapabilities capabilities,
+ ColumnValueSelector selector
+ )
+ {
+ if (capabilities == null || capabilities.getType() == null) {
+ throw DruidException.defensive("Unable to deduce type for the grouping dimension");
+ }
+ switch (capabilities.getType()) {
+ case STRING:
+ DimensionSelector dimSelector = (DimensionSelector) selector;
+ if (dimSelector.getValueCardinality() >= 0 && dimSelector.nameLookupPossibleInAdvance()) {
+ return PrebuiltDictionaryStringGroupByColumnSelectorStrategy.forType(
+ ColumnType.STRING,
+ selector,
+ capabilities
+ );
+ } else {
+ return DictionaryBuildingGroupByColumnSelectorStrategy.forType(ColumnType.STRING);
+ }
+ case LONG:
+ return new FixedWidthGroupByColumnSelectorStrategy<Long>(
+ Byte.BYTES + Long.BYTES,
Review Comment:
Good point, I am always surprised that the `NullableTypeStrategy` isn't an instance of `TypeStrategy`. I think a cleaner approach would be to make the `NullableTypeStrategy` instanceof `TypeStrategy` and proceed from there. If not addressed here, I can make up a follow-up improvement for the same.
--
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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "clintropolis (via GitHub)" <gi...@apache.org>.
clintropolis commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1538804829
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/DimensionToIdConverter.java:
##########
@@ -0,0 +1,77 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import org.apache.druid.segment.ColumnValueSelector;
+
+import javax.annotation.Nullable;
+
+/**
+ * Interface for converters of dimension to dictionary id.
+ *
+ * This is a slightly convoluted interface because it also encapsulates the additional logic for handling multi-value
+ * dimensions. It has an additional step that converts the given dimensions to "dimension holders", which represent the
+ * multi-value holders for a given dimension.
+ * Therefore, the conversion goes from ColumnValueSelector -> DimensionHolder -> DictionaryID (for each dimension in the holder)
+ *
+ * The dimension holder is only applicable for multi-value strings.
+ * For other dimensions that cannot have multi-values the dimension holder is identical to the dimension. They can be
+ * defensively cast or homogenised, for example doubles to floats for float selectors or Long[] to Object[] for array
+ * selectors, so that the upstream callers can assume the class of the dimensions. The size of these dimensions is always 1,
+ * and only contain a value at index 0.
+ *
+ * Converting a value to its dictionary id might require building dictionaries on the fly while computing the id. The
+ * return type of the methods, except {@link #multiValueSize}, takes that into account.
+ *
+ * The implementations can pre-convert the value to the dictionaryId while extracting the dimensionHolder. Extracting
+ * dictionary id for a specific value from the (potentially multi-value dimension holder) can be done by calling
+ * {@link #getIndividualValueDictId} and passing the index to the multi-value.
+ *
+ * @see IdToDimensionConverter for converting the dictionary values back to dimensions
+ *
+ * @param <DimensionHolderType> Type of the dimension holder
+ */
+public interface DimensionToIdConverter<DimensionHolderType>
Review Comment:
well, rather than explicitly writing that function, the idea would be to automatically wrap the `storageAdapter` in an `UnnestStorageAdapter` for each multi-value string being grouped. The cursors made by `UnnestStorageAdapter` already use dimension selectors in the case of a multi-value string, and so can produce dictionary encoded dimension selectors from the cursor as well, so we should be able to retain grouping directly on the dimension id. If i recall correctly, because we use the dimension selector for the unnest cursor, I _think_ it should behave the same way as the grouping engine with regards to `null` and `[]`, but I would have to confirm.
This is probably too big of a change for this PR though, so I don't think this refactor needs to be done right now, but is worth pursuing in the future I think because it feels like the right way to handle things, then grouping itself has no concept of multi-value dimensions which sounds pretty amazing to me.
--
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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "clintropolis (via GitHub)" <gi...@apache.org>.
clintropolis commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1543788649
##########
processing/src/main/java/org/apache/druid/segment/column/TypeStrategies.java:
##########
@@ -518,6 +590,12 @@ public int write(ByteBuffer buffer, Object[] value, int maxSizeBytes)
return extraNeeded < 0 ? extraNeeded : sizeBytes;
}
+ @Override
+ public boolean groupable()
+ {
+ return true;
Review Comment:
this should check if element type strategy is groupable
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/DictionaryBuildingGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,200 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import it.unimi.dsi.fastutil.objects.Object2IntMap;
+import org.apache.druid.error.DruidException;
+import org.apache.druid.query.groupby.epinephelinae.DictionaryBuildingUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.column.NullableTypeStrategy;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.List;
+
+/**
+ * Strategy for grouping dimensions which can have variable-width objects, and aren't backed by prebuilt dictionaries. It
+ * encapsulates the dictionary building logic, along with providing the implementations for dimension to dictionary id
+ * encoding-decoding.
+ * <p>
+ * This strategy can handle any dimension that can be addressed on a reverse-dictionary. Reverse dictionary uses
+ * a sorted map, rather than a hashmap.
+ * <p>
+ * This is the most expensive of all the strategies, and hence must be used only when other strategies aren't valid.
+ */
+@NotThreadSafe
+public class DictionaryBuildingGroupByColumnSelectorStrategy<DimensionType>
+ extends KeyMappingGroupByColumnSelectorStrategy<DimensionType>
+{
+
+ /**
+ * Dictionary for mapping the dimension value to an index. i-th position in the dictionary holds the value represented
+ * by the dictionaryId "i".
+ * Therefore, if a value has a dictionary id "i", dictionary.get(i) = value
+ */
+ private final List<DimensionType> dictionary;
+
+ /**
+ * Reverse dictionary for faster lookup into the dictionary, and reusing pre-existing dictionary ids.
+ * <p>
+ * An entry of form (value, i) in the reverse dictionary represents that "value" is present at the i-th location in the
+ * {@link #dictionary}.
+ * Absence of mapping of a "value" (denoted by returning {@link GroupByColumnSelectorStrategy#GROUP_BY_MISSING_VALUE})
+ * represents that the value is absent in the dictionary
+ */
+ private final Object2IntMap<DimensionType> reverseDictionary;
+
+ private DictionaryBuildingGroupByColumnSelectorStrategy(
+ DimensionToIdConverter<DimensionType> dimensionToIdConverter,
+ ColumnType columnType,
+ NullableTypeStrategy<DimensionType> nullableTypeStrategy,
+ DimensionType defaultValue,
+ IdToDimensionConverter<DimensionType> idToDimensionConverter,
+ List<DimensionType> dictionary,
+ Object2IntMap<DimensionType> reverseDictionary
+ )
+ {
+ super(dimensionToIdConverter, columnType, nullableTypeStrategy, defaultValue, idToDimensionConverter);
+ this.dictionary = dictionary;
+ this.reverseDictionary = reverseDictionary;
+ }
+
+ /**
+ * Creates an implementation of the strategy for the given type
+ */
+ public static GroupByColumnSelectorStrategy forType(final ColumnType columnType)
+ {
+ if (columnType.equals(ColumnType.STRING)) {
+ // String types are handled specially because they can have multi-value dimensions
+ throw DruidException.defensive("Should use special variant which handles multi-value dimensions");
Review Comment:
this can handle regular strings probably, since if we know that a string column definitely isn't multi-value it probably more efficient to not have to check every value?
--
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
Re: [PR] Grouping on complex columns aka unifying GroupBy strategies (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1574136998
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/DictionaryBuildingGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,203 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import it.unimi.dsi.fastutil.objects.Object2IntMap;
+import org.apache.druid.error.DruidException;
+import org.apache.druid.query.groupby.epinephelinae.DictionaryBuildingUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.column.NullableTypeStrategy;
+
+import javax.annotation.concurrent.NotThreadSafe;
+import java.util.List;
+
+/**
+ * Strategy for grouping dimensions which can have variable-width objects, and aren't backed by prebuilt dictionaries. It
+ * encapsulates the dictionary building logic, along with providing the implementations for dimension to dictionary id
+ * encoding-decoding.
+ * <p>
+ * This strategy can handle any dimension that can be addressed on a reverse-dictionary. Reverse dictionary uses
+ * a sorted map, rather than a hashmap.
+ * <p>
+ * This is the most expensive of all the strategies, and hence must be used only when other strategies aren't valid.
+ */
+@NotThreadSafe
+public class DictionaryBuildingGroupByColumnSelectorStrategy<DimensionType>
+ extends KeyMappingGroupByColumnSelectorStrategy<DimensionType>
+{
+
+ /**
+ * Dictionary for mapping the dimension value to an index. i-th position in the dictionary holds the value represented
+ * by the dictionaryId "i".
+ * Therefore, if a value has a dictionary id "i", dictionary.get(i) = value
+ */
+ private final List<DimensionType> dictionary;
+
+ /**
+ * Reverse dictionary for faster lookup into the dictionary, and reusing pre-existing dictionary ids.
+ * <p>
+ * An entry of form (value, i) in the reverse dictionary represents that "value" is present at the i-th location in the
+ * {@link #dictionary}.
+ * Absence of mapping of a "value" (denoted by returning {@link GroupByColumnSelectorStrategy#GROUP_BY_MISSING_VALUE})
+ * represents that the value is absent in the dictionary
+ */
+ private final Object2IntMap<DimensionType> reverseDictionary;
+
+ private DictionaryBuildingGroupByColumnSelectorStrategy(
+ DimensionToIdConverter<DimensionType> dimensionToIdConverter,
+ ColumnType columnType,
+ NullableTypeStrategy<DimensionType> nullableTypeStrategy,
+ DimensionType defaultValue,
+ IdToDimensionConverter<DimensionType> idToDimensionConverter,
+ List<DimensionType> dictionary,
+ Object2IntMap<DimensionType> reverseDictionary
+ )
+ {
+ super(dimensionToIdConverter, columnType, nullableTypeStrategy, defaultValue, idToDimensionConverter);
+ this.dictionary = dictionary;
+ this.reverseDictionary = reverseDictionary;
+ }
+
+ /**
+ * Creates an implementation of the strategy for the given type
+ */
+ public static GroupByColumnSelectorStrategy forType(final ColumnType columnType)
+ {
+ if (columnType.equals(ColumnType.STRING)) {
+ // String types are handled specially because they can have multi-value dimensions
+ throw DruidException.defensive("Should use special variant which handles multi-value dimensions");
+ } else if (
+ // Defensive check, primitives should be using a faster fixed-width strategy
+ columnType.equals(ColumnType.DOUBLE)
+ || columnType.equals(ColumnType.FLOAT)
+ || columnType.equals(ColumnType.LONG)) {
+ throw DruidException.defensive("Could used a fixed width strategy");
+ }
+
+ // Catch-all for all other types, that can only have single-valued dimensions
+ return forArrayAndComplexTypes(columnType);
+ }
+
+ /**
+ * Implemenatation of dictionary building strategy for types other than strings (since they can be multi-valued and need
+ * to be handled separately) and numeric primitives (since they can be handled by fixed-width strategy).
+ * This also means that we handle array and complex types here, which simplifies the generics a lot, as everything can be
+ * treated as Object in this class.
+ * <p>
+ * Also, there isn't any concept of multi-values here, therefore Dimension == DimensionHolderType == Object. We still
+ * homogenize rogue selectors which can return non-standard implementation of arrays (like Long[] for long arrays instead of
+ * Object[]) to what the callers would expect (i.e. Object[] in this case).
+ */
+ private static GroupByColumnSelectorStrategy forArrayAndComplexTypes(final ColumnType columnType)
+ {
+ final List<Object> dictionary = DictionaryBuildingUtils.createDictionary();
+ final Object2IntMap<Object> reverseDictionary =
+ DictionaryBuildingUtils.createReverseDictionary(columnType.getNullableStrategy());
Review Comment:
Even though the generics aren't used while being called, they are still helping with static type checks in the implementing class. Also, the generics arent' used properly, since there isn't any mapping between the type strategy and the java object that it requires.
--
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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1534737144
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/RowBasedGrouperHelper.java:
##########
@@ -1531,32 +1548,136 @@ private RowBasedKeySerdeHelper makeNumericSerdeHelper(
}
}
- private class ArrayNumericRowBasedKeySerdeHelper implements RowBasedKeySerdeHelper
+ private abstract class DictionaryBuildingSingleValuedRowBasedKeySerdeHelper implements RowBasedKeySerdeHelper
+ {
+ private final int keyBufferPosition;
+
+ public DictionaryBuildingSingleValuedRowBasedKeySerdeHelper(final int keyBufferPosition)
+ {
+ this.keyBufferPosition = keyBufferPosition;
+ }
+
+ @Override
+ public int getKeyBufferValueSize()
+ {
+ return Integer.BYTES;
+ }
+
+ @Override
+ public boolean putToKeyBuffer(RowBasedKey key, int idx)
+ {
+ final Object obj = key.getKey()[idx];
+ int id = getReverseDictionary().getInt(obj);
+ if (id == DimensionDictionary.ABSENT_VALUE_ID) {
+ id = getDictionary().size();
+ getReverseDictionary().put(obj, id);
+ getDictionary().add(obj);
+ }
+ keyBuffer.putInt(id);
+ return true;
+ }
+
+ @Override
+ public void getFromByteBuffer(ByteBuffer buffer, int initialOffset, int dimValIdx, Object[] dimValues)
+ {
+ dimValues[dimValIdx] = getDictionary().get(buffer.getInt(initialOffset + keyBufferPosition));
+ }
+
+ /**
+ * Raw type used because arrays and object dictionaries differ
+ */
+ @SuppressWarnings("rawtypes")
+ public abstract List getDictionary();
+
+ /**
+ * Raw types used because arrays and object dictionaries differ
+ */
+ @SuppressWarnings("rawtypes")
+ public abstract Object2IntMap getReverseDictionary();
+ }
+
+ private class ComplexRowBasedKeySerdeHelper extends DictionaryBuildingSingleValuedRowBasedKeySerdeHelper
{
final int keyBufferPosition;
final BufferComparator bufferComparator;
- final TypeSignature<ValueType> elementType;
+ final ColumnType complexType;
+ final String complexTypeName;
+
+ final List<Object> complexTypeDictionary;
+ final Object2IntMap<Object> complexTypeReverseDictionary;
+
+ public ComplexRowBasedKeySerdeHelper(
+ int keyBufferPosition,
+ ColumnType complexType
+ )
+ {
+ super(keyBufferPosition);
+ this.keyBufferPosition = keyBufferPosition;
+ this.complexType = complexType;
+ this.complexTypeName = Preconditions.checkNotNull(complexType.getComplexTypeName(), "complex type name expected");
Review Comment:
I kept it separate in case we wanna revisit using the hashmaps instead of sortedMaps for them.
--
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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1533315580
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/PrebuiltDictionaryStringGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,138 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import org.apache.druid.common.config.NullHandling;
+import org.apache.druid.error.DruidException;
+import org.apache.druid.segment.ColumnValueSelector;
+import org.apache.druid.segment.DimensionSelector;
+import org.apache.druid.segment.column.ColumnCapabilities;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.data.IndexedInts;
+
+import javax.annotation.Nullable;
+
+/**
+ * Implementation of {@link KeyMappingGroupByColumnSelectorStrategy} that relies on a prebuilt dictionary to map the
+ * dimension to the dictionaryId. It is more like a helper class, that handles the different ways that dictionaries can be
+ * provided for different types. Currently, it only handles String dimensions. Array dimensions are also backed by dictionaries,
+ * but not exposed via the ColumnValueSelector interface, hence this strategy cannot handle array dimensions.
+ */
+public class PrebuiltDictionaryStringGroupByColumnSelectorStrategy
+{
+
+ /**
+ * Create the strategy for the provided column type
+ */
+ public static GroupByColumnSelectorStrategy forType(
+ final ColumnType columnType,
+ final ColumnValueSelector columnValueSelector,
+ final ColumnCapabilities columnCapabilities
+ )
+ {
+ if (columnType.equals(ColumnType.STRING)) {
+ return forString(columnValueSelector, columnCapabilities);
+ } else {
+ // This will change with array columns
+ throw DruidException.defensive("Only string columns expose prebuilt dictionaries");
+ }
+ }
+
+ private static GroupByColumnSelectorStrategy forString(
+ final ColumnValueSelector columnValueSelector,
+ final ColumnCapabilities columnCapabilities
+ )
+ {
+ return new KeyMappingGroupByColumnSelectorStrategy<>(
+ new StringDimensionToIdConverter(),
+ ColumnType.STRING,
+ ColumnType.STRING.getNullableStrategy(),
+ NullHandling.defaultStringValue(),
+ new StringIdToDimensionConverter((DimensionSelector) columnValueSelector, columnCapabilities)
+ );
+ }
+
+ /**
+ * Dimension to id converter for string dimensions and {@link DimensionSelector}, where the dictionaries are prebuilt.
+ * The callers must ensure that's the case by checking that {@link DimensionSelector#getValueCardinality()} is known
+ * and {@link DimensionSelector#nameLookupPossibleInAdvance()} is true.
+ */
+ private static class StringDimensionToIdConverter implements DimensionToIdConverter<IndexedInts>
+ {
+ @Override
+ public MemoryEstimate<IndexedInts> getMultiValueHolder(
+ final ColumnValueSelector selector,
+ final IndexedInts reusableValue
+ )
+ {
+ return new MemoryEstimate<>(((DimensionSelector) selector).getRow(), 0);
+ }
+
+ @Override
+ public int multiValueSize(IndexedInts multiValueHolder)
+ {
+ return multiValueHolder.size();
+ }
+
+ @Override
+ public MemoryEstimate<Integer> getIndividualValueDictId(IndexedInts multiValueHolder, int index)
+ {
+ // dictId is already encoded in the indexedInt supplied by the column value selector
+ return new MemoryEstimate<>(multiValueHolder.get(index), 0);
+ }
+ }
+
+ /**
+ * ID to dimension converter for {@link DimensionSelector} with prebuilt dictionary
+ */
+ private static class StringIdToDimensionConverter implements IdToDimensionConverter<String>
+ {
+
+ final DimensionSelector dimensionSelector;
+
+ @Nullable
+ final ColumnCapabilities columnCapabilities;
+
+ public StringIdToDimensionConverter(
+ final DimensionSelector dimensionSelector,
+ @Nullable final ColumnCapabilities columnCapabilities
+ )
+ {
+ this.dimensionSelector = dimensionSelector;
+ this.columnCapabilities = columnCapabilities;
+ }
+
+ @Override
+ public String idToKey(int id)
+ {
+ // Converting back to the value is as simple as looking up the value in the prebuilt dictionary
+ return dimensionSelector.lookupName(id);
+ }
+
+ @Override
+ public boolean canCompareIds()
+ {
+ return columnCapabilities != null
+ && columnCapabilities.hasBitmapIndexes()
+ && (columnCapabilities.areDictionaryValuesSorted()
+ .and(columnCapabilities.areDictionaryValuesUnique())).isTrue();
Review Comment:
Thanks for catching this. I was also confused about the condition, but then I chose to go ahead with the pre-existing code: https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/StringGroupByColumnSelectorStrategy.java#L165.
--
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
Re: [PR] Unifying GroupBy strategies and grouping on complex columns (druid)
Posted by "LakshSingla (via GitHub)" <gi...@apache.org>.
LakshSingla commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1533345355
##########
processing/src/main/java/org/apache/druid/segment/column/TypeStrategies.java:
##########
@@ -47,6 +49,9 @@ public class TypeStrategies
public static final StringTypeStrategy STRING = new StringTypeStrategy();
public static final ConcurrentHashMap<String, TypeStrategy<?>> COMPLEX_STRATEGIES = new ConcurrentHashMap<>();
+ static {
+ ComplexMetrics.registerSerde(ColumnType.NESTED_DATA.getComplexTypeName(), new NestedDataComplexTypeSerde());
+ }
Review Comment:
oops, definitely didn't intend that there.
--
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
Re: [PR] Grouping on complex columns aka unifying GroupBy strategies (druid)
Posted by "github-advanced-security[bot] (via GitHub)" <gi...@apache.org>.
github-advanced-security[bot] commented on code in PR #16068:
URL: https://github.com/apache/druid/pull/16068#discussion_r1570539467
##########
processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/column/KeyMappingGroupByColumnSelectorStrategy.java:
##########
@@ -0,0 +1,230 @@
+/*
+ * 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.query.groupby.epinephelinae.column;
+
+import org.apache.druid.query.DimensionComparisonUtils;
+import org.apache.druid.query.groupby.ResultRow;
+import org.apache.druid.query.groupby.epinephelinae.Grouper;
+import org.apache.druid.query.ordering.StringComparator;
+import org.apache.druid.segment.ColumnValueSelector;
+import org.apache.druid.segment.DimensionHandlerUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.column.NullableTypeStrategy;
+
+import javax.annotation.Nullable;
+import javax.annotation.concurrent.NotThreadSafe;
+import java.nio.ByteBuffer;
+
+/**
+ * Strategy for grouping single value dimensions which can have variable-width objects. Materializing such objects on the buffer
+ * require an additional step of mapping them to an integer index. The integer index can be materialized on the buffer within
+ * a fixed width, and is often backed by a dictionary representing the actual dimension object. It is used for arrays,
+ * and complex types.
+ * <p>
+ * The visibility of the class is limited, and the callers must use one of the two variants of the mapping strategy:
+ * 1. TODO(laksh): PrebuiltDictionaryGroupByColumnSelectorStrategy - (not available, because no one is using it)
+ * 2. {@link DictionaryBuildingGroupByColumnSelectorStrategy}
+ * <p>
+ * {@code null} can be represented by either -1 or the position of null in the dictionary it was stored when it was
+ * encountered. This is fine, because most of the time, the dictionary id has no value of its own, and is converted back to
+ * the value it represents, before doing further operations. The only place where it would matter would be when
+ * {@link DimensionIdCodec#canCompareIds()} is true, and we compare directly on the dictionary ids for prebuilt
+ * dictionaries (we can't compare ids for the dictionaries built on the fly in the grouping strategy). However, in that case,
+ * it is guaranteed that the dictionaryId of null represented by the pre-built dictionary would be the lowest (most likely 0)
+ * and therefore nulls (-1) would be adjacent to nulls (represented by the lowest non-negative dictionary id), and would get
+ * grouped in the later merge stages.
+ * <p>
+ * It only handles single value dimensions, i.e. every type except for strings. Strings are handled by the implementations
+ * of {@link KeyMappingMultiValueGroupByColumnSelectorStrategy}
+ * <p>
+ * It only handles non-primitive types, because numeric primitives are handled by the {@link FixedWidthGroupByColumnSelectorStrategy}
+ * and the string primitives are handled by the {@link KeyMappingMultiValueGroupByColumnSelectorStrategy}
+ *
+ * @param <DimensionType>> Class of the dimension
Review Comment:
## Spurious Javadoc @param tags
@param tag "<DimensionType>>" does not match any actual type parameter of type "KeyMappingGroupByColumnSelectorStrategy".
[Show more details](https://github.com/apache/druid/security/code-scanning/7293)
--
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