You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by sl...@apache.org on 2015/11/24 15:17:39 UTC
cassandra git commit: Optimize MultiCBuilder when there is no IN
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 <sy...@datastax.com>
Authored: Thu Sep 24 10:22:50 2015 -0700
Committer: Sylvain Lebresne <sy...@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);
}
}