You are viewing a plain text version of this content. The canonical link for it is here.
Posted to pr@cassandra.apache.org by "alanwang67 (via GitHub)" <gi...@apache.org> on 2026/08/25 02:42:37 UTC
[PR] CASSANDRA-21605 Improve algorithmic complexity for finding intersecting SSTables for LCS compaction candidates [cassandra]
alanwang67 opened a new pull request, #5061:
URL: https://github.com/apache/cassandra/pull/5061
For LCS, SSTables in levels 1 through level 8 are already stored in a tree set and are disjoint. However when we look for compaction candidates we do a linear scan of the entire set to find intersecting SSTables. We can instead just take the floor of the tree set and iterate forwards until we no longer find any intersections.
patch by Alan Wang;
reviewed by for [CASSANDRA-21605](https://issues.apache.org/jira/browse/CASSANDRA-21605)
Co-authored-by: Name1
Co-authored-by: Name2
--
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-21605 Improve algorithmic complexity for finding intersecting SSTables for LCS compaction candidates [cassandra]
Posted by "dcapwell (via GitHub)" <gi...@apache.org>.
dcapwell commented on code in PR #5061:
URL: https://github.com/apache/cassandra/pull/5061#discussion_r3898529788
##########
test/unit/org/apache/cassandra/db/compaction/LeveledCompactionStrategyTest.java:
##########
@@ -595,6 +597,98 @@ public void testDisableSTCSInL0() throws IOException
}
}
+ @Test
+ public void testLinearScanTreeSetIntersectionEquivalence() throws IOException
+ {
+ ColumnFamilyStore cfs = MockSchema.newCFS();
+ List<SSTableReader> sstables = new ArrayList<>();
+
+ long seed = System.currentTimeMillis();
+ Random r = new Random(seed);
Review Comment:
is there a reason to hand roll vs just using `Property.qt()`? Random tests that only test 1 seed are problematic as it takes months before we have enough *examples* to know the test is stable. i ran this on my laptop and the whole class is 30s so you can run this test 10+ times I believe.
--
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-21605 Improve algorithmic complexity for finding intersecting SSTables for LCS compaction candidates [cassandra]
Posted by "alanwang67 (via GitHub)" <gi...@apache.org>.
alanwang67 commented on code in PR #5061:
URL: https://github.com/apache/cassandra/pull/5061#discussion_r3865870636
##########
src/java/org/apache/cassandra/db/compaction/LeveledManifest.java:
##########
@@ -592,6 +596,26 @@ private Collection<SSTableReader> getCandidatesFor(int level)
return Collections.emptyList();
}
Review Comment:
Refactored this so that we add the `sstable` outside of `getIntersectingSSTablesFromTreeSet` to make it less confusing.
--
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-21605 Improve algorithmic complexity for finding intersecting SSTables for LCS compaction candidates [cassandra]
Posted by "alanwang67 (via GitHub)" <gi...@apache.org>.
alanwang67 commented on code in PR #5061:
URL: https://github.com/apache/cassandra/pull/5061#discussion_r3865885751
##########
test/unit/org/apache/cassandra/db/compaction/LeveledCompactionStrategyTest.java:
##########
@@ -595,6 +598,93 @@ public void testDisableSTCSInL0() throws IOException
}
}
+ @Test
+ public void testLinearScanTreeSetIntersectionEquivalence() throws IOException
+ {
+ ColumnFamilyStore cfs = MockSchema.newCFS();
+ List<SSTableReader> sstables = new ArrayList<>();
+
+ long seed = System.currentTimeMillis();
Review Comment:
Did this within the assert when it fails.
--
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-21605 Improve algorithmic complexity for finding intersecting SSTables for LCS compaction candidates [cassandra]
Posted by "krummas (via GitHub)" <gi...@apache.org>.
krummas commented on code in PR #5061:
URL: https://github.com/apache/cassandra/pull/5061#discussion_r3931621285
##########
src/java/org/apache/cassandra/db/compaction/LeveledGenerations.java:
##########
@@ -96,6 +96,13 @@ Set<SSTableReader> get(int level)
return levels[level - 1];
}
+ TreeSet<SSTableReader> getSortedLevel(int level)
+ {
+ if (level > levelCount() - 1 || level <= 0)
Review Comment:
this needs to make sure `level <= 1`
--
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-21605 Improve algorithmic complexity for finding intersecting SSTables for LCS compaction candidates [cassandra]
Posted by "krummas (via GitHub)" <gi...@apache.org>.
krummas commented on code in PR #5061:
URL: https://github.com/apache/cassandra/pull/5061#discussion_r3862560683
##########
src/java/org/apache/cassandra/db/compaction/LeveledManifest.java:
##########
@@ -573,14 +575,16 @@ private Collection<SSTableReader> getCandidatesFor(int level)
return candidates;
}
+ // We know that because we are in level L0+, this is a tree set with disjoint SSTables
+ TreeSet<SSTableReader> sstablesNextLevel = (TreeSet<SSTableReader>) generations.get(level + 1);
Review Comment:
maybe add a method on `LeveledGenerations` (`getSorted`?) that gives you the treeset without having to cast?
##########
src/java/org/apache/cassandra/db/compaction/LeveledManifest.java:
##########
@@ -592,6 +596,26 @@ private Collection<SSTableReader> getCandidatesFor(int level)
return Collections.emptyList();
}
+ public static Set<SSTableReader> getIntersectingSSTablesFromTreeSet(SSTableReader sstable, TreeSet<SSTableReader> sstablesNextLevel)
+ {
+ Set<SSTableReader> candidates = new HashSet<>();
+ candidates.add(sstable);
+
+ if (sstablesNextLevel.isEmpty())
+ return candidates;
+
+ SSTableReader start = sstablesNextLevel.floor(sstable);
+ Iterator<SSTableReader> it = sstablesNextLevel.tailSet(start != null ? start : sstablesNextLevel.first(), true).iterator();
+
+ while (it.hasNext()) {
Review Comment:
nit; put the brace on newline
##########
test/unit/org/apache/cassandra/db/compaction/LeveledCompactionStrategyTest.java:
##########
@@ -595,6 +598,93 @@ public void testDisableSTCSInL0() throws IOException
}
}
+ @Test
+ public void testLinearScanTreeSetIntersectionEquivalence() throws IOException
+ {
+ ColumnFamilyStore cfs = MockSchema.newCFS();
+ List<SSTableReader> sstables = new ArrayList<>();
+
+ long seed = System.currentTimeMillis();
+ Random r = new Random(seed);
+
+ // Generates disjoint sorted SSTables that match what we see in L1
+ int i = 0;
+ int lower_bound = 10;
Review Comment:
`lowerBound`
##########
test/unit/org/apache/cassandra/db/compaction/LeveledCompactionStrategyTest.java:
##########
@@ -595,6 +598,93 @@ public void testDisableSTCSInL0() throws IOException
}
}
+ @Test
+ public void testLinearScanTreeSetIntersectionEquivalence() throws IOException
+ {
+ ColumnFamilyStore cfs = MockSchema.newCFS();
+ List<SSTableReader> sstables = new ArrayList<>();
+
+ long seed = System.currentTimeMillis();
+ Random r = new Random(seed);
+
+ // Generates disjoint sorted SSTables that match what we see in L1
+ int i = 0;
+ int lower_bound = 10;
+ while (i < 10000)
+ {
+ int start = lower_bound + 1 + r.nextInt(30);
+ int end = start + 10 + r.nextInt(30);
Review Comment:
could try single token sstables here + in the switch below?
##########
src/java/org/apache/cassandra/db/compaction/LeveledManifest.java:
##########
@@ -592,6 +596,26 @@ private Collection<SSTableReader> getCandidatesFor(int level)
return Collections.emptyList();
}
+ public static Set<SSTableReader> getIntersectingSSTablesFromTreeSet(SSTableReader sstable, TreeSet<SSTableReader> sstablesNextLevel)
Review Comment:
can be package protected and `@VisibleForTesting`
##########
src/java/org/apache/cassandra/db/compaction/LeveledManifest.java:
##########
@@ -592,6 +596,26 @@ private Collection<SSTableReader> getCandidatesFor(int level)
return Collections.emptyList();
}
Review Comment:
maybe add some javadoc to describe that `sstable` will be included in the result
##########
test/unit/org/apache/cassandra/db/compaction/LeveledCompactionStrategyTest.java:
##########
@@ -595,6 +598,93 @@ public void testDisableSTCSInL0() throws IOException
}
}
+ @Test
+ public void testLinearScanTreeSetIntersectionEquivalence() throws IOException
+ {
+ ColumnFamilyStore cfs = MockSchema.newCFS();
+ List<SSTableReader> sstables = new ArrayList<>();
+
+ long seed = System.currentTimeMillis();
Review Comment:
print/log the seed
--
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-21605 Improve algorithmic complexity for finding intersecting SSTables for LCS compaction candidates [cassandra]
Posted by "alanwang67 (via GitHub)" <gi...@apache.org>.
alanwang67 commented on code in PR #5061:
URL: https://github.com/apache/cassandra/pull/5061#discussion_r3898649949
##########
test/unit/org/apache/cassandra/db/compaction/LeveledCompactionStrategyTest.java:
##########
@@ -595,6 +597,98 @@ public void testDisableSTCSInL0() throws IOException
}
}
+ @Test
+ public void testLinearScanTreeSetIntersectionEquivalence() throws IOException
+ {
+ ColumnFamilyStore cfs = MockSchema.newCFS();
+ List<SSTableReader> sstables = new ArrayList<>();
+
+ long seed = System.currentTimeMillis();
+ Random r = new Random(seed);
Review Comment:
Gotcha, will default to using `Property.qt()` from now on.
--
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-21605 Improve algorithmic complexity for finding intersecting SSTables for LCS compaction candidates [cassandra]
Posted by "krummas (via GitHub)" <gi...@apache.org>.
krummas commented on code in PR #5061:
URL: https://github.com/apache/cassandra/pull/5061#discussion_r3931621285
##########
src/java/org/apache/cassandra/db/compaction/LeveledGenerations.java:
##########
@@ -96,6 +96,13 @@ Set<SSTableReader> get(int level)
return levels[level - 1];
}
+ TreeSet<SSTableReader> getSortedLevel(int level)
+ {
+ if (level > levelCount() - 1 || level <= 0)
Review Comment:
this needs to make sure `level <= 1`
--
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-21605 Improve algorithmic complexity for finding intersecting SSTables for LCS compaction candidates [cassandra]
Posted by "gandherva (via GitHub)" <gi...@apache.org>.
gandherva commented on code in PR #5061:
URL: https://github.com/apache/cassandra/pull/5061#discussion_r4244405035
##########
src/java/org/apache/cassandra/db/compaction/LeveledGenerations.java:
##########
@@ -96,6 +96,13 @@ Set<SSTableReader> get(int level)
return levels[level - 1];
}
+ TreeSet<SSTableReader> getSortedLevel(int level)
+ {
Review Comment:
(1) There is already `get(level)` and the new `getSortedLevel`, is a copy of `get(level)` with one additional check that level should be greater than 0.
(2) Having two methods one as `get(level)` and one as `getSortedlevel()` could mislead readers to think that the 2nd method would give something different while both return the same set.
So for these two reasons, I will suggest dropping `getSortedLevel()` method and doing one of these options.
Option A: As the only validation which is needed is level > 0 , this could be performed by the caller before calling get(level) and casting it to a Tree set. In the case of the current caller as it is level +1 before calling, may be the validation is not needed. I will leave it upto you.
Option B: Alternatively if we want to have a method for this, we could create one called `getNonL0Level` or `getNonZeroLevel` , inside that method we could do a check for level not 0 an then call `get(level)` so that it handles the rest of validations.
Both these options avoid duplication of code and avoid creation of a potentially misleading method called getSortedLevel which is almost a copy of get(level)
##########
src/java/org/apache/cassandra/db/compaction/LeveledManifest.java:
##########
@@ -592,6 +596,30 @@ private Collection<SSTableReader> getCandidatesFor(int level)
return Collections.emptyList();
}
+ /**
+ * Precondition: SSTables in sstablesNextLevel must be disjoint
+ */
+ @VisibleForTesting
+ protected static Set<SSTableReader> getIntersectingSSTablesFromTreeSet(SSTableReader sstable, TreeSet<SSTableReader> sstablesNextLevel)
+ {
+ Set<SSTableReader> candidates = new HashSet<>();
+
+ if (sstablesNextLevel.isEmpty())
+ return candidates;
+
+ SSTableReader start = sstablesNextLevel.floor(sstable);
+ Iterator<SSTableReader> it = sstablesNextLevel.tailSet(start != null ? start : sstablesNextLevel.first(), true).iterator();
Review Comment:
To improve readability and to avoid calling 'sstablesNextLevel.tailSet(sstablesNextLevel.first())', as we are calling tailSet with the first element which does extra work(an additional tree navigation to find the first element and creating a view object and its sub objects) that could be avoided by using TreeSet directly
I'd suggest to change it like this
if start is null then do
`it = sstablesNextLevel.iterator()`
or else do `it = sstablesNextLevel.tailSet(start,true).iterator() `
This will also avoid the need to do the early return with `if (sstablesNextLevel.isEmpty())` check at line 607-608. So we can remove them as well.
--
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-21605 Improve algorithmic complexity for finding intersecting SSTables for LCS compaction candidates [cassandra]
Posted by "dcapwell (via GitHub)" <gi...@apache.org>.
dcapwell commented on code in PR #5061:
URL: https://github.com/apache/cassandra/pull/5061#discussion_r3898264422
##########
src/java/org/apache/cassandra/db/compaction/LeveledManifest.java:
##########
@@ -450,7 +451,8 @@ private static Set<SSTableReader> overlapping(Collection<SSTableReader> candidat
return overlapping(first, last, others);
}
- private static Set<SSTableReader> overlappingWithBounds(SSTableReader sstable, Map<SSTableReader, Bounds<Token>> others)
+ @VisibleForTesting
Review Comment:
was changed from 'private static' to '@VisibleForTesting static'. This method is only still used internally and is not referenced by any test ; can we revert?
--
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-21605 Improve algorithmic complexity for finding intersecting SSTables for LCS compaction candidates [cassandra]
Posted by "dcapwell (via GitHub)" <gi...@apache.org>.
dcapwell commented on code in PR #5061:
URL: https://github.com/apache/cassandra/pull/5061#discussion_r3898537643
##########
test/unit/org/apache/cassandra/db/compaction/LeveledCompactionStrategyTest.java:
##########
@@ -595,6 +597,98 @@ public void testDisableSTCSInL0() throws IOException
}
}
+ @Test
+ public void testLinearScanTreeSetIntersectionEquivalence() throws IOException
Review Comment:
you didn't run this as a repeat job i assume; its failing often for me
```
unit.framework.AssertionFailedError
at org.apache.cassandra.db.compaction.LeveledManifest.overlappingWithBounds(LeveledManifest.java:471)
at org.apache.cassandra.db.compaction.LeveledManifest.overlapping(LeveledManifest.java:466)
at org.apache.cassandra.db.compaction.LeveledCompactionStrategyTest.testLinearScanTreeSetIntersectionEquivalence(LeveledCompactionStrategyTest.java:686)
at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
```
Notice how the seed was also lost? this is one of the common issues with hand rolling, which is why I always discourage 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