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 <[email protected]> Authored: Thu Sep 24 10:22:50 2015 -0700 Committer: Sylvain Lebresne <[email protected]> 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); } }
