This is an automated email from the ASF dual-hosted git repository.
hyuan pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/calcite.git
The following commit(s) were added to refs/heads/master by this push:
new ce2ae64 [CALCITE-4102] Some improvements to aggregate related
operations (Liya Fan)
ce2ae64 is described below
commit ce2ae649c9ec072ceb8462b2783f8c6bba989241
Author: liyafan82 <[email protected]>
AuthorDate: Thu Jul 2 12:38:25 2020 +0800
[CALCITE-4102] Some improvements to aggregate related operations (Liya Fan)
1. Extract a common method for ImmutableBitSet
2. Refine the use of data structures
3. Replace expensive operations with cheap ones
---
.../org/apache/calcite/rel/core/Aggregate.java | 25 ++++++++--------------
.../sql/validate/AggregatingSelectScope.java | 11 +---------
.../org/apache/calcite/util/ImmutableBitSet.java | 13 +++++++++++
.../main/java/org/apache/calcite/util/Util.java | 1 +
.../apache/calcite/util/ImmutableBitSetTest.java | 20 +++++++++++++++++
5 files changed, 44 insertions(+), 26 deletions(-)
diff --git a/core/src/main/java/org/apache/calcite/rel/core/Aggregate.java
b/core/src/main/java/org/apache/calcite/rel/core/Aggregate.java
index e8a4b73..634e0fb 100644
--- a/core/src/main/java/org/apache/calcite/rel/core/Aggregate.java
+++ b/core/src/main/java/org/apache/calcite/rel/core/Aggregate.java
@@ -51,8 +51,8 @@ import com.google.common.collect.ImmutableList;
import com.google.common.math.IntMath;
import java.util.ArrayList;
+import java.util.Collections;
import java.util.HashSet;
-import java.util.LinkedHashSet;
import java.util.List;
import java.util.Objects;
import java.util.Set;
@@ -393,7 +393,7 @@ public abstract class Aggregate extends SingleRel
implements Hintable {
final RelDataTypeField field = fieldList.get(groupKey);
containedNames.add(field.getName());
builder.add(field);
- if (groupSets != null && !allContain(groupSets, groupKey)) {
+ if (groupSets != null && !ImmutableBitSet.allContain(groupSets,
groupKey)) {
builder.nullable(true);
}
}
@@ -416,16 +416,6 @@ public abstract class Aggregate extends SingleRel
implements Hintable {
return builder.build();
}
- private static boolean allContain(List<ImmutableBitSet> groupSets,
- int groupKey) {
- for (ImmutableBitSet groupSet : groupSets) {
- if (!groupSet.get(groupKey)) {
- return false;
- }
- }
- return true;
- }
-
public boolean isValid(Litmus litmus, Context context) {
return super.isValid(litmus, context)
&& litmus.check(Util.isDistinct(getRowType().getFieldNames()),
@@ -529,7 +519,7 @@ public abstract class Aggregate extends SingleRel
implements Hintable {
// Each subsequent items must be a subset with one fewer bit than the
// previous item
if (!g.contains(bitSet)
- || g.except(bitSet).cardinality() != 1) {
+ || g.cardinality() - bitSet.cardinality() != 1) {
return false;
}
}
@@ -548,7 +538,7 @@ public abstract class Aggregate extends SingleRel
implements Hintable {
*
* @see #isRollup(ImmutableBitSet, List) */
public static List<Integer> getRollup(List<ImmutableBitSet> groupSets) {
- final Set<Integer> set = new LinkedHashSet<>();
+ final List<Integer> rollUpBits = new ArrayList<>(groupSets.size() - 1);
ImmutableBitSet g = null;
for (ImmutableBitSet bitSet : groupSets) {
if (g == null) {
@@ -556,11 +546,14 @@ public abstract class Aggregate extends SingleRel
implements Hintable {
} else {
// Each subsequent items must be a subset with one fewer bit than the
// previous item
- set.addAll(g.except(bitSet).toList());
+ ImmutableBitSet diff = g.except(bitSet);
+ assert diff.cardinality() == 1;
+ rollUpBits.add(diff.nth(0));
}
g = bitSet;
}
- return ImmutableList.copyOf(set).reverse();
+ Collections.reverse(rollUpBits);
+ return ImmutableList.copyOf(rollUpBits);
}
}
diff --git
a/core/src/main/java/org/apache/calcite/sql/validate/AggregatingSelectScope.java
b/core/src/main/java/org/apache/calcite/sql/validate/AggregatingSelectScope.java
index e0e9b3c..415a21f 100644
---
a/core/src/main/java/org/apache/calcite/sql/validate/AggregatingSelectScope.java
+++
b/core/src/main/java/org/apache/calcite/sql/validate/AggregatingSelectScope.java
@@ -166,15 +166,6 @@ public class AggregatingSelectScope
return select;
}
- private static boolean allContain(List<ImmutableBitSet> bitSets, int bit) {
- for (ImmutableBitSet bitSet : bitSets) {
- if (!bitSet.get(bit)) {
- return false;
- }
- }
- return true;
- }
-
@Override public RelDataType nullifyType(SqlNode node, RelDataType type) {
final Resolved r = this.resolved.get();
for (Ord<SqlNode> groupExpr : Ord.zip(r.groupExprList)) {
@@ -263,7 +254,7 @@ public class AggregatingSelectScope
/** Returns whether a field should be nullable due to grouping sets. */
public boolean isNullable(int i) {
- return i < groupExprList.size() && !allContain(groupSets, i);
+ return i < groupExprList.size() &&
!ImmutableBitSet.allContain(groupSets, i);
}
/** Returns whether a given expression is equal to one of the grouping
diff --git a/core/src/main/java/org/apache/calcite/util/ImmutableBitSet.java
b/core/src/main/java/org/apache/calcite/util/ImmutableBitSet.java
index aca5056..4da1c73 100644
--- a/core/src/main/java/org/apache/calcite/util/ImmutableBitSet.java
+++ b/core/src/main/java/org/apache/calcite/util/ImmutableBitSet.java
@@ -31,6 +31,7 @@ import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
+import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
@@ -902,6 +903,18 @@ public class ImmutableBitSet
}
/**
+ * Checks if all bit sets contain a particular bit.
+ */
+ public static boolean allContain(Collection<ImmutableBitSet> bitSets, int
bit) {
+ for (ImmutableBitSet bitSet : bitSets) {
+ if (!bitSet.get(bit)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
* Setup equivalence Sets for each position. If i and j are equivalent then
* they will have the same equivalence Set. The algorithm computes the
* closure relation at each position for the position wrt to positions
diff --git a/core/src/main/java/org/apache/calcite/util/Util.java
b/core/src/main/java/org/apache/calcite/util/Util.java
index 0469083..1919341 100644
--- a/core/src/main/java/org/apache/calcite/util/Util.java
+++ b/core/src/main/java/org/apache/calcite/util/Util.java
@@ -2047,6 +2047,7 @@ public class Util {
}
return -1;
}
+ // we use HashMap here, because it is more efficient than HashSet.
final Map<E, Object> set = new HashMap<>(size);
for (E e : list) {
if (set.put(e, "") != null) {
diff --git
a/core/src/test/java/org/apache/calcite/util/ImmutableBitSetTest.java
b/core/src/test/java/org/apache/calcite/util/ImmutableBitSetTest.java
index 49ad82e..4be872d 100644
--- a/core/src/test/java/org/apache/calcite/util/ImmutableBitSetTest.java
+++ b/core/src/test/java/org/apache/calcite/util/ImmutableBitSetTest.java
@@ -18,12 +18,14 @@ package org.apache.calcite.util;
import org.apache.calcite.runtime.Utilities;
+import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterables;
import org.junit.jupiter.api.Test;
import java.nio.LongBuffer;
import java.util.Arrays;
+import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
@@ -570,4 +572,22 @@ class ImmutableBitSetTest {
assertThat(emptyBitSet.get(7, 10000), is(ImmutableBitSet.of()));
assertThat(emptyBitSet.get(73, 10000), is(ImmutableBitSet.of()));
}
+
+ /**
+ * Test case for {@link ImmutableBitSet#allContain(Collection, int)}.
+ */
+ @Test void testAllContain() {
+ ImmutableBitSet set1 = ImmutableBitSet.of(0, 1, 2, 3);
+ ImmutableBitSet set2 = ImmutableBitSet.of(2, 3, 4, 5);
+ ImmutableBitSet set3 = ImmutableBitSet.of(3, 4, 5, 6);
+
+ Collection<ImmutableBitSet> collection1 = ImmutableList.of(set1, set2,
set3);
+ assertTrue(ImmutableBitSet.allContain(collection1, 3));
+ assertFalse(ImmutableBitSet.allContain(collection1, 0));
+
+ Collection<ImmutableBitSet> collection2 = ImmutableList.of(set1, set2);
+ assertTrue(ImmutableBitSet.allContain(collection2, 2));
+ assertTrue(ImmutableBitSet.allContain(collection2, 3));
+ assertFalse(ImmutableBitSet.allContain(collection2, 4));
+ }
}
