Updated Branches: refs/heads/cassandra-1.1 aa2c28ead -> 4fd6fe3fa
(cql3) Support ORDER BY when IN condition is given in WHERE clause patch by Pavel Yaskevich; reviewed by Jonathan Ellis for CASSANDRA-4327 Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/4fd6fe3f Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/4fd6fe3f Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/4fd6fe3f Branch: refs/heads/cassandra-1.1 Commit: 4fd6fe3fa6a1371f5f9c16a7199fbf81320d98c7 Parents: aa2c28e Author: Pavel Yaskevich <xe...@apache.org> Authored: Thu Jul 5 15:14:57 2012 +0300 Committer: Pavel Yaskevich <xe...@apache.org> Committed: Sat Jul 7 02:15:19 2012 +0300 ---------------------------------------------------------------------- CHANGES.txt | 1 + .../cassandra/cql3/statements/SelectStatement.java | 124 ++++++++++++-- 2 files changed, 107 insertions(+), 18 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/cassandra/blob/4fd6fe3f/CHANGES.txt ---------------------------------------------------------------------- diff --git a/CHANGES.txt b/CHANGES.txt index 1857671..15a1a30 100644 --- a/CHANGES.txt +++ b/CHANGES.txt @@ -7,6 +7,7 @@ from row cache during compaction (CASSANDRA-4364) * (stress) support for CQL prepared statements (CASSANDRA-3633) * Correctly catch exception when Snappy cannot be loaded (CASSANDRA-4400) + * (cql3) Support ORDER BY when IN condition is given in WHERE clause (CASSANDRA-4327) Merged from 1.0: * allow dropping columns shadowed by not-yet-expired supercolumn or row tombstones in PrecompactedRow (CASSANDRA-4396) http://git-wip-us.apache.org/repos/asf/cassandra/blob/4fd6fe3f/src/java/org/apache/cassandra/cql3/statements/SelectStatement.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/cql3/statements/SelectStatement.java b/src/java/org/apache/cassandra/cql3/statements/SelectStatement.java index 2f121e3..0c34eb0 100644 --- a/src/java/org/apache/cassandra/cql3/statements/SelectStatement.java +++ b/src/java/org/apache/cassandra/cql3/statements/SelectStatement.java @@ -30,17 +30,7 @@ import org.slf4j.LoggerFactory; import org.apache.cassandra.auth.Permission; import org.apache.cassandra.cql3.*; import org.apache.cassandra.config.CFMetaData; -import org.apache.cassandra.db.IColumn; -import org.apache.cassandra.db.CounterColumn; -import org.apache.cassandra.db.ColumnFamily; -import org.apache.cassandra.db.ExpiringColumn; -import org.apache.cassandra.db.RangeSliceCommand; -import org.apache.cassandra.db.ReadCommand; -import org.apache.cassandra.db.Row; -import org.apache.cassandra.db.RowPosition; -import org.apache.cassandra.db.SliceByNamesReadCommand; -import org.apache.cassandra.db.SliceFromReadCommand; -import org.apache.cassandra.db.Table; +import org.apache.cassandra.db.*; import org.apache.cassandra.db.context.CounterContext; import org.apache.cassandra.db.filter.QueryPath; import org.apache.cassandra.db.marshal.AbstractType; @@ -814,6 +804,8 @@ public class SelectStatement implements CQLStatement } } + orderResults(cqlRows); + // Internal calls always return columns in the comparator order, even when reverse was set if (isReversed) Collections.reverse(cqlRows); @@ -825,6 +817,48 @@ public class SelectStatement implements CQLStatement } /** + * Orders results when multiple keys are selected (using IN) + */ + private void orderResults(List<CqlRow> cqlRows) + { + // There is nothing to do if + // a. there are no results, + // b. no ordering information where given, + // c. key restriction wasn't given or it's not an IN expression + if (cqlRows.isEmpty() || parameters.orderings.isEmpty() || keyRestriction == null || keyRestriction.eqValues.size() < 2) + return; + + // optimization when only *one* order condition was given + // because there is no point of using composite comparator if there is only one order condition + if (parameters.orderings.size() == 1) + { + CFDefinition.Name ordering = cfDef.get(parameters.orderings.keySet().iterator().next()); + Collections.sort(cqlRows, new SingleColumnComparator(ordering.position + 1, ordering.type)); + return; + } + + // figures out where ordering would start in results (startPosition), + // builds a composite type for multi-column comparison from the comparators of the ordering components + // and passes collected position information and built composite comparator to CompositeComparator to do + // an actual comparison of the CQL rows. + int startPosition = -1; + List<AbstractType<?>> types = new ArrayList<AbstractType<?>>(); + + for (ColumnIdentifier identifier : parameters.orderings.keySet()) + { + CFDefinition.Name orderingColumn = cfDef.get(identifier); + + if (startPosition == -1) + startPosition = orderingColumn.position + 1; + + types.add(orderingColumn.type); + } + + Collections.sort(cqlRows, new CompositeComparator(startPosition, types)); + } + + + /** * For sparse composite, returns wheter two columns belong to the same * cqlRow base on the full list of component in the name. * Two columns do belong together if they differ only by the last @@ -1036,6 +1070,9 @@ public class SelectStatement implements CQLStatement if (!stmt.parameters.orderings.isEmpty()) { + if (whereClause.isEmpty()) + throw new InvalidRequestException("ORDER BY is only supported in combination with WHERE clause."); + Boolean[] reversedMap = new Boolean[cfDef.columns.size()]; int i = 0; for (Map.Entry<ColumnIdentifier, Boolean> entry : stmt.parameters.orderings.entrySet()) @@ -1074,13 +1111,6 @@ public class SelectStatement implements CQLStatement } assert isReversed != null; stmt.isReversed = isReversed; - - // Only allow ordering if the row key restriction is an equality, - // since otherwise the order will be primarily on the row key. - // TODO: we could allow ordering for IN queries, as we can do the - // sorting post-query easily, but we will have to add it - if (stmt.keyRestriction == null || !stmt.keyRestriction.isEquality() || stmt.keyRestriction.eqValues.size() != 1) - throw new InvalidRequestException("Ordering is only supported if the first part of the PRIMARY KEY is restricted by an Equal"); } // If this is a query on tokens, it's necessary a range query (there can be more than one key per token), so reject IN queries (as we don't know how to do them) @@ -1284,4 +1314,62 @@ public class SelectStatement implements CQLStatement this.isCount = isCount; } } + + /** + * Used in orderResults(...) method when single 'ORDER BY' condition where given + */ + private static class SingleColumnComparator implements Comparator<CqlRow> + { + private final int index; + private final AbstractType<?> comparator; + + public SingleColumnComparator(int columnIndex, AbstractType<?> orderer) + { + index = columnIndex; + comparator = orderer; + } + + public int compare(CqlRow a, CqlRow b) + { + Column columnA = a.getColumns().get(index); + Column columnB = b.getColumns().get(index); + + return comparator.compare(columnA.bufferForValue(), columnB.bufferForValue()); + } + } + + /** + * Used in orderResults(...) method when multiple 'ORDER BY' conditions where given + */ + private static class CompositeComparator implements Comparator<CqlRow> + { + private final int startColumnIndex; + private final List<AbstractType<?>> orderings; + + private CompositeComparator(int startIndex, List<AbstractType<?>> orderComparators) + { + startColumnIndex = startIndex; + orderings = orderComparators; + } + + public int compare(CqlRow a, CqlRow b) + { + int currentIndex = startColumnIndex; + + for (AbstractType<?> comparator : orderings) + { + ByteBuffer aValue = a.getColumns().get(currentIndex).bufferForValue(); + ByteBuffer bValue = b.getColumns().get(currentIndex).bufferForValue(); + + int comparison = comparator.compare(aValue, bValue); + + if (comparison != 0) + return comparison; + + currentIndex++; + } + + return 0; + } + } }