Add support for the BETWEEN operator in WHERE clauses

patch by Simon Chess; reviewed by Benjamin Lerer and Ekaterina Dimitrova for CASSANDRA-19604
apache · Jun 6, 2024 · 53fabf1 · 53fabf1
1 parent 87ee1ac
commit 53fabf1
Show file tree

Hide file tree

Showing 22 changed files with 679 additions and 23 deletions.
diff --git a/CHANGES.txt b/CHANGES.txt
@@ -1,4 +1,5 @@
 5.1
+ * Add support for the BETWEEN operator in WHERE clauses (CASSANDRA-19604)
  * Replace Stream iteration with for-loop for SimpleRestriction::bindAndGetClusteringElements (CASSANDRA-19679)
  * Consolidate logging on trace level (CASSANDRA-19632)
  * Expand DDL statements on coordinator before submission to the CMS (CASSANDRA-19592)

diff --git a/doc/modules/cassandra/pages/developing/cql/changes.adoc b/doc/modules/cassandra/pages/developing/cql/changes.adoc
@@ -2,6 +2,10 @@
 
 The following describes the changes in each version of CQL.
 
+== 3.4.8
+
+* Add support for the BETWEEN operator in WHERE clauses (`19604`)
+
 == 3.4.7
 
 * Add vector similarity functions (`18640`)

diff --git a/pylib/cqlshlib/cql3handling.py b/pylib/cqlshlib/cql3handling.py
@@ -743,6 +743,7 @@ def working_on_keyspace(ctxt):
                                  ( "," [rel_tokname]=<cident> )*
                              ")" ("=" | "<" | ">" | "<=" | ">=") <tokenDefinition>
              | [rel_lhs]=<cident> "IN" "(" <term> ( "," <term> )* ")"
+             | [rel_lhs]=<cident> "BETWEEN" <term> "AND" <term>
              ;
 <selectClause> ::= "DISTINCT"? <selector> ("AS" <cident>)? ("," <selector> ("AS" <cident>)?)*
                  | "*"

diff --git a/pylib/cqlshlib/test/test_cqlsh_completion.py b/pylib/cqlshlib/test/test_cqlsh_completion.py
@@ -381,7 +381,7 @@ def test_complete_in_update(self):
         self.trycompletions("UPDATE empty_table SET lonelycol = 'eggs' WHERE lonel",
                             immediate='ykey ')
         self.trycompletions("UPDATE empty_table SET lonelycol = 'eggs' WHERE lonelykey ",
-                            choices=['=', '<=', '>=', '>', '<', 'CONTAINS', 'IN', '['])
+                            choices=['=', '<=', '>=', '>', '<', 'BETWEEN', 'CONTAINS', 'IN', '['])
         self.trycompletions("UPDATE empty_table SET lonelycol = 'eggs' WHERE lonelykey = 0.0 ",
                             choices=['AND', 'IF', ';'])
         self.trycompletions("UPDATE empty_table SET lonelycol = 'eggs' WHERE lonelykey = 0.0 AND ",
@@ -464,7 +464,7 @@ def test_complete_in_delete(self):
                             choices=['a', 'b', 'TOKEN('])
 
         self.trycompletions('DELETE FROM twenty_rows_composite_table USING TIMESTAMP 0 WHERE a ',
-                            choices=['<=', '>=', 'CONTAINS', 'IN', '[', '=', '<', '>'])
+                            choices=['<=', '>=', 'BETWEEN', 'CONTAINS', 'IN', '[', '=', '<', '>'])
 
         self.trycompletions('DELETE FROM twenty_rows_composite_table USING TIMESTAMP 0 WHERE TOKEN(',
                             immediate='a ')

diff --git a/src/antlr/Lexer.g b/src/antlr/Lexer.g
@@ -124,6 +124,7 @@ K_FILTERING:   F I L T E R I N G;
 K_IF:          I F;
 K_IS:          I S;
 K_CONTAINS:    C O N T A I N S;
+K_BETWEEN:     B E T W E E N;
 K_GROUP:       G R O U P;
 K_CLUSTER:     C L U S T E R;
 K_INTERNALS:   I N T E R N A L S;

diff --git a/src/antlr/Parser.g b/src/antlr/Parser.g
@@ -1757,6 +1757,18 @@ propertyValue returns [String str]
     | u=unreserved_keyword { $str = u; }
     ;
 
+singleColumnBetweenValues returns [Terms.Raw terms]
+    @init { List<Term.Raw> list = new ArrayList<>(); }
+    @after { $terms = Terms.Raw.of(list); }
+    : t1=term { list.add(t1); } K_AND t2=term { list.add(t2); }
+    ;
+
+betweenLiterals returns [Terms.Raw literals]
+    @init { List<Term.Raw> list = new ArrayList<>(); }
+    @after { $literals = Terms.Raw.of(list); }
+    : t1=tupleLiteral { list.add(t1); } K_AND t2=tupleLiteral { list.add(t2); }
+    ;
+
 relationType returns [Operator op]
     : '='  { $op = Operator.EQ; }
     | '<'  { $op = Operator.LT; }
@@ -1768,10 +1780,12 @@ relationType returns [Operator op]
 
 relation[WhereClause.Builder clauses]
     : name=cident type=relationType t=term { $clauses.add(Relation.singleColumn(name, type, t)); }
+    | name=cident K_BETWEEN betweenValues=singleColumnBetweenValues
+            { $clauses.add(Relation.singleColumn($name.id, Operator.BETWEEN, betweenValues)); }
     | name=cident K_LIKE t=term { $clauses.add(Relation.singleColumn(name, Operator.LIKE, t)); }
     | name=cident K_IS K_NOT K_NULL { $clauses.add(Relation.singleColumn(name, Operator.IS_NOT, Constants.NULL_LITERAL)); }
-    | K_TOKEN l=tupleOfIdentifiers type=relationType t=term
-        { $clauses.add(Relation.token(l, type, t)); }
+    | K_TOKEN l=tupleOfIdentifiers type=relationType t=term { $clauses.add(Relation.token(l, type, t)); }
+    | K_TOKEN l=tupleOfIdentifiers K_BETWEEN betweenValues=singleColumnBetweenValues { $clauses.add(Relation.token(l, Operator.BETWEEN, betweenValues)); }
     | name=cident K_IN marker=inMarker
         { $clauses.add(Relation.singleColumn(name, Operator.IN, marker)); }
     | name=cident K_IN inValues=singleColumnInValues
@@ -1797,6 +1811,12 @@ relation[WhereClause.Builder clauses]
           }
       | type=relationType tupleMarker=markerForTuple /* (a, b, c) >= ? */
           { $clauses.add(Relation.multiColumn(ids, type, tupleMarker)); }
+      | K_BETWEEN
+            ( t1=tupleLiteral K_AND t2=tupleLiteral
+                    { $clauses.add(Relation.multiColumn(ids, Operator.BETWEEN, Terms.Raw.of(List.of(t1, t2)))); }
+            | m1=markerForTuple K_AND m2=markerForTuple
+                    { $clauses.add(Relation.multiColumn(ids, Operator.BETWEEN, Terms.Raw.of(List.of(m1, m2)))); }
+            )
       )
     | '(' relation[$clauses] ')'
     ;
@@ -2016,5 +2036,6 @@ basic_unreserved_keyword returns [String str]
         | K_SELECT_MASKED
         | K_VECTOR
         | K_ANN
+        | K_BETWEEN
         ) { $str = $k.text; }
     ;
diff --git a/src/java/org/apache/cassandra/cql3/Operator.java b/src/java/org/apache/cassandra/cql3/Operator.java
@@ -268,6 +268,11 @@ public boolean canBeUsedWith(ColumnsExpression.Kind kind)
     },
     IN(7)
     {
+        @Override
+        public Kind kind() {
+            return Kind.MULTI_VALUE;
+        }
+
         public boolean isSatisfiedBy(AbstractType<?> type, ByteBuffer leftOperand, ByteBuffer rightOperand)
         {
             ListSerializer<?> serializer = ListType.getInstance(type, false).getSerializer();
@@ -507,6 +512,62 @@ public boolean requiresIndexing()
         {
             return true;
         }
+    },
+    BETWEEN(19)
+    {
+        @Override
+        public Kind kind() {
+            return Kind.TERNARY;
+        }
+
+        @Override
+        public String toString()
+        {
+            return "BETWEEN";
+        }
+
+        @Override
+        public boolean isSatisfiedBy(AbstractType<?> type, ByteBuffer leftOperand, ByteBuffer rightOperand)
+        {
+            List<ByteBuffer> buffers = ListType.getInstance(type, false).unpack(rightOperand);
+            buffers.sort(type);
+            return type.compareForCQL(leftOperand, buffers.get(0)) >= 0 && type.compareForCQL(leftOperand, buffers.get(1)) <= 0;
+        }
+
+        @Override
+        public boolean requiresFilteringOrIndexingFor(ColumnMetadata.Kind columnKind)
+        {
+            return columnKind != ColumnMetadata.Kind.CLUSTERING;
+        }
+
+        @Override
+        public void restrict(RangeSet<ClusteringElements> rangeSet, List<ClusteringElements> args)
+        {
+            assert args.size() == 2 : this + " accepts exactly two values";
+            args.sort(ClusteringElements.CQL_COMPARATOR);
+            rangeSet.removeAll(ClusteringElements.lessThan(args.get(0)));
+            rangeSet.removeAll(ClusteringElements.greaterThan(args.get(1)));
+        }
+
+        @Override
+        public boolean isSlice()
+        {
+            return true;
+        }
+
+        @Override
+        public boolean canBeUsedWith(ColumnsExpression.Kind kind)
+        {
+            return kind != ColumnsExpression.Kind.MAP_ELEMENT;
+        }
+    };
+
+    /**
+     * The different kinds of operators
+     */
+    public enum Kind
+    {
+        BINARY, TERNARY, MULTI_VALUE;
     };
 
     /**
@@ -539,6 +600,24 @@ public int getValue()
         return b;
     }
 
+    /**
+     * Returns the kind of this operator.
+     * @return the kind of this operator
+     */
+    public Kind kind()
+    {
+        return Kind.BINARY;
+    }
+
+    /**
+     * Checks if this operator is a ternary operator.
+     * @return {@code true} if this operator is a ternary operator, {@code false} otherwise.
+     */
+    public boolean isTernary()
+    {
+        return kind() == Kind.TERNARY;
+    }
+
     /**
      * Deserializes a <code>Operator</code> instance from the specified input.
      *

diff --git a/src/java/org/apache/cassandra/cql3/Relation.java b/src/java/org/apache/cassandra/cql3/Relation.java
@@ -72,7 +72,7 @@ public Operator operator()
      */
     public static Relation singleColumn(ColumnIdentifier identifier, Operator operator, Term.Raw rawTerm)
     {
-        assert operator != Operator.IN;
+        assert operator.kind() == Operator.Kind.BINARY;
         return new Relation(ColumnsExpression.Raw.singleColumn(identifier), operator, Terms.Raw.of(rawTerm));
     }
 
@@ -86,6 +86,7 @@ public static Relation singleColumn(ColumnIdentifier identifier, Operator operat
      */
     public static Relation singleColumn(ColumnIdentifier identifier, Operator operator, Terms.Raw rawTerms)
     {
+        assert operator.kind() != Operator.Kind.BINARY;
         return new Relation(ColumnsExpression.Raw.singleColumn(identifier), operator, rawTerms);
     }
 
@@ -100,6 +101,7 @@ public static Relation singleColumn(ColumnIdentifier identifier, Operator operat
      */
     public static Relation mapElement(ColumnIdentifier identifier, Term.Raw rawKey, Operator operator, Term.Raw rawTerm)
     {
+        assert operator.kind() == Operator.Kind.BINARY;
         return new Relation(ColumnsExpression.Raw.mapElement(identifier, rawKey), operator, Terms.Raw.of(rawTerm));
     }
 
@@ -113,7 +115,7 @@ public static Relation mapElement(ColumnIdentifier identifier, Term.Raw rawKey,
      */
     public static Relation multiColumn(List<ColumnIdentifier> identifiers, Operator operator, Term.Raw rawTerm)
     {
-        assert operator != Operator.IN;
+        assert operator.kind() == Operator.Kind.BINARY;
         return new Relation(ColumnsExpression.Raw.multiColumn(identifiers), operator, Terms.Raw.of(rawTerm));
     }
 
@@ -127,6 +129,7 @@ public static Relation multiColumn(List<ColumnIdentifier> identifiers, Operator
      */
     public static Relation multiColumn(List<ColumnIdentifier> identifiers, Operator operator, Terms.Raw rawTerms)
     {
+        assert operator.kind() != Operator.Kind.BINARY;
         return new Relation(ColumnsExpression.Raw.multiColumn(identifiers), operator, rawTerms);
     }
 
@@ -140,9 +143,24 @@ public static Relation multiColumn(List<ColumnIdentifier> identifiers, Operator
      */
     public static Relation token(List<ColumnIdentifier> identifiers, Operator operator, Term.Raw rawTerm)
     {
+        assert operator.kind() == Operator.Kind.BINARY;
         return new Relation(ColumnsExpression.Raw.token(identifiers), operator, Terms.Raw.of(rawTerm));
     }
 
+    /**
+     * Creates a relation for token expression (e.g. {@code token(columnA, columnB) = ?} ).
+     *
+     * @param identifiers the column identifiers for the partition columns
+     * @param operator the relation operator
+     * @param rawTerms the terms to which the token value must be compared
+     * @return a relation for a token expression.
+     */
+    public static Relation token(List<ColumnIdentifier> identifiers, Operator operator, Terms.Raw rawTerms)
+    {
+        assert operator.kind() == Operator.Kind.TERNARY;
+        return new Relation(ColumnsExpression.Raw.token(identifiers), operator, rawTerms);
+    }
+
     /**
      * Checks if this relation is a token relation (e.g. <pre>token(a) = token(1)</pre>).
      *
@@ -225,6 +243,11 @@ public int hashCode()
      */
     public String toCQLString()
     {
+        if (operator.isTernary())
+        {
+            List<? extends Term.Raw> terms = rawTerms.asList();
+            return String.format("%s %s %s AND %s", rawExpressions.toCQLString(), operator, terms.get(0), terms.get(1));
+        }
         return String.format("%s %s %s", rawExpressions.toCQLString(), operator, rawTerms.getText());
     }
 

diff --git a/src/java/org/apache/cassandra/cql3/restrictions/ClusteringElements.java b/src/java/org/apache/cassandra/cql3/restrictions/ClusteringElements.java
@@ -19,6 +19,7 @@
 package org.apache.cassandra.cql3.restrictions;
 
 import java.nio.ByteBuffer;
+import java.util.Comparator;
 import java.util.List;
 import java.util.Objects;
 
@@ -64,6 +65,32 @@
  */
 public class ClusteringElements extends ForwardingList<ByteBuffer> implements Comparable<ClusteringElements>
 {
+    /**
+     * A comparator for {@code ClusteringElements} that is used to compare elements from a CQL point of view.
+     * <p>The Comparator will ignore reverse type as well as the number of elements (e.g. elements with different length but same prefix value are considered equals)</p>
+     */
+    public static  final Comparator<ClusteringElements> CQL_COMPARATOR = new Comparator<ClusteringElements>()
+    {
+        @Override
+        public int compare(ClusteringElements a, ClusteringElements b)
+        {
+            if (a == null || b == null)
+                throw new NullPointerException();
+
+            a.isComparableWith(b);
+
+            for (int i = 0, m = Math.min(a.size(), b.size()); i < m; i++)
+            {
+                int comparison = a.columnType(i).compareForCQL(a.values.get(i), b.values.get(i));
+
+                if (comparison != 0)
+                    return comparison;
+            }
+
+            return 0;
+        }
+    };
+
     /**
      * The empty {@code ClusteringElements} instance used to avoid creating unecessary empty instances.
      */

diff --git a/src/java/org/apache/cassandra/cql3/restrictions/MergedRestriction.java b/src/java/org/apache/cassandra/cql3/restrictions/MergedRestriction.java
@@ -141,15 +141,15 @@ private static void validate(SimpleRestriction restriction, SimpleRestriction ot
                                      column.name);
             }
 
-            if ((restriction.operator() == Operator.GT || restriction.operator() == Operator.GTE) &&
-                    (other.operator() == Operator.GT || other.operator() == Operator.GTE))
+            if ((restriction.operator() == Operator.GT || restriction.operator() == Operator.GTE || restriction.operator() == Operator.BETWEEN) &&
+                    (other.operator() == Operator.GT || other.operator() == Operator.GTE || other.operator() == Operator.BETWEEN))
             {
                 throw invalidRequest("More than one restriction was found for the start bound on %s",
                                      toCQLString(getColumnsInCommons(restriction, other)));
             }
 
-            if ((restriction.operator() == Operator.LT || restriction.operator() == Operator.LTE) &&
-                    (other.operator() == Operator.LT || other.operator() == Operator.LTE))
+            if ((restriction.operator() == Operator.LT || restriction.operator() == Operator.LTE || restriction.operator() == Operator.BETWEEN) &&
+                    (other.operator() == Operator.LT || other.operator() == Operator.LTE || other.operator() == Operator.BETWEEN))
             {
                 throw invalidRequest("More than one restriction was found for the end bound on %s",
                                      toCQLString(getColumnsInCommons(restriction, other)));

diff --git a/src/java/org/apache/cassandra/cql3/restrictions/SimpleRestriction.java b/src/java/org/apache/cassandra/cql3/restrictions/SimpleRestriction.java
@@ -325,9 +325,9 @@ public void addToRowFilter(RowFilter filter, IndexRegistry indexRegistry, QueryO
                 List<ByteBuffer> buffers = bindAndGet(options);
 
                 ColumnMetadata column = firstColumn();
-                if (operator == Operator.IN)
+                if (operator == Operator.IN || operator == Operator.BETWEEN)
                 {
-                    filter.add(column, operator, inValues(column, buffers));
+                    filter.add(column, operator, multiInputOperatorValues(column, buffers));
                 }
                 else if (operator == Operator.LIKE)
                 {
@@ -366,7 +366,7 @@ else if (isIN())
                                                                              .map(elements -> elements.get(0))
                                                                              .collect(Collectors.toList());
 
-                        filter.add(firstColumn(), Operator.IN, inValues(firstColumn(), values));
+                        filter.add(firstColumn(), Operator.IN, multiInputOperatorValues(firstColumn(), values));
                     }
                     else
                     {
@@ -383,14 +383,20 @@ else if (isIN())
         }
     }
 
-    private static ByteBuffer inValues(ColumnMetadata column, List<ByteBuffer> values)
+    private static ByteBuffer multiInputOperatorValues(ColumnMetadata column, List<ByteBuffer> values)
     {
+
         return ListType.getInstance(column.type, false).pack(values);
     }
 
     @Override
     public String toString()
     {
+        if (operator.isTernary())
+        {
+            List<? extends Term> terms = values.asList();
+            return String.format("%s %s %s AND %s", columnsExpression.toCQLString(), operator, terms.get(0), terms.get(1));
+        }
         return String.format("%s %s %s", columnsExpression.toCQLString(), operator, values);
     }
 }