You are viewing a plain text version of this content. The canonical link for it is here.
Posted to pr@cassandra.apache.org by "dcapwell (via GitHub)" <gi...@apache.org> on 2025/07/16 18:15:09 UTC

[PR] CASSANDRA-20772 Accord Route Index does not filter based off txn_id range which causes segments which can't contain the data to be queried [cassandra]

dcapwell opened a new pull request, #4257:
URL: https://github.com/apache/cassandra/pull/4257

   (no comment)


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


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


Re: [PR] CASSANDRA-20772 Accord Route Index does not filter based off txn_id range which causes segments which can't contain the data to be queried [cassandra]

Posted by "dcapwell (via GitHub)" <gi...@apache.org>.
dcapwell commented on PR #4257:
URL: https://github.com/apache/cassandra/pull/4257#issuecomment-3105095436

   merged


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


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


Re: [PR] CASSANDRA-20772 Accord Route Index does not filter based off txn_id range which causes segments which can't contain the data to be queried [cassandra]

Posted by "dcapwell (via GitHub)" <gi...@apache.org>.
dcapwell commented on code in PR #4257:
URL: https://github.com/apache/cassandra/pull/4257#discussion_r2211277310


##########
src/java/org/apache/cassandra/index/accord/RouteJournalIndex.java:
##########
@@ -414,19 +412,49 @@ else if (e.column() == AccordJournalTable.SyntheticColumn.store_id.metadata && e
             {
                 storeId = Int32Type.instance.compose(e.getIndexValue());
             }
+            else if (e.column() == AccordJournalTable.SyntheticColumn.txn_id.metadata)

Review Comment:
   i could reject exclusive as the logic is 100% inclusive... this is all synthetic anyways so can only be called with w/e the route index writes and can't come from a user.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


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


Re: [PR] CASSANDRA-20772 Accord Route Index does not filter based off txn_id range which causes segments which can't contain the data to be queried [cassandra]

Posted by "belliottsmith (via GitHub)" <gi...@apache.org>.
belliottsmith commented on code in PR #4257:
URL: https://github.com/apache/cassandra/pull/4257#discussion_r2213652565


##########
src/java/org/apache/cassandra/index/accord/Key.java:
##########
@@ -22,12 +22,12 @@
 
 import org.apache.cassandra.schema.TableId;
 
-public class Group implements Comparable<Group>
+public class Key implements Comparable<Key>
 {
     public final int storeId;
     public final TableId tableId;
 
-    public Group(int storeId, TableId tableId)
+    public Key(int storeId, TableId tableId)

Review Comment:
   not sure it's worth changing, but `storeId` always maps to a single `TableId` now



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


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


Re: [PR] CASSANDRA-20772 Accord Route Index does not filter based off txn_id range which causes segments which can't contain the data to be queried [cassandra]

Posted by "dcapwell (via GitHub)" <gi...@apache.org>.
dcapwell commented on code in PR #4257:
URL: https://github.com/apache/cassandra/pull/4257#discussion_r2211265971


##########
src/java/org/apache/cassandra/index/accord/RangeMemoryIndex.java:
##########
@@ -58,13 +63,51 @@ public class RangeMemoryIndex
 {
 
     @GuardedBy("this")
-    private final Map<Group, RangeTree<byte[], Range, DecoratedKey>> map = new HashMap<>();
-    @GuardedBy("this")
-    private final Map<Group, Metadata> groupMetadata = new HashMap<>();
+    private final Map<Key, Group> map = new HashMap<>();
 
-    private static class Metadata
+    private static class Group
     {
+        private RangeTree<byte[], Range, DecoratedKey> tree = createRangeTree();
         public byte[] minTerm, maxTerm;
+        public TxnId minTimestamp = TxnId.MAX;
+        public TxnId maxTimestamp = TxnId.NONE;
+
+        void add(Range range, DecoratedKey key, TxnId txnId, byte[] start, byte[] end)
+        {
+            tree.add(range, key);
+            minTerm = minTerm == null ? start : ByteArrayUtil.compareUnsigned(minTerm, 0, start, 0, minTerm.length) > 0 ? start : minTerm;
+            maxTerm = maxTerm == null ? end : ByteArrayUtil.compareUnsigned(maxTerm, 0, end, 0, maxTerm.length) < 0 ? end : maxTerm;
+            if (minTimestamp.compareTo(txnId) > 0)
+                minTimestamp = txnId;
+            if (maxTimestamp.compareTo(txnId) < 0)
+                maxTimestamp = txnId;
+        }
+
+        void search(byte[] start, byte[] end,
+                    Timestamp minTimestamp, Timestamp maxTimestamp,
+                    Consumer<Map.Entry<RangeMemoryIndex.Range, DecoratedKey>> fn)
+        {
+            if (this.minTimestamp.compareTo(maxTimestamp) > 0 || this.maxTimestamp.compareTo(minTimestamp) < 0)
+                return;
+            tree.search(new Range(start, end), e -> {
+                TxnId id = AccordKeyspace.JournalColumns.getJournalKey(e.getValue()).id;

Review Comment:
   Ok so think i can just remove this logic...
   
   `org.apache.cassandra.service.accord.RangeSearcher.DefaultResult#consume(java.util.function.Consumer<accord.primitives.TxnId>)`
   
   We filter at this layer so won't return the result to the caller without applying the filter... but this means we have to deserialize the key to do the filter, so this logic just does that twice!



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


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


Re: [PR] CASSANDRA-20772 Accord Route Index does not filter based off txn_id range which causes segments which can't contain the data to be queried [cassandra]

Posted by "dcapwell (via GitHub)" <gi...@apache.org>.
dcapwell commented on code in PR #4257:
URL: https://github.com/apache/cassandra/pull/4257#discussion_r2211255158


##########
src/java/org/apache/cassandra/index/accord/RouteJournalIndex.java:
##########
@@ -414,19 +412,49 @@ else if (e.column() == AccordJournalTable.SyntheticColumn.store_id.metadata && e
             {
                 storeId = Int32Type.instance.compose(e.getIndexValue());
             }
+            else if (e.column() == AccordJournalTable.SyntheticColumn.txn_id.metadata)
+            {
+                switch (e.operator())
+                {
+                    case GT:
+                        minTimestamp = CommandSerializers.timestamp.deserialize(e.getIndexValue());
+                        break;
+                    case GTE:
+                        minTimestamp = CommandSerializers.timestamp.deserialize(e.getIndexValue());
+                        break;
+                    case LT:
+                        maxTimestamp = CommandSerializers.timestamp.deserialize(e.getIndexValue());
+                        break;
+                    case LTE:
+                        maxTimestamp = CommandSerializers.timestamp.deserialize(e.getIndexValue());
+                        break;
+                    default:
+                        return null;
+                }
+            }
             else
             {
-                throw new IllegalArgumentException("Unexpected expression: " + e.toCQLString());
+                String cqlString;
+                try
+                {
+                    cqlString = e.toCQLString();

Review Comment:
   this failed when touching the new column, so made it defensive...



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


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


Re: [PR] CASSANDRA-20772 Accord Route Index does not filter based off txn_id range which causes segments which can't contain the data to be queried [cassandra]

Posted by "dcapwell (via GitHub)" <gi...@apache.org>.
dcapwell commented on code in PR #4257:
URL: https://github.com/apache/cassandra/pull/4257#discussion_r2211275356


##########
src/java/org/apache/cassandra/index/accord/RouteIndexFormat.java:
##########
@@ -284,7 +286,9 @@ static List<Segment> readSegments(Map<IndexComponent, FileHandle> index) throws
                     }
                     byte[] minTerm = ByteArrayUtil.readWithVIntLength(segmentReader);
                     byte[] maxTerm = ByteArrayUtil.readWithVIntLength(segmentReader);
-                    Segment.Metadata existing = groups.put(group, new Segment.Metadata(metas, minTerm, maxTerm));
+                    Timestamp minTimestamp = CommandSerializers.timestamp.deserialize(segmentReader);
+                    Timestamp maxTimestamp = CommandSerializers.timestamp.deserialize(segmentReader);
+                    Segment.Metadata existing = groups.put(group, new Segment.Metadata(metas, minTerm, maxTerm, minTimestamp, maxTimestamp));

Review Comment:
   i "feel" like there isn't a good memory gain by trying to dedup these objects, as I don't "feel" like its very likely that the segments will have identical timestamps and are far more likely to have distinct timestamps...



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


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


Re: [PR] CASSANDRA-20772 Accord Route Index does not filter based off txn_id range which causes segments which can't contain the data to be queried [cassandra]

Posted by "dcapwell (via GitHub)" <gi...@apache.org>.
dcapwell commented on code in PR #4257:
URL: https://github.com/apache/cassandra/pull/4257#discussion_r2219663330


##########
src/java/org/apache/cassandra/index/accord/MemtableIndex.java:
##########
@@ -63,13 +65,23 @@ public Segment write(IndexDescriptor id) throws IOException
         return memoryIndex.write(id);
     }
 
-    public Collection<ByteBuffer> search(int storeId, TableId tableId, byte[] start, boolean startInclusive, byte[] end, boolean endInclusive)
+    public void search(int storeId, TableId tableId, byte[] start, byte[] end,
+                       Timestamp minTimestamp,

Review Comment:
   made this change, all tests are passing now



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


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


Re: [PR] CASSANDRA-20772 Accord Route Index does not filter based off txn_id range which causes segments which can't contain the data to be queried [cassandra]

Posted by "dcapwell (via GitHub)" <gi...@apache.org>.
dcapwell commented on code in PR #4257:
URL: https://github.com/apache/cassandra/pull/4257#discussion_r2211285108


##########
src/java/org/apache/cassandra/service/accord/RouteInMemoryIndex.java:
##########
@@ -151,46 +166,74 @@ private void add(TxnId id, Unseekable keyOrRange)
             tableIndex.computeIfAbsent(tableId, i -> new TableIndex()).add(id, ts);
         }
 
-        public void search(TableId tableId, byte[] start, byte[] end, Consumer<Map.Entry<IndexRange, TxnId>> fn)
+        public void search(TableId tableId,
+                           byte[] start, byte[] end,
+                           TxnId minTxnId, Timestamp maxTxnId,
+                           Consumer<Map.Entry<IndexRange, TxnId>> fn)
         {
             TableIndex index = tableIndex.get(tableId);
             if (index == null) return;
-            index.search(start, end, fn);
+            index.search(start, end, minTxnId, maxTxnId, fn);
         }
 
-        public void search(TableId tableId, byte[] key, Consumer<Map.Entry<IndexRange, TxnId>> fn)
+        public void search(TableId tableId,
+                           byte[] key,
+                           TxnId minTxnId, Timestamp maxTxnId,
+                           Consumer<Map.Entry<IndexRange, TxnId>> fn)
         {
             TableIndex index = tableIndex.get(tableId);
             if (index == null) return;
-            index.search(key, fn);
+            index.search(key, minTxnId, maxTxnId, fn);
         }
     }
 
     private static class TableIndex
     {
         private final RangeTree<byte[], IndexRange, TxnId> index = createRangeTree();
+        private TxnId min = TxnId.MAX;
+        private TxnId max = TxnId.NONE;
 
         private TableIndex()
         {
         }
 
-        public void add(TxnId id, TokenRange ts)
+        private void add(TxnId id, TokenRange ts)
         {
             byte[] start = OrderedRouteSerializer.serializeTokenOnly(ts.start());
             byte[] end = OrderedRouteSerializer.serializeTokenOnly(ts.end());
             IndexRange range = new IndexRange(start, end);
 
             index.add(range, id);
+            if (min.compareTo(id) > 0)
+                min = id;
+            if (max.compareTo(id) < 0)
+                max = id;
         }
 
-        public void search(byte[] start, byte[] end, Consumer<Map.Entry<IndexRange, TxnId>> fn)
+        private void search(byte[] start, byte[] end,
+                           TxnId minTxnId, Timestamp maxTxnId,
+                           Consumer<Map.Entry<IndexRange, TxnId>> fn)
         {
-            index.search(new IndexRange(start, end), fn);
+            if (minTxnId.compareTo(max) > 0) return;
+            if (maxTxnId.compareTo(min) < 0) return;
+            index.search(new IndexRange(start, end), e -> {
+                if (minTxnId.compareTo(e.getValue()) > 0) return;
+                if (maxTxnId.compareTo(e.getValue()) < 0) return;

Review Comment:
   stated in other comments, this is going to happen higher up so its not 100% needed, but it will drastically shrink the amount of data put into the `TreeSet` that requires post-filtering; so still best to keep it.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


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


Re: [PR] CASSANDRA-20772 Accord Route Index does not filter based off txn_id range which causes segments which can't contain the data to be queried [cassandra]

Posted by "belliottsmith (via GitHub)" <gi...@apache.org>.
belliottsmith commented on code in PR #4257:
URL: https://github.com/apache/cassandra/pull/4257#discussion_r2221936344


##########
src/java/org/apache/cassandra/service/accord/RouteInMemoryIndex.java:
##########
@@ -151,46 +174,79 @@ private void add(TxnId id, Unseekable keyOrRange)
             tableIndex.computeIfAbsent(tableId, i -> new TableIndex()).add(id, ts);
         }
 
-        public void search(TableId tableId, byte[] start, byte[] end, Consumer<Map.Entry<IndexRange, TxnId>> fn)
+        public void search(TableId tableId,
+                           byte[] start, byte[] end,
+                           TxnId minTxnId, Timestamp maxTxnId, @Nullable TxnId minDecidedId,
+                           Consumer<Map.Entry<IndexRange, TxnId>> fn)
         {
             TableIndex index = tableIndex.get(tableId);
             if (index == null) return;
-            index.search(start, end, fn);
+            index.search(start, end, minTxnId, maxTxnId, minDecidedId, fn);
         }
 
-        public void search(TableId tableId, byte[] key, Consumer<Map.Entry<IndexRange, TxnId>> fn)
+        public void search(TableId tableId,
+                           byte[] key,
+                           TxnId minTxnId, Timestamp maxTxnId, @Nullable TxnId minDecidedId,
+                           Consumer<Map.Entry<IndexRange, TxnId>> fn)
         {
             TableIndex index = tableIndex.get(tableId);
             if (index == null) return;
-            index.search(key, fn);
+            index.search(key, minTxnId, maxTxnId, minDecidedId, fn);
         }
     }
 
     private static class TableIndex
     {
         private final RangeTree<byte[], IndexRange, TxnId> index = createRangeTree();
+        private TxnId min = TxnId.MAX;
+        private TxnId max = TxnId.NONE;
+        private TxnId maxRX = TxnId.NONE;
 
         private TableIndex()
         {
         }
 
-        public void add(TxnId id, TokenRange ts)
+        private void add(TxnId id, TokenRange ts)
         {
             byte[] start = OrderedRouteSerializer.serializeTokenOnly(ts.start());
             byte[] end = OrderedRouteSerializer.serializeTokenOnly(ts.end());
             IndexRange range = new IndexRange(start, end);
 
             index.add(range, id);
+            if (min.compareTo(id) > 0)
+                min = id;
+            if (max.compareTo(id) < 0)
+                max = id;
+            if (id.is(Txn.Kind.ExclusiveSyncPoint) && id.compareTo(maxRX) > 0)
+                maxRX = id;

Review Comment:
   We probably need to null this out if we witness a non-RX, so we know we cannot filter on it (until we have time to embellish the indexing behaviour)



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


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


Re: [PR] CASSANDRA-20772 Accord Route Index does not filter based off txn_id range which causes segments which can't contain the data to be queried [cassandra]

Posted by "dcapwell (via GitHub)" <gi...@apache.org>.
dcapwell commented on code in PR #4257:
URL: https://github.com/apache/cassandra/pull/4257#discussion_r2211273200


##########
src/java/org/apache/cassandra/index/accord/RangeMemoryIndex.java:
##########
@@ -58,13 +63,51 @@ public class RangeMemoryIndex
 {
 
     @GuardedBy("this")
-    private final Map<Group, RangeTree<byte[], Range, DecoratedKey>> map = new HashMap<>();
-    @GuardedBy("this")
-    private final Map<Group, Metadata> groupMetadata = new HashMap<>();
+    private final Map<Key, Group> map = new HashMap<>();
 
-    private static class Metadata
+    private static class Group
     {
+        private RangeTree<byte[], Range, DecoratedKey> tree = createRangeTree();
         public byte[] minTerm, maxTerm;
+        public TxnId minTimestamp = TxnId.MAX;
+        public TxnId maxTimestamp = TxnId.NONE;
+
+        void add(Range range, DecoratedKey key, TxnId txnId, byte[] start, byte[] end)
+        {
+            tree.add(range, key);
+            minTerm = minTerm == null ? start : ByteArrayUtil.compareUnsigned(minTerm, 0, start, 0, minTerm.length) > 0 ? start : minTerm;
+            maxTerm = maxTerm == null ? end : ByteArrayUtil.compareUnsigned(maxTerm, 0, end, 0, maxTerm.length) < 0 ? end : maxTerm;
+            if (minTimestamp.compareTo(txnId) > 0)
+                minTimestamp = txnId;
+            if (maxTimestamp.compareTo(txnId) < 0)
+                maxTimestamp = txnId;
+        }
+
+        void search(byte[] start, byte[] end,
+                    Timestamp minTimestamp, Timestamp maxTimestamp,
+                    Consumer<Map.Entry<RangeMemoryIndex.Range, DecoratedKey>> fn)
+        {
+            if (this.minTimestamp.compareTo(maxTimestamp) > 0 || this.maxTimestamp.compareTo(minTimestamp) < 0)
+                return;
+            tree.search(new Range(start, end), e -> {
+                TxnId id = AccordKeyspace.JournalColumns.getJournalKey(e.getValue()).id;

Review Comment:
   FYI given how we do things today, we don't ever touch this object... journal directly creates SSTables and ignores memtable, so it really doesn't matter too much what we do here...
   
   2i *requires* we have memory indexes and its mostly here just to be "correct" if we ever do rely on memtable for some reason (such as to patch a journal entry?)...



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


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


Re: [PR] CASSANDRA-20772 Accord Route Index does not filter based off txn_id range which causes segments which can't contain the data to be queried [cassandra]

Posted by "dcapwell (via GitHub)" <gi...@apache.org>.
dcapwell closed pull request #4257: CASSANDRA-20772 Accord Route Index does not filter based off txn_id range which causes segments which can't contain the data to be queried
URL: https://github.com/apache/cassandra/pull/4257


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


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


Re: [PR] CASSANDRA-20772 Accord Route Index does not filter based off txn_id range which causes segments which can't contain the data to be queried [cassandra]

Posted by "dcapwell (via GitHub)" <gi...@apache.org>.
dcapwell commented on code in PR #4257:
URL: https://github.com/apache/cassandra/pull/4257#discussion_r2211251941


##########
src/java/org/apache/cassandra/index/accord/RangeMemoryIndex.java:
##########
@@ -58,13 +63,51 @@ public class RangeMemoryIndex
 {
 
     @GuardedBy("this")
-    private final Map<Group, RangeTree<byte[], Range, DecoratedKey>> map = new HashMap<>();
-    @GuardedBy("this")
-    private final Map<Group, Metadata> groupMetadata = new HashMap<>();
+    private final Map<Key, Group> map = new HashMap<>();
 
-    private static class Metadata
+    private static class Group
     {
+        private RangeTree<byte[], Range, DecoratedKey> tree = createRangeTree();
         public byte[] minTerm, maxTerm;
+        public TxnId minTimestamp = TxnId.MAX;
+        public TxnId maxTimestamp = TxnId.NONE;
+
+        void add(Range range, DecoratedKey key, TxnId txnId, byte[] start, byte[] end)
+        {
+            tree.add(range, key);
+            minTerm = minTerm == null ? start : ByteArrayUtil.compareUnsigned(minTerm, 0, start, 0, minTerm.length) > 0 ? start : minTerm;
+            maxTerm = maxTerm == null ? end : ByteArrayUtil.compareUnsigned(maxTerm, 0, end, 0, maxTerm.length) < 0 ? end : maxTerm;
+            if (minTimestamp.compareTo(txnId) > 0)
+                minTimestamp = txnId;
+            if (maxTimestamp.compareTo(txnId) < 0)
+                maxTimestamp = txnId;
+        }
+
+        void search(byte[] start, byte[] end,
+                    Timestamp minTimestamp, Timestamp maxTimestamp,
+                    Consumer<Map.Entry<RangeMemoryIndex.Range, DecoratedKey>> fn)
+        {
+            if (this.minTimestamp.compareTo(maxTimestamp) > 0 || this.maxTimestamp.compareTo(minTimestamp) < 0)
+                return;
+            tree.search(new Range(start, end), e -> {
+                TxnId id = AccordKeyspace.JournalColumns.getJournalKey(e.getValue()).id;

Review Comment:
   2 things i can do to lower this cost
   
   1) rather than construct the full `JournalColum`, only construct the `TxnId`.  This "should" be very similar CPU cost but would have slightly less memory cost
   2) try to do a byte compare to avoid the memory cost.  I don't believe we have this setup already so think i would have to roll my own here.
   
   For this class i don't think it matters too much (its the stuff that hasn't been flushed to sstable), but for the sstable side this "should" matter more i think



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


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


Re: [PR] CASSANDRA-20772 Accord Route Index does not filter based off txn_id range which causes segments which can't contain the data to be queried [cassandra]

Posted by "dcapwell (via GitHub)" <gi...@apache.org>.
dcapwell commented on code in PR #4257:
URL: https://github.com/apache/cassandra/pull/4257#discussion_r2211279866


##########
src/java/org/apache/cassandra/index/accord/SSTableIndex.java:
##########
@@ -81,11 +82,13 @@ public static SSTableIndex create(IndexDescriptor id) throws IOException
         return new SSTableIndex(id, files, segments, cleanup);
     }
 
-    public Collection<? extends ByteBuffer> search(Group group, byte[] key)
+    public Collection<? extends ByteBuffer> search(Key group, byte[] key, Timestamp minTimestamp, Timestamp maxTimestamp)
     {
         List<Segment> matches = segments.stream().filter(s -> {
                                             Segment.Metadata metadata = s.groups.get(group);
                                             if (metadata == null) return false;
+                                            if (metadata.maxTimestamp.compareTo(minTimestamp) < 0 || metadata.minTimestamp.compareTo(maxTimestamp) > 0)

Review Comment:
   only do a metadata filter for segments.  The thinking is that `org.apache.cassandra.service.accord.RangeSearcher.DefaultResult#consume(java.util.function.Consumer<accord.primitives.TxnId>)` is going to do the filtering on the actual values, so don't get a benefit by filtering out within a segment (its already going to do that)



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


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


Re: [PR] CASSANDRA-20772 Accord Route Index does not filter based off txn_id range which causes segments which can't contain the data to be queried [cassandra]

Posted by "belliottsmith (via GitHub)" <gi...@apache.org>.
belliottsmith commented on code in PR #4257:
URL: https://github.com/apache/cassandra/pull/4257#discussion_r2218620732


##########
src/java/org/apache/cassandra/index/accord/MemtableIndex.java:
##########
@@ -63,13 +65,23 @@ public Segment write(IndexDescriptor id) throws IOException
         return memoryIndex.write(id);
     }
 
-    public Collection<ByteBuffer> search(int storeId, TableId tableId, byte[] start, boolean startInclusive, byte[] end, boolean endInclusive)
+    public void search(int storeId, TableId tableId, byte[] start, byte[] end,
+                       Timestamp minTimestamp,

Review Comment:
   why Timestamp vs TxnId? Would I think make intent clearer to stick to TxnId



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


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


Re: [PR] CASSANDRA-20772 Accord Route Index does not filter based off txn_id range which causes segments which can't contain the data to be queried [cassandra]

Posted by "belliottsmith (via GitHub)" <gi...@apache.org>.
belliottsmith commented on code in PR #4257:
URL: https://github.com/apache/cassandra/pull/4257#discussion_r2218620732


##########
src/java/org/apache/cassandra/index/accord/MemtableIndex.java:
##########
@@ -63,13 +65,23 @@ public Segment write(IndexDescriptor id) throws IOException
         return memoryIndex.write(id);
     }
 
-    public Collection<ByteBuffer> search(int storeId, TableId tableId, byte[] start, boolean startInclusive, byte[] end, boolean endInclusive)
+    public void search(int storeId, TableId tableId, byte[] start, byte[] end,
+                       Timestamp minTimestamp,

Review Comment:
   I think would be clearer to at least name the parameters minTxnId and maxTxnId, even if we accept Timestamp (realise max may be a Timestamp). Would be good to apply this more generally, and also to use TxnId where appropriate (e.g. inside the actual indexes where we only manage TxnId - only the parameters may be Timestamp instead)



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


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


Re: [PR] CASSANDRA-20772 Accord Route Index does not filter based off txn_id range which causes segments which can't contain the data to be queried [cassandra]

Posted by "dcapwell (via GitHub)" <gi...@apache.org>.
dcapwell commented on code in PR #4257:
URL: https://github.com/apache/cassandra/pull/4257#discussion_r2211286056


##########
test/unit/org/apache/cassandra/index/accord/AccordIndexUtil.java:
##########
@@ -0,0 +1,41 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.cassandra.index.accord;
+
+import accord.primitives.TxnId;
+import org.apache.cassandra.service.accord.TokenRange;
+import org.apache.cassandra.service.accord.api.TokenKey;
+
+public class AccordIndexUtil

Review Comment:
   our identifies are too verbose in the tests, so just utility class to make error messages and stateful histories clean



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


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


Re: [PR] CASSANDRA-20772 Accord Route Index does not filter based off txn_id range which causes segments which can't contain the data to be queried [cassandra]

Posted by "dcapwell (via GitHub)" <gi...@apache.org>.
dcapwell commented on code in PR #4257:
URL: https://github.com/apache/cassandra/pull/4257#discussion_r2211246184


##########
src/java/org/apache/cassandra/index/accord/RangeMemoryIndex.java:
##########
@@ -58,13 +63,51 @@ public class RangeMemoryIndex
 {
 
     @GuardedBy("this")
-    private final Map<Group, RangeTree<byte[], Range, DecoratedKey>> map = new HashMap<>();
-    @GuardedBy("this")
-    private final Map<Group, Metadata> groupMetadata = new HashMap<>();
+    private final Map<Key, Group> map = new HashMap<>();
 
-    private static class Metadata
+    private static class Group
     {
+        private RangeTree<byte[], Range, DecoratedKey> tree = createRangeTree();
         public byte[] minTerm, maxTerm;
+        public TxnId minTimestamp = TxnId.MAX;
+        public TxnId maxTimestamp = TxnId.NONE;
+
+        void add(Range range, DecoratedKey key, TxnId txnId, byte[] start, byte[] end)
+        {
+            tree.add(range, key);
+            minTerm = minTerm == null ? start : ByteArrayUtil.compareUnsigned(minTerm, 0, start, 0, minTerm.length) > 0 ? start : minTerm;
+            maxTerm = maxTerm == null ? end : ByteArrayUtil.compareUnsigned(maxTerm, 0, end, 0, maxTerm.length) < 0 ? end : maxTerm;
+            if (minTimestamp.compareTo(txnId) > 0)
+                minTimestamp = txnId;
+            if (maxTimestamp.compareTo(txnId) < 0)
+                maxTimestamp = txnId;
+        }
+
+        void search(byte[] start, byte[] end,
+                    Timestamp minTimestamp, Timestamp maxTimestamp,
+                    Consumer<Map.Entry<RangeMemoryIndex.Range, DecoratedKey>> fn)
+        {
+            if (this.minTimestamp.compareTo(maxTimestamp) > 0 || this.maxTimestamp.compareTo(minTimestamp) < 0)
+                return;
+            tree.search(new Range(start, end), e -> {
+                TxnId id = AccordKeyspace.JournalColumns.getJournalKey(e.getValue()).id;

Review Comment:
   not a fan of this cost, but my thinking is as follows
   
   1) the in-memory cost is the `ByteBuffer`
   2) only called when the range intersects, so each call are limited to possible matches, so just need to do the timestamp filter.
   
   I don't know if min/max are no-op in the common case (i doubt it as it should be based off durability as far as i can tell), so don't think it really makes sense to try to optimize the filter to avoid this cost when min/max are the full range



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


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