calcite-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jh...@apache.org
Subject [55/58] [abbrv] incubator-calcite git commit: [CALCITE-460] Add ImmutableBitSet and replace uses of BitSet
Date Fri, 14 Nov 2014 21:33:03 GMT
[CALCITE-460] Add ImmutableBitSet and replace uses of BitSet


Project: http://git-wip-us.apache.org/repos/asf/incubator-calcite/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-calcite/commit/b9d8de38
Tree: http://git-wip-us.apache.org/repos/asf/incubator-calcite/tree/b9d8de38
Diff: http://git-wip-us.apache.org/repos/asf/incubator-calcite/diff/b9d8de38

Branch: refs/heads/master
Commit: b9d8de38d2aa4ee6791aec42ffe2adb58942060a
Parents: a0ba73c
Author: Julian Hyde <jhyde@apache.org>
Authored: Thu Nov 13 18:24:57 2014 -0800
Committer: Julian Hyde <jhyde@apache.org>
Committed: Thu Nov 13 19:00:43 2014 -0800

----------------------------------------------------------------------
 .../calcite/adapter/clone/ArrayTable.java       |   9 +-
 .../apache/calcite/adapter/clone/ListTable.java |   7 +-
 .../adapter/enumerable/EnumerableAggregate.java |  14 +-
 .../adapter/enumerable/EnumerableWindow.java    |   3 +-
 .../apache/calcite/adapter/jdbc/JdbcRules.java  |  13 +-
 .../org/apache/calcite/materialize/Lattice.java |  28 +-
 .../materialize/MaterializationService.java     |  11 +-
 .../org/apache/calcite/materialize/TileKey.java |   8 +-
 .../calcite/plan/RelOptAbstractTable.java       |   4 +-
 .../org/apache/calcite/plan/RelOptLattice.java  |   4 +-
 .../org/apache/calcite/plan/RelOptTable.java    |   4 +-
 .../org/apache/calcite/plan/RelOptUtil.java     |  78 +-
 .../java/org/apache/calcite/plan/Strong.java    |  10 +-
 .../calcite/plan/SubstitutionVisitor.java       |  23 +-
 .../apache/calcite/plan/hep/HepRelVertex.java   |   4 +-
 .../apache/calcite/plan/volcano/RelSubset.java  |   4 +-
 .../apache/calcite/prepare/RelOptTableImpl.java |   4 +-
 .../org/apache/calcite/rel/AbstractRelNode.java |   7 +-
 .../java/org/apache/calcite/rel/RelInput.java   |   4 +-
 .../java/org/apache/calcite/rel/RelNode.java    |   4 +-
 .../org/apache/calcite/rel/core/Aggregate.java  |  24 +-
 .../org/apache/calcite/rel/core/Intersect.java  |   4 +-
 .../org/apache/calcite/rel/core/JoinInfo.java   |  11 +-
 .../java/org/apache/calcite/rel/core/Minus.java |   4 +-
 .../apache/calcite/rel/core/RelFactories.java   |   6 +-
 .../java/org/apache/calcite/rel/core/SetOp.java |   4 +-
 .../org/apache/calcite/rel/core/TableScan.java  |  14 +-
 .../org/apache/calcite/rel/core/Window.java     |   6 +-
 .../apache/calcite/rel/externalize/RelJson.java |   9 +-
 .../calcite/rel/externalize/RelJsonReader.java  |   7 +-
 .../calcite/rel/logical/LogicalAggregate.java   |   6 +-
 .../calcite/rel/logical/LogicalWindow.java      |  14 +-
 .../calcite/rel/metadata/BuiltInMetadata.java   |  14 +-
 .../rel/metadata/RelMdColumnUniqueness.java     |  46 +-
 .../rel/metadata/RelMdDistinctRowCount.java     |  35 +-
 .../rel/metadata/RelMdPopulationSize.java       |  39 +-
 .../calcite/rel/metadata/RelMdPredicates.java   |  54 +-
 .../calcite/rel/metadata/RelMdRowCount.java     |   8 +-
 .../calcite/rel/metadata/RelMdSelectivity.java  |   4 +-
 .../calcite/rel/metadata/RelMdUniqueKeys.java   |  71 +-
 .../apache/calcite/rel/metadata/RelMdUtil.java  | 114 +--
 .../calcite/rel/metadata/RelMetadataQuery.java  |  24 +-
 .../AggregateExpandDistinctAggregatesRule.java  |  17 +-
 .../rel/rules/AggregateFilterTransposeRule.java |  23 +-
 .../rel/rules/AggregateProjectMergeRule.java    |  11 +-
 .../AggregateProjectPullUpConstantsRule.java    |   8 +-
 .../rel/rules/AggregateStarTableRule.java       |  25 +-
 .../rel/rules/FilterAggregateTransposeRule.java |   9 +-
 .../calcite/rel/rules/JoinAssociateRule.java    |   8 +-
 .../rel/rules/JoinPushThroughJoinRule.java      |  12 +-
 .../calcite/rel/rules/JoinToMultiJoinRule.java  |   6 +-
 .../apache/calcite/rel/rules/LoptMultiJoin.java |  88 +-
 .../calcite/rel/rules/LoptOptimizeJoinRule.java |  74 +-
 .../rel/rules/LoptSemiJoinOptimizer.java        |  23 +-
 .../org/apache/calcite/rel/rules/MultiJoin.java |   8 +-
 .../rel/rules/MultiJoinOptimizeBushyRule.java   |  44 +-
 .../apache/calcite/rel/rules/PushProjector.java |  25 +-
 .../apache/calcite/rel/rules/SemiJoinRule.java  |  17 +-
 .../org/apache/calcite/schema/Statistic.java    |   4 +-
 .../org/apache/calcite/schema/Statistics.java   |  14 +-
 .../apache/calcite/sql2rel/RelDecorrelator.java |  13 +-
 .../apache/calcite/sql2rel/RelFieldTrimmer.java | 121 ++-
 .../calcite/sql2rel/SqlToRelConverter.java      |  15 +-
 .../java/org/apache/calcite/util/BitSets.java   |  22 +
 .../org/apache/calcite/util/BuiltInMethod.java  |  10 +-
 .../apache/calcite/util/ImmutableBitSet.java    | 882 +++++++++++++++++++
 .../apache/calcite/util/mapping/Mappings.java   |  23 +
 .../org/apache/calcite/plan/RelWriterTest.java  |   4 +-
 .../org/apache/calcite/test/CalciteSuite.java   |   2 +
 .../apache/calcite/test/MockCatalogReader.java  |   4 +-
 .../apache/calcite/test/RelMetadataTest.java    |   4 +-
 .../org/apache/calcite/test/RexProgramTest.java |  15 +-
 .../apache/calcite/test/SqlToRelTestBase.java   |   6 +-
 .../calcite/util/ImmutableBitSetTest.java       | 383 ++++++++
 .../calcite/adapter/mongodb/MongoAggregate.java |  13 +-
 .../calcite/adapter/tpcds/TpcdsSchema.java      |   4 +-
 76 files changed, 1975 insertions(+), 723 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/adapter/clone/ArrayTable.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/adapter/clone/ArrayTable.java b/core/src/main/java/org/apache/calcite/adapter/clone/ArrayTable.java
index 6bfe42f..7c7ccf3 100644
--- a/core/src/main/java/org/apache/calcite/adapter/clone/ArrayTable.java
+++ b/core/src/main/java/org/apache/calcite/adapter/clone/ArrayTable.java
@@ -29,18 +29,17 @@ import org.apache.calcite.schema.SchemaPlus;
 import org.apache.calcite.schema.Statistic;
 import org.apache.calcite.schema.Statistics;
 import org.apache.calcite.schema.impl.AbstractTableQueryable;
-import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.Pair;
 
 import com.google.common.base.Supplier;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Lists;
 
 import java.lang.reflect.Array;
 import java.lang.reflect.Type;
 import java.util.AbstractList;
-import java.util.ArrayList;
 import java.util.Arrays;
-import java.util.BitSet;
 import java.util.Collections;
 import java.util.List;
 
@@ -67,11 +66,11 @@ class ArrayTable extends AbstractQueryableTable {
   }
 
   public Statistic getStatistic() {
-    final List<BitSet> keys = new ArrayList<BitSet>();
+    final List<ImmutableBitSet> keys = Lists.newArrayList();
     final Content content = supplier.get();
     for (Ord<Column> ord : Ord.zip(content.columns)) {
       if (ord.e.cardinality == content.size) {
-        keys.add(BitSets.of(ord.i));
+        keys.add(ImmutableBitSet.of(ord.i));
       }
     }
     return Statistics.of(content.size, keys);

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/adapter/clone/ListTable.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/adapter/clone/ListTable.java b/core/src/main/java/org/apache/calcite/adapter/clone/ListTable.java
index c07ea0a..cb446ff 100644
--- a/core/src/main/java/org/apache/calcite/adapter/clone/ListTable.java
+++ b/core/src/main/java/org/apache/calcite/adapter/clone/ListTable.java
@@ -29,10 +29,11 @@ import org.apache.calcite.rel.type.RelProtoDataType;
 import org.apache.calcite.schema.SchemaPlus;
 import org.apache.calcite.schema.Statistic;
 import org.apache.calcite.schema.Statistics;
+import org.apache.calcite.util.ImmutableBitSet;
+
+import com.google.common.collect.ImmutableList;
 
 import java.lang.reflect.Type;
-import java.util.BitSet;
-import java.util.Collections;
 import java.util.Iterator;
 import java.util.List;
 
@@ -63,7 +64,7 @@ class ListTable extends AbstractQueryableTable {
   }
 
   public Statistic getStatistic() {
-    return Statistics.of(list.size(), Collections.<BitSet>emptyList());
+    return Statistics.of(list.size(), ImmutableList.<ImmutableBitSet>of());
   }
 
   public <T> Queryable<T> asQueryable(final QueryProvider queryProvider,

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableAggregate.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableAggregate.java b/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableAggregate.java
index 7f19cdf..91014bf 100644
--- a/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableAggregate.java
+++ b/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableAggregate.java
@@ -39,8 +39,8 @@ import org.apache.calcite.rex.RexInputRef;
 import org.apache.calcite.rex.RexNode;
 import org.apache.calcite.sql.SqlAggFunction;
 import org.apache.calcite.sql.fun.SqlStdOperatorTable;
-import org.apache.calcite.util.BitSets;
 import org.apache.calcite.util.BuiltInMethod;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.Pair;
 import org.apache.calcite.util.Util;
 
@@ -48,7 +48,6 @@ import com.google.common.collect.ImmutableList;
 
 import java.lang.reflect.Type;
 import java.util.ArrayList;
-import java.util.BitSet;
 import java.util.Collections;
 import java.util.List;
 
@@ -67,7 +66,7 @@ public class EnumerableAggregate extends Aggregate
       RelOptCluster cluster,
       RelTraitSet traitSet,
       RelNode child,
-      BitSet groupSet,
+      ImmutableBitSet groupSet,
       List<AggregateCall> aggCalls)
       throws InvalidRelException {
     super(cluster, traitSet, child, groupSet, aggCalls);
@@ -88,7 +87,7 @@ public class EnumerableAggregate extends Aggregate
   }
 
   @Override public EnumerableAggregate copy(RelTraitSet traitSet,
-      RelNode input, BitSet groupSet, List<AggregateCall> aggCalls) {
+      RelNode input, ImmutableBitSet groupSet, List<AggregateCall> aggCalls) {
     try {
       return new EnumerableAggregate(getCluster(), traitSet, input,
           groupSet, aggCalls);
@@ -179,15 +178,14 @@ public class EnumerableAggregate extends Aggregate
         Expressions.parameter(inputPhysType.getJavaRowType(), "a0");
 
     final PhysType keyPhysType =
-        inputPhysType.project(
-            BitSets.toList(groupSet), JavaRowFormat.LIST);
+        inputPhysType.project(groupSet.toList(), JavaRowFormat.LIST);
     final int keyArity = groupSet.cardinality();
     final Expression keySelector =
         builder.append(
             "keySelector",
             inputPhysType.generateSelector(
                 parameter,
-                BitSets.toList(groupSet),
+                groupSet.toList(),
                 keyPhysType.getFormat()));
 
     final List<AggImpState> aggs =
@@ -385,7 +383,7 @@ public class EnumerableAggregate extends Aggregate
                       resultSelector))));
     } else if (aggCalls.isEmpty()
         && groupSet.equals(
-            BitSets.range(child.getRowType().getFieldCount()))) {
+            ImmutableBitSet.range(child.getRowType().getFieldCount()))) {
       builder.add(
           Expressions.return_(
               null,

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableWindow.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableWindow.java b/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableWindow.java
index de0ddd1..fd0304b 100644
--- a/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableWindow.java
+++ b/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableWindow.java
@@ -46,7 +46,6 @@ import org.apache.calcite.rex.RexLiteral;
 import org.apache.calcite.rex.RexNode;
 import org.apache.calcite.rex.RexWindowBound;
 import org.apache.calcite.runtime.SortedMultiMap;
-import org.apache.calcite.util.BitSets;
 import org.apache.calcite.util.BuiltInMethod;
 import org.apache.calcite.util.Pair;
 import org.apache.calcite.util.Util;
@@ -697,7 +696,7 @@ public class EnumerableWindow extends Window implements EnumerableRel {
             0, "key",
             inputPhysType.selector(
                 v_,
-                BitSets.toList(group.keys),
+                group.keys.toList(),
                 JavaRowFormat.CUSTOM));
     builder2.add(declare);
     final ParameterExpression key_ = declare.parameter;

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/adapter/jdbc/JdbcRules.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/adapter/jdbc/JdbcRules.java b/core/src/main/java/org/apache/calcite/adapter/jdbc/JdbcRules.java
index f793a43..a085429 100644
--- a/core/src/main/java/org/apache/calcite/adapter/jdbc/JdbcRules.java
+++ b/core/src/main/java/org/apache/calcite/adapter/jdbc/JdbcRules.java
@@ -88,7 +88,7 @@ import org.apache.calcite.sql.type.InferTypes;
 import org.apache.calcite.sql.type.OperandTypes;
 import org.apache.calcite.sql.type.ReturnTypes;
 import org.apache.calcite.sql.validate.SqlValidatorUtil;
-import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.ImmutableIntList;
 import org.apache.calcite.util.Pair;
 import org.apache.calcite.util.trace.CalciteTrace;
@@ -96,7 +96,6 @@ import org.apache.calcite.util.trace.CalciteTrace;
 import com.google.common.collect.ImmutableList;
 
 import java.util.ArrayList;
-import java.util.BitSet;
 import java.util.Collections;
 import java.util.List;
 import java.util.Set;
@@ -271,8 +270,8 @@ public class JdbcRules {
     }
 
     @Override public double getRows() {
-      final boolean leftKey = left.isKey(BitSets.of(leftKeys));
-      final boolean rightKey = right.isKey(BitSets.of(rightKeys));
+      final boolean leftKey = left.isKey(ImmutableBitSet.of(leftKeys));
+      final boolean rightKey = right.isKey(ImmutableBitSet.of(rightKeys));
       final double leftRowCount = left.getRows();
       final double rightRowCount = right.getRows();
       if (leftKey && rightKey) {
@@ -566,7 +565,7 @@ public class JdbcRules {
         RelOptCluster cluster,
         RelTraitSet traitSet,
         RelNode child,
-        BitSet groupSet,
+        ImmutableBitSet groupSet,
         List<AggregateCall> aggCalls)
         throws InvalidRelException {
       super(cluster, traitSet, child, groupSet, aggCalls);
@@ -574,7 +573,7 @@ public class JdbcRules {
     }
 
     @Override public JdbcAggregate copy(RelTraitSet traitSet, RelNode input,
-        BitSet groupSet, List<AggregateCall> aggCalls) {
+        ImmutableBitSet groupSet, List<AggregateCall> aggCalls) {
       try {
         return new JdbcAggregate(getCluster(), traitSet, input, groupSet,
             aggCalls);
@@ -592,7 +591,7 @@ public class JdbcRules {
           x.builder(this, JdbcImplementor.Clause.GROUP_BY);
       List<SqlNode> groupByList = Expressions.list();
       final List<SqlNode> selectList = new ArrayList<SqlNode>();
-      for (int group : BitSets.toIter(groupSet)) {
+      for (int group : groupSet) {
         final SqlNode field = builder.context.field(group);
         addSelect(selectList, field, getRowType());
         groupByList.add(field);

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/materialize/Lattice.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/materialize/Lattice.java b/core/src/main/java/org/apache/calcite/materialize/Lattice.java
index b4a75c3..f1d926a 100644
--- a/core/src/main/java/org/apache/calcite/materialize/Lattice.java
+++ b/core/src/main/java/org/apache/calcite/materialize/Lattice.java
@@ -44,6 +44,7 @@ import org.apache.calcite.sql.SqlUtil;
 import org.apache.calcite.sql.fun.SqlStdOperatorTable;
 import org.apache.calcite.sql.validate.SqlValidatorUtil;
 import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.Util;
 import org.apache.calcite.util.graph.DefaultDirectedGraph;
 import org.apache.calcite.util.graph.DefaultEdge;
@@ -61,7 +62,6 @@ import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
 
 import java.math.BigInteger;
-import java.util.BitSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -228,18 +228,22 @@ public class Lattice {
     throw new AssertionError("input not found");
   }
 
-  public String sql(BitSet groupSet, List<Measure> aggCallList) {
-    final BitSet columnSet = (BitSet) groupSet.clone();
+  public String sql(ImmutableBitSet groupSet, List<Measure> aggCallList) {
+    final ImmutableBitSet.Builder columnSetBuilder =
+        ImmutableBitSet.builder(groupSet);
     for (Measure call : aggCallList) {
       for (Column arg : call.args) {
-        columnSet.set(arg.ordinal);
+        columnSetBuilder.set(arg.ordinal);
       }
     }
+    final ImmutableBitSet columnSet = columnSetBuilder.build();
+
     // Figure out which nodes are needed. Use a node if its columns are used
     // or if has a child whose columns are used.
     List<Node> usedNodes = Lists.newArrayList();
     for (Node node : nodes) {
-      if (BitSets.range(node.startCol, node.endCol).intersects(columnSet)) {
+      if (ImmutableBitSet.range(node.startCol, node.endCol)
+          .intersects(columnSet)) {
         use(usedNodes, node);
       }
     }
@@ -522,12 +526,12 @@ public class Lattice {
     }
 
     /** Returns the set of distinct argument ordinals. */
-    public BitSet argBitSet() {
-      final BitSet bitSet = new BitSet();
+    public ImmutableBitSet argBitSet() {
+      final ImmutableBitSet.Builder bitSet = ImmutableBitSet.builder();
       for (Column arg : args) {
         bitSet.set(arg.ordinal);
       }
-      return bitSet;
+      return bitSet.build();
     }
 
     /** Returns a list of argument ordinals. */
@@ -819,7 +823,7 @@ public class Lattice {
   public static class Tile {
     public final ImmutableList<Measure> measures;
     public final ImmutableList<Column> dimensions;
-    public final BitSet bitSet = new BitSet();
+    public final ImmutableBitSet bitSet;
 
     public Tile(ImmutableList<Measure> measures,
         ImmutableList<Column> dimensions) {
@@ -827,16 +831,18 @@ public class Lattice {
       this.dimensions = dimensions;
       assert Util.isStrictlySorted(dimensions);
       assert Util.isStrictlySorted(measures);
+      final ImmutableBitSet.Builder bitSetBuilder = ImmutableBitSet.builder();
       for (Column dimension : dimensions) {
-        bitSet.set(dimension.ordinal);
+        bitSetBuilder.set(dimension.ordinal);
       }
+      bitSet = bitSetBuilder.build();
     }
 
     public static TileBuilder builder() {
       return new TileBuilder();
     }
 
-    public BitSet bitSet() {
+    public ImmutableBitSet bitSet() {
       return bitSet;
     }
   }

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/materialize/MaterializationService.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/materialize/MaterializationService.java b/core/src/main/java/org/apache/calcite/materialize/MaterializationService.java
index a4e289c..c142454 100644
--- a/core/src/main/java/org/apache/calcite/materialize/MaterializationService.java
+++ b/core/src/main/java/org/apache/calcite/materialize/MaterializationService.java
@@ -37,7 +37,7 @@ import org.apache.calcite.rel.type.RelDataTypeImpl;
 import org.apache.calcite.runtime.Hook;
 import org.apache.calcite.schema.Schemas;
 import org.apache.calcite.schema.Table;
-import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.Pair;
 import org.apache.calcite.util.Util;
 
@@ -48,7 +48,6 @@ import com.google.common.collect.Sets;
 
 import java.lang.reflect.Type;
 import java.util.ArrayList;
-import java.util.BitSet;
 import java.util.Comparator;
 import java.util.Iterator;
 import java.util.LinkedHashSet;
@@ -199,8 +198,8 @@ public class MaterializationService {
    * materialization would try to create itself to populate itself!
    */
   public Pair<CalciteSchema.TableEntry, TileKey> defineTile(Lattice lattice,
-      BitSet groupSet, List<Lattice.Measure> measureList, CalciteSchema schema,
-      boolean create, boolean exact) {
+      ImmutableBitSet groupSet, List<Lattice.Measure> measureList,
+      CalciteSchema schema, boolean create, boolean exact) {
     MaterializationKey materializationKey;
     final TileKey tileKey =
         new TileKey(lattice, groupSet, ImmutableList.copyOf(measureList));
@@ -251,7 +250,7 @@ public class MaterializationService {
           : actor.keyByTile.entrySet()) {
         final TileKey tileKey2 = entry.getKey();
         if (tileKey2.lattice == lattice
-            && BitSets.contains(tileKey2.dimensions, groupSet)
+            && tileKey2.dimensions.contains(groupSet)
             && !tileKey2.dimensions.equals(groupSet)
             && allSatisfiable(measureList, tileKey2)) {
           materializationKey = entry.getValue();
@@ -321,7 +320,7 @@ public class MaterializationService {
     // less obviously, if it is composed of grouping columns.
     for (Lattice.Measure measure : measureList) {
       if (!(tileKey.measures.contains(measure)
-          || BitSets.contains(tileKey.dimensions, measure.argBitSet()))) {
+          || tileKey.dimensions.contains(measure.argBitSet()))) {
         return false;
       }
     }

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/materialize/TileKey.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/materialize/TileKey.java b/core/src/main/java/org/apache/calcite/materialize/TileKey.java
index 642edb6..1db02a9 100644
--- a/core/src/main/java/org/apache/calcite/materialize/TileKey.java
+++ b/core/src/main/java/org/apache/calcite/materialize/TileKey.java
@@ -16,11 +16,11 @@
  */
 package org.apache.calcite.materialize;
 
+import org.apache.calcite.util.ImmutableBitSet;
+
 import com.google.common.base.Objects;
 import com.google.common.collect.ImmutableList;
 
-import java.util.BitSet;
-
 /** Definition of a particular combination of dimensions and measures of a
  * lattice that is the basis of a materialization.
  *
@@ -29,11 +29,11 @@ import java.util.BitSet;
  * immutable and tiles are not added after their creation. */
 public class TileKey {
   public final Lattice lattice;
-  public final BitSet dimensions;
+  public final ImmutableBitSet dimensions;
   public final ImmutableList<Lattice.Measure> measures;
 
   /** Creates a TileKey. */
-  public TileKey(Lattice lattice, BitSet dimensions,
+  public TileKey(Lattice lattice, ImmutableBitSet dimensions,
       ImmutableList<Lattice.Measure> measures) {
     this.lattice = lattice;
     this.dimensions = dimensions;

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/plan/RelOptAbstractTable.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/RelOptAbstractTable.java b/core/src/main/java/org/apache/calcite/plan/RelOptAbstractTable.java
index 5496477..2c3099d 100644
--- a/core/src/main/java/org/apache/calcite/plan/RelOptAbstractTable.java
+++ b/core/src/main/java/org/apache/calcite/plan/RelOptAbstractTable.java
@@ -21,10 +21,10 @@ import org.apache.calcite.rel.RelCollation;
 import org.apache.calcite.rel.RelNode;
 import org.apache.calcite.rel.logical.LogicalTableScan;
 import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.util.ImmutableBitSet;
 
 import com.google.common.collect.ImmutableList;
 
-import java.util.BitSet;
 import java.util.Collections;
 import java.util.List;
 
@@ -83,7 +83,7 @@ public abstract class RelOptAbstractTable implements RelOptTable {
   }
 
   // Override to define keys
-  public boolean isKey(BitSet columns) {
+  public boolean isKey(ImmutableBitSet columns) {
     return false;
   }
 

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/plan/RelOptLattice.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/RelOptLattice.java b/core/src/main/java/org/apache/calcite/plan/RelOptLattice.java
index 9131ba3..a32f55d 100644
--- a/core/src/main/java/org/apache/calcite/plan/RelOptLattice.java
+++ b/core/src/main/java/org/apache/calcite/plan/RelOptLattice.java
@@ -22,9 +22,9 @@ import org.apache.calcite.materialize.Lattice;
 import org.apache.calcite.materialize.MaterializationService;
 import org.apache.calcite.materialize.TileKey;
 import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.Pair;
 
-import java.util.BitSet;
 import java.util.List;
 
 /**
@@ -70,7 +70,7 @@ public class RelOptLattice {
    * @return Materialized table
    */
   public Pair<CalciteSchema.TableEntry, TileKey> getAggregate(
-      RelOptPlanner planner, BitSet groupSet,
+      RelOptPlanner planner, ImmutableBitSet groupSet,
       List<Lattice.Measure> measureList) {
     final CalciteConnectionConfig config =
         planner.getContext().unwrap(CalciteConnectionConfig.class);

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/plan/RelOptTable.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/RelOptTable.java b/core/src/main/java/org/apache/calcite/plan/RelOptTable.java
index 571fbd1..c628f71 100644
--- a/core/src/main/java/org/apache/calcite/plan/RelOptTable.java
+++ b/core/src/main/java/org/apache/calcite/plan/RelOptTable.java
@@ -20,8 +20,8 @@ import org.apache.calcite.linq4j.tree.Expression;
 import org.apache.calcite.rel.RelCollation;
 import org.apache.calcite.rel.RelNode;
 import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.util.ImmutableBitSet;
 
-import java.util.BitSet;
 import java.util.List;
 
 /**
@@ -82,7 +82,7 @@ public interface RelOptTable {
    * @param columns Ordinals of key columns
    * @return Whether the given columns are a key or a superset of a key
    */
-  boolean isKey(BitSet columns);
+  boolean isKey(ImmutableBitSet columns);
 
   /**
    * Finds an interface implemented by this table.

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java b/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java
index e188d35..5949dbf 100644
--- a/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java
+++ b/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java
@@ -67,9 +67,9 @@ import org.apache.calcite.sql.fun.SqlStdOperatorTable;
 import org.apache.calcite.sql.type.MultisetSqlType;
 import org.apache.calcite.sql.type.SqlTypeName;
 import org.apache.calcite.sql.validate.SqlValidatorUtil;
-import org.apache.calcite.util.BitSets;
 import org.apache.calcite.util.Bug;
 import org.apache.calcite.util.Holder;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.Pair;
 import org.apache.calcite.util.Permutation;
 import org.apache.calcite.util.Util;
@@ -360,7 +360,7 @@ public abstract class RelOptUtil {
           new LogicalAggregate(
               ret.getCluster(),
               ret,
-              BitSets.of(),
+              ImmutableBitSet.of(),
               ImmutableList.of(aggCall));
     }
 
@@ -401,7 +401,7 @@ public abstract class RelOptUtil {
       final int keyCount = ret.getRowType().getFieldCount();
       if (!needsOuterJoin) {
         return Pair.<RelNode, Boolean>of(
-            new LogicalAggregate(cluster, ret, BitSets.range(keyCount),
+            new LogicalAggregate(cluster, ret, ImmutableBitSet.range(keyCount),
                 ImmutableList.<AggregateCall>of()),
             false);
       }
@@ -438,7 +438,7 @@ public abstract class RelOptUtil {
       ret = new LogicalAggregate(
           cluster,
           ret,
-          BitSets.range(projectedKeyCount),
+          ImmutableBitSet.range(projectedKeyCount),
           ImmutableList.of(aggCall));
 
       switch (logic) {
@@ -683,7 +683,7 @@ public abstract class RelOptUtil {
     return new LogicalAggregate(
         rel.getCluster(),
         rel,
-        BitSets.of(),
+        ImmutableBitSet.of(),
         aggCalls);
   }
 
@@ -698,7 +698,7 @@ public abstract class RelOptUtil {
     return new LogicalAggregate(
         rel.getCluster(),
         rel,
-        BitSets.range(rel.getRowType().getFieldCount()),
+        ImmutableBitSet.range(rel.getRowType().getFieldCount()),
         ImmutableList.<AggregateCall>of());
   }
 
@@ -967,8 +967,8 @@ public abstract class RelOptUtil {
         RexNode op0 = operands.get(0);
         RexNode op1 = operands.get(1);
 
-        final BitSet projRefs0 = RelOptUtil.InputFinder.bits(op0);
-        final BitSet projRefs1 = RelOptUtil.InputFinder.bits(op1);
+        final ImmutableBitSet projRefs0 = InputFinder.bits(op0);
+        final ImmutableBitSet projRefs1 = InputFinder.bits(op1);
 
         if ((projRefs0.nextSetBit(firstRightField) < 0)
             && (projRefs1.nextSetBit(firstLeftField)
@@ -1041,7 +1041,7 @@ public abstract class RelOptUtil {
         //     f(LHS) > 0 ===> ( f(LHS) > 0 ) = TRUE,
         // and make the RHS produce TRUE, but only if we're strictly
         // looking for equi-joins
-        final BitSet projRefs = RelOptUtil.InputFinder.bits(condition);
+        final ImmutableBitSet projRefs = InputFinder.bits(condition);
         leftKey = null;
         rightKey = null;
 
@@ -2008,8 +2008,10 @@ public abstract class RelOptUtil {
     assert nTotalFields == nSysFields + nFieldsLeft + nFieldsRight;
 
     // set the reference bitmaps for the left and right children
-    BitSet leftBitmap = BitSets.range(nSysFields, nSysFields + nFieldsLeft);
-    BitSet rightBitmap = BitSets.range(nSysFields + nFieldsLeft, nTotalFields);
+    ImmutableBitSet leftBitmap =
+        ImmutableBitSet.range(nSysFields, nSysFields + nFieldsLeft);
+    ImmutableBitSet rightBitmap =
+        ImmutableBitSet.range(nSysFields + nFieldsLeft, nTotalFields);
 
     for (RexNode filter : aboveFilters) {
       if (joinType.generatesNullsOnLeft()
@@ -2117,14 +2119,15 @@ public abstract class RelOptUtil {
         : nSysFields + nFieldsLeft + nFieldsRight);
 
     // set the reference bitmaps for the left and right children
-    BitSet leftBitmap =
-        BitSets.range(nSysFields, nSysFields + nFieldsLeft);
-    BitSet rightBitmap =
-        BitSets.range(nSysFields + nFieldsLeft, nTotalFields);
+    ImmutableBitSet leftBitmap =
+        ImmutableBitSet.range(nSysFields, nSysFields + nFieldsLeft);
+    ImmutableBitSet rightBitmap =
+        ImmutableBitSet.range(nSysFields + nFieldsLeft, nTotalFields);
 
     final List<RexNode> filtersToRemove = Lists.newArrayList();
     for (RexNode filter : filters) {
       final InputFinder inputFinder = InputFinder.analyze(filter);
+      final ImmutableBitSet inputBits = inputFinder.inputBitSet.build();
 
       // REVIEW - are there any expressions that need special handling
       // and therefore cannot be pushed?
@@ -2132,7 +2135,7 @@ public abstract class RelOptUtil {
       // filters can be pushed to the left child if the left child
       // does not generate NULLs and the only columns referenced in
       // the filter originate from the left child
-      if (pushLeft && BitSets.contains(leftBitmap, inputFinder.inputBitSet)) {
+      if (pushLeft && leftBitmap.contains(inputBits)) {
         // ignore filters that always evaluate to true
         if (!filter.isAlwaysTrue()) {
           // adjust the field references in the filter to reflect
@@ -2156,8 +2159,7 @@ public abstract class RelOptUtil {
         // filters can be pushed to the right child if the right child
         // does not generate NULLs and the only columns referenced in
         // the filter originate from the right child
-      } else if (pushRight
-          && BitSets.contains(rightBitmap, inputFinder.inputBitSet)) {
+      } else if (pushRight && rightBitmap.contains(inputBits)) {
         if (!filter.isAlwaysTrue()) {
           // adjust the field references in the filter to reflect
           // that fields in the right now shift over to the left;
@@ -2234,15 +2236,15 @@ public abstract class RelOptUtil {
    *                    the child input
    */
   public static void splitFilters(
-      BitSet childBitmap,
+      ImmutableBitSet childBitmap,
       RexNode predicate,
       List<RexNode> pushable,
       List<RexNode> notPushable) {
     // for each filter, if the filter only references the child inputs,
     // then it can be pushed
     for (RexNode filter : conjunctions(predicate)) {
-      BitSet filterRefs = RelOptUtil.InputFinder.bits(filter);
-      if (BitSets.contains(childBitmap, filterRefs)) {
+      ImmutableBitSet filterRefs = InputFinder.bits(filter);
+      if (childBitmap.contains(filterRefs)) {
         pushable.add(filter);
       } else {
         notPushable.add(filter);
@@ -2447,12 +2449,12 @@ public abstract class RelOptUtil {
     // the post-join filter.  Since the filter effectively sits in
     // between the LogicalProject and the MultiJoin, the projection needs
     // to include those filter references.
-    BitSet inputRefs = InputFinder.bits(
-        project.getProjects(), multiJoin.getPostJoinFilter());
+    ImmutableBitSet inputRefs =
+        InputFinder.bits(project.getProjects(), multiJoin.getPostJoinFilter());
 
     // create new copies of the bitmaps
     List<RelNode> multiJoinInputs = multiJoin.getInputs();
-    List<BitSet> newProjFields = new ArrayList<BitSet>();
+    List<BitSet> newProjFields = Lists.newArrayList();
     for (RelNode multiJoinInput : multiJoinInputs) {
       newProjFields.add(
           new BitSet(multiJoinInput.getRowType().getFieldCount()));
@@ -2462,7 +2464,7 @@ public abstract class RelOptUtil {
     int currInput = -1;
     int startField = 0;
     int nFields = 0;
-    for (int bit : BitSets.toIter(inputRefs)) {
+    for (int bit : inputRefs) {
       while (bit >= (startField + nFields)) {
         startField += nFields;
         currInput++;
@@ -2483,7 +2485,7 @@ public abstract class RelOptUtil {
         multiJoin.isFullOuterJoin(),
         multiJoin.getOuterJoinConditions(),
         multiJoin.getJoinTypes(),
-        newProjFields,
+        Lists.transform(newProjFields, ImmutableBitSet.FROM_BIT_SET),
         multiJoin.getJoinFieldRefCountsMap(),
         multiJoin.getPostJoinFilter());
   }
@@ -3071,22 +3073,22 @@ public abstract class RelOptUtil {
    * Visitor which builds a bitmap of the inputs used by an expression.
    */
   public static class InputFinder extends RexVisitorImpl<Void> {
-    final BitSet inputBitSet;
+    public final ImmutableBitSet.Builder inputBitSet;
     private final Set<RelDataTypeField> extraFields;
 
-    public InputFinder(BitSet inputBitSet) {
-      this(inputBitSet, null);
+    public InputFinder() {
+      this(null);
     }
 
-    public InputFinder(BitSet inputBitSet, Set<RelDataTypeField> extraFields) {
+    public InputFinder(Set<RelDataTypeField> extraFields) {
       super(true);
-      this.inputBitSet = inputBitSet;
+      this.inputBitSet = ImmutableBitSet.builder();
       this.extraFields = extraFields;
     }
 
     /** Returns an input finder that has analyzed a given expression. */
     public static InputFinder analyze(RexNode node) {
-      final InputFinder inputFinder = new InputFinder(new BitSet());
+      final InputFinder inputFinder = new InputFinder();
       node.accept(inputFinder);
       return inputFinder;
     }
@@ -3094,18 +3096,18 @@ public abstract class RelOptUtil {
     /**
      * Returns a bit set describing the inputs used by an expression.
      */
-    public static BitSet bits(RexNode node) {
-      return analyze(node).inputBitSet;
+    public static ImmutableBitSet bits(RexNode node) {
+      return analyze(node).inputBitSet.build();
     }
 
     /**
      * Returns a bit set describing the inputs used by a collection of
      * project expressions and an optional condition.
      */
-    public static BitSet bits(List<RexNode> exprs, RexNode expr) {
-      final BitSet inputBitSet = new BitSet();
-      RexProgram.apply(new InputFinder(inputBitSet), exprs, expr);
-      return inputBitSet;
+    public static ImmutableBitSet bits(List<RexNode> exprs, RexNode expr) {
+      final InputFinder inputFinder = new InputFinder();
+      RexProgram.apply(inputFinder, exprs, expr);
+      return inputFinder.inputBitSet.build();
     }
 
     public Void visitInputRef(RexInputRef inputRef) {

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/plan/Strong.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/Strong.java b/core/src/main/java/org/apache/calcite/plan/Strong.java
index e279b14..5957bc7 100644
--- a/core/src/main/java/org/apache/calcite/plan/Strong.java
+++ b/core/src/main/java/org/apache/calcite/plan/Strong.java
@@ -20,8 +20,8 @@ import org.apache.calcite.rex.RexCall;
 import org.apache.calcite.rex.RexInputRef;
 import org.apache.calcite.rex.RexLiteral;
 import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.util.ImmutableBitSet;
 
-import java.util.BitSet;
 import java.util.List;
 
 /** Utilities for strong predicates.
@@ -42,19 +42,19 @@ import java.util.List;
  * </ul>
  */
 public class Strong {
-  private final BitSet nullColumns;
+  private final ImmutableBitSet nullColumns;
 
-  private Strong(BitSet nullColumns) {
+  private Strong(ImmutableBitSet nullColumns) {
     this.nullColumns = nullColumns;
   }
 
-  public static Strong of(BitSet nullColumns) {
+  public static Strong of(ImmutableBitSet nullColumns) {
     return new Strong(nullColumns);
   }
 
   /** Returns whether the analyzed expression will return null if a given set
    * of input columns are null. */
-  public static boolean is(RexNode node, BitSet nullColumns) {
+  public static boolean is(RexNode node, ImmutableBitSet nullColumns) {
     return of(nullColumns).strong(node);
   }
 

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java b/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java
index 0b95f82..c61208e 100644
--- a/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java
+++ b/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java
@@ -48,8 +48,8 @@ import org.apache.calcite.sql.SqlAggFunction;
 import org.apache.calcite.sql.SqlKind;
 import org.apache.calcite.sql.fun.SqlStdOperatorTable;
 import org.apache.calcite.sql.validate.SqlValidatorUtil;
-import org.apache.calcite.util.BitSets;
 import org.apache.calcite.util.ControlFlowException;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.IntList;
 import org.apache.calcite.util.Pair;
 import org.apache.calcite.util.Util;
@@ -72,7 +72,6 @@ import com.google.common.collect.Sets;
 
 import java.util.AbstractList;
 import java.util.ArrayList;
-import java.util.BitSet;
 import java.util.HashMap;
 import java.util.Iterator;
 import java.util.List;
@@ -1134,7 +1133,7 @@ public class SubstitutionVisitor {
       //   target: SELECT x, y, SUM(a) AS s, COUNT(b) AS cb FROM t GROUP BY x, y
       // transforms to
       //   result: SELECT x, SUM(cb) FROM (target) GROUP BY x
-      if (!BitSets.contains(target.getGroupSet(), query.getGroupSet())) {
+      if (!target.getGroupSet().contains(query.getGroupSet())) {
         return null;
       }
       MutableRel result = unifyAggregates(query, target);
@@ -1147,7 +1146,7 @@ public class SubstitutionVisitor {
 
   public static MutableAggregate permute(MutableAggregate aggregate,
       MutableRel input, Mapping mapping) {
-    BitSet groupSet = Mappings.apply(mapping, aggregate.getGroupSet());
+    ImmutableBitSet groupSet = Mappings.apply(mapping, aggregate.getGroupSet());
     List<AggregateCall> aggregateCalls =
         apply(mapping, aggregate.getAggCallList());
     return MutableAggregate.of(input, groupSet, aggregateCalls);
@@ -1183,9 +1182,9 @@ public class SubstitutionVisitor {
       result = MutableRels.createProject(target, projects);
     } else {
       // Target is coarser level of aggregation. Generate an aggregate.
-      final BitSet groupSet = new BitSet();
-      final IntList targetGroupList = BitSets.toList(target.getGroupSet());
-      for (int c : BitSets.toIter(query.getGroupSet())) {
+      final ImmutableBitSet.Builder groupSet = ImmutableBitSet.builder();
+      final IntList targetGroupList = target.getGroupSet().toList();
+      for (int c : query.getGroupSet()) {
         int c2 = targetGroupList.indexOf(c);
         if (c2 < 0) {
           return null;
@@ -1207,7 +1206,7 @@ public class SubstitutionVisitor {
                 ImmutableList.of(target.groupSet.cardinality() + i),
                 aggregateCall.type, aggregateCall.name));
       }
-      result = MutableAggregate.of(target, groupSet, aggregateCalls);
+      result = MutableAggregate.of(target, groupSet.build(), aggregateCalls);
     }
     return MutableRels.createCastRel(result, query.getRowType(), true);
   }
@@ -1621,17 +1620,17 @@ public class SubstitutionVisitor {
   /** Mutable equivalent of
    * {@link org.apache.calcite.rel.logical.LogicalAggregate}. */
   private static class MutableAggregate extends MutableSingleRel {
-    private final BitSet groupSet;
+    private final ImmutableBitSet groupSet;
     private final List<AggregateCall> aggCalls;
 
     private MutableAggregate(MutableRel input, RelDataType rowType,
-        BitSet groupSet, List<AggregateCall> aggCalls) {
+        ImmutableBitSet groupSet, List<AggregateCall> aggCalls) {
       super(MutableRelType.AGGREGATE, rowType, input);
       this.groupSet = groupSet;
       this.aggCalls = aggCalls;
     }
 
-    static MutableAggregate of(MutableRel input, BitSet groupSet,
+    static MutableAggregate of(MutableRel input, ImmutableBitSet groupSet,
         List<AggregateCall> aggCalls) {
       RelDataType rowType =
           Aggregate.deriveRowType(input.cluster.getTypeFactory(),
@@ -1656,7 +1655,7 @@ public class SubstitutionVisitor {
           .append(", calls: ").append(aggCalls).append(")");
     }
 
-    public BitSet getGroupSet() {
+    public ImmutableBitSet getGroupSet() {
       return groupSet;
     }
 

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/plan/hep/HepRelVertex.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/hep/HepRelVertex.java b/core/src/main/java/org/apache/calcite/plan/hep/HepRelVertex.java
index 5e8fab4..3ee9739 100644
--- a/core/src/main/java/org/apache/calcite/plan/hep/HepRelVertex.java
+++ b/core/src/main/java/org/apache/calcite/plan/hep/HepRelVertex.java
@@ -24,9 +24,9 @@ import org.apache.calcite.rel.RelNode;
 import org.apache.calcite.rel.RelWriter;
 import org.apache.calcite.rel.metadata.RelMetadataQuery;
 import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.Util;
 
-import java.util.BitSet;
 import java.util.List;
 
 /**
@@ -80,7 +80,7 @@ public class HepRelVertex extends AbstractRelNode {
     return currentRel.isDistinct();
   }
 
-  @Override public boolean isKey(BitSet columns) {
+  @Override public boolean isKey(ImmutableBitSet columns) {
     return currentRel.isKey(columns);
   }
 

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java b/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java
index 294a29c..b08320b 100644
--- a/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java
+++ b/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java
@@ -30,13 +30,13 @@ import org.apache.calcite.rel.RelNode;
 import org.apache.calcite.rel.RelWriter;
 import org.apache.calcite.rel.metadata.RelMetadataQuery;
 import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.Util;
 import org.apache.calcite.util.trace.CalciteTrace;
 
 import java.io.PrintWriter;
 import java.io.StringWriter;
 import java.util.ArrayList;
-import java.util.BitSet;
 import java.util.Collection;
 import java.util.Iterator;
 import java.util.LinkedHashSet;
@@ -185,7 +185,7 @@ public class RelSubset extends AbstractRelNode {
     return false;
   }
 
-  @Override public boolean isKey(BitSet columns) {
+  @Override public boolean isKey(ImmutableBitSet columns) {
     for (RelNode rel : set.rels) {
       if (rel.isKey(columns)) {
         return true;

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/prepare/RelOptTableImpl.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/prepare/RelOptTableImpl.java b/core/src/main/java/org/apache/calcite/prepare/RelOptTableImpl.java
index a3377a0..68e0dcf 100644
--- a/core/src/main/java/org/apache/calcite/prepare/RelOptTableImpl.java
+++ b/core/src/main/java/org/apache/calcite/prepare/RelOptTableImpl.java
@@ -35,6 +35,7 @@ import org.apache.calcite.schema.Table;
 import org.apache.calcite.schema.TranslatableTable;
 import org.apache.calcite.sql.SqlAccessType;
 import org.apache.calcite.sql.validate.SqlMonotonicity;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.Util;
 
 import com.google.common.base.Function;
@@ -42,7 +43,6 @@ import com.google.common.base.Functions;
 import com.google.common.collect.ImmutableList;
 
 import java.lang.reflect.Type;
-import java.util.BitSet;
 import java.util.Collections;
 import java.util.List;
 
@@ -215,7 +215,7 @@ public class RelOptTableImpl implements Prepare.PreparingTable {
     return Collections.emptyList();
   }
 
-  public boolean isKey(BitSet columns) {
+  public boolean isKey(ImmutableBitSet columns) {
     return table.getStatistic().isKey(columns);
   }
 

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/AbstractRelNode.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/AbstractRelNode.java b/core/src/main/java/org/apache/calcite/rel/AbstractRelNode.java
index 4a60299..1bd85cb 100644
--- a/core/src/main/java/org/apache/calcite/rel/AbstractRelNode.java
+++ b/core/src/main/java/org/apache/calcite/rel/AbstractRelNode.java
@@ -32,7 +32,7 @@ import org.apache.calcite.rel.metadata.RelMetadataQuery;
 import org.apache.calcite.rel.type.RelDataType;
 import org.apache.calcite.rex.RexNode;
 import org.apache.calcite.sql.SqlExplainLevel;
-import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.Pair;
 import org.apache.calcite.util.Util;
 import org.apache.calcite.util.trace.CalciteTrace;
@@ -42,7 +42,6 @@ import com.google.common.collect.ImmutableList;
 import java.io.PrintWriter;
 import java.io.StringWriter;
 import java.util.ArrayList;
-import java.util.BitSet;
 import java.util.Collections;
 import java.util.List;
 import java.util.Set;
@@ -169,10 +168,10 @@ public abstract class AbstractRelNode implements RelNode {
   }
 
   public boolean isDistinct() {
-    return isKey(BitSets.range(getRowType().getFieldCount()));
+    return isKey(ImmutableBitSet.range(getRowType().getFieldCount()));
   }
 
-  public boolean isKey(BitSet columns) {
+  public boolean isKey(ImmutableBitSet columns) {
     return false;
   }
 

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/RelInput.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/RelInput.java b/core/src/main/java/org/apache/calcite/rel/RelInput.java
index 0eff922..2ffe64f 100644
--- a/core/src/main/java/org/apache/calcite/rel/RelInput.java
+++ b/core/src/main/java/org/apache/calcite/rel/RelInput.java
@@ -23,8 +23,8 @@ import org.apache.calcite.rel.core.AggregateCall;
 import org.apache.calcite.rel.type.RelDataType;
 import org.apache.calcite.rex.RexLiteral;
 import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.util.ImmutableBitSet;
 
-import java.util.BitSet;
 import java.util.List;
 
 /**
@@ -51,7 +51,7 @@ public interface RelInput {
    */
   RexNode getExpression(String tag);
 
-  BitSet getBitSet(String tag);
+  ImmutableBitSet getBitSet(String tag);
 
   List<AggregateCall> getAggregateCalls(String tag);
 

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/RelNode.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/RelNode.java b/core/src/main/java/org/apache/calcite/rel/RelNode.java
index 50da558..fa28861 100644
--- a/core/src/main/java/org/apache/calcite/rel/RelNode.java
+++ b/core/src/main/java/org/apache/calcite/rel/RelNode.java
@@ -27,8 +27,8 @@ import org.apache.calcite.rel.metadata.Metadata;
 import org.apache.calcite.rel.metadata.RelMetadataQuery;
 import org.apache.calcite.rel.type.RelDataType;
 import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.util.ImmutableBitSet;
 
-import java.util.BitSet;
 import java.util.List;
 import java.util.Set;
 
@@ -345,7 +345,7 @@ public interface RelNode extends RelOptNode, Cloneable {
    * @param columns Ordinals of key columns
    * @return Whether the given columns are a key or a superset of a key
    */
-  boolean isKey(BitSet columns);
+  boolean isKey(ImmutableBitSet columns);
 
   /**
    * Accepts a visit from a shuttle.

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/core/Aggregate.java
----------------------------------------------------------------------
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 920ef46..d0e19be 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
@@ -38,15 +38,14 @@ import org.apache.calcite.sql.SqlOperatorBinding;
 import org.apache.calcite.sql.SqlUtil;
 import org.apache.calcite.sql.parser.SqlParserPos;
 import org.apache.calcite.sql.validate.SqlValidatorException;
-import org.apache.calcite.util.BitSets;
 import org.apache.calcite.util.CompositeList;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.IntList;
 import org.apache.calcite.util.Util;
 
 import com.google.common.collect.ImmutableList;
 
 import java.util.AbstractList;
-import java.util.BitSet;
 import java.util.List;
 
 /**
@@ -69,7 +68,7 @@ public abstract class Aggregate extends SingleRel {
   //~ Instance fields --------------------------------------------------------
 
   protected final List<AggregateCall> aggCalls;
-  protected final BitSet groupSet;
+  protected final ImmutableBitSet groupSet;
 
   //~ Constructors -----------------------------------------------------------
 
@@ -86,16 +85,13 @@ public abstract class Aggregate extends SingleRel {
       RelOptCluster cluster,
       RelTraitSet traits,
       RelNode child,
-      BitSet groupSet,
+      ImmutableBitSet groupSet,
       List<AggregateCall> aggCalls) {
     super(cluster, traits, child);
     assert aggCalls != null;
     this.aggCalls = ImmutableList.copyOf(aggCalls);
     this.groupSet = groupSet;
     assert groupSet != null;
-    assert groupSet.isEmpty() == (groupSet.cardinality() == 0)
-        : "See https://bugs.openjdk.java.net/browse/JDK-6222207, "
-        + "BitSet internal invariants may be violated";
     assert groupSet.length() <= child.getRowType().getFieldCount();
     for (AggregateCall aggCall : aggCalls) {
       assert typeMatchesInferred(aggCall, true);
@@ -122,7 +118,7 @@ public abstract class Aggregate extends SingleRel {
    * @see #copy(org.apache.calcite.plan.RelTraitSet, java.util.List)
    */
   public abstract Aggregate copy(RelTraitSet traitSet, RelNode input,
-      BitSet groupSet, List<AggregateCall> aggCalls);
+      ImmutableBitSet groupSet, List<AggregateCall> aggCalls);
 
   // implement RelNode
   public boolean isDistinct() {
@@ -156,11 +152,11 @@ public abstract class Aggregate extends SingleRel {
   }
 
   /**
-   * Returns a bitmap of the grouping fields.
+   * Returns a bit set of the grouping fields.
    *
-   * @return bitset of ordinals of grouping fields
+   * @return bit set of ordinals of grouping fields
    */
-  public BitSet getGroupSet() {
+  public ImmutableBitSet getGroupSet() {
     return groupSet;
   }
 
@@ -209,9 +205,9 @@ public abstract class Aggregate extends SingleRel {
 
   /** Computes the row type of an {@code Aggregate} before it exists. */
   public static RelDataType deriveRowType(RelDataTypeFactory typeFactory,
-      final RelDataType inputRowType, BitSet groupSet,
+      final RelDataType inputRowType, ImmutableBitSet groupSet,
       final List<AggregateCall> aggCalls) {
-    final IntList groupList = BitSets.toList(groupSet);
+    final IntList groupList = groupSet.toList();
     assert groupList.size() == groupSet.cardinality();
     return typeFactory.createStructType(
         CompositeList.of(
@@ -257,7 +253,7 @@ public abstract class Aggregate extends SingleRel {
   private boolean typeMatchesInferred(
       final AggregateCall aggCall,
       final boolean fail) {
-    SqlAggFunction aggFunction = (SqlAggFunction) aggCall.getAggregation();
+    SqlAggFunction aggFunction = aggCall.getAggregation();
     AggCallBinding callBinding = aggCall.createBinding(this);
     RelDataType type = aggFunction.inferReturnType(callBinding);
     RelDataType expectedType = aggCall.type;

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/core/Intersect.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/core/Intersect.java b/core/src/main/java/org/apache/calcite/rel/core/Intersect.java
index 472cd92..139567c 100644
--- a/core/src/main/java/org/apache/calcite/rel/core/Intersect.java
+++ b/core/src/main/java/org/apache/calcite/rel/core/Intersect.java
@@ -22,8 +22,8 @@ import org.apache.calcite.rel.RelInput;
 import org.apache.calcite.rel.RelNode;
 import org.apache.calcite.rel.metadata.RelMetadataQuery;
 import org.apache.calcite.sql.SqlKind;
+import org.apache.calcite.util.ImmutableBitSet;
 
-import java.util.BitSet;
 import java.util.List;
 
 /**
@@ -63,7 +63,7 @@ public abstract class Intersect extends SetOp {
     return dRows;
   }
 
-  @Override public boolean isKey(BitSet columns) {
+  @Override public boolean isKey(ImmutableBitSet columns) {
     for (RelNode input : inputs) {
       if (input.isKey(columns)) {
         return true;

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/core/JoinInfo.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/core/JoinInfo.java b/core/src/main/java/org/apache/calcite/rel/core/JoinInfo.java
index b1c8a18..03a955e 100644
--- a/core/src/main/java/org/apache/calcite/rel/core/JoinInfo.java
+++ b/core/src/main/java/org/apache/calcite/rel/core/JoinInfo.java
@@ -20,14 +20,13 @@ import org.apache.calcite.plan.RelOptUtil;
 import org.apache.calcite.rel.RelNode;
 import org.apache.calcite.rex.RexBuilder;
 import org.apache.calcite.rex.RexNode;
-import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.ImmutableIntList;
 import org.apache.calcite.util.mapping.IntPair;
 
 import com.google.common.base.Preconditions;
 
 import java.util.ArrayList;
-import java.util.BitSet;
 import java.util.List;
 
 /** An analyzed join condition.
@@ -82,12 +81,12 @@ public abstract class JoinInfo {
     return IntPair.zip(leftKeys, rightKeys);
   }
 
-  public BitSet leftSet() {
-    return BitSets.of(leftKeys);
+  public ImmutableBitSet leftSet() {
+    return ImmutableBitSet.of(leftKeys);
   }
 
-  public BitSet rightSet() {
-    return BitSets.of(rightKeys);
+  public ImmutableBitSet rightSet() {
+    return ImmutableBitSet.of(rightKeys);
   }
 
   public abstract RexNode getRemaining(RexBuilder rexBuilder);

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/core/Minus.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/core/Minus.java b/core/src/main/java/org/apache/calcite/rel/core/Minus.java
index 12feba8..92b0784 100644
--- a/core/src/main/java/org/apache/calcite/rel/core/Minus.java
+++ b/core/src/main/java/org/apache/calcite/rel/core/Minus.java
@@ -22,8 +22,8 @@ import org.apache.calcite.rel.RelInput;
 import org.apache.calcite.rel.RelNode;
 import org.apache.calcite.rel.metadata.RelMetadataQuery;
 import org.apache.calcite.sql.SqlKind;
+import org.apache.calcite.util.ImmutableBitSet;
 
-import java.util.BitSet;
 import java.util.List;
 
 /**
@@ -61,7 +61,7 @@ public abstract class Minus extends SetOp {
     return dRows;
   }
 
-  @Override public boolean isKey(BitSet columns) {
+  @Override public boolean isKey(ImmutableBitSet columns) {
     return inputs.get(0).isKey(columns)
         || super.isKey(columns);
   }

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/core/RelFactories.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/core/RelFactories.java b/core/src/main/java/org/apache/calcite/rel/core/RelFactories.java
index fcc9a2d..332fdd5 100644
--- a/core/src/main/java/org/apache/calcite/rel/core/RelFactories.java
+++ b/core/src/main/java/org/apache/calcite/rel/core/RelFactories.java
@@ -31,10 +31,10 @@ import org.apache.calcite.rel.logical.LogicalUnion;
 import org.apache.calcite.rel.type.RelDataTypeField;
 import org.apache.calcite.rex.RexNode;
 import org.apache.calcite.sql.SqlKind;
+import org.apache.calcite.util.ImmutableBitSet;
 
 import com.google.common.collect.ImmutableList;
 
-import java.util.BitSet;
 import java.util.List;
 import java.util.Set;
 
@@ -148,7 +148,7 @@ public class RelFactories {
    */
   public interface AggregateFactory {
     /** Creates an aggregate. */
-    RelNode createAggregate(RelNode child, BitSet groupSet,
+    RelNode createAggregate(RelNode child, ImmutableBitSet groupSet,
         List<AggregateCall> aggCalls);
   }
 
@@ -157,7 +157,7 @@ public class RelFactories {
    * that returns a vanilla {@link LogicalAggregate}.
    */
   private static class AggregateFactoryImpl implements AggregateFactory {
-    public RelNode createAggregate(RelNode child, BitSet groupSet,
+    public RelNode createAggregate(RelNode child, ImmutableBitSet groupSet,
         List<AggregateCall> aggCalls) {
       return new LogicalAggregate(child.getCluster(), child, groupSet,
           aggCalls);

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/core/SetOp.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/core/SetOp.java b/core/src/main/java/org/apache/calcite/rel/core/SetOp.java
index 7b0187a..2b17733 100644
--- a/core/src/main/java/org/apache/calcite/rel/core/SetOp.java
+++ b/core/src/main/java/org/apache/calcite/rel/core/SetOp.java
@@ -26,13 +26,13 @@ import org.apache.calcite.rel.RelNode;
 import org.apache.calcite.rel.RelWriter;
 import org.apache.calcite.rel.type.RelDataType;
 import org.apache.calcite.sql.SqlKind;
+import org.apache.calcite.util.ImmutableBitSet;
 
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 
 import java.util.AbstractList;
 import java.util.ArrayList;
-import java.util.BitSet;
 import java.util.List;
 
 /**
@@ -88,7 +88,7 @@ public abstract class SetOp extends AbstractRelNode {
     recomputeDigest();
   }
 
-  @Override public boolean isKey(BitSet columns) {
+  @Override public boolean isKey(ImmutableBitSet columns) {
     // If not ALL then the rows are distinct.
     // Therefore the set of all columns is a key.
     return !all && columns.nextClearBit(0) >= getRowType().getFieldCount();

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/core/TableScan.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/core/TableScan.java b/core/src/main/java/org/apache/calcite/rel/core/TableScan.java
index 9eaa931..496e39b 100644
--- a/core/src/main/java/org/apache/calcite/rel/core/TableScan.java
+++ b/core/src/main/java/org/apache/calcite/rel/core/TableScan.java
@@ -31,10 +31,9 @@ import org.apache.calcite.rel.type.RelDataType;
 import org.apache.calcite.rel.type.RelDataTypeField;
 import org.apache.calcite.rex.RexBuilder;
 import org.apache.calcite.rex.RexNode;
-import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
 
 import java.util.ArrayList;
-import java.util.BitSet;
 import java.util.List;
 import java.util.Set;
 
@@ -83,7 +82,7 @@ public abstract class TableScan extends AbstractRelNode {
     return table.getCollationList();
   }
 
-  @Override public boolean isKey(BitSet columns) {
+  @Override public boolean isKey(ImmutableBitSet columns) {
     return table.isKey(columns);
   }
 
@@ -120,10 +119,11 @@ public abstract class TableScan extends AbstractRelNode {
    *                    wanted by the consumer
    * @return Relational expression that projects the desired fields
    */
-  public RelNode project(BitSet fieldsUsed, Set<RelDataTypeField> extraFields,
-    RelFactories.ProjectFactory projectFactory) {
+  public RelNode project(ImmutableBitSet fieldsUsed,
+      Set<RelDataTypeField> extraFields,
+      RelFactories.ProjectFactory projectFactory) {
     final int fieldCount = getRowType().getFieldCount();
-    if (fieldsUsed.equals(BitSets.range(fieldCount))
+    if (fieldsUsed.equals(ImmutableBitSet.range(fieldCount))
         && extraFields.isEmpty()) {
       return this;
     }
@@ -133,7 +133,7 @@ public abstract class TableScan extends AbstractRelNode {
     final List<RelDataTypeField> fields = getRowType().getFieldList();
 
     // Project the subset of fields.
-    for (int i : BitSets.toIter(fieldsUsed)) {
+    for (int i : fieldsUsed) {
       RelDataTypeField field = fields.get(i);
       exprList.add(rexBuilder.makeInputRef(this, i));
       nameList.add(field.getName());

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/core/Window.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/core/Window.java b/core/src/main/java/org/apache/calcite/rel/core/Window.java
index 043da29..fc090f8 100644
--- a/core/src/main/java/org/apache/calcite/rel/core/Window.java
+++ b/core/src/main/java/org/apache/calcite/rel/core/Window.java
@@ -35,13 +35,13 @@ import org.apache.calcite.rex.RexNode;
 import org.apache.calcite.rex.RexSlot;
 import org.apache.calcite.rex.RexWindowBound;
 import org.apache.calcite.sql.SqlAggFunction;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.ImmutableIntList;
 import org.apache.calcite.util.Util;
 
 import com.google.common.collect.ImmutableList;
 
 import java.util.AbstractList;
-import java.util.BitSet;
 import java.util.List;
 
 /**
@@ -190,7 +190,7 @@ public abstract class Window extends SingleRel {
    * </ul>
    */
   public static class Group {
-    public final BitSet keys;
+    public final ImmutableBitSet keys;
     public final boolean isRows;
     public final RexWindowBound lowerBound;
     public final RexWindowBound upperBound;
@@ -205,7 +205,7 @@ public abstract class Window extends SingleRel {
     public final ImmutableList<RexWinAggCall> aggCalls;
 
     public Group(
-        BitSet keys,
+        ImmutableBitSet keys,
         boolean isRows,
         RexWindowBound lowerBound,
         RexWindowBound upperBound,

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/externalize/RelJson.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/externalize/RelJson.java b/core/src/main/java/org/apache/calcite/rel/externalize/RelJson.java
index 4c77805..ff6c570 100644
--- a/core/src/main/java/org/apache/calcite/rel/externalize/RelJson.java
+++ b/core/src/main/java/org/apache/calcite/rel/externalize/RelJson.java
@@ -39,7 +39,7 @@ import org.apache.calcite.sql.SqlFunction;
 import org.apache.calcite.sql.SqlOperator;
 import org.apache.calcite.sql.fun.SqlStdOperatorTable;
 import org.apache.calcite.sql.type.SqlTypeName;
-import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.JsonBuilder;
 import org.apache.calcite.util.Util;
 
@@ -49,7 +49,6 @@ import java.lang.reflect.Constructor;
 import java.lang.reflect.InvocationTargetException;
 import java.math.BigDecimal;
 import java.util.ArrayList;
-import java.util.BitSet;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
@@ -211,7 +210,7 @@ public class RelJson {
 
   public Object toJson(AggregateCall node) {
     final Map<String, Object> map = jsonBuilder.map();
-    map.put("agg", toJson((SqlOperator) node.getAggregation()));
+    map.put("agg", toJson(node.getAggregation()));
     map.put("type", toJson(node.getType()));
     map.put("distinct", node.isDistinct());
     map.put("operands", node.getArgList());
@@ -234,9 +233,9 @@ public class RelJson {
         list.add(toJson(o));
       }
       return list;
-    } else if (value instanceof BitSet) {
+    } else if (value instanceof ImmutableBitSet) {
       final List<Object> list = jsonBuilder.list();
-      for (Integer integer : BitSets.toIter((BitSet) value)) {
+      for (Integer integer : (ImmutableBitSet) value) {
         list.add(toJson(integer));
       }
       return list;

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/externalize/RelJsonReader.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/externalize/RelJsonReader.java b/core/src/main/java/org/apache/calcite/rel/externalize/RelJsonReader.java
index 8e20b7f..31dbdac 100644
--- a/core/src/main/java/org/apache/calcite/rel/externalize/RelJsonReader.java
+++ b/core/src/main/java/org/apache/calcite/rel/externalize/RelJsonReader.java
@@ -30,7 +30,7 @@ import org.apache.calcite.rex.RexLiteral;
 import org.apache.calcite.rex.RexNode;
 import org.apache.calcite.schema.Schema;
 import org.apache.calcite.sql.SqlAggFunction;
-import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.Pair;
 import org.apache.calcite.util.Util;
 
@@ -44,7 +44,6 @@ import java.lang.reflect.Constructor;
 import java.lang.reflect.InvocationTargetException;
 import java.util.AbstractList;
 import java.util.ArrayList;
-import java.util.BitSet;
 import java.util.LinkedHashMap;
 import java.util.List;
 import java.util.Map;
@@ -131,8 +130,8 @@ public class RelJsonReader {
         return relJson.toRex(this, jsonRel.get(tag));
       }
 
-      public BitSet getBitSet(String tag) {
-        return BitSets.of(getIntegerList(tag));
+      public ImmutableBitSet getBitSet(String tag) {
+        return ImmutableBitSet.of(getIntegerList(tag));
       }
 
       public List<Integer> getIntegerList(String tag) {

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/logical/LogicalAggregate.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/logical/LogicalAggregate.java b/core/src/main/java/org/apache/calcite/rel/logical/LogicalAggregate.java
index 198f242..5f1d579 100644
--- a/core/src/main/java/org/apache/calcite/rel/logical/LogicalAggregate.java
+++ b/core/src/main/java/org/apache/calcite/rel/logical/LogicalAggregate.java
@@ -24,8 +24,8 @@ import org.apache.calcite.rel.RelNode;
 import org.apache.calcite.rel.RelShuttle;
 import org.apache.calcite.rel.core.Aggregate;
 import org.apache.calcite.rel.core.AggregateCall;
+import org.apache.calcite.util.ImmutableBitSet;
 
-import java.util.BitSet;
 import java.util.List;
 
 /**
@@ -54,7 +54,7 @@ public final class LogicalAggregate extends Aggregate {
   public LogicalAggregate(
       RelOptCluster cluster,
       RelNode child,
-      BitSet groupSet,
+      ImmutableBitSet groupSet,
       List<AggregateCall> aggCalls) {
     super(
         cluster,
@@ -74,7 +74,7 @@ public final class LogicalAggregate extends Aggregate {
   //~ Methods ----------------------------------------------------------------
 
   @Override public LogicalAggregate copy(RelTraitSet traitSet, RelNode input,
-      BitSet groupSet, List<AggregateCall> aggCalls) {
+      ImmutableBitSet groupSet, List<AggregateCall> aggCalls) {
     assert traitSet.containsIfApplicable(Convention.NONE);
     return new LogicalAggregate(getCluster(), input, groupSet, aggCalls);
   }

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/logical/LogicalWindow.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/logical/LogicalWindow.java b/core/src/main/java/org/apache/calcite/rel/logical/LogicalWindow.java
index e75d340..4534d56 100644
--- a/core/src/main/java/org/apache/calcite/rel/logical/LogicalWindow.java
+++ b/core/src/main/java/org/apache/calcite/rel/logical/LogicalWindow.java
@@ -34,7 +34,7 @@ import org.apache.calcite.rex.RexProgram;
 import org.apache.calcite.rex.RexShuttle;
 import org.apache.calcite.rex.RexWindow;
 import org.apache.calcite.rex.RexWindowBound;
-import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.Pair;
 
 import com.google.common.base.Objects;
@@ -46,7 +46,6 @@ import com.google.common.collect.Multimap;
 
 import java.util.AbstractList;
 import java.util.ArrayList;
-import java.util.BitSet;
 import java.util.Collection;
 import java.util.HashMap;
 import java.util.List;
@@ -275,14 +274,14 @@ public final class LogicalWindow extends Window {
    * (regardless of how it is specified, in terms of a named window or specified
    * attribute by attribute) will end up with the same window key. */
   private static class WindowKey {
-    private final BitSet groupSet;
+    private final ImmutableBitSet groupSet;
     private final RelCollation orderKeys;
     private final boolean isRows;
     private final RexWindowBound lowerBound;
     private final RexWindowBound upperBound;
 
     public WindowKey(
-        BitSet groupSet,
+        ImmutableBitSet groupSet,
         RelCollation orderKeys,
         boolean isRows,
         RexWindowBound lowerBound,
@@ -329,13 +328,14 @@ public final class LogicalWindow extends Window {
               return rexFieldCollation.left instanceof RexLocalRef;
             }
           })));
-    BitSet groupSet =
-        BitSets.of(getProjectOrdinals(aggWindow.partitionKeys));
+    ImmutableBitSet groupSet =
+        ImmutableBitSet.of(getProjectOrdinals(aggWindow.partitionKeys));
     final int groupLength = groupSet.length();
     if (inputFieldCount < groupLength) {
       // If PARTITION BY references constant, we can ignore such partition key.
       // All the inputs after inputFieldCount are literals, thus we can clear.
-      groupSet.clear(inputFieldCount, groupLength);
+      groupSet =
+          groupSet.except(ImmutableBitSet.range(inputFieldCount, groupLength));
     }
 
     WindowKey windowKey =

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/metadata/BuiltInMetadata.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/metadata/BuiltInMetadata.java b/core/src/main/java/org/apache/calcite/rel/metadata/BuiltInMetadata.java
index 4d890b6..5aa668f 100644
--- a/core/src/main/java/org/apache/calcite/rel/metadata/BuiltInMetadata.java
+++ b/core/src/main/java/org/apache/calcite/rel/metadata/BuiltInMetadata.java
@@ -21,8 +21,8 @@ import org.apache.calcite.plan.RelOptPredicateList;
 import org.apache.calcite.rel.RelNode;
 import org.apache.calcite.rex.RexNode;
 import org.apache.calcite.sql.SqlExplainLevel;
+import org.apache.calcite.util.ImmutableBitSet;
 
-import java.util.BitSet;
 import java.util.Set;
 
 /**
@@ -49,8 +49,8 @@ public abstract class BuiltInMetadata {
   public interface UniqueKeys extends Metadata {
     /**
      * Determines the set of unique minimal keys for this expression. A key is
-     * represented as a {@link BitSet}, where each bit position represents a
-     * 0-based output column ordinal.
+     * represented as an {@link org.apache.calcite.util.ImmutableBitSet}, where
+     * each bit position represents a 0-based output column ordinal.
      *
      * <p>Note that {@link RelNode#isDistinct} should return {@code true} if and
      * only if at least one key is known.</p>
@@ -63,7 +63,7 @@ public abstract class BuiltInMetadata {
      * @return set of keys, or null if this information cannot be determined
      * (whereas empty set indicates definitely no keys at all)
      */
-    Set<BitSet> getUniqueKeys(boolean ignoreNulls);
+    Set<ImmutableBitSet> getUniqueKeys(boolean ignoreNulls);
   }
 
   /** Metadata about whether a set of columns uniquely identifies a row. */
@@ -82,7 +82,7 @@ public abstract class BuiltInMetadata {
      * @return whether the columns are unique, or
      * null if not enough information is available to make that determination
      */
-    Boolean areColumnsUnique(BitSet columns, boolean ignoreNulls);
+    Boolean areColumnsUnique(ImmutableBitSet columns, boolean ignoreNulls);
   }
 
   /** Metadata about the number of rows returned by a relational expression. */
@@ -114,7 +114,7 @@ public abstract class BuiltInMetadata {
      * @return distinct row count for groupKey, filtered by predicate, or null
      * if no reliable estimate can be determined
      */
-    Double getDistinctRowCount(BitSet groupKey, RexNode predicate);
+    Double getDistinctRowCount(ImmutableBitSet groupKey, RexNode predicate);
   }
 
   /** Metadata about the proportion of original rows that remain in a relational
@@ -145,7 +145,7 @@ public abstract class BuiltInMetadata {
      * @return distinct row count for the given groupKey, or null if no reliable
      * estimate can be determined
      */
-    Double getPopulationSize(BitSet groupKey);
+    Double getPopulationSize(ImmutableBitSet groupKey);
   }
 
   /** Metadata about the origins of columns. */

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/metadata/RelMdColumnUniqueness.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdColumnUniqueness.java b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdColumnUniqueness.java
index 262d9e5..bede712 100644
--- a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdColumnUniqueness.java
+++ b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdColumnUniqueness.java
@@ -31,10 +31,9 @@ import org.apache.calcite.rex.RexCall;
 import org.apache.calcite.rex.RexInputRef;
 import org.apache.calcite.rex.RexNode;
 import org.apache.calcite.sql.fun.SqlStdOperatorTable;
-import org.apache.calcite.util.BitSets;
 import org.apache.calcite.util.BuiltInMethod;
+import org.apache.calcite.util.ImmutableBitSet;
 
-import java.util.BitSet;
 import java.util.List;
 
 /**
@@ -54,7 +53,7 @@ public class RelMdColumnUniqueness {
 
   public Boolean areColumnsUnique(
       Filter rel,
-      BitSet columns,
+      ImmutableBitSet columns,
       boolean ignoreNulls) {
     return RelMetadataQuery.areColumnsUnique(
         rel.getInput(),
@@ -64,7 +63,7 @@ public class RelMdColumnUniqueness {
 
   public Boolean areColumnsUnique(
       Sort rel,
-      BitSet columns,
+      ImmutableBitSet columns,
       boolean ignoreNulls) {
     return RelMetadataQuery.areColumnsUnique(
         rel.getInput(),
@@ -74,7 +73,7 @@ public class RelMdColumnUniqueness {
 
   public Boolean areColumnsUnique(
       Correlator rel,
-      BitSet columns,
+      ImmutableBitSet columns,
       boolean ignoreNulls) {
     return RelMetadataQuery.areColumnsUnique(
         rel.getLeft(),
@@ -84,7 +83,7 @@ public class RelMdColumnUniqueness {
 
   public Boolean areColumnsUnique(
       Project rel,
-      BitSet columns,
+      ImmutableBitSet columns,
       boolean ignoreNulls) {
     // LogicalProject maps a set of rows to a different set;
     // Without knowledge of the mapping function(whether it
@@ -95,8 +94,8 @@ public class RelMdColumnUniqueness {
     // references
 
     List<RexNode> projExprs = rel.getProjects();
-    BitSet childColumns = new BitSet();
-    for (int bit : BitSets.toIter(columns)) {
+    ImmutableBitSet.Builder childColumns = ImmutableBitSet.builder();
+    for (int bit : columns) {
       RexNode projExpr = projExprs.get(bit);
       if (projExpr instanceof RexInputRef) {
         childColumns.set(((RexInputRef) projExpr).getIndex());
@@ -139,14 +138,14 @@ public class RelMdColumnUniqueness {
 
     return RelMetadataQuery.areColumnsUnique(
         rel.getInput(),
-        childColumns,
+        childColumns.build(),
         ignoreNulls);
   }
 
   public Boolean areColumnsUnique(
       Join rel,
-      BitSet columns, boolean
-      ignoreNulls) {
+      ImmutableBitSet columns,
+      boolean ignoreNulls) {
     if (columns.cardinality() == 0) {
       return false;
     }
@@ -156,10 +155,10 @@ public class RelMdColumnUniqueness {
 
     // Divide up the input column mask into column masks for the left and
     // right sides of the join
-    BitSet leftColumns = new BitSet();
-    BitSet rightColumns = new BitSet();
+    ImmutableBitSet.Builder leftColumns = ImmutableBitSet.builder();
+    ImmutableBitSet.Builder rightColumns = ImmutableBitSet.builder();
     int nLeftColumns = left.getRowType().getFieldCount();
-    for (int bit : BitSets.toIter(columns)) {
+    for (int bit : columns) {
       if (bit < nLeftColumns) {
         leftColumns.set(bit);
       } else {
@@ -171,9 +170,11 @@ public class RelMdColumnUniqueness {
     // right hand side, then the columns are unique if and only if they're
     // unique for their respective join inputs
     Boolean leftUnique =
-        RelMetadataQuery.areColumnsUnique(left, leftColumns, ignoreNulls);
+        RelMetadataQuery.areColumnsUnique(left, leftColumns.build(),
+            ignoreNulls);
     Boolean rightUnique =
-        RelMetadataQuery.areColumnsUnique(right, rightColumns, ignoreNulls);
+        RelMetadataQuery.areColumnsUnique(right, rightColumns.build(),
+            ignoreNulls);
     if ((leftColumns.cardinality() > 0)
         && (rightColumns.cardinality() > 0)) {
       if ((leftUnique == null) || (rightUnique == null)) {
@@ -219,7 +220,7 @@ public class RelMdColumnUniqueness {
 
   public Boolean areColumnsUnique(
       SemiJoin rel,
-      BitSet columns,
+      ImmutableBitSet columns,
       boolean ignoreNulls) {
     // only return the unique keys from the LHS since a semijoin only
     // returns the LHS
@@ -231,15 +232,12 @@ public class RelMdColumnUniqueness {
 
   public Boolean areColumnsUnique(
       Aggregate rel,
-      BitSet columns,
+      ImmutableBitSet columns,
       boolean ignoreNulls) {
     // group by keys form a unique key
     if (rel.getGroupCount() > 0) {
-      BitSet groupKey = new BitSet();
-      for (int i = 0; i < rel.getGroupCount(); i++) {
-        groupKey.set(i);
-      }
-      return BitSets.contains(columns, groupKey);
+      ImmutableBitSet groupKey = ImmutableBitSet.range(rel.getGroupCount());
+      return columns.contains(groupKey);
     } else {
       // interpret an empty set as asking whether the aggregation is full
       // table (in which case it returns at most one row);
@@ -253,7 +251,7 @@ public class RelMdColumnUniqueness {
   // Catch-all rule when none of the others apply.
   public Boolean areColumnsUnique(
       RelNode rel,
-      BitSet columns,
+      ImmutableBitSet columns,
       boolean ignoreNulls) {
     // no information available
     return null;

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/metadata/RelMdDistinctRowCount.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdDistinctRowCount.java b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdDistinctRowCount.java
index e4d847d..2092379 100644
--- a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdDistinctRowCount.java
+++ b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdDistinctRowCount.java
@@ -30,12 +30,11 @@ import org.apache.calcite.rex.RexBuilder;
 import org.apache.calcite.rex.RexNode;
 import org.apache.calcite.rex.RexUtil;
 import org.apache.calcite.sql.fun.SqlStdOperatorTable;
-import org.apache.calcite.util.BitSets;
 import org.apache.calcite.util.BuiltInMethod;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.NumberUtil;
 
 import java.util.ArrayList;
-import java.util.BitSet;
 import java.util.List;
 
 /**
@@ -56,7 +55,7 @@ public class RelMdDistinctRowCount {
 
   public Double getDistinctRowCount(
       Union rel,
-      BitSet groupKey,
+      ImmutableBitSet groupKey,
       RexNode predicate) {
     Double rowCount = 0.0;
     int[] adjustments = new int[rel.getRowType().getFieldCount()];
@@ -90,7 +89,7 @@ public class RelMdDistinctRowCount {
 
   public Double getDistinctRowCount(
       Sort rel,
-      BitSet groupKey,
+      ImmutableBitSet groupKey,
       RexNode predicate) {
     return RelMetadataQuery.getDistinctRowCount(
         rel.getInput(),
@@ -100,7 +99,7 @@ public class RelMdDistinctRowCount {
 
   public Double getDistinctRowCount(
       Filter rel,
-      BitSet groupKey,
+      ImmutableBitSet groupKey,
       RexNode predicate) {
     // REVIEW zfong 4/18/06 - In the Broadbase code, duplicates are not
     // removed from the two filter lists.  However, the code below is
@@ -119,7 +118,7 @@ public class RelMdDistinctRowCount {
 
   public Double getDistinctRowCount(
       Join rel,
-      BitSet groupKey,
+      ImmutableBitSet groupKey,
       RexNode predicate) {
     return RelMdUtil.getJoinDistinctRowCount(
         rel,
@@ -131,7 +130,7 @@ public class RelMdDistinctRowCount {
 
   public Double getDistinctRowCount(
       SemiJoin rel,
-      BitSet groupKey,
+      ImmutableBitSet groupKey,
       RexNode predicate) {
     // create a RexNode representing the selectivity of the
     // semijoin filter and pass it to getDistinctRowCount
@@ -153,7 +152,7 @@ public class RelMdDistinctRowCount {
 
   public Double getDistinctRowCount(
       Aggregate rel,
-      BitSet groupKey,
+      ImmutableBitSet groupKey,
       RexNode predicate) {
     // determine which predicates can be applied on the child of the
     // aggregate
@@ -169,13 +168,13 @@ public class RelMdDistinctRowCount {
         RexUtil.composeConjunction(rexBuilder, pushable, true);
 
     // set the bits as they correspond to the child input
-    BitSet childKey = new BitSet();
+    ImmutableBitSet.Builder childKey = ImmutableBitSet.builder();
     RelMdUtil.setAggChildKeys(groupKey, rel, childKey);
 
     Double distinctRowCount =
         RelMetadataQuery.getDistinctRowCount(
             rel.getInput(),
-            childKey,
+            childKey.build(),
             childPreds);
     if (distinctRowCount == null) {
       return null;
@@ -190,7 +189,7 @@ public class RelMdDistinctRowCount {
 
   public Double getDistinctRowCount(
       Values rel,
-      BitSet groupKey,
+      ImmutableBitSet groupKey,
       RexNode predicate) {
     Double selectivity = RelMdUtil.guessSelectivity(predicate);
 
@@ -201,17 +200,17 @@ public class RelMdDistinctRowCount {
 
   public Double getDistinctRowCount(
       Project rel,
-      BitSet groupKey,
+      ImmutableBitSet groupKey,
       RexNode predicate) {
-    BitSet baseCols = new BitSet();
-    BitSet projCols = new BitSet();
+    ImmutableBitSet.Builder baseCols = ImmutableBitSet.builder();
+    ImmutableBitSet.Builder projCols = ImmutableBitSet.builder();
     List<RexNode> projExprs = rel.getProjects();
     RelMdUtil.splitCols(projExprs, groupKey, baseCols, projCols);
 
     List<RexNode> notPushable = new ArrayList<RexNode>();
     List<RexNode> pushable = new ArrayList<RexNode>();
     RelOptUtil.splitFilters(
-        BitSets.range(rel.getRowType().getFieldCount()),
+        ImmutableBitSet.range(rel.getRowType().getFieldCount()),
         predicate,
         pushable,
         notPushable);
@@ -231,7 +230,7 @@ public class RelMdDistinctRowCount {
     Double distinctRowCount =
         RelMetadataQuery.getDistinctRowCount(
             rel.getInput(),
-            baseCols,
+            baseCols.build(),
             modifiedPred);
 
     if (distinctRowCount == null) {
@@ -249,7 +248,7 @@ public class RelMdDistinctRowCount {
     }
 
     // multiply by the cardinality of the non-child projection expressions
-    for (int bit : BitSets.toIter(projCols)) {
+    for (int bit : projCols.build()) {
       Double subRowCount =
           RelMdUtil.cardOfProjExpr(rel, projExprs.get(bit));
       if (subRowCount == null) {
@@ -266,7 +265,7 @@ public class RelMdDistinctRowCount {
   // Catch-all rule when none of the others apply.
   public Double getDistinctRowCount(
       RelNode rel,
-      BitSet groupKey,
+      ImmutableBitSet groupKey,
       RexNode predicate) {
     // REVIEW zfong 4/19/06 - Broadbase code does not take into
     // consideration selectivity of predicates passed in.  Also, they


Mime
View raw message