You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by ma...@apache.org on 2025/05/27 20:55:07 UTC

(cassandra) branch cassandra-5.0 updated: Avoid lambda usage in TrieMemoryIndex range queries and ensure queue size tracking is per column

This is an automated email from the ASF dual-hosted git repository.

maedhroz pushed a commit to branch cassandra-5.0
in repository https://gitbox.apache.org/repos/asf/cassandra.git


The following commit(s) were added to refs/heads/cassandra-5.0 by this push:
     new dd0d8c03b9 Avoid lambda usage in TrieMemoryIndex range queries and ensure queue size tracking is per column
dd0d8c03b9 is described below

commit dd0d8c03b9414afeeffef2be0b37c0078ca72592
Author: Caleb Rackliffe <ca...@gmail.com>
AuthorDate: Wed May 21 17:10:41 2025 -0500

    Avoid lambda usage in TrieMemoryIndex range queries and ensure queue size tracking is per column
    
    patch by Caleb Rackliffe; reviewed by David Capwell for CASSANDRA-20668
---
 CHANGES.txt                                        |  1 +
 .../index/sai/memory/TrieMemoryIndex.java          | 60 +++++++++-------------
 .../index/sai/memory/TrieMemoryIndexTest.java      | 26 ++++++++++
 3 files changed, 51 insertions(+), 36 deletions(-)

diff --git a/CHANGES.txt b/CHANGES.txt
index 4aaed8bdb9..8b2f843107 100644
--- a/CHANGES.txt
+++ b/CHANGES.txt
@@ -1,4 +1,5 @@
 5.0.5
+ * Avoid lambda usage in TrieMemoryIndex range queries and ensure queue size tracking is per column (CASSANDRA-20668)
  * Avoid CQLSH throwing an exception loading .cqlshrc on non-supported platforms (CASSANDRA-20478)
  * Relax validation of snapshot name as a part of SSTable files path validation (CASSANDRA-20649)
  * Optimize initial skipping logic for SAI queries on large partitions (CASSANDRA-20191)
diff --git a/src/java/org/apache/cassandra/index/sai/memory/TrieMemoryIndex.java b/src/java/org/apache/cassandra/index/sai/memory/TrieMemoryIndex.java
index c8d32a8386..1468f4ef8f 100644
--- a/src/java/org/apache/cassandra/index/sai/memory/TrieMemoryIndex.java
+++ b/src/java/org/apache/cassandra/index/sai/memory/TrieMemoryIndex.java
@@ -23,13 +23,13 @@ import java.util.Iterator;
 import java.util.Map;
 import java.util.PriorityQueue;
 import java.util.SortedSet;
+import java.util.concurrent.atomic.AtomicInteger;
 import java.util.concurrent.atomic.LongAdder;
 import java.util.function.Function;
 
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
-import io.netty.util.concurrent.FastThreadLocal;
 import org.apache.cassandra.db.Clustering;
 import org.apache.cassandra.db.DecoratedKey;
 import org.apache.cassandra.db.PartitionPosition;
@@ -59,6 +59,7 @@ public class TrieMemoryIndex extends MemoryIndex
 {
     private static final Logger logger = LoggerFactory.getLogger(TrieMemoryIndex.class);
     private static final int MAX_RECURSIVE_KEY_LENGTH = 128;
+    private static final int MINIMUM_PRIORITY_QUEUE_SIZE = 128;
 
     private final InMemoryTrie<PrimaryKeys> data;
     private final PrimaryKeysReducer primaryKeysReducer;
@@ -66,6 +67,11 @@ public class TrieMemoryIndex extends MemoryIndex
     private ByteBuffer minTerm;
     private ByteBuffer maxTerm;
 
+    // Maintain the last queue size used on this index to use for the next range match.
+    // This allows for receiving a stream of wide range queries where the queue size
+    // is larger than we would want to default the size to.
+    private final AtomicInteger lastPriorityQueueSize = new AtomicInteger(MINIMUM_PRIORITY_QUEUE_SIZE);
+
     public TrieMemoryIndex(StorageAttachedIndex index)
     {
         super(index);
@@ -143,7 +149,11 @@ public class TrieMemoryIndex extends MemoryIndex
             case CONTAINS_VALUE:
                 return exactMatch(expression, keyRange);
             case RANGE:
-                return rangeMatch(expression, keyRange);
+                KeyRangeIterator keyIterator = rangeMatch(expression, keyRange);
+                int keyCount = (int) keyIterator.getMaxKeys();
+                if (keyCount > MINIMUM_PRIORITY_QUEUE_SIZE)
+                    lastPriorityQueueSize.set(keyCount);
+                return keyIterator;
             default:
                 throw new IllegalArgumentException("Unsupported expression: " + expression);
         }
@@ -252,29 +262,15 @@ public class TrieMemoryIndex extends MemoryIndex
 
     private static class Collector
     {
-        private static final int MINIMUM_QUEUE_SIZE = 128;
-
-        // Maintain the last queue size used on this index to use for the next range match.
-        // This allows for receiving a stream of wide range queries where the queue size
-        // is larger than we would want to default the size to.
-        // TODO Investigate using a decaying histogram here to avoid the effect of outliers.
-        private static final FastThreadLocal<Integer> lastQueueSize = new FastThreadLocal<>()
-        {
-            protected Integer initialValue()
-            {
-                return MINIMUM_QUEUE_SIZE;
-            }
-        };
+        final PriorityQueue<PrimaryKey> mergedKeys;
+        final AbstractBounds<PartitionPosition> keyRange;
 
-        PrimaryKey minimumKey = null;
         PrimaryKey maximumKey = null;
-        final PriorityQueue<PrimaryKey> mergedKeys = new PriorityQueue<>(lastQueueSize.get());
 
-        final AbstractBounds<PartitionPosition> keyRange;
-
-        public Collector(AbstractBounds<PartitionPosition> keyRange)
+        public Collector(AbstractBounds<PartitionPosition> keyRange, int expectedKeys)
         {
             this.keyRange = keyRange;
+            this.mergedKeys = new PriorityQueue<>(expectedKeys);
         }
 
         public void processContent(PrimaryKeys keys)
@@ -296,12 +292,8 @@ public class TrieMemoryIndex extends MemoryIndex
                 || primaryKeys.last().partitionKey().compareTo(keyRange.left) < 0)
                 return;
 
-            primaryKeys.forEach(this::processKey);
-        }
-
-        public void updateLastQueueSize()
-        {
-            lastQueueSize.set(Math.max(MINIMUM_QUEUE_SIZE, mergedKeys.size()));
+            for (PrimaryKey primaryKey : primaryKeys)
+                processKey(primaryKey);
         }
 
         private void processKey(PrimaryKey key)
@@ -310,7 +302,7 @@ public class TrieMemoryIndex extends MemoryIndex
             {
                 mergedKeys.add(key);
 
-                minimumKey = minimumKey == null ? key : key.compareTo(minimumKey) < 0 ? key : minimumKey;
+                // We only track the maximum key, as the minimum can be peeked in constant time on the PQ itself.
                 maximumKey = maximumKey == null ? key : key.compareTo(maximumKey) > 0 ? key : maximumKey;
             }
         }
@@ -342,20 +334,16 @@ public class TrieMemoryIndex extends MemoryIndex
             upperInclusive = false;
         }
 
-        Collector cd = new Collector(keyRange);
+        Collector cd = new Collector(keyRange, lastPriorityQueueSize.get());
+        Iterator<PrimaryKeys> values = data.subtrie(lowerBound, lowerInclusive, upperBound, upperInclusive).valueIterator();
 
-        data.subtrie(lowerBound, lowerInclusive, upperBound, upperInclusive)
-            .values()
-            .forEach(cd::processContent);
+        while (values.hasNext())
+            cd.processContent(values.next());
 
         if (cd.mergedKeys.isEmpty())
-        {
             return KeyRangeIterator.empty();
-        }
-
-        cd.updateLastQueueSize();
 
-        return new InMemoryKeyRangeIterator(cd.minimumKey, cd.maximumKey, cd.mergedKeys);
+        return new InMemoryKeyRangeIterator(cd.mergedKeys.peek(), cd.maximumKey, cd.mergedKeys);
     }
 
     private static class PrimaryKeysReducer implements InMemoryTrie.UpsertTransformer<PrimaryKeys, PrimaryKey>
diff --git a/test/unit/org/apache/cassandra/index/sai/memory/TrieMemoryIndexTest.java b/test/unit/org/apache/cassandra/index/sai/memory/TrieMemoryIndexTest.java
index 0ab4c846f7..963742c02c 100644
--- a/test/unit/org/apache/cassandra/index/sai/memory/TrieMemoryIndexTest.java
+++ b/test/unit/org/apache/cassandra/index/sai/memory/TrieMemoryIndexTest.java
@@ -29,8 +29,10 @@ import java.util.TreeMap;
 import java.util.function.IntFunction;
 import java.util.stream.Collectors;
 
+import org.junit.Ignore;
 import org.junit.Test;
 
+import org.HdrHistogram.Histogram;
 import org.apache.cassandra.cql3.Operator;
 import org.apache.cassandra.cql3.statements.schema.IndexTarget;
 import org.apache.cassandra.db.Clustering;
@@ -243,4 +245,28 @@ public class TrieMemoryIndexTest extends SAIRandomizedTester
         index = new StorageAttachedIndex(cfs, indexMetadata);
         return new TrieMemoryIndex(index);
     }
+
+    @Ignore
+    @Test
+    public void testMemtableRangeQueryPerformance()
+    {
+        createTable("CREATE TABLE %S (pk int, ck int, val int, PRIMARY KEY (pk, ck))");
+        createIndex("CREATE INDEX ON %s(val) USING 'sai'");
+
+        for (int pk = 0; pk < 20; pk++)
+            for (int ck = 0; ck < 10000; ck++)
+                execute("INSERT INTO %s (pk, ck, val) VALUES (?, ?, ?)", pk, ck, ck);
+
+        Histogram histogram = new Histogram(4);
+
+        for (int i = 0; i < 20000; i++)
+        {
+            long start = System.nanoTime();
+            execute("SELECT * FROM %s WHERE pk = 5 AND val > ? LIMIT 10", 4000);
+            histogram.recordValue(System.nanoTime() - start);
+        }
+
+        System.out.println("50th: " + histogram.getValueAtPercentile(0.5));
+        System.out.println("99th: " + histogram.getValueAtPercentile(0.99));
+    }
 }


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@cassandra.apache.org
For additional commands, e-mail: commits-help@cassandra.apache.org