calcite-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jh...@apache.org
Subject [53/58] [abbrv] incubator-calcite git commit: [CALCITE-460] Add ImmutableBitSet and replace uses of BitSet
Date Fri, 14 Nov 2014 21:33:01 GMT
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/rules/MultiJoin.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/rules/MultiJoin.java b/core/src/main/java/org/apache/calcite/rel/rules/MultiJoin.java
index cd70844..ce651bc 100644
--- a/core/src/main/java/org/apache/calcite/rel/rules/MultiJoin.java
+++ b/core/src/main/java/org/apache/calcite/rel/rules/MultiJoin.java
@@ -26,6 +26,7 @@ import org.apache.calcite.rel.RelWriter;
 import org.apache.calcite.rel.core.JoinRelType;
 import org.apache.calcite.rel.type.RelDataType;
 import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.ImmutableIntList;
 import org.apache.calcite.util.ImmutableNullableList;
 
@@ -34,7 +35,6 @@ import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Lists;
 
 import java.util.ArrayList;
-import java.util.BitSet;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
@@ -52,7 +52,7 @@ public final class MultiJoin extends AbstractRelNode {
   private final boolean isFullOuterJoin;
   private final List<RexNode> outerJoinConditions;
   private final ImmutableList<JoinRelType> joinTypes;
-  private final List<BitSet> projFields;
+  private final List<ImmutableBitSet> projFields;
   public final ImmutableMap<Integer, ImmutableIntList> joinFieldRefCountsMap;
   private final RexNode postJoinFilter;
 
@@ -91,7 +91,7 @@ public final class MultiJoin extends AbstractRelNode {
       boolean isFullOuterJoin,
       List<RexNode> outerJoinConditions,
       List<JoinRelType> joinTypes,
-      List<BitSet> projFields,
+      List<ImmutableBitSet> projFields,
       ImmutableMap<Integer, ImmutableIntList> joinFieldRefCountsMap,
       RexNode postJoinFilter) {
     super(cluster, cluster.traitSetOf(Convention.NONE));
@@ -214,7 +214,7 @@ public final class MultiJoin extends AbstractRelNode {
    * @return bitmaps representing the fields projected from each input; if an
    * entry is null, all fields are projected
    */
-  public List<BitSet> getProjFields() {
+  public List<ImmutableBitSet> getProjFields() {
     return projFields;
   }
 

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/rules/MultiJoinOptimizeBushyRule.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/rules/MultiJoinOptimizeBushyRule.java b/core/src/main/java/org/apache/calcite/rel/rules/MultiJoinOptimizeBushyRule.java
index 62eef89..2e6667c 100644
--- a/core/src/main/java/org/apache/calcite/rel/rules/MultiJoinOptimizeBushyRule.java
+++ b/core/src/main/java/org/apache/calcite/rel/rules/MultiJoinOptimizeBushyRule.java
@@ -30,7 +30,7 @@ import org.apache.calcite.rex.RexNode;
 import org.apache.calcite.rex.RexPermuteInputsShuttle;
 import org.apache.calcite.rex.RexUtil;
 import org.apache.calcite.rex.RexVisitor;
-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.mapping.Mappings;
@@ -41,7 +41,6 @@ import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Lists;
 
 import java.io.PrintWriter;
-import java.util.BitSet;
 import java.util.Comparator;
 import java.util.Iterator;
 import java.util.List;
@@ -132,8 +131,7 @@ public class MultiJoinOptimizeBushyRule extends RelOptRule {
       if (edgeOrdinal == -1) {
         // No more edges. Are there any un-joined vertexes?
         final Vertex lastVertex = Util.last(vertexes);
-        final int z =
-            BitSets.previousClearBit(lastVertex.factors, lastVertex.id - 1);
+        final int z = lastVertex.factors.previousClearBit(lastVertex.id - 1);
         if (z < 0) {
           break;
         }
@@ -147,7 +145,7 @@ public class MultiJoinOptimizeBushyRule extends RelOptRule {
         // Therefore, for now, the factors that are merged are exactly the
         // factors on this edge.
         assert bestEdge.factors.cardinality() == 2;
-        factors = BitSets.toArray(bestEdge.factors);
+        factors = bestEdge.factors.toArray();
       }
 
       // Determine which factor is to be on the LHS of the join.
@@ -165,26 +163,29 @@ public class MultiJoinOptimizeBushyRule extends RelOptRule {
 
       // Find the join conditions. All conditions whose factors are now all in
       // the join can now be used.
-      final BitSet newFactors =
-          BitSets.union(majorVertex.factors, minorVertex.factors);
+      final int v = vertexes.size();
+      final ImmutableBitSet newFactors =
+          ImmutableBitSet.builder(majorVertex.factors)
+              .addAll(minorVertex.factors)
+              .set(v)
+              .build();
+
       final List<RexNode> conditions = Lists.newArrayList();
       final Iterator<LoptMultiJoin.Edge> edgeIterator = unusedEdges.iterator();
       while (edgeIterator.hasNext()) {
         LoptMultiJoin.Edge edge = edgeIterator.next();
-        if (BitSets.contains(newFactors, edge.factors)) {
+        if (newFactors.contains(edge.factors)) {
           conditions.add(edge.condition);
           edgeIterator.remove();
           usedEdges.add(edge);
         }
       }
 
-      final int v = vertexes.size();
       double cost =
           majorVertex.cost
           * minorVertex.cost
           * RelMdUtil.guessSelectivity(
               RexUtil.composeConjunction(rexBuilder, conditions, false));
-      newFactors.set(v);
       final Vertex newVertex =
           new JoinVertex(v, majorFactor, minorFactor, newFactors,
               cost, ImmutableList.copyOf(conditions));
@@ -197,13 +198,16 @@ public class MultiJoinOptimizeBushyRule extends RelOptRule {
       // This vertex has fewer rows (1k rows) -- a fact that is critical to
       // decisions made later. (Hence "greedy" algorithm not "simple".)
       // The adjacent edges are modified.
-      final BitSet merged = BitSets.of(minorFactor, majorFactor);
+      final ImmutableBitSet merged =
+          ImmutableBitSet.of(minorFactor, majorFactor);
       for (int i = 0; i < unusedEdges.size(); i++) {
         final LoptMultiJoin.Edge edge = unusedEdges.get(i);
         if (edge.factors.intersects(merged)) {
-          BitSet newEdgeFactors = (BitSet) edge.factors.clone();
-          newEdgeFactors.andNot(newFactors);
-          newEdgeFactors.set(v);
+          ImmutableBitSet newEdgeFactors =
+              ImmutableBitSet.builder(edge.factors)
+              .removeAll(newFactors)
+              .set(v)
+              .build();
           assert newEdgeFactors.cardinality() == 2;
           final LoptMultiJoin.Edge newEdge =
               new LoptMultiJoin.Edge(edge.condition, newEdgeFactors,
@@ -251,7 +255,7 @@ public class MultiJoinOptimizeBushyRule extends RelOptRule {
             RexUtil.composeConjunction(rexBuilder, joinVertex.conditions,
                 false);
         relNodes.add(
-            Pair.of((RelNode)
+            Pair.of(
                 joinFactory.createJoin(left, right, condition.accept(shuttle),
                     JoinRelType.INNER, ImmutableSet.<String>of(), false),
                 mapping));
@@ -321,10 +325,10 @@ public class MultiJoinOptimizeBushyRule extends RelOptRule {
   abstract static class Vertex {
     final int id;
 
-    protected final BitSet factors;
+    protected final ImmutableBitSet factors;
     final double cost;
 
-    Vertex(int id, BitSet factors, double cost) {
+    Vertex(int id, ImmutableBitSet factors, double cost) {
       this.id = id;
       this.factors = factors;
       this.cost = cost;
@@ -337,7 +341,7 @@ public class MultiJoinOptimizeBushyRule extends RelOptRule {
     final int fieldOffset;
 
     LeafVertex(int id, RelNode rel, double cost, int fieldOffset) {
-      super(id, BitSets.of(id), cost);
+      super(id, ImmutableBitSet.of(id), cost);
       this.rel = rel;
       this.fieldOffset = fieldOffset;
     }
@@ -359,8 +363,8 @@ public class MultiJoinOptimizeBushyRule extends RelOptRule {
      * columns (not in terms of the outputs of left and right input factors). */
     final ImmutableList<RexNode> conditions;
 
-    JoinVertex(int id, int leftFactor, int rightFactor,
-        BitSet factors, double cost, ImmutableList<RexNode> conditions) {
+    JoinVertex(int id, int leftFactor, int rightFactor, ImmutableBitSet factors,
+        double cost, ImmutableList<RexNode> conditions) {
       super(id, factors, cost);
       this.leftFactor = leftFactor;
       this.rightFactor = rightFactor;

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/rules/PushProjector.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/rules/PushProjector.java b/core/src/main/java/org/apache/calcite/rel/rules/PushProjector.java
index d317237..cfaf740 100644
--- a/core/src/main/java/org/apache/calcite/rel/rules/PushProjector.java
+++ b/core/src/main/java/org/apache/calcite/rel/rules/PushProjector.java
@@ -31,6 +31,7 @@ import org.apache.calcite.rex.RexUtil;
 import org.apache.calcite.rex.RexVisitorImpl;
 import org.apache.calcite.sql.SqlOperator;
 import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.Pair;
 
 import com.google.common.collect.ImmutableList;
@@ -88,14 +89,14 @@ public class PushProjector {
    * pushed past, if the RelNode is not a join. If the RelNode is a join, then
    * the fields correspond to the left hand side of the join.
    */
-  final BitSet childBitmap;
+  final ImmutableBitSet childBitmap;
 
   /**
    * Bitmap containing the fields in the right hand side of a join, in the
    * case where the projection is being pushed past a join. Not used
    * otherwise.
    */
-  final BitSet rightBitmap;
+  final ImmutableBitSet rightBitmap;
 
   /**
    * Number of fields in the RelNode that the projection is being pushed past,
@@ -215,13 +216,13 @@ public class PushProjector {
       nFieldsRight = rightFields.size();
       nSysFields = joinRel.getSystemFieldList().size();
       childBitmap =
-          BitSets.range(nSysFields, nFields + nSysFields);
+          ImmutableBitSet.range(nSysFields, nFields + nSysFields);
       rightBitmap =
-          BitSets.range(nFields + nSysFields, nChildFields);
+          ImmutableBitSet.range(nFields + nSysFields, nChildFields);
     } else {
       nFields = nChildFields;
       nFieldsRight = 0;
-      childBitmap = BitSets.range(nChildFields);
+      childBitmap = ImmutableBitSet.range(nChildFields);
       rightBitmap = null;
       nSysFields = 0;
     }
@@ -574,16 +575,16 @@ public class PushProjector {
    */
   private class InputSpecialOpFinder extends RexVisitorImpl<Void> {
     private final BitSet rexRefs;
-    private final BitSet leftFields;
-    private final BitSet rightFields;
+    private final ImmutableBitSet leftFields;
+    private final ImmutableBitSet rightFields;
     private final ExprCondition preserveExprCondition;
     private final List<RexNode> preserveLeft;
     private final List<RexNode> preserveRight;
 
     public InputSpecialOpFinder(
         BitSet rexRefs,
-        BitSet leftFields,
-        BitSet rightFields,
+        ImmutableBitSet leftFields,
+        ImmutableBitSet rightFields,
         ExprCondition preserveExprCondition,
         List<RexNode> preserveLeft,
         List<RexNode> preserveRight) {
@@ -609,12 +610,12 @@ public class PushProjector {
         // if the arguments of the expression only reference the
         // left hand side, preserve it on the left; similarly, if
         // it only references expressions on the right
-        final BitSet exprArgs = RelOptUtil.InputFinder.bits(call);
+        final ImmutableBitSet exprArgs = RelOptUtil.InputFinder.bits(call);
         if (exprArgs.cardinality() > 0) {
-          if (BitSets.contains(leftFields, exprArgs)) {
+          if (leftFields.contains(exprArgs)) {
             addExpr(preserveLeft, call);
             return true;
-          } else if (BitSets.contains(rightFields, exprArgs)) {
+          } else if (rightFields.contains(exprArgs)) {
             assert preserveRight != null;
             addExpr(preserveRight, call);
             return true;

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/rel/rules/SemiJoinRule.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/rules/SemiJoinRule.java b/core/src/main/java/org/apache/calcite/rel/rules/SemiJoinRule.java
index bedea88..28d9454 100644
--- a/core/src/main/java/org/apache/calcite/rel/rules/SemiJoinRule.java
+++ b/core/src/main/java/org/apache/calcite/rel/rules/SemiJoinRule.java
@@ -26,13 +26,12 @@ import org.apache.calcite.rel.core.Join;
 import org.apache.calcite.rel.core.JoinInfo;
 import org.apache.calcite.rel.core.Project;
 import org.apache.calcite.rel.core.SemiJoin;
-import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.ImmutableIntList;
 import org.apache.calcite.util.IntList;
 
 import com.google.common.collect.Lists;
 
-import java.util.BitSet;
 import java.util.List;
 
 /**
@@ -56,21 +55,23 @@ public class SemiJoinRule extends RelOptRule {
     final Join join = call.rel(1);
     final RelNode left = call.rel(2);
     final Aggregate aggregate = call.rel(3);
-    final BitSet bits = RelOptUtil.InputFinder.bits(project.getProjects(),
-        null);
-    final BitSet rightBits = BitSets.range(left.getRowType().getFieldCount(),
-        join.getRowType().getFieldCount());
+    final ImmutableBitSet bits =
+        RelOptUtil.InputFinder.bits(project.getProjects(), null);
+    final ImmutableBitSet rightBits =
+        ImmutableBitSet.range(left.getRowType().getFieldCount(),
+            join.getRowType().getFieldCount());
     if (bits.intersects(rightBits)) {
       return;
     }
     final JoinInfo joinInfo = join.analyzeCondition();
-    if (!joinInfo.rightSet().equals(BitSets.range(aggregate.getGroupCount()))) {
+    if (!joinInfo.rightSet().equals(
+        ImmutableBitSet.range(aggregate.getGroupCount()))) {
       // Rule requires that aggregate key to be the same as the join key.
       // By the way, neither a super-set nor a sub-set would work.
       return;
     }
     final List<Integer> newRightKeys = Lists.newArrayList();
-    final IntList aggregateKeys = BitSets.toList(aggregate.getGroupSet());
+    final IntList aggregateKeys = aggregate.getGroupSet().toList();
     for (int key : joinInfo.rightKeys) {
       newRightKeys.add(aggregateKeys.get(key));
     }

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/schema/Statistic.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/schema/Statistic.java b/core/src/main/java/org/apache/calcite/schema/Statistic.java
index fa907da..b725d4b 100644
--- a/core/src/main/java/org/apache/calcite/schema/Statistic.java
+++ b/core/src/main/java/org/apache/calcite/schema/Statistic.java
@@ -16,7 +16,7 @@
  */
 package org.apache.calcite.schema;
 
-import java.util.BitSet;
+import org.apache.calcite.util.ImmutableBitSet;
 
 /**
  * Statistics about a {@link Table}.
@@ -32,7 +32,7 @@ public interface Statistic {
   /** Returns whether the given set of columns is a unique key, or a superset
    * of a unique key, of the table.
    */
-  boolean isKey(BitSet columns);
+  boolean isKey(ImmutableBitSet columns);
 }
 
 // End Statistic.java

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/schema/Statistics.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/schema/Statistics.java b/core/src/main/java/org/apache/calcite/schema/Statistics.java
index 9712e7c..4b2611a 100644
--- a/core/src/main/java/org/apache/calcite/schema/Statistics.java
+++ b/core/src/main/java/org/apache/calcite/schema/Statistics.java
@@ -16,9 +16,8 @@
  */
 package org.apache.calcite.schema;
 
-import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
 
-import java.util.BitSet;
 import java.util.List;
 
 /**
@@ -35,21 +34,22 @@ public class Statistics {
           return null;
         }
 
-        public boolean isKey(BitSet columns) {
+        public boolean isKey(ImmutableBitSet columns) {
           return false;
         }
       };
 
   /** Returns a statistic with a given row count and set of unique keys. */
-  public static Statistic of(final double rowCount, final List<BitSet> keys) {
+  public static Statistic of(final double rowCount,
+      final List<ImmutableBitSet> keys) {
     return new Statistic() {
       public Double getRowCount() {
         return rowCount;
       }
 
-      public boolean isKey(BitSet columns) {
-        for (BitSet key : keys) {
-          if (BitSets.contains(columns, key)) {
+      public boolean isKey(ImmutableBitSet columns) {
+        for (ImmutableBitSet key : keys) {
+          if (columns.contains(key)) {
             return true;
           }
         }

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/sql2rel/RelDecorrelator.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/sql2rel/RelDecorrelator.java b/core/src/main/java/org/apache/calcite/sql2rel/RelDecorrelator.java
index 4da6445..6da2268 100644
--- a/core/src/main/java/org/apache/calcite/sql2rel/RelDecorrelator.java
+++ b/core/src/main/java/org/apache/calcite/sql2rel/RelDecorrelator.java
@@ -64,9 +64,9 @@ import org.apache.calcite.sql.SqlOperator;
 import org.apache.calcite.sql.fun.SqlCountAggFunction;
 import org.apache.calcite.sql.fun.SqlSingleValueAggFunction;
 import org.apache.calcite.sql.fun.SqlStdOperatorTable;
-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.ReflectUtil;
 import org.apache.calcite.util.ReflectiveVisitDispatcher;
@@ -87,7 +87,6 @@ import com.google.common.collect.SortedSetMultimap;
 
 import java.math.BigDecimal;
 import java.util.ArrayList;
-import java.util.BitSet;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
@@ -582,7 +581,7 @@ public class RelDecorrelator implements ReflectiveVisitor {
         new LogicalAggregate(
             rel.getCluster(),
             newProjectRel,
-            BitSets.range(newGroupKeyCount),
+            ImmutableBitSet.range(newGroupKeyCount),
             newAggCalls);
 
     mapOldToNewRel.put(rel, newAggregate);
@@ -2202,7 +2201,7 @@ public class RelDecorrelator implements ReflectiveVisitor {
         }
 
         int nFields = leftInputRel.getRowType().getFieldCount();
-        BitSet allCols = BitSets.range(nFields);
+        ImmutableBitSet allCols = ImmutableBitSet.range(nFields);
 
         // leftInputRel contains unique keys
         // i.e. each row is distinct and can group by on all the left
@@ -2345,8 +2344,8 @@ public class RelDecorrelator implements ReflectiveVisitor {
                 aggRel.getGroupCount(), groupCount));
       }
 
-      BitSet groupSet =
-          BitSets.range(groupCount);
+      ImmutableBitSet groupSet =
+          ImmutableBitSet.range(groupCount);
       LogicalAggregate newAggRel =
           new LogicalAggregate(
               cluster,
@@ -2355,7 +2354,7 @@ public class RelDecorrelator implements ReflectiveVisitor {
               newAggCalls);
 
       List<RexNode> newAggOutputProjExprList = Lists.newArrayList();
-      for (int i : BitSets.toIter(groupSet)) {
+      for (int i : groupSet) {
         newAggOutputProjExprList.add(
             rexBuilder.makeInputRef(newAggRel, i));
       }

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/sql2rel/RelFieldTrimmer.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/sql2rel/RelFieldTrimmer.java b/core/src/main/java/org/apache/calcite/sql2rel/RelFieldTrimmer.java
index 075def1..c68273d 100644
--- a/core/src/main/java/org/apache/calcite/sql2rel/RelFieldTrimmer.java
+++ b/core/src/main/java/org/apache/calcite/sql2rel/RelFieldTrimmer.java
@@ -47,8 +47,8 @@ import org.apache.calcite.rex.RexPermuteInputsShuttle;
 import org.apache.calcite.rex.RexUtil;
 import org.apache.calcite.rex.RexVisitor;
 import org.apache.calcite.sql.validate.SqlValidator;
-import org.apache.calcite.util.BitSets;
 import org.apache.calcite.util.Bug;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.Pair;
 import org.apache.calcite.util.ReflectUtil;
 import org.apache.calcite.util.ReflectiveVisitor;
@@ -63,7 +63,6 @@ import com.google.common.collect.ImmutableList;
 
 import java.math.BigDecimal;
 import java.util.ArrayList;
-import java.util.BitSet;
 import java.util.Collections;
 import java.util.LinkedHashSet;
 import java.util.List;
@@ -144,7 +143,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
             this,
             "trimFields",
             RelNode.class,
-            BitSet.class,
+            ImmutableBitSet.class,
             Set.class);
     this.projectFactory = Preconditions.checkNotNull(projectFactory);
     this.filterFactory = Preconditions.checkNotNull(filterFactory);
@@ -168,7 +167,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
    */
   public RelNode trim(RelNode root) {
     final int fieldCount = root.getRowType().getFieldCount();
-    final BitSet fieldsUsed = BitSets.range(fieldCount);
+    final ImmutableBitSet fieldsUsed = ImmutableBitSet.range(fieldCount);
     final Set<RelDataTypeField> extraFields = Collections.emptySet();
     final TrimResult trimResult =
         dispatchTrimFields(root, fieldsUsed, extraFields);
@@ -189,14 +188,14 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
   protected TrimResult trimChild(
       RelNode rel,
       RelNode input,
-      BitSet fieldsUsed,
+      ImmutableBitSet fieldsUsed,
       Set<RelDataTypeField> extraFields) {
     Util.discard(rel);
     if (input.getClass().getName().endsWith("MedMdrClassExtentRel")) {
       // MedMdrJoinRule cannot handle Join of Project of
       // MedMdrClassExtentRel, only naked MedMdrClassExtentRel.
       // So, disable trimming.
-      fieldsUsed = BitSets.range(input.getRowType().getFieldCount());
+      fieldsUsed = ImmutableBitSet.range(input.getRowType().getFieldCount());
     }
     return dispatchTrimFields(input, fieldsUsed, extraFields);
   }
@@ -217,7 +216,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
   protected TrimResult trimChildRestore(
       RelNode rel,
       RelNode input,
-      BitSet fieldsUsed,
+      ImmutableBitSet fieldsUsed,
       Set<RelDataTypeField> extraFields) {
     TrimResult trimResult = trimChild(rel, input, fieldsUsed, extraFields);
     if (trimResult.right.isIdentity()) {
@@ -255,7 +254,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
    */
   protected final TrimResult dispatchTrimFields(
       RelNode rel,
-      BitSet fieldsUsed,
+      ImmutableBitSet fieldsUsed,
       Set<RelDataTypeField> extraFields) {
     final TrimResult trimResult =
         trimFieldsDispatcher.invoke(rel, fieldsUsed, extraFields);
@@ -296,7 +295,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
    */
   public TrimResult trimFields(
       RelNode rel,
-      BitSet fieldsUsed,
+      ImmutableBitSet fieldsUsed,
       Set<RelDataTypeField> extraFields) {
     // We don't know how to trim this kind of relational expression, so give
     // it back intact.
@@ -308,12 +307,12 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
   }
 
   /**
-   * Variant of {@link #trimFields(RelNode, BitSet, Set)} for
+   * Variant of {@link #trimFields(RelNode, ImmutableBitSet, Set)} for
    * {@link org.apache.calcite.rel.logical.LogicalProject}.
    */
   public TrimResult trimFields(
       Project project,
-      BitSet fieldsUsed,
+      ImmutableBitSet fieldsUsed,
       Set<RelDataTypeField> extraFields) {
     final RelDataType rowType = project.getRowType();
     final int fieldCount = rowType.getFieldCount();
@@ -321,16 +320,16 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
     final RelDataType inputRowType = input.getRowType();
 
     // Which fields are required from the input?
-    BitSet inputFieldsUsed = new BitSet(inputRowType.getFieldCount());
     final Set<RelDataTypeField> inputExtraFields =
         new LinkedHashSet<RelDataTypeField>(extraFields);
     RelOptUtil.InputFinder inputFinder =
-        new RelOptUtil.InputFinder(inputFieldsUsed, inputExtraFields);
+        new RelOptUtil.InputFinder(inputExtraFields);
     for (Ord<RexNode> ord : Ord.zip(project.getProjects())) {
       if (fieldsUsed.get(ord.i)) {
         ord.e.accept(inputFinder);
       }
     }
+    ImmutableBitSet inputFieldsUsed = inputFinder.inputBitSet.build();
 
     // Create input with trimmed columns.
     TrimResult trimResult =
@@ -416,12 +415,12 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
   }
 
   /**
-   * Variant of {@link #trimFields(RelNode, BitSet, Set)} for
+   * Variant of {@link #trimFields(RelNode, ImmutableBitSet, Set)} for
    * {@link org.apache.calcite.rel.logical.LogicalFilter}.
    */
   public TrimResult trimFields(
       Filter filter,
-      BitSet fieldsUsed,
+      ImmutableBitSet fieldsUsed,
       Set<RelDataTypeField> extraFields) {
     final RelDataType rowType = filter.getRowType();
     final int fieldCount = rowType.getFieldCount();
@@ -430,12 +429,13 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
 
     // We use the fields used by the consumer, plus any fields used in the
     // filter.
-    BitSet inputFieldsUsed = (BitSet) fieldsUsed.clone();
     final Set<RelDataTypeField> inputExtraFields =
         new LinkedHashSet<RelDataTypeField>(extraFields);
     RelOptUtil.InputFinder inputFinder =
-        new RelOptUtil.InputFinder(inputFieldsUsed, inputExtraFields);
+        new RelOptUtil.InputFinder(inputExtraFields);
+    inputFinder.inputBitSet.addAll(fieldsUsed);
     conditionExpr.accept(inputFinder);
+    final ImmutableBitSet inputFieldsUsed = inputFinder.inputBitSet.build();
 
     // Create input with trimmed columns.
     TrimResult trimResult =
@@ -468,12 +468,12 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
   }
 
   /**
-   * Variant of {@link #trimFields(RelNode, BitSet, Set)} for
+   * Variant of {@link #trimFields(RelNode, ImmutableBitSet, Set)} for
    * {@link org.apache.calcite.rel.core.Sort}.
    */
   public TrimResult trimFields(
       Sort sort,
-      BitSet fieldsUsed,
+      ImmutableBitSet fieldsUsed,
       Set<RelDataTypeField> extraFields) {
     final RelDataType rowType = sort.getRowType();
     final int fieldCount = rowType.getFieldCount();
@@ -482,7 +482,8 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
 
     // We use the fields used by the consumer, plus any fields used as sort
     // keys.
-    BitSet inputFieldsUsed = (BitSet) fieldsUsed.clone();
+    final ImmutableBitSet.Builder inputFieldsUsed =
+        ImmutableBitSet.builder(fieldsUsed);
     for (RelFieldCollation field : collation.getFieldCollations()) {
       inputFieldsUsed.set(field.getFieldIndex());
     }
@@ -490,7 +491,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
     // Create input with trimmed columns.
     final Set<RelDataTypeField> inputExtraFields = Collections.emptySet();
     TrimResult trimResult =
-        trimChild(sort, input, inputFieldsUsed, inputExtraFields);
+        trimChild(sort, input, inputFieldsUsed.build(), inputExtraFields);
     RelNode newInput = trimResult.left;
     final Mapping inputMapping = trimResult.right;
 
@@ -517,12 +518,12 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
   }
 
   /**
-   * Variant of {@link #trimFields(RelNode, BitSet, Set)} for
+   * Variant of {@link #trimFields(RelNode, ImmutableBitSet, Set)} for
    * {@link org.apache.calcite.rel.logical.LogicalJoin}.
    */
   public TrimResult trimFields(
       Join join,
-      BitSet fieldsUsed,
+      ImmutableBitSet fieldsUsed,
       Set<RelDataTypeField> extraFields) {
     final int fieldCount = join.getSystemFieldList().size()
         + join.getLeft().getRowType().getFieldCount()
@@ -531,13 +532,13 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
     final int systemFieldCount = join.getSystemFieldList().size();
 
     // Add in fields used in the condition.
-    BitSet fieldsUsedPlus = (BitSet) fieldsUsed.clone();
     final Set<RelDataTypeField> combinedInputExtraFields =
         new LinkedHashSet<RelDataTypeField>(extraFields);
     RelOptUtil.InputFinder inputFinder =
-        new RelOptUtil.InputFinder(
-            fieldsUsedPlus, combinedInputExtraFields);
+        new RelOptUtil.InputFinder(combinedInputExtraFields);
+    inputFinder.inputBitSet.addAll(fieldsUsed);
     conditionExpr.accept(inputFinder);
+    final ImmutableBitSet fieldsUsedPlus = inputFinder.inputBitSet.build();
 
     // If no system fields are used, we can remove them.
     int systemFieldUsedCount = 0;
@@ -564,8 +565,8 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
       final int inputFieldCount = inputRowType.getFieldCount();
 
       // Compute required mapping.
-      BitSet inputFieldsUsed = new BitSet(inputFieldCount);
-      for (int bit : BitSets.toIter(fieldsUsedPlus)) {
+      ImmutableBitSet.Builder inputFieldsUsed = ImmutableBitSet.builder();
+      for (int bit : fieldsUsedPlus) {
         if (bit >= offset && bit < offset + inputFieldCount) {
           inputFieldsUsed.set(bit - offset);
         }
@@ -573,11 +574,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
 
       // If there are system fields, we automatically use the
       // corresponding field in each input.
-      if (newSystemFieldCount > 0) {
-        // calling with newSystemFieldCount == 0 should be safe but hits
-        // http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6222207
-        inputFieldsUsed.set(0, newSystemFieldCount);
-      }
+      inputFieldsUsed.set(0, newSystemFieldCount);
 
       // FIXME: We ought to collect extra fields for each input
       // individually. For now, we assume that just one input has
@@ -588,7 +585,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
               : combinedInputExtraFields;
       inputExtraFieldCounts.add(inputExtraFields.size());
       TrimResult trimResult =
-          trimChild(join, input, inputFieldsUsed, inputExtraFields);
+          trimChild(join, input, inputFieldsUsed.build(), inputExtraFields);
       newInputs.add(trimResult.left);
       if (trimResult.left != input) {
         ++changeCount;
@@ -662,12 +659,12 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
   }
 
   /**
-   * Variant of {@link #trimFields(RelNode, BitSet, Set)} for
+   * Variant of {@link #trimFields(RelNode, ImmutableBitSet, Set)} for
    * {@link org.apache.calcite.rel.core.SetOp} (including UNION and UNION ALL).
    */
   public TrimResult trimFields(
       SetOp setOp,
-      BitSet fieldsUsed,
+      ImmutableBitSet fieldsUsed,
       Set<RelDataTypeField> extraFields) {
     final RelDataType rowType = setOp.getRowType();
     final int fieldCount = rowType.getFieldCount();
@@ -677,7 +674,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
     // wants the last field. (The last field is the least likely to be a
     // system field.)
     if (fieldsUsed.isEmpty()) {
-      fieldsUsed.set(rowType.getFieldCount() - 1);
+      fieldsUsed = ImmutableBitSet.of(rowType.getFieldCount() - 1);
     }
 
     // Compute the desired field mapping. Give the consumer the fields they
@@ -730,12 +727,12 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
   }
 
   /**
-   * Variant of {@link #trimFields(RelNode, BitSet, Set)} for
+   * Variant of {@link #trimFields(RelNode, ImmutableBitSet, Set)} for
    * {@link org.apache.calcite.rel.logical.LogicalAggregate}.
    */
   public TrimResult trimFields(
       Aggregate aggregate,
-      BitSet fieldsUsed,
+      ImmutableBitSet fieldsUsed,
       Set<RelDataTypeField> extraFields) {
     // Fields:
     //
@@ -753,11 +750,9 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
     final RelDataType rowType = aggregate.getRowType();
 
     // Compute which input fields are used.
-    BitSet inputFieldsUsed = new BitSet();
     // 1. group fields are always used
-    for (int i : BitSets.toIter(aggregate.getGroupSet())) {
-      inputFieldsUsed.set(i);
-    }
+    final ImmutableBitSet.Builder inputFieldsUsed =
+        ImmutableBitSet.builder(aggregate.getGroupSet());
     // 2. agg functions
     for (AggregateCall aggCall : aggregate.getAggCallList()) {
       for (int i : aggCall.getArgList()) {
@@ -769,14 +764,14 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
     final RelNode input = aggregate.getInput(0);
     final Set<RelDataTypeField> inputExtraFields = Collections.emptySet();
     final TrimResult trimResult =
-        trimChild(aggregate, input, inputFieldsUsed, inputExtraFields);
+        trimChild(aggregate, input, inputFieldsUsed.build(), inputExtraFields);
     final RelNode newInput = trimResult.left;
     final Mapping inputMapping = trimResult.right;
 
     // If the input is unchanged, and we need to project all columns,
     // there's nothing to do.
     if (input == newInput
-        && fieldsUsed.equals(BitSets.range(rowType.getFieldCount()))) {
+        && fieldsUsed.equals(ImmutableBitSet.range(rowType.getFieldCount()))) {
       return new TrimResult(
           aggregate,
           Mappings.createIdentity(rowType.getFieldCount()));
@@ -800,7 +795,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
             groupCount
                 + usedAggCallCount);
 
-    final BitSet newGroupSet =
+    final ImmutableBitSet newGroupSet =
         Mappings.apply(inputMapping, aggregate.getGroupSet());
 
     // Populate mapping of where to find the fields. System and grouping
@@ -840,12 +835,12 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
   }
 
   /**
-   * Variant of {@link #trimFields(RelNode, BitSet, Set)} for
+   * Variant of {@link #trimFields(RelNode, ImmutableBitSet, Set)} for
    * {@link org.apache.calcite.rel.logical.LogicalTableModify}.
    */
   public TrimResult trimFields(
       LogicalTableModify modifier,
-      BitSet fieldsUsed,
+      ImmutableBitSet fieldsUsed,
       Set<RelDataTypeField> extraFields) {
     // Ignore what consumer wants. We always project all columns.
     Util.discard(fieldsUsed);
@@ -856,7 +851,8 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
 
     // We want all fields from the child.
     final int inputFieldCount = input.getRowType().getFieldCount();
-    BitSet inputFieldsUsed = BitSets.range(inputFieldCount);
+    final ImmutableBitSet inputFieldsUsed =
+        ImmutableBitSet.range(inputFieldCount);
 
     // Create input with trimmed columns.
     final Set<RelDataTypeField> inputExtraFields = Collections.emptySet();
@@ -886,12 +882,12 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
   }
 
   /**
-   * Variant of {@link #trimFields(RelNode, BitSet, Set)} for
+   * Variant of {@link #trimFields(RelNode, ImmutableBitSet, Set)} for
    * {@link org.apache.calcite.rel.logical.LogicalTableFunctionScan}.
    */
   public TrimResult trimFields(
       LogicalTableFunctionScan tabFun,
-      BitSet fieldsUsed,
+      ImmutableBitSet fieldsUsed,
       Set<RelDataTypeField> extraFields) {
     final RelDataType rowType = tabFun.getRowType();
     final int fieldCount = rowType.getFieldCount();
@@ -899,7 +895,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
 
     for (RelNode input : tabFun.getInputs()) {
       final int inputFieldCount = input.getRowType().getFieldCount();
-      BitSet inputFieldsUsed = BitSets.range(inputFieldCount);
+      ImmutableBitSet inputFieldsUsed = ImmutableBitSet.range(inputFieldCount);
 
       // Create input with trimmed columns.
       final Set<RelDataTypeField> inputExtraFields =
@@ -923,12 +919,12 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
   }
 
   /**
-   * Variant of {@link #trimFields(RelNode, BitSet, Set)} for
+   * Variant of {@link #trimFields(RelNode, ImmutableBitSet, Set)} for
    * {@link org.apache.calcite.rel.logical.LogicalValues}.
    */
   public TrimResult trimFields(
       LogicalValues values,
-      BitSet fieldsUsed,
+      ImmutableBitSet fieldsUsed,
       Set<RelDataTypeField> extraFields) {
     final RelDataType rowType = values.getRowType();
     final int fieldCount = rowType.getFieldCount();
@@ -937,11 +933,11 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
     // because zero-column records are illegal. Give them the last field,
     // which is unlikely to be a system field.
     if (fieldsUsed.isEmpty()) {
-      fieldsUsed = BitSets.range(fieldCount - 1, fieldCount);
+      fieldsUsed = ImmutableBitSet.range(fieldCount - 1, fieldCount);
     }
 
     // If all fields are used, return unchanged.
-    if (fieldsUsed.equals(BitSets.range(fieldCount))) {
+    if (fieldsUsed.equals(ImmutableBitSet.range(fieldCount))) {
       Mapping mapping = Mappings.createIdentity(fieldCount);
       return new TrimResult(values, mapping);
     }
@@ -949,7 +945,7 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
     List<List<RexLiteral>> newTuples = new ArrayList<List<RexLiteral>>();
     for (List<RexLiteral> tuple : values.getTuples()) {
       List<RexLiteral> newTuple = new ArrayList<RexLiteral>();
-      for (int field : BitSets.toIter(fieldsUsed)) {
+      for (int field : fieldsUsed) {
         newTuple.add(tuple.get(field));
       }
       newTuples.add(newTuple);
@@ -964,29 +960,30 @@ public class RelFieldTrimmer implements ReflectiveVisitor {
     return new TrimResult(newValues, mapping);
   }
 
-  private Mapping createMapping(BitSet fieldsUsed, int fieldCount) {
+  private Mapping createMapping(ImmutableBitSet fieldsUsed, int fieldCount) {
     final Mapping mapping =
         Mappings.create(
             MappingType.INVERSE_SURJECTION,
             fieldCount,
             fieldsUsed.cardinality());
     int i = 0;
-    for (int field : BitSets.toIter(fieldsUsed)) {
+    for (int field : fieldsUsed) {
       mapping.set(field, i++);
     }
     return mapping;
   }
 
   /**
-   * Variant of {@link #trimFields(RelNode, BitSet, Set)} for
+   * Variant of {@link #trimFields(RelNode, ImmutableBitSet, Set)} for
    * {@link org.apache.calcite.rel.logical.LogicalTableScan}.
    */
   public TrimResult trimFields(
       final TableScan tableAccessRel,
-      BitSet fieldsUsed,
+      ImmutableBitSet fieldsUsed,
       Set<RelDataTypeField> extraFields) {
     final int fieldCount = tableAccessRel.getRowType().getFieldCount();
-    if (fieldsUsed.equals(BitSets.range(fieldCount)) && extraFields.isEmpty()) {
+    if (fieldsUsed.equals(ImmutableBitSet.range(fieldCount))
+        && extraFields.isEmpty()) {
       // if there is nothing to project or if we are projecting everything
       // then no need to introduce another RelNode
       return trimFields(

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java b/core/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java
index ce1cb4a..ceb6a1a 100644
--- a/core/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java
+++ b/core/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java
@@ -127,7 +127,7 @@ import org.apache.calcite.sql.validate.SqlValidatorImpl;
 import org.apache.calcite.sql.validate.SqlValidatorNamespace;
 import org.apache.calcite.sql.validate.SqlValidatorScope;
 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.NlsString;
 import org.apache.calcite.util.NumberUtil;
@@ -148,7 +148,6 @@ import java.lang.reflect.Type;
 import java.math.BigDecimal;
 import java.util.AbstractList;
 import java.util.ArrayList;
-import java.util.BitSet;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.EnumSet;
@@ -714,7 +713,7 @@ public class SqlToRelConverter {
     rel =
         createAggregate(
             bb,
-            BitSets.range(rel.getRowType().getFieldCount()),
+            ImmutableBitSet.range(rel.getRowType().getFieldCount()),
             ImmutableList.<AggregateCall>of());
 
     bb.setRoot(
@@ -1033,7 +1032,7 @@ public class SqlToRelConverter {
         final int keyCount = leftKeys.size();
         final List<Integer> args = ImmutableIntList.range(0, keyCount);
         LogicalAggregate aggregate =
-            new LogicalAggregate(cluster, seek, BitSets.of(),
+            new LogicalAggregate(cluster, seek, ImmutableBitSet.of(),
                 ImmutableList.of(
                     new AggregateCall(SqlStdOperatorTable.COUNT, false,
                         ImmutableList.<Integer>of(), longType, null),
@@ -2276,7 +2275,7 @@ public class SqlToRelConverter {
     case LITERAL:
       return node;
     default:
-      BitSet bits = RelOptUtil.InputFinder.bits(node);
+      ImmutableBitSet bits = RelOptUtil.InputFinder.bits(node);
       final int mid = leftCount + extraLeftExprs.size();
       switch (Side.of(bits, mid)) {
       case LEFT:
@@ -2312,7 +2311,7 @@ public class SqlToRelConverter {
   enum Side {
     LEFT, RIGHT, BOTH, EMPTY;
 
-    static Side of(BitSet bitSet, int middle) {
+    static Side of(ImmutableBitSet bitSet, int middle) {
       final int firstBit = bitSet.nextSetBit(0);
       if (firstBit < 0) {
         return EMPTY;
@@ -2646,7 +2645,7 @@ public class SqlToRelConverter {
       bb.setRoot(
           createAggregate(
               bb,
-              BitSets.range(aggConverter.groupExprs.size()),
+              ImmutableBitSet.range(aggConverter.groupExprs.size()),
               aggConverter.getAggCalls()),
           false);
 
@@ -2744,7 +2743,7 @@ public class SqlToRelConverter {
    */
   protected RelNode createAggregate(
       Blackboard bb,
-      BitSet groupSet,
+      ImmutableBitSet groupSet,
       List<AggregateCall> aggCalls) {
     return new LogicalAggregate(
         cluster,

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/util/BitSets.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/util/BitSets.java b/core/src/main/java/org/apache/calcite/util/BitSets.java
index 0d79c85..bbab792 100644
--- a/core/src/main/java/org/apache/calcite/util/BitSets.java
+++ b/core/src/main/java/org/apache/calcite/util/BitSets.java
@@ -48,6 +48,24 @@ public final class BitSets {
   }
 
   /**
+   * Returns true if all bits set in the second parameter are also set in the
+   * first. In other words, whether x is a super-set of y.
+   *
+   * @param set0 Containing bitmap
+   * @param set1 Bitmap to be checked
+   *
+   * @return Whether all bits in set1 are set in set0
+   */
+  public static boolean contains(BitSet set0, ImmutableBitSet set1) {
+    for (int i = set1.nextSetBit(0); i >= 0; i = set1.nextSetBit(i + 1)) {
+      if (!set0.get(i)) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  /**
    * Returns an iterable over the bits in a bitmap that are set to '1'.
    *
    * <p>This allows you to iterate over a bit set using a 'foreach' construct.
@@ -86,6 +104,10 @@ public final class BitSets {
     };
   }
 
+  public static Iterable<Integer> toIter(final ImmutableBitSet bitSet) {
+    return bitSet;
+  }
+
   /**
    * Converts a bitset to a list.
    *

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/util/BuiltInMethod.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/util/BuiltInMethod.java b/core/src/main/java/org/apache/calcite/util/BuiltInMethod.java
index 8ad1742..20ecfa5 100644
--- a/core/src/main/java/org/apache/calcite/util/BuiltInMethod.java
+++ b/core/src/main/java/org/apache/calcite/util/BuiltInMethod.java
@@ -63,7 +63,6 @@ import java.lang.reflect.Method;
 import java.sql.ResultSet;
 import java.sql.Time;
 import java.sql.Timestamp;
-import java.util.BitSet;
 import java.util.Calendar;
 import java.util.Collection;
 import java.util.Collections;
@@ -265,14 +264,15 @@ public enum BuiltInMethod {
   ELEMENT(SqlFunctions.class, "element", List.class),
   SELECTIVITY(Selectivity.class, "getSelectivity", RexNode.class),
   UNIQUE_KEYS(UniqueKeys.class, "getUniqueKeys", boolean.class),
-  COLUMN_UNIQUENESS(ColumnUniqueness.class, "areColumnsUnique", BitSet.class,
-      boolean.class),
+  COLUMN_UNIQUENESS(ColumnUniqueness.class, "areColumnsUnique",
+      ImmutableBitSet.class, boolean.class),
   ROW_COUNT(RowCount.class, "getRowCount"),
   DISTINCT_ROW_COUNT(DistinctRowCount.class, "getDistinctRowCount",
-      BitSet.class, RexNode.class),
+      ImmutableBitSet.class, RexNode.class),
   PERCENTAGE_ORIGINAL_ROWS(PercentageOriginalRows.class,
       "getPercentageOriginalRows"),
-  POPULATION_SIZE(PopulationSize.class, "getPopulationSize", BitSet.class),
+  POPULATION_SIZE(PopulationSize.class, "getPopulationSize",
+      ImmutableBitSet.class),
   COLUMN_ORIGIN(ColumnOrigin.class, "getColumnOrigins", int.class),
   CUMULATIVE_COST(CumulativeCost.class, "getCumulativeCost"),
   NON_CUMULATIVE_COST(NonCumulativeCost.class, "getNonCumulativeCost"),

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/util/ImmutableBitSet.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/util/ImmutableBitSet.java b/core/src/main/java/org/apache/calcite/util/ImmutableBitSet.java
new file mode 100644
index 0000000..a757dd5
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/util/ImmutableBitSet.java
@@ -0,0 +1,882 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.util;
+
+import org.apache.calcite.runtime.Utilities;
+
+import com.google.common.base.Function;
+import com.google.common.collect.Maps;
+
+import java.io.Serializable;
+import java.util.AbstractList;
+import java.util.Arrays;
+import java.util.BitSet;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.SortedMap;
+
+/**
+ * An immutable list of bits.
+ */
+public class ImmutableBitSet
+    implements Iterable<Integer>, Serializable, Comparable<ImmutableBitSet> {
+  /** Compares bit sets topologically, so that enclosing bit sets come first,
+   * using natural ordering to break ties. */
+  public static final Comparator<ImmutableBitSet> COMPARATOR =
+      new Comparator<ImmutableBitSet>() {
+        public int compare(ImmutableBitSet o1, ImmutableBitSet o2) {
+          if (o1.equals(o2)) {
+            return 0;
+          }
+          if (o1.contains(o2)) {
+            return -1;
+          }
+          if (o2.contains(o1)) {
+            return 1;
+          }
+          return o1.compareTo(o2);
+        }
+      };
+
+  // BitSets are packed into arrays of "words."  Currently a word is
+  // a long, which consists of 64 bits, requiring 6 address bits.
+  // The choice of word size is determined purely by performance concerns.
+  private static final int ADDRESS_BITS_PER_WORD = 6;
+  private static final int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
+
+  /* Used to shift left or right for a partial word mask */
+  private static final long WORD_MASK = 0xffffffffffffffffL;
+
+  private static final long[] EMPTY_LONGS = new long[0];
+
+  private static final ImmutableBitSet EMPTY =
+      new ImmutableBitSet(EMPTY_LONGS);
+
+  public static final Function<? super BitSet, ImmutableBitSet> FROM_BIT_SET =
+      new Function<BitSet, ImmutableBitSet>() {
+        public ImmutableBitSet apply(BitSet input) {
+          return ImmutableBitSet.of(BitSets.toIter(input));
+        }
+      };
+
+  private final long[] words;
+
+  /** Private constructor. Does not copy the array. */
+  private ImmutableBitSet(long[] words) {
+    this.words = words;
+    assert words.length == 0
+        ? words == EMPTY_LONGS
+        : words[words.length - 1] != 0L;
+  }
+
+  /** Creates an ImmutableBitSet with no bits. */
+  public static ImmutableBitSet of() {
+    return EMPTY;
+  }
+
+  public static ImmutableBitSet of(int... bits) {
+    int max = -1;
+    for (int bit : bits) {
+      max = Math.max(bit, max);
+    }
+    if (max == -1) {
+      return EMPTY;
+    }
+    long[] words = new long[wordIndex(max) + 1];
+    for (int bit : bits) {
+      int wordIndex = wordIndex(bit);
+      words[wordIndex] |= 1L << bit;
+    }
+    return new ImmutableBitSet(words);
+  }
+
+  public static ImmutableBitSet of(Iterable<Integer>  bits) {
+    if (bits instanceof ImmutableBitSet) {
+      return (ImmutableBitSet) bits;
+    }
+    int max = -1;
+    for (int bit : bits) {
+      max = Math.max(bit, max);
+    }
+    if (max == -1) {
+      return EMPTY;
+    }
+    long[] words = new long[wordIndex(max) + 1];
+    for (int bit : bits) {
+      int wordIndex = wordIndex(bit);
+      words[wordIndex] |= 1L << bit;
+    }
+    return new ImmutableBitSet(words);
+  }
+
+  /**
+   * Creates an ImmutableBitSet with given bits set.
+   *
+   * <p>For example, <code>of(ImmutableIntList.of(0, 3))</code> returns a bit
+   * set with bits {0, 3} set.
+   *
+   * @param bits Collection of bits to set
+   * @return Bit set
+   */
+  public static ImmutableBitSet of(ImmutableIntList bits) {
+    return builder().addAll(bits).build();
+  }
+
+  /**
+   * Creates an ImmutableBitSet with bits from {@code fromIndex} (inclusive) to
+   * specified {@code toIndex} (exclusive) set to {@code true}.
+   *
+   * <p>For example, {@code range(0, 3)} returns a bit set with bits
+   * {0, 1, 2} set.
+   *
+   * @param fromIndex Index of the first bit to be set.
+   * @param toIndex   Index after the last bit to be set.
+   * @return Bit set
+   */
+  public static ImmutableBitSet range(int fromIndex, int toIndex) {
+    if (fromIndex > toIndex) {
+      throw new IllegalArgumentException();
+    }
+    if (toIndex < 0) {
+      throw new IllegalArgumentException();
+    }
+    if (fromIndex == toIndex) {
+      return EMPTY;
+    }
+    int startWordIndex = wordIndex(fromIndex);
+    int endWordIndex   = wordIndex(toIndex - 1);
+    long[] words = new long[endWordIndex + 1];
+
+    long firstWordMask = WORD_MASK << fromIndex;
+    long lastWordMask  = WORD_MASK >>> -toIndex;
+    if (startWordIndex == endWordIndex) {
+      // One word
+      words[startWordIndex] |= firstWordMask & lastWordMask;
+    } else {
+      // First word, middle words, last word
+      words[startWordIndex] |= firstWordMask;
+      for (int i = startWordIndex + 1; i < endWordIndex; i++) {
+        words[i] = WORD_MASK;
+      }
+      words[endWordIndex] |= lastWordMask;
+    }
+    return new ImmutableBitSet(words);
+  }
+
+  /** Creates an ImmutableBitSet with bits between 0 and {@code toIndex} set. */
+  public static ImmutableBitSet range(int toIndex) {
+    return range(0, toIndex);
+  }
+
+  /**
+   * Given a bit index, return word index containing it.
+   */
+  private static int wordIndex(int bitIndex) {
+    return bitIndex >> ADDRESS_BITS_PER_WORD;
+  }
+
+  /**
+   * Returns the value of the bit with the specified index. The value
+   * is {@code true} if the bit with the index {@code bitIndex}
+   * is currently set in this {@code ImmutableBitSet}; otherwise, the result
+   * is {@code false}.
+   *
+   * @param  bitIndex   the bit index
+   * @return the value of the bit with the specified index
+   * @throws IndexOutOfBoundsException if the specified index is negative
+   */
+  public boolean get(int bitIndex) {
+    if (bitIndex < 0) {
+      throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
+    }
+    int wordIndex = wordIndex(bitIndex);
+    return (wordIndex < words.length)
+        && ((words[wordIndex] & (1L << bitIndex)) != 0);
+  }
+
+  /**
+   * Returns a string representation of this bit set. For every index
+   * for which this {@code BitSet} contains a bit in the set
+   * state, the decimal representation of that index is included in
+   * the result. Such indices are listed in order from lowest to
+   * highest, separated by ",&nbsp;" (a comma and a space) and
+   * surrounded by braces, resulting in the usual mathematical
+   * notation for a set of integers.
+   *
+   * <p>Example:
+   * <pre>
+   * BitSet drPepper = new BitSet();</pre>
+   * Now {@code drPepper.toString()} returns "{@code {}}".
+   * <pre>
+   * drPepper.set(2);</pre>
+   * Now {@code drPepper.toString()} returns "{@code {2}}".
+   * <pre>
+   * drPepper.set(4);
+   * drPepper.set(10);</pre>
+   * Now {@code drPepper.toString()} returns "{@code {2, 4, 10}}".
+   *
+   * @return a string representation of this bit set
+   */
+  public String toString() {
+    int numBits = words.length * BITS_PER_WORD;
+    StringBuilder b = new StringBuilder(6 * numBits + 2);
+    b.append('{');
+
+    int i = nextSetBit(0);
+    if (i != -1) {
+      b.append(i);
+      for (i = nextSetBit(i + 1); i >= 0; i = nextSetBit(i + 1)) {
+        int endOfRun = nextClearBit(i);
+        do { b.append(", ").append(i); }
+        while (++i < endOfRun);
+      }
+    }
+
+    b.append('}');
+    return b.toString();
+  }
+
+  /**
+   * Returns true if the specified {@code ImmutableBitSet} has any bits set to
+   * {@code true} that are also set to {@code true} in this
+   * {@code ImmutableBitSet}.
+   *
+   * @param  set {@code ImmutableBitSet} to intersect with
+   * @return boolean indicating whether this {@code ImmutableBitSet} intersects
+   *         the specified {@code ImmutableBitSet}
+   */
+  public boolean intersects(ImmutableBitSet set) {
+    for (int i = Math.min(words.length, set.words.length) - 1; i >= 0; i--) {
+      if ((words[i] & set.words[i]) != 0) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  /** Returns the number of bits set to {@code true} in this
+   * {@code ImmutableBitSet}. */
+  public int cardinality() {
+    return countBits(words);
+  }
+
+  private static int countBits(long[] words) {
+    int sum = 0;
+    for (long word : words) {
+      sum += Long.bitCount(word);
+    }
+    return sum;
+  }
+
+  /**
+   * Returns the hash code value for this bit set. The hash code
+   * depends only on which bits are set within this {@code ImmutableBitSet}.
+   *
+   * <p>The hash code is defined using the same calculation as
+   * {@link java.util.BitSet#hashCode()}.
+   *
+   * @return the hash code value for this bit set
+   */
+  public int hashCode() {
+    long h = 1234;
+    for (int i = words.length; --i >= 0;) {
+      h ^= words[i] * (i + 1);
+    }
+    return (int) ((h >> 32) ^ h);
+  }
+
+  /**
+   * Returns the number of bits of space actually in use by this
+   * {@code ImmutableBitSet} to represent bit values.
+   * The maximum element in the set is the size - 1st element.
+   *
+   * @return the number of bits currently in this bit set
+   */
+  public int size() {
+    return words.length * BITS_PER_WORD;
+  }
+
+  /**
+   * Compares this object against the specified object.
+   * The result is {@code true} if and only if the argument is
+   * not {@code null} and is a {@code ImmutableBitSet} object that has
+   * exactly the same set of bits set to {@code true} as this bit
+   * set.
+   *
+   * @param  obj the object to compare with
+   * @return {@code true} if the objects are the same;
+   *         {@code false} otherwise
+   * @see    #size()
+   */
+  public boolean equals(Object obj) {
+    if (this == obj) {
+      return true;
+    }
+    if (!(obj instanceof ImmutableBitSet)) {
+      return false;
+    }
+    ImmutableBitSet set = (ImmutableBitSet) obj;
+    return Arrays.equals(words, set.words);
+  }
+
+  /** Compares this ImmutableBitSet with another, using a lexicographic
+   * ordering.
+   *
+   * <p>Bit sets {@code (), (0), (0, 1), (0, 1, 3), (1), (2, 3)} are in sorted
+   * order.</p>
+   */
+  public int compareTo(ImmutableBitSet o) {
+    int i = 0;
+    for (;;) {
+      int n0 = nextSetBit(i);
+      int n1 = o.nextSetBit(i);
+      int c = Utilities.compare(n0, n1);
+      if (c != 0 || n0 < 0) {
+        return c;
+      }
+      i = n0 + 1;
+    }
+  }
+
+  /**
+   * Returns the index of the first bit that is set to {@code true}
+   * that occurs on or after the specified starting index. If no such
+   * bit exists then {@code -1} is returned.
+   *
+   * <p>Based upon {@link BitSet#nextSetBit}.
+   *
+   * @param  fromIndex the index to start checking from (inclusive)
+   * @return the index of the next set bit, or {@code -1} if there
+   *         is no such bit
+   * @throws IndexOutOfBoundsException if the specified index is negative
+   */
+  public int nextSetBit(int fromIndex) {
+    if (fromIndex < 0) {
+      throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
+    }
+    int u = wordIndex(fromIndex);
+    if (u >= words.length) {
+      return -1;
+    }
+    long word = words[u] & (WORD_MASK << fromIndex);
+
+    while (true) {
+      if (word != 0) {
+        return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
+      }
+      if (++u == words.length) {
+        return -1;
+      }
+      word = words[u];
+    }
+  }
+
+  /**
+   * Returns the index of the first bit that is set to {@code false}
+   * that occurs on or after the specified starting index.
+   *
+   * @param  fromIndex the index to start checking from (inclusive)
+   * @return the index of the next clear bit
+   * @throws IndexOutOfBoundsException if the specified index is negative
+   */
+  public int nextClearBit(int fromIndex) {
+    if (fromIndex < 0) {
+      throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
+    }
+    int u = wordIndex(fromIndex);
+    if (u >= words.length) {
+      return fromIndex;
+    }
+    long word = ~words[u] & (WORD_MASK << fromIndex);
+
+    while (true) {
+      if (word != 0) {
+        return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
+      }
+      if (++u == words.length) {
+        return words.length * BITS_PER_WORD;
+      }
+      word = ~words[u];
+    }
+  }
+
+  /**
+   * Returns the index of the nearest bit that is set to {@code false}
+   * that occurs on or before the specified starting index.
+   * If no such bit exists, or if {@code -1} is given as the
+   * starting index, then {@code -1} is returned.
+   *
+   * @param  fromIndex the index to start checking from (inclusive)
+   * @return the index of the previous clear bit, or {@code -1} if there
+   *         is no such bit
+   * @throws IndexOutOfBoundsException if the specified index is less
+   *         than {@code -1}
+   */
+  public int previousClearBit(int fromIndex) {
+    if (fromIndex < 0) {
+      if (fromIndex == -1) {
+        return -1;
+      }
+      throw new IndexOutOfBoundsException("fromIndex < -1: " + fromIndex);
+    }
+
+    int u = wordIndex(fromIndex);
+    if (u >= words.length) {
+      return fromIndex;
+    }
+    long word = ~words[u] & (WORD_MASK >>> -(fromIndex + 1));
+
+    while (true) {
+      if (word != 0) {
+        return (u + 1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word);
+      }
+      if (u-- == 0) {
+        return -1;
+      }
+      word = ~words[u];
+    }
+  }
+
+  public Iterator<Integer> iterator() {
+    return new Iterator<Integer>() {
+      int i = nextSetBit(0);
+
+      public boolean hasNext() {
+        return i >= 0;
+      }
+
+      public Integer next() {
+        int prev = i;
+        i = nextSetBit(i + 1);
+        return prev;
+      }
+
+      public void remove() {
+        throw new UnsupportedOperationException();
+      }
+    };
+  }
+
+  /** Converts this bit set to a list. */
+  public IntList toList() {
+    final IntList list = new IntList();
+    for (int i = nextSetBit(0); i >= 0; i = nextSetBit(i + 1)) {
+      list.add(i);
+    }
+    return list;
+  }
+
+  /** Creates a view onto this bit set as a list of integers.
+   *
+   * <p>The {@code cardinality} and {@code get} methods are both O(n), but
+   * the iterator is efficient. The list is memory efficient, and the CPU cost
+   * breaks even (versus {@link #toList}) if you intend to scan it only once. */
+  public List<Integer> asList() {
+    return new AbstractList<Integer>() {
+      @Override public Integer get(int index) {
+        return nth(index);
+      }
+
+      @Override public int size() {
+        return cardinality();
+      }
+
+      @Override public Iterator<Integer> iterator() {
+        return ImmutableBitSet.this.iterator();
+      }
+    };
+  }
+
+  /**
+   * Converts this bit set to an array.
+   *
+   * @return Array of set bits
+   */
+  public int[] toArray() {
+    final int[] integers = new int[cardinality()];
+    int j = 0;
+    for (int i = nextSetBit(0); i >= 0; i = nextSetBit(i + 1)) {
+      integers[j++] = i;
+    }
+    return integers;
+  }
+
+  /** Returns the union of this bit set with another. */
+  public ImmutableBitSet union(ImmutableBitSet other) {
+    return builder(this)
+        .addAll(other)
+        .build();
+  }
+
+  /** Returns the union of a number of bit sets. */
+  public static ImmutableBitSet union(
+      Iterable<? extends ImmutableBitSet> sets) {
+    final Builder builder = builder();
+    for (ImmutableBitSet set : sets) {
+      builder.addAll(set);
+    }
+    return builder.build();
+  }
+
+  /** Returns a bit set with all the bits in this set that are not in
+   * another.
+   *
+   *  @see BitSet#andNot(java.util.BitSet) */
+  public ImmutableBitSet except(ImmutableBitSet that) {
+    final Builder builder = builder(this);
+    builder.removeAll(that);
+    return builder.build(this);
+  }
+
+  /** Returns a bit set with all the bits set in both this set and in
+   *  another.
+   *
+   *  @see BitSet#and */
+  public ImmutableBitSet intersect(ImmutableBitSet that) {
+    final Builder builder = builder(this);
+    builder.intersect(that);
+    return builder.build(this);
+  }
+
+  /**
+   * Returns true if all bits set in the second parameter are also set in the
+   * first. In other words, whether x is a super-set of y.
+   *
+   * @param set1 Bitmap to be checked
+   *
+   * @return Whether all bits in set1 are set in set0
+   */
+  public boolean contains(ImmutableBitSet set1) {
+    for (int i = set1.nextSetBit(0); i >= 0; i = set1.nextSetBit(i + 1)) {
+      if (!get(i)) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  /**
+   * The ordinal of a given bit, or -1 if it is not set.
+   */
+  public int indexOf(int bit) {
+    for (int i = nextSetBit(0), k = 0;; i = nextSetBit(i + 1), ++k) {
+      if (i < 0) {
+        return -1;
+      }
+      if (i == bit) {
+        return k;
+      }
+    }
+  }
+
+  /** Computes the closure of a map from integers to bits.
+   *
+   * <p>The input must have an entry for each position.
+   *
+   * <p>Does not modify the input map or its bit sets. */
+  public static SortedMap<Integer, ImmutableBitSet> closure(
+      SortedMap<Integer, ImmutableBitSet> equivalence) {
+    final Closure closure = new Closure(equivalence);
+    return closure.closure;
+  }
+
+  /**
+   * Returns the "logical size" of this {@code ImmutableBitSet}: the index of
+   * the highest set bit in the {@code ImmutableBitSet} plus one. Returns zero
+   * if the {@code ImmutableBitSet} contains no set bits.
+   *
+   * @return the logical size of this {@code ImmutableBitSet}
+   */
+  public int length() {
+    if (words.length == 0) {
+      return 0;
+    }
+    return BITS_PER_WORD * (words.length - 1)
+        + (BITS_PER_WORD - Long.numberOfLeadingZeros(words[words.length - 1]));
+  }
+
+  /**
+   * Returns true if this {@code ImmutableBitSet} contains no bits that are set
+   * to {@code true}.
+   */
+  public boolean isEmpty() {
+    return words.length == 0;
+  }
+
+  public static Builder builder() {
+    return new Builder();
+  }
+
+  public static Builder builder(ImmutableBitSet bitSet) {
+    return new Builder(bitSet);
+  }
+
+  /** Returns the {@code n}th set bit.
+   *
+   * @throws java.lang.IndexOutOfBoundsException if n is less than 0 or greater
+   * than the number of bits set */
+  public int nth(int n) {
+    int start = 0;
+    for (long word : words) {
+      final int bitCount = Long.bitCount(word);
+      if (n < bitCount) {
+        while (word != 0) {
+          if ((word & 1) == 1) {
+            if (n == 0) {
+              return start;
+            }
+            --n;
+          }
+          word >>= 1;
+          ++start;
+        }
+      }
+      start += 64;
+      n -= bitCount;
+    }
+    throw new IndexOutOfBoundsException("index out of range: " + n);
+  }
+
+  /** Returns a bit set the same as this but with a given bit cleared. */
+  public ImmutableBitSet clear(int i) {
+    return except(ImmutableBitSet.of(i));
+  }
+
+  /** Returns a {@link BitSet} that has the same contents as this
+   * {@code ImmutableBitSet}. */
+  public BitSet toBitSet() {
+    return BitSets.of(this);
+  }
+
+  /**
+   * Setup equivalence Sets for each position. If i & 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
+   * greater than it. Once a closure is computed for a position, the closure
+   * Set is set on all its descendants. So the closure computation bubbles up
+   * from lower positions and the final equivalence Set is propagated down
+   * from the lowest element in the Set.
+   */
+  private static class Closure {
+    private SortedMap<Integer, ImmutableBitSet> equivalence;
+    private final SortedMap<Integer, ImmutableBitSet> closure =
+        Maps.newTreeMap();
+
+    public Closure(SortedMap<Integer, ImmutableBitSet> equivalence) {
+      this.equivalence = equivalence;
+      final ImmutableIntList keys =
+          ImmutableIntList.copyOf(equivalence.keySet());
+      for (int pos : keys) {
+        computeClosure(pos);
+      }
+    }
+
+    private ImmutableBitSet computeClosure(int pos) {
+      ImmutableBitSet o = closure.get(pos);
+      if (o != null) {
+        return o;
+      }
+      final ImmutableBitSet b = equivalence.get(pos);
+      o = b;
+      int i = b.nextSetBit(pos + 1);
+      for (; i >= 0; i = b.nextSetBit(i + 1)) {
+        o = o.union(computeClosure(i));
+      }
+      closure.put(pos, o);
+      i = o.nextSetBit(pos + 1);
+      for (; i >= 0; i = b.nextSetBit(i + 1)) {
+        closure.put(i, o);
+      }
+      return o;
+    }
+  }
+
+  /** Builder. */
+  public static class Builder {
+    private long[] words;
+
+    public Builder(ImmutableBitSet bitSet) {
+      words = bitSet.words.clone();
+    }
+
+    public Builder() {
+      words = EMPTY_LONGS;
+    }
+
+    /** Builds an ImmutableBitSet from the contents of this Builder.
+     *
+     * <p>After calling this method, the Builder cannot be used again. */
+    public ImmutableBitSet build() {
+      if (words.length == 0) {
+        return EMPTY;
+      }
+      long[] words = this.words;
+      this.words = null; // prevent re-use of builder
+      return new ImmutableBitSet(words);
+    }
+
+    /** Builds an ImmutableBitSet from the contents of this Builder, using
+     * an existing ImmutableBitSet if it happens to have the same contents.
+     *
+     * <p>Supplying the existing bit set if useful for set operations,
+     * where there is a significant chance that the original bit set is
+     * unchanged. We save memory because we use the same copy. For example:
+     *
+     * <blockquote><pre>
+     * ImmutableBitSet primeNumbers;
+     * ImmutableBitSet hundreds = ImmutableBitSet.of(100, 200, 300);
+     * return primeNumbers.except(hundreds);</pre></blockquote>
+     *
+     * <p>After calling this method, the Builder cannot be used again. */
+    public ImmutableBitSet build(ImmutableBitSet bitSet) {
+      if (wouldEqual(bitSet)) {
+        return bitSet;
+      }
+      return build();
+    }
+
+    public Builder set(int bit) {
+      if (words == null) {
+        throw new IllegalArgumentException("can only use builder once");
+      }
+      int wordIndex = wordIndex(bit);
+      if (wordIndex >= words.length) {
+        words = Arrays.copyOf(words, wordIndex + 1);
+      }
+      words[wordIndex] |= 1L << bit;
+      return this;
+    }
+
+    private void trim(int wordCount) {
+      while (wordCount > 0 && words[wordCount - 1] == 0L) {
+        --wordCount;
+      }
+      if (wordCount == words.length) {
+        return;
+      }
+      if (wordCount == 0) {
+        words = EMPTY_LONGS;
+      } else {
+        words = Arrays.copyOfRange(words, 0, wordCount);
+      }
+    }
+
+    public Builder clear(int bit) {
+      int wordIndex = wordIndex(bit);
+      if (wordIndex < words.length) {
+        words[wordIndex] &= ~(1L << bit);
+        trim(words.length);
+      }
+      return this;
+    }
+
+    /** Returns whether the bit set that would be created by this Builder would
+     * equal a given bit set. */
+    public boolean wouldEqual(ImmutableBitSet bitSet) {
+      if (words == null) {
+        throw new IllegalArgumentException("can only use builder once");
+      }
+      return Arrays.equals(words, bitSet.words);
+    }
+
+    /** Returns the number of set bits. */
+    public int cardinality() {
+      return countBits(words);
+    }
+
+    /** Sets all bits in a given bit set. */
+    public Builder addAll(ImmutableBitSet bitSet) {
+      for (Integer bit : bitSet) {
+        set(bit);
+      }
+      return this;
+    }
+
+    /** Sets all bits in a given list of bits. */
+    public Builder addAll(Iterable<Integer> integers) {
+      for (Integer integer : integers) {
+        set(integer);
+      }
+      return this;
+    }
+
+    /** Sets all bits in a given list of {@code int}s. */
+    public Builder addAll(ImmutableIntList integers) {
+      //noinspection ForLoopReplaceableByForEach
+      for (int i = 0; i < integers.size(); i++) {
+        set(integers.get(i));
+      }
+      return this;
+    }
+
+    /** Clears all bits in a given bit set. */
+    public Builder removeAll(ImmutableBitSet bitSet) {
+      for (Integer bit : bitSet) {
+        clear(bit);
+      }
+      return this;
+    }
+
+    /** Sets a range of bits, from {@code from} to {@code to} - 1. */
+    public Builder set(int fromIndex, int toIndex) {
+      if (fromIndex > toIndex) {
+        throw new IllegalArgumentException();
+      }
+      if (toIndex < 0) {
+        throw new IllegalArgumentException();
+      }
+      if (fromIndex < toIndex) {
+        // Increase capacity if necessary
+        int startWordIndex = wordIndex(fromIndex);
+        int endWordIndex   = wordIndex(toIndex - 1);
+        if (endWordIndex >= words.length) {
+          words = Arrays.copyOf(words, endWordIndex + 1);
+        }
+
+        long firstWordMask = WORD_MASK << fromIndex;
+        long lastWordMask  = WORD_MASK >>> -toIndex;
+        if (startWordIndex == endWordIndex) {
+          // One word
+          words[startWordIndex] |= firstWordMask & lastWordMask;
+        } else {
+          // First word, middle words, last word
+          words[startWordIndex] |= firstWordMask;
+          for (int i = startWordIndex + 1; i < endWordIndex; i++) {
+            words[i] = WORD_MASK;
+          }
+          words[endWordIndex] |= lastWordMask;
+        }
+      }
+      return this;
+    }
+
+    public boolean isEmpty() {
+      return words.length == 0;
+    }
+
+    public void intersect(ImmutableBitSet that) {
+      int x = Math.min(words.length, that.words.length);
+      for (int i = 0; i < x; i++) {
+        words[i] &= that.words[i];
+      }
+      trim(x);
+    }
+  }
+}
+
+// End ImmutableBitSet.java

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/main/java/org/apache/calcite/util/mapping/Mappings.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/util/mapping/Mappings.java b/core/src/main/java/org/apache/calcite/util/mapping/Mappings.java
index 8d9733b..8c16163 100644
--- a/core/src/main/java/org/apache/calcite/util/mapping/Mappings.java
+++ b/core/src/main/java/org/apache/calcite/util/mapping/Mappings.java
@@ -17,6 +17,7 @@
 package org.apache.calcite.util.mapping;
 
 import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.IntList;
 import org.apache.calcite.util.Permutation;
 import org.apache.calcite.util.Util;
@@ -188,6 +189,28 @@ public abstract class Mappings {
   }
 
   /**
+   * Applies a mapping to an {@code ImmutableBitSet}.
+   *
+   * <p>If the mapping does not affect the bit set, returns the original.
+   * Never changes the original.
+   *
+   * @param mapping Mapping
+   * @param bitSet  Bit set
+   * @return Bit set with mapping applied
+   */
+  public static ImmutableBitSet apply(Mapping mapping, ImmutableBitSet bitSet) {
+    final ImmutableBitSet.Builder builder = ImmutableBitSet.builder();
+    for (int source : bitSet) {
+      final int target = mapping.getTarget(source);
+      builder.set(target);
+    }
+    if (builder.wouldEqual(bitSet)) {
+      return bitSet;
+    }
+    return builder.build();
+  }
+
+  /**
    * Applies a mapping to a list.
    *
    * @param mapping Mapping

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/test/java/org/apache/calcite/plan/RelWriterTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/plan/RelWriterTest.java b/core/src/test/java/org/apache/calcite/plan/RelWriterTest.java
index 5ef1877..6dc6aa4 100644
--- a/core/src/test/java/org/apache/calcite/plan/RelWriterTest.java
+++ b/core/src/test/java/org/apache/calcite/plan/RelWriterTest.java
@@ -32,7 +32,7 @@ import org.apache.calcite.sql.fun.SqlStdOperatorTable;
 import org.apache.calcite.sql.type.SqlTypeName;
 import org.apache.calcite.test.JdbcTest;
 import org.apache.calcite.tools.Frameworks;
-import org.apache.calcite.util.BitSets;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.Util;
 
 import com.google.common.collect.ImmutableList;
@@ -138,7 +138,7 @@ public class RelWriterTest {
                 final RelDataType bigIntType =
                     cluster.getTypeFactory().createSqlType(SqlTypeName.BIGINT);
                 LogicalAggregate aggregate =
-                    new LogicalAggregate(cluster, filter, BitSets.of(0),
+                    new LogicalAggregate(cluster, filter, ImmutableBitSet.of(0),
                         ImmutableList.of(
                             new AggregateCall(SqlStdOperatorTable.COUNT,
                                 true, ImmutableList.of(1), bigIntType, "c"),

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/test/java/org/apache/calcite/test/CalciteSuite.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/CalciteSuite.java b/core/src/test/java/org/apache/calcite/test/CalciteSuite.java
index 3a3ec53..081ac93 100644
--- a/core/src/test/java/org/apache/calcite/test/CalciteSuite.java
+++ b/core/src/test/java/org/apache/calcite/test/CalciteSuite.java
@@ -33,6 +33,7 @@ import org.apache.calcite.tools.FrameworksTest;
 import org.apache.calcite.tools.PlannerTest;
 import org.apache.calcite.util.BitSetsTest;
 import org.apache.calcite.util.ChunkListTest;
+import org.apache.calcite.util.ImmutableBitSetTest;
 import org.apache.calcite.util.PartiallyOrderedSetTest;
 import org.apache.calcite.util.PermutationTestCase;
 import org.apache.calcite.util.ReflectVisitorTest;
@@ -57,6 +58,7 @@ import org.junit.runners.Suite;
     // very fast tests (under 0.1s)
     ArrayTableTest.class,
     BitSetsTest.class,
+    ImmutableBitSetTest.class,
     DirectedGraphTest.class,
     ReflectVisitorTest.class,
     RelOptUtilTest.class,

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/test/java/org/apache/calcite/test/MockCatalogReader.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/MockCatalogReader.java b/core/src/test/java/org/apache/calcite/test/MockCatalogReader.java
index 7abe734..f915e1b 100644
--- a/core/src/test/java/org/apache/calcite/test/MockCatalogReader.java
+++ b/core/src/test/java/org/apache/calcite/test/MockCatalogReader.java
@@ -41,6 +41,7 @@ import org.apache.calcite.sql.validate.SqlMonikerType;
 import org.apache.calcite.sql.validate.SqlMonotonicity;
 import org.apache.calcite.sql.validate.SqlValidatorCatalogReader;
 import org.apache.calcite.sql.validate.SqlValidatorUtil;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.Pair;
 import org.apache.calcite.util.Util;
 
@@ -49,7 +50,6 @@ import com.google.common.collect.Ordering;
 
 import java.util.ArrayList;
 import java.util.Arrays;
-import java.util.BitSet;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.List;
@@ -401,7 +401,7 @@ public class MockCatalogReader implements Prepare.CatalogReader {
       return collationList;
     }
 
-    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/test/java/org/apache/calcite/test/RelMetadataTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java b/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java
index 41caea0..67b30de 100644
--- a/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java
+++ b/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java
@@ -30,6 +30,7 @@ import org.apache.calcite.rel.metadata.ReflectiveRelMetadataProvider;
 import org.apache.calcite.rel.metadata.RelColumnOrigin;
 import org.apache.calcite.rel.metadata.RelMetadataProvider;
 import org.apache.calcite.rel.metadata.RelMetadataQuery;
+import org.apache.calcite.util.ImmutableBitSet;
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
@@ -41,7 +42,6 @@ import org.junit.Test;
 
 import java.lang.reflect.Method;
 import java.util.ArrayList;
-import java.util.BitSet;
 import java.util.List;
 import java.util.Set;
 
@@ -539,7 +539,7 @@ public class RelMetadataTest extends SqlToRelTestBase {
   @Test public void testDistinctRowCountTable() {
     // no unique key information is available so return null
     RelNode rel = convertSql("select * from emp where deptno = 10");
-    BitSet groupKey = new BitSet();
+    ImmutableBitSet groupKey = ImmutableBitSet.of();
     Double result =
         RelMetadataQuery.getDistinctRowCount(
             rel, groupKey, null);

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/test/java/org/apache/calcite/test/RexProgramTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/RexProgramTest.java b/core/src/test/java/org/apache/calcite/test/RexProgramTest.java
index d1d0bae..aaa6b01 100644
--- a/core/src/test/java/org/apache/calcite/test/RexProgramTest.java
+++ b/core/src/test/java/org/apache/calcite/test/RexProgramTest.java
@@ -34,7 +34,7 @@ import org.apache.calcite.rex.RexProgramBuilder;
 import org.apache.calcite.rex.RexUtil;
 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.TestUtil;
 import org.apache.calcite.util.Util;
 
@@ -46,7 +46,6 @@ import org.junit.Test;
 
 import java.math.BigDecimal;
 import java.util.Arrays;
-import java.util.BitSet;
 import java.util.List;
 
 import static org.hamcrest.CoreMatchers.equalTo;
@@ -322,7 +321,7 @@ public class RexProgramTest {
     return builder;
   }
 
-  static boolean strongIf(RexNode e, BitSet b) {
+  static boolean strongIf(RexNode e, ImmutableBitSet b) {
     return Strong.is(e, b);
   }
 
@@ -330,11 +329,11 @@ public class RexProgramTest {
   @Test public void testStrong() {
     final RelDataType intType = typeFactory.createSqlType(SqlTypeName.INTEGER);
 
-    final BitSet c = BitSets.of();
-    final BitSet c0 = BitSets.of(0);
-    final BitSet c1 = BitSets.of(1);
-    final BitSet c01 = BitSets.of(0, 1);
-    final BitSet c13 = BitSets.of(1, 3);
+    final ImmutableBitSet c = ImmutableBitSet.of();
+    final ImmutableBitSet c0 = ImmutableBitSet.of(0);
+    final ImmutableBitSet c1 = ImmutableBitSet.of(1);
+    final ImmutableBitSet c01 = ImmutableBitSet.of(0, 1);
+    final ImmutableBitSet c13 = ImmutableBitSet.of(1, 3);
 
     // input ref
     final RexInputRef aRef = rexBuilder.makeInputRef(intType, 0);

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/b9d8de38/core/src/test/java/org/apache/calcite/test/SqlToRelTestBase.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/SqlToRelTestBase.java b/core/src/test/java/org/apache/calcite/test/SqlToRelTestBase.java
index ab2cd05..1d88316 100644
--- a/core/src/test/java/org/apache/calcite/test/SqlToRelTestBase.java
+++ b/core/src/test/java/org/apache/calcite/test/SqlToRelTestBase.java
@@ -47,6 +47,7 @@ import org.apache.calcite.sql.validate.SqlValidatorTable;
 import org.apache.calcite.sql2rel.RelFieldTrimmer;
 import org.apache.calcite.sql2rel.SqlToRelConverter;
 import org.apache.calcite.sql2rel.StandardConvertletTable;
+import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.Util;
 
 import com.google.common.base.Function;
@@ -54,7 +55,6 @@ import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
 
 import java.util.ArrayList;
-import java.util.BitSet;
 import java.util.List;
 
 import static org.junit.Assert.assertEquals;
@@ -353,7 +353,7 @@ public abstract class SqlToRelTestBase {
         return collationList;
       }
 
-      public boolean isKey(BitSet columns) {
+      public boolean isKey(ImmutableBitSet columns) {
         return false;
       }
 
@@ -406,7 +406,7 @@ public abstract class SqlToRelTestBase {
       return parent.getCollationList();
     }
 
-    public boolean isKey(BitSet columns) {
+    public boolean isKey(ImmutableBitSet columns) {
       return parent.isKey(columns);
     }
   }


Mime
View raw message