cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From slebre...@apache.org
Subject cassandra git commit: Optimize MultiCBuilder when there is no IN
Date Tue, 24 Nov 2015 14:17:39 GMT
Repository: cassandra
Updated Branches:
  refs/heads/trunk 1a694a9fd -> 958aa7c95


Optimize MultiCBuilder when there is no IN

patch by slebresne; reviewed by blerer for CASSANDRA-10409


Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo
Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/958aa7c9
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/958aa7c9
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/958aa7c9

Branch: refs/heads/trunk
Commit: 958aa7c959cb6c2bca4ed62d78974e83a5371787
Parents: 1a694a9
Author: Sylvain Lebresne <sylvain@datastax.com>
Authored: Thu Sep 24 10:22:50 2015 -0700
Committer: Sylvain Lebresne <sylvain@datastax.com>
Committed: Tue Nov 24 15:17:30 2015 +0100

----------------------------------------------------------------------
 CHANGES.txt                                     |   1 +
 .../restrictions/PrimaryKeyRestrictionSet.java  |  18 +-
 .../cql3/restrictions/RestrictionSet.java       |   4 +-
 .../org/apache/cassandra/db/MultiCBuilder.java  | 414 ++++++++++++-------
 .../apache/cassandra/utils/btree/BTreeSet.java  |   2 +-
 5 files changed, 274 insertions(+), 165 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/cassandra/blob/958aa7c9/CHANGES.txt
----------------------------------------------------------------------
diff --git a/CHANGES.txt b/CHANGES.txt
index a468077..dd17f11 100644
--- a/CHANGES.txt
+++ b/CHANGES.txt
@@ -1,4 +1,5 @@
 3.2
+ * Optimize building of Clustering object when only one is created (CASSANDRA-10409)
  * Make index building pluggable (CASSANDRA-10681)
  * Add sstable flush observer (CASSANDRA-10678)
  * Improve NTS endpoints calculation (CASSANDRA-10200)

http://git-wip-us.apache.org/repos/asf/cassandra/blob/958aa7c9/src/java/org/apache/cassandra/cql3/restrictions/PrimaryKeyRestrictionSet.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/cql3/restrictions/PrimaryKeyRestrictionSet.java
b/src/java/org/apache/cassandra/cql3/restrictions/PrimaryKeyRestrictionSet.java
index 107cbd1..0730593 100644
--- a/src/java/org/apache/cassandra/cql3/restrictions/PrimaryKeyRestrictionSet.java
+++ b/src/java/org/apache/cassandra/cql3/restrictions/PrimaryKeyRestrictionSet.java
@@ -175,10 +175,24 @@ final class PrimaryKeyRestrictionSet extends AbstractPrimaryKeyRestrictions
         return new PrimaryKeyRestrictionSet(this, restriction);
     }
 
+    // Whether any of the underlying restriction is an IN
+    private boolean hasIN()
+    {
+        if (isIN())
+            return true;
+
+        for (Restriction restriction : restrictions)
+        {
+            if (restriction.isIN())
+                return true;
+        }
+        return false;
+    }
+
     @Override
     public NavigableSet<Clustering> valuesAsClustering(QueryOptions options) throws
InvalidRequestException
     {
-        return appendTo(MultiCBuilder.create(comparator), options).build();
+        return appendTo(MultiCBuilder.create(comparator, hasIN()), options).build();
     }
 
     @Override
@@ -202,7 +216,7 @@ final class PrimaryKeyRestrictionSet extends AbstractPrimaryKeyRestrictions
     @Override
     public NavigableSet<Slice.Bound> boundsAsClustering(Bound bound, QueryOptions options)
throws InvalidRequestException
     {
-        MultiCBuilder builder = MultiCBuilder.create(comparator);
+        MultiCBuilder builder = MultiCBuilder.create(comparator, hasIN());
         int keyPosition = 0;
         for (Restriction r : restrictions)
         {

http://git-wip-us.apache.org/repos/asf/cassandra/blob/958aa7c9/src/java/org/apache/cassandra/cql3/restrictions/RestrictionSet.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/cql3/restrictions/RestrictionSet.java b/src/java/org/apache/cassandra/cql3/restrictions/RestrictionSet.java
index 700840d..ccab2dc 100644
--- a/src/java/org/apache/cassandra/cql3/restrictions/RestrictionSet.java
+++ b/src/java/org/apache/cassandra/cql3/restrictions/RestrictionSet.java
@@ -96,13 +96,13 @@ final class RestrictionSet implements Restrictions, Iterable<Restriction>
     @Override
     public final boolean isEmpty()
     {
-        return getColumnDefs().isEmpty();
+        return restrictions.isEmpty();
     }
 
     @Override
     public final int size()
     {
-        return getColumnDefs().size();
+        return restrictions.size();
     }
 
     /**

http://git-wip-us.apache.org/repos/asf/cassandra/blob/958aa7c9/src/java/org/apache/cassandra/db/MultiCBuilder.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/MultiCBuilder.java b/src/java/org/apache/cassandra/db/MultiCBuilder.java
index be654fa..8353703 100644
--- a/src/java/org/apache/cassandra/db/MultiCBuilder.java
+++ b/src/java/org/apache/cassandra/db/MultiCBuilder.java
@@ -26,44 +26,39 @@ import org.apache.cassandra.utils.btree.BTreeSet;
 /**
  * Builder that allow to build multiple Clustering/Slice.Bound at the same time.
  */
-public class MultiCBuilder
+public abstract class MultiCBuilder
 {
     /**
      * The table comparator.
      */
-    private final ClusteringComparator comparator;
+    protected final ClusteringComparator comparator;
 
     /**
-     * The elements of the clusterings
+     * The number of clustering elements that have been added.
      */
-    private final List<List<ByteBuffer>> elementsList = new ArrayList<>();
-
-    /**
-     * The number of elements that have been added.
-     */
-    private int size;
+    protected int size;
 
     /**
      * <code>true</code> if the clusterings have been build, <code>false</code>
otherwise.
      */
-    private boolean built;
+    protected boolean built;
 
     /**
      * <code>true</code> if the clusterings contains some <code>null</code>
elements.
      */
-    private boolean containsNull;
+    protected boolean containsNull;
 
     /**
      * <code>true</code> if the composites contains some <code>unset</code>
elements.
      */
-    private boolean containsUnset;
+    protected boolean containsUnset;
 
     /**
      * <code>true</code> if some empty collection have been added.
      */
-    private boolean hasMissingElements;
+    protected boolean hasMissingElements;
 
-    private MultiCBuilder(ClusteringComparator comparator)
+    protected MultiCBuilder(ClusteringComparator comparator)
     {
         this.comparator = comparator;
     }
@@ -71,19 +66,11 @@ public class MultiCBuilder
     /**
      * Creates a new empty {@code MultiCBuilder}.
      */
-    public static MultiCBuilder create(ClusteringComparator comparator)
-    {
-        return new MultiCBuilder(comparator);
-    }
-
-    /**
-     * Checks if this builder is empty.
-     *
-     * @return <code>true</code> if this builder is empty, <code>false</code>
otherwise.
-     */
-    private boolean isEmpty()
+    public static MultiCBuilder create(ClusteringComparator comparator, boolean forMultipleValues)
     {
-        return elementsList.isEmpty();
+        return forMultipleValues
+             ? new MultiClusteringBuilder(comparator)
+             : new OneClusteringBuilder(comparator);
     }
 
     /**
@@ -96,25 +83,7 @@ public class MultiCBuilder
      * @param value the value of the next element
      * @return this <code>MulitCBuilder</code>
      */
-    public MultiCBuilder addElementToAll(ByteBuffer value)
-    {
-        checkUpdateable();
-
-        if (isEmpty())
-            elementsList.add(new ArrayList<ByteBuffer>());
-
-        for (int i = 0, m = elementsList.size(); i < m; i++)
-        {
-            if (value == null)
-                containsNull = true;
-            if (value == ByteBufferUtil.UNSET_BYTE_BUFFER)
-                containsUnset = true;
-
-            elementsList.get(i).add(value);
-        }
-        size++;
-        return this;
-    }
+    public abstract MultiCBuilder addElementToAll(ByteBuffer value);
 
     /**
      * Adds individually each of the specified elements to the end of all of the existing
clusterings.
@@ -126,42 +95,7 @@ public class MultiCBuilder
      * @param values the elements to add
      * @return this <code>CompositeBuilder</code>
      */
-    public MultiCBuilder addEachElementToAll(List<ByteBuffer> values)
-    {
-        checkUpdateable();
-
-        if (isEmpty())
-            elementsList.add(new ArrayList<ByteBuffer>());
-
-        if (values.isEmpty())
-        {
-            hasMissingElements = true;
-        }
-        else
-        {
-            for (int i = 0, m = elementsList.size(); i < m; i++)
-            {
-                List<ByteBuffer> oldComposite = elementsList.remove(0);
-
-                for (int j = 0, n = values.size(); j < n; j++)
-                {
-                    List<ByteBuffer> newComposite = new ArrayList<>(oldComposite);
-                    elementsList.add(newComposite);
-
-                    ByteBuffer value = values.get(j);
-
-                    if (value == null)
-                        containsNull = true;
-                    if (value == ByteBufferUtil.UNSET_BYTE_BUFFER)
-                        containsUnset = true;
-
-                    newComposite.add(values.get(j));
-                }
-            }
-        }
-        size++;
-        return this;
-    }
+    public abstract MultiCBuilder addEachElementToAll(List<ByteBuffer> values);
 
     /**
      * Adds individually each of the specified list of elements to the end of all of the
existing composites.
@@ -173,44 +107,12 @@ public class MultiCBuilder
      * @param values the elements to add
      * @return this <code>CompositeBuilder</code>
      */
-    public MultiCBuilder addAllElementsToAll(List<List<ByteBuffer>> values)
-    {
-        checkUpdateable();
-
-        if (isEmpty())
-            elementsList.add(new ArrayList<ByteBuffer>());
-
-        if (values.isEmpty())
-        {
-            hasMissingElements = true;
-        }
-        else
-        {
-            for (int i = 0, m = elementsList.size(); i < m; i++)
-            {
-                List<ByteBuffer> oldComposite = elementsList.remove(0);
+    public abstract MultiCBuilder addAllElementsToAll(List<List<ByteBuffer>>
values);
 
-                for (int j = 0, n = values.size(); j < n; j++)
-                {
-                    List<ByteBuffer> newComposite = new ArrayList<>(oldComposite);
-                    elementsList.add(newComposite);
-
-                    List<ByteBuffer> value = values.get(j);
-
-                    if (value.isEmpty())
-                        hasMissingElements = true;
-
-                    if (value.contains(null))
-                        containsNull = true;
-                    if (value.contains(ByteBufferUtil.UNSET_BYTE_BUFFER))
-                        containsUnset = true;
-
-                    newComposite.addAll(value);
-                }
-            }
-            size += values.get(0).size();
-        }
-        return this;
+    protected void checkUpdateable()
+    {
+        if (!hasRemaining() || built)
+            throw new IllegalStateException("this builder cannot be updated anymore");
     }
 
     /**
@@ -257,68 +159,260 @@ public class MultiCBuilder
      *
      * @return the clusterings
      */
-    public NavigableSet<Clustering> build()
+    public abstract NavigableSet<Clustering> build();
+
+    /**
+     * Builds the <code>clusterings</code> with the specified EOC.
+     *
+     * @return the clusterings
+     */
+    public abstract NavigableSet<Slice.Bound> buildBound(boolean isStart, boolean isInclusive);
+
+    /**
+     * Checks if some elements can still be added to the clusterings.
+     *
+     * @return <code>true</code> if it is possible to add more elements to the
clusterings, <code>false</code> otherwise.
+     */
+    public boolean hasRemaining()
     {
-        built = true;
+        return remainingCount() > 0;
+    }
 
-        if (hasMissingElements)
-            return BTreeSet.empty(comparator);
+    /**
+     * Specialization of MultiCBuilder when we know only one clustering/bound is created.
+     */
+    private static class OneClusteringBuilder extends MultiCBuilder
+    {
+        /**
+         * The elements of the clusterings
+         */
+        private final ByteBuffer[] elements;
+
+        public OneClusteringBuilder(ClusteringComparator comparator)
+        {
+            super(comparator);
+            this.elements = new ByteBuffer[comparator.size()];
+        }
+
+        public MultiCBuilder addElementToAll(ByteBuffer value)
+        {
+            checkUpdateable();
 
-        CBuilder builder = CBuilder.create(comparator);
+            if (value == null)
+                containsNull = true;
+            if (value == ByteBufferUtil.UNSET_BYTE_BUFFER)
+                containsUnset = true;
 
-        if (elementsList.isEmpty())
-            return BTreeSet.of(builder.comparator(), builder.build());
+            elements[size++] = value;
+            return this;
+        }
 
-        BTreeSet.Builder<Clustering> set = BTreeSet.builder(builder.comparator());
-        for (int i = 0, m = elementsList.size(); i < m; i++)
+        public MultiCBuilder addEachElementToAll(List<ByteBuffer> values)
         {
-            List<ByteBuffer> elements = elementsList.get(i);
-            set.add(builder.buildWith(elements));
+            if (values.isEmpty())
+            {
+                hasMissingElements = true;
+                return this;
+            }
+
+            assert values.size() == 1;
+
+            return addElementToAll(values.get(0));
         }
-        return set.build();
-    }
 
-    /**
-     * Builds the <code>clusterings</code> with the specified EOC.
-     *
-     * @return the clusterings
-     */
-    public NavigableSet<Slice.Bound> buildBound(boolean isStart, boolean isInclusive)
-    {
-        built = true;
+        public MultiCBuilder addAllElementsToAll(List<List<ByteBuffer>> values)
+        {
+            if (values.isEmpty())
+            {
+                hasMissingElements = true;
+                return this;
+            }
 
-        if (hasMissingElements)
-            return BTreeSet.empty(comparator);
+            assert values.size() == 1;
+            return addEachElementToAll(values.get(0));
+        }
 
-        CBuilder builder = CBuilder.create(comparator);
+        public NavigableSet<Clustering> build()
+        {
+            built = true;
 
-        if (elementsList.isEmpty())
-            return BTreeSet.of(comparator, builder.buildBound(isStart, isInclusive));
+            if (hasMissingElements)
+                return BTreeSet.empty(comparator);
 
-        // Use a TreeSet to sort and eliminate duplicates
-        BTreeSet.Builder<Slice.Bound> set = BTreeSet.builder(comparator);
+            return BTreeSet.of(comparator, size == 0 ? Clustering.EMPTY : new Clustering(elements));
+        }
 
-        for (int i = 0, m = elementsList.size(); i < m; i++)
+        public NavigableSet<Slice.Bound> buildBound(boolean isStart, boolean isInclusive)
         {
-            List<ByteBuffer> elements = elementsList.get(i);
-            set.add(builder.buildBoundWith(elements, isStart, isInclusive));
+            built = true;
+
+            if (hasMissingElements)
+                return BTreeSet.empty(comparator);
+
+            if (size == 0)
+                return BTreeSet.of(comparator, isStart ? Slice.Bound.BOTTOM : Slice.Bound.TOP);
+
+            ByteBuffer[] newValues = size == elements.length
+                                   ? elements
+                                   : Arrays.copyOf(elements, size);
+
+            return BTreeSet.of(comparator, Slice.Bound.create(Slice.Bound.boundKind(isStart,
isInclusive), newValues));
         }
-        return set.build();
     }
 
     /**
-     * Checks if some elements can still be added to the clusterings.
-     *
-     * @return <code>true</code> if it is possible to add more elements to the
clusterings, <code>false</code> otherwise.
+     * MultiCBuilder implementation actually supporting the creation of multiple clustering/bound.
      */
-    public boolean hasRemaining()
+    private static class MultiClusteringBuilder extends MultiCBuilder
     {
-        return remainingCount() > 0;
-    }
+        /**
+         * The elements of the clusterings
+         */
+        private final List<List<ByteBuffer>> elementsList = new ArrayList<>();
 
-    private void checkUpdateable()
-    {
-        if (!hasRemaining() || built)
-            throw new IllegalStateException("this builder cannot be updated anymore");
+        public MultiClusteringBuilder(ClusteringComparator comparator)
+        {
+            super(comparator);
+        }
+
+        public MultiCBuilder addElementToAll(ByteBuffer value)
+        {
+            checkUpdateable();
+
+            if (elementsList.isEmpty())
+                elementsList.add(new ArrayList<ByteBuffer>());
+
+            if (value == null)
+                containsNull = true;
+            else if (value == ByteBufferUtil.UNSET_BYTE_BUFFER)
+                containsUnset = true;
+
+            for (int i = 0, m = elementsList.size(); i < m; i++)
+                elementsList.get(i).add(value);
+
+            size++;
+            return this;
+        }
+
+        public MultiCBuilder addEachElementToAll(List<ByteBuffer> values)
+        {
+            checkUpdateable();
+
+            if (elementsList.isEmpty())
+                elementsList.add(new ArrayList<ByteBuffer>());
+
+            if (values.isEmpty())
+            {
+                hasMissingElements = true;
+            }
+            else
+            {
+                for (int i = 0, m = elementsList.size(); i < m; i++)
+                {
+                    List<ByteBuffer> oldComposite = elementsList.remove(0);
+
+                    for (int j = 0, n = values.size(); j < n; j++)
+                    {
+                        List<ByteBuffer> newComposite = new ArrayList<>(oldComposite);
+                        elementsList.add(newComposite);
+
+                        ByteBuffer value = values.get(j);
+
+                        if (value == null)
+                            containsNull = true;
+                        if (value == ByteBufferUtil.UNSET_BYTE_BUFFER)
+                            containsUnset = true;
+
+                        newComposite.add(values.get(j));
+                    }
+                }
+            }
+            size++;
+            return this;
+        }
+
+        public MultiCBuilder addAllElementsToAll(List<List<ByteBuffer>> values)
+        {
+            checkUpdateable();
+
+            if (elementsList.isEmpty())
+                elementsList.add(new ArrayList<ByteBuffer>());
+
+            if (values.isEmpty())
+            {
+                hasMissingElements = true;
+            }
+            else
+            {
+                for (int i = 0, m = elementsList.size(); i < m; i++)
+                {
+                    List<ByteBuffer> oldComposite = elementsList.remove(0);
+
+                    for (int j = 0, n = values.size(); j < n; j++)
+                    {
+                        List<ByteBuffer> newComposite = new ArrayList<>(oldComposite);
+                        elementsList.add(newComposite);
+
+                        List<ByteBuffer> value = values.get(j);
+
+                        if (value.isEmpty())
+                            hasMissingElements = true;
+
+                        if (value.contains(null))
+                            containsNull = true;
+                        if (value.contains(ByteBufferUtil.UNSET_BYTE_BUFFER))
+                            containsUnset = true;
+
+                        newComposite.addAll(value);
+                    }
+                }
+                size += values.get(0).size();
+            }
+            return this;
+        }
+
+        public NavigableSet<Clustering> build()
+        {
+            built = true;
+
+            if (hasMissingElements)
+                return BTreeSet.empty(comparator);
+
+            CBuilder builder = CBuilder.create(comparator);
+
+            if (elementsList.isEmpty())
+                return BTreeSet.of(builder.comparator(), builder.build());
+
+            BTreeSet.Builder<Clustering> set = BTreeSet.builder(builder.comparator());
+            for (int i = 0, m = elementsList.size(); i < m; i++)
+            {
+                List<ByteBuffer> elements = elementsList.get(i);
+                set.add(builder.buildWith(elements));
+            }
+            return set.build();
+        }
+
+        public NavigableSet<Slice.Bound> buildBound(boolean isStart, boolean isInclusive)
+        {
+            built = true;
+
+            if (hasMissingElements)
+                return BTreeSet.empty(comparator);
+
+            CBuilder builder = CBuilder.create(comparator);
+
+            if (elementsList.isEmpty())
+                return BTreeSet.of(comparator, builder.buildBound(isStart, isInclusive));
+
+            // Use a TreeSet to sort and eliminate duplicates
+            BTreeSet.Builder<Slice.Bound> set = BTreeSet.builder(comparator);
+
+            for (int i = 0, m = elementsList.size(); i < m; i++)
+            {
+                List<ByteBuffer> elements = elementsList.get(i);
+                set.add(builder.buildBoundWith(elements, isStart, isInclusive));
+            }
+            return set.build();
+        }
     }
 }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/958aa7c9/src/java/org/apache/cassandra/utils/btree/BTreeSet.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/utils/btree/BTreeSet.java b/src/java/org/apache/cassandra/utils/btree/BTreeSet.java
index 03fa1ec..9517009 100644
--- a/src/java/org/apache/cassandra/utils/btree/BTreeSet.java
+++ b/src/java/org/apache/cassandra/utils/btree/BTreeSet.java
@@ -639,6 +639,6 @@ public class BTreeSet<V> implements NavigableSet<V>, List<V>
 
     public static <V> BTreeSet<V> of(Comparator<? super V> comparator,
V value)
     {
-        return new BTreeSet<>(BTree.build(ImmutableList.of(value), UpdateFunction.<V>noOp()),
comparator);
+        return new BTreeSet<>(BTree.singleton(value), comparator);
     }
 }


Mime
View raw message