This is an automated email from the ASF dual-hosted git repository.
FrankChen021 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/druid.git
The following commit(s) were added to refs/heads/master by this push:
new d2c01508581 build: upgrade fastutil to 8.5.19 (#20771)
d2c01508581 is described below
commit d2c015085816174151a08f0fc3040c240ebf4b01
Author: Frank Chen <[email protected]>
AuthorDate: Fri Oct 30 12:52:48 2026 +0800
build: upgrade fastutil to 8.5.19 (#20771)
* build: upgrade fastutil to 8.5.19
Moved out of the Dependabot group update in #20765.
- fastutil 8.5.19 is a self-contained jar and no longer depends on
fastutil-core, so modules declare fastutil instead of fastutil-core to
satisfy dependency:analyze.
- IntArrayList#grow(int) became public, so DruidIntList drops its private
copy and uses the inherited one.
- fastutil object tree maps and sets now reject null keys, so
SortedDimensionDictionary and ComparatorSortedDimensionDictionary keep
null out of the map, and array_overlap with a constant array uses a
java.util.TreeSet.
* perf: sort dimension dictionaries by id instead of a tree map
SortedDimensionDictionary and ComparatorSortedDimensionDictionary now sort
an int[] of ids by their values rather than building an Object2IntRBTreeMap.
Null is ordered by the comparator like any other value, so it no longer
needs special handling, and the sort allocates only the result arrays.
Lists that are not RandomAccess are copied before sorting.
Adds unit tests for both classes.
* test: tighten sorted dimension dictionary tests
- Pin Java String ordering for STRING_STRATEGY with characters whose
UTF-8 byte order differs.
- Test sort() through StringDimensionDictionary and
ComparatorDimensionDictionary, the real callers.
- Drop the copy for lists that are not RandomAccess, which no caller
passes, along with its test.
- Drop the comparator suite's testEmpty, which only asserted an
exception.
* Address review: drop fastutil-core, delegate SortedDimensionDictionary
- Remove unused fastutil-core from root dependencyManagement and
licenses.yaml.
- SortedDimensionDictionary now delegates to
ComparatorSortedDimensionDictionary
with Comparators.naturalNullsFirst(), so the sort lives in one place.
* Address review: drop stale fastutil-extra from licenses.yaml
---
benchmarks/pom.xml | 2 +-
embedded-tests/pom.xml | 2 +-
extensions-contrib/ddsketch/pom.xml | 2 +-
extensions-contrib/distinctcount/pom.xml | 5 -
.../druid-deltalake-extensions/pom.xml | 3 +-
.../druid-exact-count-bitmap/pom.xml | 2 +-
extensions-contrib/spectator-histogram/pom.xml | 5 -
extensions-contrib/tdigestsketch/pom.xml | 2 +-
extensions-core/datasketches/pom.xml | 2 +-
extensions-core/histogram/pom.xml | 2 +-
extensions-core/lookups-cached-global/pom.xml | 2 +-
extensions-core/orc-extensions/pom.xml | 5 -
extensions-core/s3-extensions/pom.xml | 2 +-
indexing-service/pom.xml | 2 +-
licenses.yaml | 4 +-
multi-stage-query/pom.xml | 5 -
pom.xml | 7 +-
processing/pom.xml | 4 -
.../druid/collections/fastutil/DruidIntList.java | 23 ---
.../java/org/apache/druid/math/expr/Function.java | 3 +-
.../ComparatorSortedDimensionDictionary.java | 49 +++--
.../druid/segment/SortedDimensionDictionary.java | 57 +-----
.../ComparatorSortedDimensionDictionaryTest.java | 211 +++++++++++++++++++++
.../segment/SortedDimensionDictionaryTest.java | 184 ++++++++++++++++++
server/pom.xml | 2 +-
sql/pom.xml | 2 +-
26 files changed, 448 insertions(+), 141 deletions(-)
diff --git a/benchmarks/pom.xml b/benchmarks/pom.xml
index f96bb0eca95..82d47ea4b0e 100644
--- a/benchmarks/pom.xml
+++ b/benchmarks/pom.xml
@@ -170,7 +170,7 @@
</dependency>
<dependency>
<groupId>it.unimi.dsi</groupId>
- <artifactId>fastutil-core</artifactId>
+ <artifactId>fastutil</artifactId>
</dependency>
<dependency>
<groupId>org.roaringbitmap</groupId>
diff --git a/embedded-tests/pom.xml b/embedded-tests/pom.xml
index cc8982968a7..33e97ece929 100644
--- a/embedded-tests/pom.xml
+++ b/embedded-tests/pom.xml
@@ -525,7 +525,7 @@
</dependency>
<dependency>
<groupId>it.unimi.dsi</groupId>
- <artifactId>fastutil-core</artifactId>
+ <artifactId>fastutil</artifactId>
<scope>test</scope>
</dependency>
<dependency>
diff --git a/extensions-contrib/ddsketch/pom.xml
b/extensions-contrib/ddsketch/pom.xml
index bde1593cf99..57c40af876e 100644
--- a/extensions-contrib/ddsketch/pom.xml
+++ b/extensions-contrib/ddsketch/pom.xml
@@ -110,7 +110,7 @@
</dependency>
<dependency>
<groupId>it.unimi.dsi</groupId>
- <artifactId>fastutil-core</artifactId>
+ <artifactId>fastutil</artifactId>
<scope>provided</scope>
</dependency>
<dependency>
diff --git a/extensions-contrib/distinctcount/pom.xml
b/extensions-contrib/distinctcount/pom.xml
index ade118ab4f6..dfabaa39bf8 100644
--- a/extensions-contrib/distinctcount/pom.xml
+++ b/extensions-contrib/distinctcount/pom.xml
@@ -90,11 +90,6 @@
<artifactId>fastutil</artifactId>
<scope>provided</scope>
</dependency>
- <dependency>
- <groupId>it.unimi.dsi</groupId>
- <artifactId>fastutil-core</artifactId>
- <scope>provided</scope>
- </dependency>
<!-- Tests -->
<dependency>
diff --git a/extensions-contrib/druid-deltalake-extensions/pom.xml
b/extensions-contrib/druid-deltalake-extensions/pom.xml
index 6d5dfc11c38..c7503bbfa10 100644
--- a/extensions-contrib/druid-deltalake-extensions/pom.xml
+++ b/extensions-contrib/druid-deltalake-extensions/pom.xml
@@ -115,8 +115,7 @@
</dependency>
<dependency>
<groupId>it.unimi.dsi</groupId>
- <artifactId>fastutil-core</artifactId>
- <version>8.5.4</version>
+ <artifactId>fastutil</artifactId>
<scope>provided</scope>
</dependency>
<dependency>
diff --git a/extensions-contrib/druid-exact-count-bitmap/pom.xml
b/extensions-contrib/druid-exact-count-bitmap/pom.xml
index b45c93a2548..9b878d6498c 100644
--- a/extensions-contrib/druid-exact-count-bitmap/pom.xml
+++ b/extensions-contrib/druid-exact-count-bitmap/pom.xml
@@ -74,7 +74,7 @@
</dependency>
<dependency>
<groupId>it.unimi.dsi</groupId>
- <artifactId>fastutil-core</artifactId>
+ <artifactId>fastutil</artifactId>
<scope>provided</scope>
</dependency>
diff --git a/extensions-contrib/spectator-histogram/pom.xml
b/extensions-contrib/spectator-histogram/pom.xml
index 481f9d39636..3d98daf7273 100644
--- a/extensions-contrib/spectator-histogram/pom.xml
+++ b/extensions-contrib/spectator-histogram/pom.xml
@@ -101,11 +101,6 @@
<artifactId>jackson-annotations</artifactId>
<scope>provided</scope>
</dependency>
- <dependency>
- <groupId>it.unimi.dsi</groupId>
- <artifactId>fastutil-core</artifactId>
- <scope>provided</scope>
- </dependency>
<dependency>
<groupId>com.google.errorprone</groupId>
<artifactId>error_prone_annotations</artifactId>
diff --git a/extensions-contrib/tdigestsketch/pom.xml
b/extensions-contrib/tdigestsketch/pom.xml
index 1b528736159..e395bc24543 100644
--- a/extensions-contrib/tdigestsketch/pom.xml
+++ b/extensions-contrib/tdigestsketch/pom.xml
@@ -111,7 +111,7 @@
</dependency>
<dependency>
<groupId>it.unimi.dsi</groupId>
- <artifactId>fastutil-core</artifactId>
+ <artifactId>fastutil</artifactId>
<scope>provided</scope>
</dependency>
<dependency>
diff --git a/extensions-core/datasketches/pom.xml
b/extensions-core/datasketches/pom.xml
index 746b2d21406..d086d891753 100644
--- a/extensions-core/datasketches/pom.xml
+++ b/extensions-core/datasketches/pom.xml
@@ -99,7 +99,7 @@
</dependency>
<dependency>
<groupId>it.unimi.dsi</groupId>
- <artifactId>fastutil-core</artifactId>
+ <artifactId>fastutil</artifactId>
<scope>provided</scope>
</dependency>
diff --git a/extensions-core/histogram/pom.xml
b/extensions-core/histogram/pom.xml
index 9e119f56223..6d73479cca1 100644
--- a/extensions-core/histogram/pom.xml
+++ b/extensions-core/histogram/pom.xml
@@ -83,7 +83,7 @@
</dependency>
<dependency>
<groupId>it.unimi.dsi</groupId>
- <artifactId>fastutil-core</artifactId>
+ <artifactId>fastutil</artifactId>
<scope>provided</scope>
</dependency>
<dependency>
diff --git a/extensions-core/lookups-cached-global/pom.xml
b/extensions-core/lookups-cached-global/pom.xml
index 0d584c22b9d..81d2fac38dc 100644
--- a/extensions-core/lookups-cached-global/pom.xml
+++ b/extensions-core/lookups-cached-global/pom.xml
@@ -51,7 +51,7 @@
</dependency>
<dependency>
<groupId>it.unimi.dsi</groupId>
- <artifactId>fastutil-core</artifactId>
+ <artifactId>fastutil</artifactId>
<scope>provided</scope>
</dependency>
<dependency>
diff --git a/extensions-core/orc-extensions/pom.xml
b/extensions-core/orc-extensions/pom.xml
index ed60bdc9bd6..f1e3e78d7be 100644
--- a/extensions-core/orc-extensions/pom.xml
+++ b/extensions-core/orc-extensions/pom.xml
@@ -177,11 +177,6 @@
<artifactId>fastutil</artifactId>
<scope>provided</scope>
</dependency>
- <dependency>
- <groupId>it.unimi.dsi</groupId>
- <artifactId>fastutil-core</artifactId>
- <scope>provided</scope>
- </dependency>
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
diff --git a/extensions-core/s3-extensions/pom.xml
b/extensions-core/s3-extensions/pom.xml
index 976ce809ea3..d13a746306c 100644
--- a/extensions-core/s3-extensions/pom.xml
+++ b/extensions-core/s3-extensions/pom.xml
@@ -179,7 +179,7 @@
</dependency>
<dependency>
<groupId>it.unimi.dsi</groupId>
- <artifactId>fastutil-core</artifactId>
+ <artifactId>fastutil</artifactId>
<scope>provided</scope>
</dependency>
<!-- Tests -->
diff --git a/indexing-service/pom.xml b/indexing-service/pom.xml
index 150d3a019a1..218da4caa20 100644
--- a/indexing-service/pom.xml
+++ b/indexing-service/pom.xml
@@ -138,7 +138,7 @@
</dependency>
<dependency>
<groupId>it.unimi.dsi</groupId>
- <artifactId>fastutil-core</artifactId>
+ <artifactId>fastutil</artifactId>
</dependency>
<dependency>
<groupId>org.apache.logging.log4j</groupId>
diff --git a/licenses.yaml b/licenses.yaml
index 2119cd8ffa0..40cfad635cd 100644
--- a/licenses.yaml
+++ b/licenses.yaml
@@ -1756,11 +1756,9 @@ name: fastutil
license_category: binary
module: java-core
license_name: Apache License version 2.0
-version: 8.5.4
+version: 8.5.19
libraries:
- it.unimi.dsi: fastutil
- - it.unimi.dsi: fastutil-core
- - it.unimi.dsi: fastutil-extra
---
diff --git a/multi-stage-query/pom.xml b/multi-stage-query/pom.xml
index 97df5ed6ab4..57752fa2400 100644
--- a/multi-stage-query/pom.xml
+++ b/multi-stage-query/pom.xml
@@ -194,11 +194,6 @@
<artifactId>fastutil</artifactId>
<scope>provided</scope>
</dependency>
- <dependency>
- <groupId>it.unimi.dsi</groupId>
- <artifactId>fastutil-core</artifactId>
- <scope>provided</scope>
- </dependency>
<dependency>
<groupId>commons-io</groupId>
<artifactId>commons-io</artifactId>
diff --git a/pom.xml b/pom.xml
index fd0b3748f7b..47e38e91892 100644
--- a/pom.xml
+++ b/pom.xml
@@ -99,7 +99,7 @@
<errorprone.annotations.version>2.50.0</errorprone.annotations.version>
<errorprone.version>2.50.0</errorprone.version>
<fabric8.version>8.0.0</fabric8.version>
- <fastutil.version>8.5.4</fastutil.version>
+ <fastutil.version>8.5.19</fastutil.version>
<guava.version>33.7.2-jre</guava.version>
<guice.version>6.0.0</guice.version>
<hamcrest.version>3.0</hamcrest.version>
@@ -1116,11 +1116,6 @@
<artifactId>fastutil</artifactId>
<version>${fastutil.version}</version>
</dependency>
- <dependency>
- <groupId>it.unimi.dsi</groupId>
- <artifactId>fastutil-core</artifactId>
- <version>${fastutil.version}</version>
- </dependency>
<dependency>
<groupId>com.opencsv</groupId>
<artifactId>opencsv</artifactId>
diff --git a/processing/pom.xml b/processing/pom.xml
index b3a04ce8f23..79c1fc0dfd8 100644
--- a/processing/pom.xml
+++ b/processing/pom.xml
@@ -233,10 +233,6 @@
<groupId>it.unimi.dsi</groupId>
<artifactId>fastutil</artifactId>
</dependency>
- <dependency>
- <groupId>it.unimi.dsi</groupId>
- <artifactId>fastutil-core</artifactId>
- </dependency>
<dependency>
<groupId>org.antlr</groupId>
<artifactId>antlr4-runtime</artifactId>
diff --git
a/processing/src/main/java/org/apache/druid/collections/fastutil/DruidIntList.java
b/processing/src/main/java/org/apache/druid/collections/fastutil/DruidIntList.java
index d732c972356..67fe2b51791 100644
---
a/processing/src/main/java/org/apache/druid/collections/fastutil/DruidIntList.java
+++
b/processing/src/main/java/org/apache/druid/collections/fastutil/DruidIntList.java
@@ -19,9 +19,7 @@
package org.apache.druid.collections.fastutil;
-import it.unimi.dsi.fastutil.Arrays;
import it.unimi.dsi.fastutil.ints.IntArrayList;
-import it.unimi.dsi.fastutil.ints.IntArrays;
public class DruidIntList extends IntArrayList
{
@@ -75,25 +73,4 @@ public class DruidIntList extends IntArrayList
a = new int[targetSize];
size = 0;
}
-
- /**
- * Method gratuitously "borrowed" from IntArrayList, would've been nice if
that method wasn't private, but ah well.
- *
- * @param capacity the capacity to grow to
- * @see IntArrayList#grow(int)
- */
- @SuppressWarnings("ArrayEquality")
- private void grow(int capacity)
- {
- if (capacity <= a.length) {
- return;
- }
- if (a != IntArrays.DEFAULT_EMPTY_ARRAY) {
- capacity = (int) Math.max(Math.min((long) a.length + (a.length >> 1),
Arrays.MAX_ARRAY_SIZE), capacity);
- } else if (capacity < DEFAULT_INITIAL_CAPACITY) {
- capacity = DEFAULT_INITIAL_CAPACITY;
- }
- a = IntArrays.forceCapacity(a, capacity, size);
- assert size <= a.length;
- }
}
diff --git a/processing/src/main/java/org/apache/druid/math/expr/Function.java
b/processing/src/main/java/org/apache/druid/math/expr/Function.java
index d2d9995d9c9..98e12596bac 100644
--- a/processing/src/main/java/org/apache/druid/math/expr/Function.java
+++ b/processing/src/main/java/org/apache/druid/math/expr/Function.java
@@ -21,7 +21,6 @@ package org.apache.druid.math.expr;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableSet;
-import it.unimi.dsi.fastutil.objects.ObjectAVLTreeSet;
import it.unimi.dsi.fastutil.objects.ObjectArrays;
import it.unimi.dsi.fastutil.objects.ObjectOpenHashSet;
import org.apache.druid.annotations.SuppressFBWarnings;
@@ -4254,7 +4253,7 @@ public interface Function extends NamedFunction
}
};
}
- final Set<Object> set = new
ObjectAVLTreeSet<>(lhsArrayType.getElementType().getNullableStrategy());
+ final Set<Object> set = new
TreeSet<>(lhsArrayType.getElementType().getNullableStrategy());
set.addAll(Arrays.asList(rhsArray));
return new OverlapConstantArray(set);
}
diff --git
a/processing/src/main/java/org/apache/druid/segment/ComparatorSortedDimensionDictionary.java
b/processing/src/main/java/org/apache/druid/segment/ComparatorSortedDimensionDictionary.java
index 0bb1e28577a..a5968d9fee4 100644
---
a/processing/src/main/java/org/apache/druid/segment/ComparatorSortedDimensionDictionary.java
+++
b/processing/src/main/java/org/apache/druid/segment/ComparatorSortedDimensionDictionary.java
@@ -20,20 +20,15 @@
package org.apache.druid.segment;
-import com.google.common.collect.Lists;
-import it.unimi.dsi.fastutil.ints.IntIterator;
-import it.unimi.dsi.fastutil.objects.Object2IntRBTreeMap;
-import it.unimi.dsi.fastutil.objects.Object2IntSortedMap;
+import it.unimi.dsi.fastutil.ints.IntArrays;
+import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
/**
- * {@link Comparator} based {@link SortedDimensionDictionary}
- *
- * There are a number of unused methods, because nested columns don't merge
bitmap indexes during
- * the merge phase, rather they are created when serializing the column, but
leaving for now for
- * compatibility with the other implementation
+ * Creates a sorted dictionary given some existing dictionary and a {@link
Comparator}, storing a mapping of both
+ * sorted id to unsorted id and unsorted id to sorted id. {@link
SortedDimensionDictionary} uses natural ordering.
*/
public class ComparatorSortedDimensionDictionary<T>
{
@@ -41,26 +36,40 @@ public class ComparatorSortedDimensionDictionary<T>
private final int[] idToIndex;
private final int[] indexToId;
+ /**
+ * @param idToValue unsorted dictionary values, which must be unique. The
sort looks up values by id many
+ * times, so this should be a {@link
java.util.RandomAccess} list such as {@link ArrayList}.
+ * @param comparator ordering of the values, which must handle null
+ * @param length number of ids, from the start of {@code idToValue}, to
include
+ */
public ComparatorSortedDimensionDictionary(List<T> idToValue, Comparator<T>
comparator, int length)
{
- Object2IntSortedMap<T> sortedMap = new Object2IntRBTreeMap<>(comparator);
+ final int[] sortedIds = new int[length];
for (int id = 0; id < length; id++) {
- T value = idToValue.get(id);
- sortedMap.put(value, id);
+ sortedIds[id] = id;
}
- this.sortedVals = Lists.newArrayList(sortedMap.keySet());
+ IntArrays.quickSort(sortedIds, (id1, id2) ->
comparator.compare(idToValue.get(id1), idToValue.get(id2)));
+
+ this.sortedVals = new ArrayList<>(length);
this.idToIndex = new int[length];
- this.indexToId = new int[length];
- int index = 0;
- for (IntIterator iterator = sortedMap.values().iterator();
iterator.hasNext(); ) {
- int id = iterator.nextInt();
+ this.indexToId = sortedIds;
+ for (int index = 0; index < length; index++) {
+ final int id = sortedIds[index];
+ sortedVals.add(idToValue.get(id));
idToIndex[id] = index;
- indexToId[index] = id;
- index++;
}
}
- @SuppressWarnings("unused")
+ /**
+ * Number of ids in this sorted view, captured at {@link
DimensionDictionary#sort()} time. Both the sorted-id and
+ * unsorted-id spaces cover {@code [0, size())}. Useful when iterating a
snapshot taken concurrently with a still-
+ * growing source dictionary, where re-reading the source size would be
inconsistent with this view.
+ */
+ public int size()
+ {
+ return sortedVals.size();
+ }
+
public int getUnsortedIdFromSortedId(int index)
{
return indexToId[index];
diff --git
a/processing/src/main/java/org/apache/druid/segment/SortedDimensionDictionary.java
b/processing/src/main/java/org/apache/druid/segment/SortedDimensionDictionary.java
index fdd79b341a1..0215ebecc41 100644
---
a/processing/src/main/java/org/apache/druid/segment/SortedDimensionDictionary.java
+++
b/processing/src/main/java/org/apache/druid/segment/SortedDimensionDictionary.java
@@ -19,65 +19,24 @@
package org.apache.druid.segment;
-import com.google.common.collect.Lists;
-import it.unimi.dsi.fastutil.ints.IntIterator;
-import it.unimi.dsi.fastutil.objects.Object2IntRBTreeMap;
-import it.unimi.dsi.fastutil.objects.Object2IntSortedMap;
import org.apache.druid.java.util.common.guava.Comparators;
import java.util.List;
/**
* Creates a sorted dictionary given some existing dictionary, storing a
mapping of both sorted id to unsorted id
- * and unsorted id to sorted id
+ * and unsorted id to sorted id. Values are sorted by natural order with nulls
first.
*/
-public class SortedDimensionDictionary<T extends Comparable<T>>
+public class SortedDimensionDictionary<T extends Comparable<T>> extends
ComparatorSortedDimensionDictionary<T>
{
- private final List<T> sortedVals;
- private final int[] idToIndex;
- private final int[] indexToId;
-
- public SortedDimensionDictionary(List<T> idToValue, int length)
- {
- Object2IntSortedMap<T> sortedMap = new
Object2IntRBTreeMap<>(Comparators.naturalNullsFirst());
- for (int id = 0; id < length; id++) {
- T value = idToValue.get(id);
- sortedMap.put(value, id);
- }
- this.sortedVals = Lists.newArrayList(sortedMap.keySet());
- this.idToIndex = new int[length];
- this.indexToId = new int[length];
- int index = 0;
- for (IntIterator iterator = sortedMap.values().iterator();
iterator.hasNext(); ) {
- int id = iterator.nextInt();
- idToIndex[id] = index;
- indexToId[index] = id;
- index++;
- }
- }
-
/**
- * Number of ids in this sorted view, captured at {@link
DimensionDictionary#sort()} time. Both the sorted-id and
- * unsorted-id spaces cover {@code [0, size())}. Useful when iterating a
snapshot taken concurrently with a still-
- * growing source dictionary, where re-reading the source size would be
inconsistent with this view.
+ * @param idToValue unsorted dictionary values, which must be unique. The
sort looks up values by id many
+ * times, so this should be a {@link
java.util.RandomAccess} list such as
+ * {@link java.util.ArrayList}.
+ * @param length number of ids, from the start of {@code idToValue}, to
include
*/
- public int size()
- {
- return sortedVals.size();
- }
-
- public int getUnsortedIdFromSortedId(int index)
- {
- return indexToId[index];
- }
-
- public int getSortedIdFromUnsortedId(int id)
- {
- return idToIndex[id];
- }
-
- public T getValueFromSortedId(int index)
+ public SortedDimensionDictionary(List<T> idToValue, int length)
{
- return sortedVals.get(index);
+ super(idToValue, Comparators.naturalNullsFirst(), length);
}
}
diff --git
a/processing/src/test/java/org/apache/druid/segment/ComparatorSortedDimensionDictionaryTest.java
b/processing/src/test/java/org/apache/druid/segment/ComparatorSortedDimensionDictionaryTest.java
new file mode 100644
index 00000000000..87dae30a33f
--- /dev/null
+++
b/processing/src/test/java/org/apache/druid/segment/ComparatorSortedDimensionDictionaryTest.java
@@ -0,0 +1,211 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.segment;
+
+import org.apache.druid.java.util.common.StringUtils;
+import org.apache.druid.segment.column.ColumnType;
+import org.apache.druid.segment.data.GenericIndexed;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+
+public class ComparatorSortedDimensionDictionaryTest
+{
+ @Test
+ public void testStringsWithNull()
+ {
+ final List<String> idToValue = Arrays.asList("b", null, "c", "a");
+ final ComparatorSortedDimensionDictionary<String> dictionary =
+ new ComparatorSortedDimensionDictionary<>(idToValue,
GenericIndexed.STRING_STRATEGY, 4);
+
+ assertDictionary(idToValue, 4, dictionary, Arrays.asList(null, "a", "b",
"c"));
+ Assertions.assertEquals(1, dictionary.getUnsortedIdFromSortedId(0));
+ Assertions.assertEquals(3, dictionary.getUnsortedIdFromSortedId(1));
+ Assertions.assertEquals(0, dictionary.getUnsortedIdFromSortedId(2));
+ Assertions.assertEquals(2, dictionary.getUnsortedIdFromSortedId(3));
+ }
+
+ @Test
+ public void testStringsSortInJavaStringOrder()
+ {
+ // U+FFFD sorts after U+1F600 in Java String order but before it in UTF-8
byte order. STRING_STRATEGY uses Java
+ // String order, consistent with GenericIndexed.UTF8_STRATEGY, which
compares UTF-8 bytes using Java String order.
+ final String replacementChar = "\uFFFD";
+ final String emoji = "\uD83D\uDE00";
+
Assertions.assertTrue(Arrays.compareUnsigned(StringUtils.toUtf8(replacementChar),
StringUtils.toUtf8(emoji)) < 0);
+
+ final List<String> idToValue = Arrays.asList(replacementChar, null, emoji,
"a");
+ assertDictionary(
+ idToValue,
+ 4,
+ new ComparatorSortedDimensionDictionary<>(idToValue,
GenericIndexed.STRING_STRATEGY, 4),
+ Arrays.asList(null, "a", emoji, replacementChar)
+ );
+ }
+
+ @Test
+ public void testLongs()
+ {
+ final List<Long> idToValue = Arrays.asList(5L, -3L, null, 0L,
Long.MAX_VALUE, Long.MIN_VALUE);
+ assertDictionary(
+ idToValue,
+ 6,
+ new ComparatorSortedDimensionDictionary<>(idToValue,
ColumnType.LONG.getNullableStrategy(), 6),
+ Arrays.asList(null, Long.MIN_VALUE, -3L, 0L, 5L, Long.MAX_VALUE)
+ );
+ }
+
+ @Test
+ public void testDoubles()
+ {
+ final List<Double> idToValue = Arrays.asList(1.5, null, -2.25, 0.0, 100.0);
+ assertDictionary(
+ idToValue,
+ 5,
+ new ComparatorSortedDimensionDictionary<>(idToValue,
ColumnType.DOUBLE.getNullableStrategy(), 5),
+ Arrays.asList(null, -2.25, 0.0, 1.5, 100.0)
+ );
+ }
+
+ @Test
+ public void testNullsLastComparator()
+ {
+ final List<String> idToValue = Arrays.asList("b", null, "c", "a");
+ assertDictionary(
+ idToValue,
+ 4,
+ new ComparatorSortedDimensionDictionary<>(idToValue,
Comparator.nullsLast(Comparator.naturalOrder()), 4),
+ Arrays.asList("a", "b", "c", null)
+ );
+ }
+
+ @Test
+ public void testReverseComparator()
+ {
+ final List<String> idToValue = Arrays.asList("b", null, "c", "a");
+ assertDictionary(
+ idToValue,
+ 4,
+ new ComparatorSortedDimensionDictionary<>(
+ idToValue,
+ Comparator.nullsFirst(Comparator.<String>reverseOrder()),
+ 4
+ ),
+ Arrays.asList(null, "c", "b", "a")
+ );
+ }
+
+ @Test
+ public void testOnlyNull()
+ {
+ final List<String> idToValue = Collections.singletonList(null);
+ assertDictionary(
+ idToValue,
+ 1,
+ new ComparatorSortedDimensionDictionary<>(idToValue,
GenericIndexed.STRING_STRATEGY, 1),
+ Collections.singletonList(null)
+ );
+ }
+
+ @Test
+ public void testLengthSmallerThanList()
+ {
+ final List<String> idToValue = Arrays.asList("c", null, "a", "b", "z");
+ final ComparatorSortedDimensionDictionary<String> dictionary =
+ new ComparatorSortedDimensionDictionary<>(idToValue,
GenericIndexed.STRING_STRATEGY, 4);
+
+ assertDictionary(idToValue, 4, dictionary, Arrays.asList(null, "a", "b",
"c"));
+ Assertions.assertThrows(IndexOutOfBoundsException.class, () ->
dictionary.getValueFromSortedId(4));
+ }
+
+ @Test
+ public void testSortFromDimensionDictionary()
+ {
+ final ComparatorDimensionDictionary<String> dictionary =
+ new ComparatorDimensionDictionary<>(GenericIndexed.STRING_STRATEGY)
+ {
+ @Override
+ public long estimateSizeOfValue(String value)
+ {
+ return value.length();
+ }
+ };
+ for (final String value : Arrays.asList("c", null, "a", "b", "a", null,
"c")) {
+ dictionary.add(value);
+ }
+
+ final ComparatorSortedDimensionDictionary<String> sorted =
dictionary.sort();
+ final List<String> expected = Arrays.asList(null, "a", "b", "c");
+ for (int index = 0; index < expected.size(); index++) {
+ final String value = expected.get(index);
+ Assertions.assertEquals(value, sorted.getValueFromSortedId(index));
+ Assertions.assertEquals(dictionary.getId(value),
sorted.getUnsortedIdFromSortedId(index));
+ Assertions.assertEquals(index,
sorted.getSortedIdFromUnsortedId(dictionary.getId(value)));
+ }
+ Assertions.assertThrows(IndexOutOfBoundsException.class, () ->
sorted.getValueFromSortedId(expected.size()));
+ }
+
+ @Test
+ public void testRandomStrings()
+ {
+ final Random random = new Random(42);
+ final Set<String> seen = new HashSet<>();
+ final List<String> idToValue = new ArrayList<>();
+ while (idToValue.size() < 1000) {
+ final String value = Integer.toString(random.nextInt(), 36);
+ if (seen.add(value)) {
+ idToValue.add(value);
+ }
+ }
+ idToValue.add(random.nextInt(idToValue.size()), null);
+
+ final List<String> expected = new ArrayList<>(idToValue);
+ expected.sort(GenericIndexed.STRING_STRATEGY);
+ assertDictionary(
+ idToValue,
+ idToValue.size(),
+ new ComparatorSortedDimensionDictionary<>(idToValue,
GenericIndexed.STRING_STRATEGY, idToValue.size()),
+ expected
+ );
+ }
+
+ private static <T> void assertDictionary(
+ List<T> idToValue,
+ int length,
+ ComparatorSortedDimensionDictionary<T> dictionary,
+ List<T> expectedSortedValues
+ )
+ {
+ for (int index = 0; index < length; index++) {
+ Assertions.assertEquals(expectedSortedValues.get(index),
dictionary.getValueFromSortedId(index));
+ final int id = dictionary.getUnsortedIdFromSortedId(index);
+ Assertions.assertEquals(expectedSortedValues.get(index),
idToValue.get(id));
+ Assertions.assertEquals(index, dictionary.getSortedIdFromUnsortedId(id));
+ }
+ }
+}
diff --git
a/processing/src/test/java/org/apache/druid/segment/SortedDimensionDictionaryTest.java
b/processing/src/test/java/org/apache/druid/segment/SortedDimensionDictionaryTest.java
new file mode 100644
index 00000000000..201a7de2ec4
--- /dev/null
+++
b/processing/src/test/java/org/apache/druid/segment/SortedDimensionDictionaryTest.java
@@ -0,0 +1,184 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.segment;
+
+import org.apache.druid.java.util.common.guava.Comparators;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+
+public class SortedDimensionDictionaryTest
+{
+ @Test
+ public void testStringsWithNull()
+ {
+ final List<String> idToValue = Arrays.asList("b", null, "c", "a");
+ final SortedDimensionDictionary<String> dictionary = new
SortedDimensionDictionary<>(idToValue, 4);
+
+ assertDictionary(idToValue, 4, dictionary, Arrays.asList(null, "a", "b",
"c"));
+ Assertions.assertEquals(1, dictionary.getUnsortedIdFromSortedId(0));
+ Assertions.assertEquals(3, dictionary.getUnsortedIdFromSortedId(1));
+ Assertions.assertEquals(0, dictionary.getUnsortedIdFromSortedId(2));
+ Assertions.assertEquals(2, dictionary.getUnsortedIdFromSortedId(3));
+ }
+
+ @Test
+ public void testStringsWithoutNull()
+ {
+ final List<String> idToValue = Arrays.asList("b", "", "c", "a");
+ assertDictionary(
+ idToValue,
+ 4,
+ new SortedDimensionDictionary<>(idToValue, 4),
+ Arrays.asList("", "a", "b", "c")
+ );
+ }
+
+ @Test
+ public void testLongs()
+ {
+ final List<Long> idToValue = Arrays.asList(5L, -3L, null, 0L,
Long.MAX_VALUE, Long.MIN_VALUE);
+ assertDictionary(
+ idToValue,
+ 6,
+ new SortedDimensionDictionary<>(idToValue, 6),
+ Arrays.asList(null, Long.MIN_VALUE, -3L, 0L, 5L, Long.MAX_VALUE)
+ );
+ }
+
+ @Test
+ public void testDoubles()
+ {
+ final List<Double> idToValue = Arrays.asList(1.5, null, -2.25, 0.0, 100.0);
+ assertDictionary(
+ idToValue,
+ 5,
+ new SortedDimensionDictionary<>(idToValue, 5),
+ Arrays.asList(null, -2.25, 0.0, 1.5, 100.0)
+ );
+ }
+
+ @Test
+ public void testFloats()
+ {
+ final List<Float> idToValue = Arrays.asList(3f, -1f, null, 2.5f);
+ assertDictionary(
+ idToValue,
+ 4,
+ new SortedDimensionDictionary<>(idToValue, 4),
+ Arrays.asList(null, -1f, 2.5f, 3f)
+ );
+ }
+
+ @Test
+ public void testEmpty()
+ {
+ final SortedDimensionDictionary<String> dictionary = new
SortedDimensionDictionary<>(new ArrayList<String>(), 0);
+ Assertions.assertEquals(0, dictionary.size());
+ }
+
+ @Test
+ public void testOnlyNull()
+ {
+ final List<String> idToValue = Collections.singletonList(null);
+ assertDictionary(
+ idToValue,
+ 1,
+ new SortedDimensionDictionary<>(idToValue, 1),
+ Collections.singletonList(null)
+ );
+ }
+
+ @Test
+ public void testLengthSmallerThanList()
+ {
+ final List<String> idToValue = Arrays.asList("c", null, "a", "b", "z");
+ final SortedDimensionDictionary<String> dictionary = new
SortedDimensionDictionary<>(idToValue, 4);
+
+ Assertions.assertEquals(4, dictionary.size());
+ assertDictionary(idToValue, 4, dictionary, Arrays.asList(null, "a", "b",
"c"));
+ }
+
+ @Test
+ public void testSortFromDimensionDictionary()
+ {
+ final StringDimensionDictionary dictionary = new
StringDimensionDictionary();
+ for (final String value : Arrays.asList("c", null, "a", "b", "a", null,
"c")) {
+ dictionary.add(value);
+ }
+
+ final SortedDimensionDictionary<String> sorted = dictionary.sort();
+ final List<String> expected = Arrays.asList(null, "a", "b", "c");
+ Assertions.assertEquals(expected.size(), sorted.size());
+ for (int index = 0; index < expected.size(); index++) {
+ final String value = expected.get(index);
+ Assertions.assertEquals(value, sorted.getValueFromSortedId(index));
+ Assertions.assertEquals(dictionary.getId(value),
sorted.getUnsortedIdFromSortedId(index));
+ Assertions.assertEquals(index,
sorted.getSortedIdFromUnsortedId(dictionary.getId(value)));
+ }
+ }
+
+ @Test
+ public void testRandomStrings()
+ {
+ final Random random = new Random(42);
+ final Set<String> seen = new HashSet<>();
+ final List<String> idToValue = new ArrayList<>();
+ while (idToValue.size() < 1000) {
+ final String value = Integer.toString(random.nextInt(), 36);
+ if (seen.add(value)) {
+ idToValue.add(value);
+ }
+ }
+ idToValue.add(random.nextInt(idToValue.size()), null);
+
+ final List<String> expected = new ArrayList<>(idToValue);
+ expected.sort(Comparators.naturalNullsFirst());
+ assertDictionary(
+ idToValue,
+ idToValue.size(),
+ new SortedDimensionDictionary<>(idToValue, idToValue.size()),
+ expected
+ );
+ }
+
+ private static <T extends Comparable<T>> void assertDictionary(
+ List<T> idToValue,
+ int length,
+ SortedDimensionDictionary<T> dictionary,
+ List<T> expectedSortedValues
+ )
+ {
+ Assertions.assertEquals(length, dictionary.size());
+ for (int index = 0; index < length; index++) {
+ Assertions.assertEquals(expectedSortedValues.get(index),
dictionary.getValueFromSortedId(index));
+ final int id = dictionary.getUnsortedIdFromSortedId(index);
+ Assertions.assertEquals(expectedSortedValues.get(index),
idToValue.get(id));
+ Assertions.assertEquals(index, dictionary.getSortedIdFromUnsortedId(id));
+ }
+ }
+}
diff --git a/server/pom.xml b/server/pom.xml
index 42282f03832..0e9f1cb7999 100644
--- a/server/pom.xml
+++ b/server/pom.xml
@@ -175,7 +175,7 @@
</dependency>
<dependency>
<groupId>it.unimi.dsi</groupId>
- <artifactId>fastutil-core</artifactId>
+ <artifactId>fastutil</artifactId>
</dependency>
<dependency>
<groupId>com.github.ben-manes.caffeine</groupId>
diff --git a/sql/pom.xml b/sql/pom.xml
index 7e342d1e431..56707abe63c 100644
--- a/sql/pom.xml
+++ b/sql/pom.xml
@@ -161,7 +161,7 @@
</dependency>
<dependency>
<groupId>it.unimi.dsi</groupId>
- <artifactId>fastutil-core</artifactId>
+ <artifactId>fastutil</artifactId>
</dependency>
<dependency>
<groupId>com.fasterxml.jackson.core</groupId>
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
