You are viewing a plain text version of this content. The canonical link for it is here.
Posted to pr@cassandra.apache.org by "maedhroz (via GitHub)" <gi...@apache.org> on 2024/11/01 21:41:44 UTC
[PR] CASSANDRA-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
maedhroz opened a new pull request, #3649:
URL: https://github.com/apache/cassandra/pull/3649
(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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "maedhroz (via GitHub)" <gi...@apache.org>.
maedhroz commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1833400112
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -164,33 +183,75 @@ public UnfilteredRowIterator computeNext()
// saying this iterator must not return the same partition twice.
skipToNextPartition();
- UnfilteredRowIterator iterator = nextRowIterator(this::nextSelectedKeyInRange);
- return iterator != null
- ? iteratePartition(iterator)
- : endOfData();
+ UnfilteredRowIterator iterator = nextRowIterator(this::nextSelectedKeysInRange);
+ return iterator != null ? iteratePartition(iterator) : endOfData();
}
/**
- * Tries to obtain a row iterator for one of the supplied keys by repeatedly calling
+ * Tries to obtain a row iterator for the supplied keys by repeatedly calling
* {@link ResultRetriever#queryStorageAndFilter} until it gives a non-null result.
- * The keySupplier should return the next key with every call to get() and
- * null when there are no more keys to try.
+ * The keysSupplier should return the next batch of keys with every call to get()
+ * and null when there are no more keys to try.
*
* @return an iterator or null if all keys were tried with no success
*/
- private @Nullable UnfilteredRowIterator nextRowIterator(@Nonnull Supplier<PrimaryKey> keySupplier)
+ private @Nullable UnfilteredRowIterator nextRowIterator(@Nonnull Supplier<List<PrimaryKey>> keysSupplier)
{
UnfilteredRowIterator iterator = null;
while (iterator == null)
{
- PrimaryKey key = keySupplier.get();
- if (key == null)
+ List<PrimaryKey> keys = keysSupplier.get();
+ if (keys.isEmpty())
return null;
- iterator = queryStorageAndFilter(key);
+ iterator = queryStorageAndFilter(keys);
}
return iterator;
}
+ /**
+ * Retrieves the next batch of primary keys (i.e. up to {@link #partitionRowBatchSize} of them) that are
+ * contained by one of the query key ranges and selected by the {@link QueryController}. If the next key falls
+ * out of the current key range, it skips to the next key range, and so on. If no more keys accepted by
+ * the controller are available, and empty list is returned.
+ *
+ * @return a list of up to {@link #partitionRowBatchSize} primary keys
+ */
+ private List<PrimaryKey> nextSelectedKeysInRange()
+ {
+ List<PrimaryKey> threadLocalNextKeys = nextKeys.get();
+ threadLocalNextKeys.clear();
+ PrimaryKey firstKey;
+
+ do
+ {
+ firstKey = nextKeyInRange();
+
+ if (firstKey == null)
+ return Collections.emptyList();
+ }
+ while (queryController.doesNotSelect(firstKey) || firstKey.equals(lastKey));
+
+ lastKey = firstKey;
+ threadLocalNextKeys.add(firstKey);
+ fillNextSelectedKeysInPartition(firstKey.partitionKey(), threadLocalNextKeys);
Review Comment:
@jasonstack The first iterator now batches, so we'll be able to ensure a single partition read when there are PARTITION_ROW_BATCH_SIZE matches or fewer.
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "jasonstack (via GitHub)" <gi...@apache.org>.
jasonstack commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1832203612
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -222,45 +236,57 @@ public UnfilteredRowIterator computeNext()
/**
* Returns the next available key contained by one of the keyRanges and selected by the queryController.
* If the next key falls out of the current key range, it skips to the next key range, and so on.
- * If no more keys acceptd by the controller are available, returns null.
+ * If no more keys acceptd by the controller are available, returns an empty list.
*/
- private @Nullable PrimaryKey nextSelectedKeyInRange()
+ private List<PrimaryKey> nextSelectedKeyInRange()
{
+ List<PrimaryKey> threadLocalNextKeys = nextKeys.get();
+ threadLocalNextKeys.clear();
PrimaryKey key;
+
do
{
key = nextKeyInRange();
+
+ if (key == null)
+ return Collections.emptyList();
}
- while (key != null && queryController.doesNotSelect(key));
- return key;
+ while (queryController.doesNotSelect(key) || key.equals(lastKey));
+
+ lastKey = key;
+ threadLocalNextKeys.add(key);
+ return threadLocalNextKeys;
}
/**
- * Retrieves the next primary key that belongs to the given partition and is selected by the query controller.
- * The underlying key iterator is advanced only if the key belongs to the same partition.
- * <p>
- * Returns null if:
- * <ul>
- * <li>there are no more keys</li>
- * <li>the next key is beyond the upper bound</li>
- * <li>the next key belongs to a different partition</li>
- * </ul>
- * </p>
+ * Retrieves the next batch of primary keys (i.e. up to {@link #partitionRowBatchSize} of them) that belong to
+ * the given partition and are selected by the query controller, advancing the underlying iterator only while
+ * the next key belongs to that partition.
+ *
+ * @return a list of up to {@link #partitionRowBatchSize} primary keys within the given partition and data range
*/
- private @Nullable PrimaryKey nextSelectedKeyInPartition(DecoratedKey partitionKey)
+ private List<PrimaryKey> nextSelectedKeysInPartition(DecoratedKey partitionKey)
Review Comment:
so, for this wide schema:
```
createTable("CREATE TABLE %s (pk int, ck int, v1 int, primary key(pk, ck))");
executeNet("CREATE INDEX index_1 ON %s(v1) USING 'sai'");
waitForTableIndexesQueryable();
execute("INSERT INTO %s (pk, ck, v1) VALUES(1, 1, 1)");
execute("INSERT INTO %s (pk, ck, v1) VALUES(1, 2, 1)");
execute("INSERT INTO %s (pk, ck, v1) VALUES(1, 3, 1)");
execute("INSERT INTO %s (pk, ck, v1) VALUES(1, 4, 1)");
execute("INSERT INTO %s (pk, ck, v1) VALUES(1, 5, 1)");
flush();
ResultSet rows = executeNet("SELECT * FROM %s WHERE v1 = 1");
```
`queryStorageAndFilter` is called twice:
* first time reading with pk=1 and ck=1
* second time reading with pk=1 and ck in [2,3,4,5]
can we improve it to execute one local read?
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "maedhroz (via GitHub)" <gi...@apache.org>.
maedhroz commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1833111954
##########
test/distributed/org/apache/cassandra/fuzz/sai/PagingStaticsTortureTest.java:
##########
@@ -0,0 +1,54 @@
+/*
+ * 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.fuzz.sai;
+
+import org.junit.BeforeClass;
+
+import org.apache.cassandra.distributed.Cluster;
+import org.apache.cassandra.harry.sut.injvm.InJvmSut;
+import org.apache.cassandra.harry.sut.injvm.InJvmSutBase;
+
+public class PagingStaticsTortureTest extends StaticsTortureTest
+{
+ private static final int FETCH_SIZE = 10;
+
+ @BeforeClass
+ public static void before() throws Throwable
+ {
+ cluster = Cluster.build()
+ .withNodes(1)
+ .withConfig(InJvmSutBase.defaultConfig())
+ .createWithoutStarting();
+ cluster.setUncaughtExceptionsFilter(t -> {
+ logger.error("Caught exception, reporting during shutdown. Ignoring.", t);
Review Comment:
Not sure. It's a pattern used in a few Harry tests...will explore...
CC @ifesdjeen
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "jasonstack (via GitHub)" <gi...@apache.org>.
jasonstack commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1832154044
##########
test/distributed/org/apache/cassandra/fuzz/sai/PagingStaticsTortureTest.java:
##########
@@ -0,0 +1,54 @@
+/*
+ * 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.fuzz.sai;
+
+import org.junit.BeforeClass;
+
+import org.apache.cassandra.distributed.Cluster;
+import org.apache.cassandra.harry.sut.injvm.InJvmSut;
+import org.apache.cassandra.harry.sut.injvm.InJvmSutBase;
+
+public class PagingStaticsTortureTest extends StaticsTortureTest
+{
+ private static final int FETCH_SIZE = 10;
+
+ @BeforeClass
+ public static void before() throws Throwable
+ {
+ cluster = Cluster.build()
+ .withNodes(1)
+ .withConfig(InJvmSutBase.defaultConfig())
+ .createWithoutStarting();
+ cluster.setUncaughtExceptionsFilter(t -> {
+ logger.error("Caught exception, reporting during shutdown. Ignoring.", t);
Review Comment:
is it always reported during shutdown?
##########
src/java/org/apache/cassandra/utils/InsertionOrderedNavigableSet.java:
##########
@@ -0,0 +1,297 @@
+/*
+ * 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.utils;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.NavigableSet;
+import java.util.NoSuchElementException;
+import java.util.Objects;
+import java.util.SortedSet;
+
+import com.google.common.base.Preconditions;
+
+/**
+ * A {@link NavigableSet} that enforces in-order insertion of elements. This is helpful when we
+ * have an already-ordered collection with no duplicates and want constant time insertion.
+ * <p>
+ * Note: Not all methods of {@link NavigableSet} are implemented.
+ *
+ * @param <E> the type of elements maintained by this set
+ */
+public class InsertionOrderedNavigableSet<E> implements NavigableSet<E>
+{
+ private final ArrayList<E> elements;
+ private final Comparator<? super E> comparator;
+
+ public InsertionOrderedNavigableSet(Comparator<? super E> comparator)
+ {
+ this.elements = new ArrayList<>();
+ this.comparator = comparator;
+ }
+
+ @Override
+ public E lower(E e)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public E floor(E e)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public E ceiling(E e)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public E higher(E e)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public E pollFirst()
+ {
+ if (isEmpty())
+ return null;
+
+ return elements.remove(0);
+ }
+
+ @Override
+ public E pollLast()
+ {
+ if (isEmpty())
+ return null;
+
+ return elements.remove(size() - 1);
+ }
+
+ @Override
+ public int size()
+ {
+ return elements.size();
+ }
+
+ @Override
+ public boolean isEmpty()
+ {
+ return elements.isEmpty();
+ }
+
+ @Override
+ public boolean contains(Object o)
+ {
+ return elements.contains(o);
+ }
+
+ @Override
+ public Iterator<E> iterator()
+ {
+ return elements.iterator();
+ }
+
+ @Override
+ public Object[] toArray()
+ {
+ return elements.toArray();
+ }
+
+ @Override
+ public <T> T[] toArray(T[] a)
+ {
+ return elements.toArray(a);
+ }
+
+ @Override
+ public boolean add(E e)
+ {
+ if (!isEmpty() && comparator.compare(e, last()) <= 0)
+ throw new IllegalStateException("Cannot add element less than or equal to current last element");
+
+ return elements.add(e);
+ }
+
+ @Override
+ public boolean remove(Object o)
+ {
+ return elements.remove(o);
+ }
+
+ @Override
+ public boolean containsAll(Collection<?> c)
+ {
+ return elements.containsAll(c);
+ }
+
+ @Override
+ public boolean addAll(Collection<? extends E> c)
+ {
+ boolean modified = false;
+ for (E element : c)
+ if (add(element))
+ modified = true;
+ return modified;
+ }
+
+ @Override
+ public boolean retainAll(Collection<?> c)
+ {
+ return elements.retainAll(c);
+ }
+
+ @Override
+ public boolean removeAll(Collection<?> c)
+ {
+ return elements.removeAll(c);
+ }
+
+ @Override
+ public void clear()
+ {
+ elements.clear();
+ }
+
+ @Override
+ public NavigableSet<E> descendingSet()
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public Iterator<E> descendingIterator()
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public NavigableSet<E> headSet(E toElement, boolean inclusive)
+ {
+ Preconditions.checkNotNull(toElement);
+
+ if (isEmpty())
+ return Collections.emptyNavigableSet();
+
+ NavigableSet<E> head = new InsertionOrderedNavigableSet<>(comparator);
+
+ for (E element : elements)
+ {
+ int comparison = comparator.compare(element, toElement);
+ if (comparison > 0 || comparison == 0 && inclusive )
Review Comment:
if it's not inclusive and the same comparison, we skip it.
##########
src/java/org/apache/cassandra/utils/InsertionOrderedNavigableSet.java:
##########
@@ -0,0 +1,297 @@
+/*
+ * 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.utils;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.NavigableSet;
+import java.util.NoSuchElementException;
+import java.util.Objects;
+import java.util.SortedSet;
+
+import com.google.common.base.Preconditions;
+
+/**
+ * A {@link NavigableSet} that enforces in-order insertion of elements. This is helpful when we
+ * have an already-ordered collection with no duplicates and want constant time insertion.
+ * <p>
+ * Note: Not all methods of {@link NavigableSet} are implemented.
+ *
+ * @param <E> the type of elements maintained by this set
+ */
+public class InsertionOrderedNavigableSet<E> implements NavigableSet<E>
+{
+ private final ArrayList<E> elements;
+ private final Comparator<? super E> comparator;
+
+ public InsertionOrderedNavigableSet(Comparator<? super E> comparator)
+ {
+ this.elements = new ArrayList<>();
+ this.comparator = comparator;
+ }
+
+ @Override
+ public E lower(E e)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public E floor(E e)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public E ceiling(E e)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public E higher(E e)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public E pollFirst()
+ {
+ if (isEmpty())
+ return null;
+
+ return elements.remove(0);
+ }
+
+ @Override
+ public E pollLast()
+ {
+ if (isEmpty())
+ return null;
+
+ return elements.remove(size() - 1);
+ }
+
+ @Override
+ public int size()
+ {
+ return elements.size();
+ }
+
+ @Override
+ public boolean isEmpty()
+ {
+ return elements.isEmpty();
+ }
+
+ @Override
+ public boolean contains(Object o)
+ {
+ return elements.contains(o);
+ }
+
+ @Override
+ public Iterator<E> iterator()
+ {
+ return elements.iterator();
+ }
+
+ @Override
+ public Object[] toArray()
+ {
+ return elements.toArray();
+ }
+
+ @Override
+ public <T> T[] toArray(T[] a)
+ {
+ return elements.toArray(a);
+ }
+
+ @Override
+ public boolean add(E e)
+ {
+ if (!isEmpty() && comparator.compare(e, last()) <= 0)
+ throw new IllegalStateException("Cannot add element less than or equal to current last element");
+
+ return elements.add(e);
+ }
+
+ @Override
+ public boolean remove(Object o)
+ {
+ return elements.remove(o);
+ }
+
+ @Override
+ public boolean containsAll(Collection<?> c)
+ {
+ return elements.containsAll(c);
+ }
+
+ @Override
+ public boolean addAll(Collection<? extends E> c)
+ {
+ boolean modified = false;
+ for (E element : c)
+ if (add(element))
+ modified = true;
+ return modified;
+ }
+
+ @Override
+ public boolean retainAll(Collection<?> c)
+ {
+ return elements.retainAll(c);
+ }
+
+ @Override
+ public boolean removeAll(Collection<?> c)
+ {
+ return elements.removeAll(c);
+ }
+
+ @Override
+ public void clear()
+ {
+ elements.clear();
+ }
+
+ @Override
+ public NavigableSet<E> descendingSet()
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public Iterator<E> descendingIterator()
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public NavigableSet<E> headSet(E toElement, boolean inclusive)
+ {
+ Preconditions.checkNotNull(toElement);
+
+ if (isEmpty())
+ return Collections.emptyNavigableSet();
+
+ NavigableSet<E> head = new InsertionOrderedNavigableSet<>(comparator);
+
+ for (E element : elements)
+ {
+ int comparison = comparator.compare(element, toElement);
+ if (comparison > 0 || comparison == 0 && inclusive )
Review Comment:
```suggestion
if (comparison > 0 || comparison == 0 && !inclusive)
```
##########
src/java/org/apache/cassandra/utils/InsertionOrderedNavigableSet.java:
##########
@@ -0,0 +1,297 @@
+/*
+ * 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.utils;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.NavigableSet;
+import java.util.NoSuchElementException;
+import java.util.Objects;
+import java.util.SortedSet;
+
+import com.google.common.base.Preconditions;
+
+/**
+ * A {@link NavigableSet} that enforces in-order insertion of elements. This is helpful when we
+ * have an already-ordered collection with no duplicates and want constant time insertion.
+ * <p>
+ * Note: Not all methods of {@link NavigableSet} are implemented.
+ *
+ * @param <E> the type of elements maintained by this set
+ */
+public class InsertionOrderedNavigableSet<E> implements NavigableSet<E>
+{
+ private final ArrayList<E> elements;
+ private final Comparator<? super E> comparator;
+
+ public InsertionOrderedNavigableSet(Comparator<? super E> comparator)
+ {
+ this.elements = new ArrayList<>();
+ this.comparator = comparator;
+ }
+
+ @Override
+ public E lower(E e)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public E floor(E e)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public E ceiling(E e)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public E higher(E e)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public E pollFirst()
+ {
+ if (isEmpty())
+ return null;
+
+ return elements.remove(0);
+ }
+
+ @Override
+ public E pollLast()
+ {
+ if (isEmpty())
+ return null;
+
+ return elements.remove(size() - 1);
+ }
+
+ @Override
+ public int size()
+ {
+ return elements.size();
+ }
+
+ @Override
+ public boolean isEmpty()
+ {
+ return elements.isEmpty();
+ }
+
+ @Override
+ public boolean contains(Object o)
+ {
+ return elements.contains(o);
+ }
+
+ @Override
+ public Iterator<E> iterator()
+ {
+ return elements.iterator();
+ }
+
+ @Override
+ public Object[] toArray()
+ {
+ return elements.toArray();
+ }
+
+ @Override
+ public <T> T[] toArray(T[] a)
+ {
+ return elements.toArray(a);
+ }
+
+ @Override
+ public boolean add(E e)
+ {
+ if (!isEmpty() && comparator.compare(e, last()) <= 0)
+ throw new IllegalStateException("Cannot add element less than or equal to current last element");
Review Comment:
would be nice to `e` into exception message
##########
src/java/org/apache/cassandra/utils/InsertionOrderedNavigableSet.java:
##########
@@ -0,0 +1,297 @@
+/*
+ * 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.utils;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.NavigableSet;
+import java.util.NoSuchElementException;
+import java.util.Objects;
+import java.util.SortedSet;
+
+import com.google.common.base.Preconditions;
+
+/**
+ * A {@link NavigableSet} that enforces in-order insertion of elements. This is helpful when we
+ * have an already-ordered collection with no duplicates and want constant time insertion.
+ * <p>
+ * Note: Not all methods of {@link NavigableSet} are implemented.
+ *
+ * @param <E> the type of elements maintained by this set
+ */
+public class InsertionOrderedNavigableSet<E> implements NavigableSet<E>
+{
+ private final ArrayList<E> elements;
+ private final Comparator<? super E> comparator;
+
+ public InsertionOrderedNavigableSet(Comparator<? super E> comparator)
+ {
+ this.elements = new ArrayList<>();
+ this.comparator = comparator;
+ }
+
+ @Override
+ public E lower(E e)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public E floor(E e)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public E ceiling(E e)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public E higher(E e)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public E pollFirst()
+ {
+ if (isEmpty())
+ return null;
+
+ return elements.remove(0);
+ }
+
+ @Override
+ public E pollLast()
+ {
+ if (isEmpty())
+ return null;
+
+ return elements.remove(size() - 1);
+ }
+
+ @Override
+ public int size()
+ {
+ return elements.size();
+ }
+
+ @Override
+ public boolean isEmpty()
+ {
+ return elements.isEmpty();
+ }
+
+ @Override
+ public boolean contains(Object o)
+ {
+ return elements.contains(o);
+ }
+
+ @Override
+ public Iterator<E> iterator()
+ {
+ return elements.iterator();
+ }
+
+ @Override
+ public Object[] toArray()
+ {
+ return elements.toArray();
+ }
+
+ @Override
+ public <T> T[] toArray(T[] a)
+ {
+ return elements.toArray(a);
+ }
+
+ @Override
+ public boolean add(E e)
+ {
+ if (!isEmpty() && comparator.compare(e, last()) <= 0)
+ throw new IllegalStateException("Cannot add element less than or equal to current last element");
Review Comment:
would be nice to include `e` into exception message
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "maedhroz (via GitHub)" <gi...@apache.org>.
maedhroz commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1831797045
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -412,15 +433,15 @@ private UnfilteredRowIterator applyIndexFilter(PrimaryKey key, UnfilteredRowIter
{
queryContext.rowsFiltered++;
- if (tree.isSatisfiedBy(key.partitionKey(), staticRow, staticRow))
+ if (tree.isSatisfiedBy(partition.partitionKey(), staticRow, staticRow))
hasMatch = true;
}
if (!hasMatch)
{
// shadowed by expired TTL or row tombstone or range tombstone
if (topK)
- queryContext.vectorContext().recordShadowedPrimaryKey(key);
+ queryContext.vectorContext().recordShadowedPrimaryKey(keys);
Review Comment:
@jasonstack @mike-tr-adamson @jbellis @pkolaczk I want to say I've broken things by shadowing all of the keys here. It seems like what I'd actually want to do is move this to the first loop above (while) and call this key by key is `isSatisfiedBy()` fails? Otherwise, I think what I have here will miss recording when _any_ matches occur....
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "maedhroz (via GitHub)" <gi...@apache.org>.
maedhroz commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1833407074
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -400,36 +430,43 @@ private UnfilteredRowIterator applyIndexFilter(PrimaryKey key, UnfilteredRowIter
{
queryContext.rowsFiltered++;
- if (tree.isSatisfiedBy(partition.partitionKey(), (Row) unfiltered, staticRow))
+ if (tree.isSatisfiedBy(partitionKey, (Row) unfiltered, staticRow))
{
- matchingRows.add(unfiltered);
+ matches.add(unfiltered);
hasMatch = true;
+
+ if (topK)
+ {
+ PrimaryKey shadowed = keyFactory.hasClusteringColumns()
+ ? keyFactory.create(partitionKey, ((Row) unfiltered).clustering())
+ : keyFactory.create(partitionKey);
+ keysToShadow.remove(shadowed);
+ }
}
}
}
- if (!hasMatch)
+ if (topK)
{
- queryContext.rowsFiltered++;
+ // If any rows match the filter, there should be no need to shadow the static primary key:
+ if (hasMatch && keyFactory.hasClusteringColumns())
+ keysToShadow.remove(keyFactory.create(partitionKey, Clustering.STATIC_CLUSTERING));
- if (tree.isSatisfiedBy(key.partitionKey(), staticRow, staticRow))
- hasMatch = true;
+ // Record primary keys shadowed by expired TTLs, row tombstones, or range tombstones:
+ if (!keysToShadow.isEmpty())
+ queryContext.vectorContext().recordShadowedPrimaryKeys(keysToShadow);
Review Comment:
@jasonstack It looks like `VectorUpdateDeleteTest` does touch every codepath in this method. Indeed, it did break down a couple times during my refactor. What I've done here is loosely inspired on your suggestion, albeit with some protections to avoid allocations in the non-topK case.
I've also removed what really does look like an unnecessary second round of `isSatisfiedBy()` calls using just the static row. Before CASSANDRA-19034, this actually happened before the `while` loop that filters the rows, but it was never strictly necessary. I suppose I'll see if CI disagrees, but I think this make sense.
WDYT?
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "maedhroz (via GitHub)" <gi...@apache.org>.
maedhroz commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1833645393
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -400,36 +430,56 @@ private UnfilteredRowIterator applyIndexFilter(PrimaryKey key, UnfilteredRowIter
{
queryContext.rowsFiltered++;
- if (tree.isSatisfiedBy(partition.partitionKey(), (Row) unfiltered, staticRow))
+ if (tree.isSatisfiedBy(partitionKey, (Row) unfiltered, staticRow))
{
- matchingRows.add(unfiltered);
+ matches.add(unfiltered);
hasMatch = true;
+
+ if (topK)
+ {
+ PrimaryKey shadowed = keyFactory.hasClusteringColumns()
+ ? keyFactory.create(partitionKey, ((Row) unfiltered).clustering())
+ : keyFactory.create(partitionKey);
+ keysToShadow.remove(shadowed);
+ }
}
}
}
+ // If any non-static rows match the filter, there should be no need to shadow the static primary key:
+ if (topK && hasMatch && keyFactory.hasClusteringColumns())
+ keysToShadow.remove(keyFactory.create(partitionKey, Clustering.STATIC_CLUSTERING));
+
+ // We may not have any non-static row data to filter...
if (!hasMatch)
{
queryContext.rowsFiltered++;
- if (tree.isSatisfiedBy(key.partitionKey(), staticRow, staticRow))
+ if (tree.isSatisfiedBy(partitionKey, staticRow, staticRow))
+ {
hasMatch = true;
+
+ if (topK)
+ keysToShadow.remove(keyFactory.create(partitionKey, staticRow.clustering()));
Review Comment:
I think you're right...changing...
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "jasonstack (via GitHub)" <gi...@apache.org>.
jasonstack commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1832203612
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -222,45 +236,57 @@ public UnfilteredRowIterator computeNext()
/**
* Returns the next available key contained by one of the keyRanges and selected by the queryController.
* If the next key falls out of the current key range, it skips to the next key range, and so on.
- * If no more keys acceptd by the controller are available, returns null.
+ * If no more keys acceptd by the controller are available, returns an empty list.
*/
- private @Nullable PrimaryKey nextSelectedKeyInRange()
+ private List<PrimaryKey> nextSelectedKeyInRange()
{
+ List<PrimaryKey> threadLocalNextKeys = nextKeys.get();
+ threadLocalNextKeys.clear();
PrimaryKey key;
+
do
{
key = nextKeyInRange();
+
+ if (key == null)
+ return Collections.emptyList();
}
- while (key != null && queryController.doesNotSelect(key));
- return key;
+ while (queryController.doesNotSelect(key) || key.equals(lastKey));
+
+ lastKey = key;
+ threadLocalNextKeys.add(key);
+ return threadLocalNextKeys;
}
/**
- * Retrieves the next primary key that belongs to the given partition and is selected by the query controller.
- * The underlying key iterator is advanced only if the key belongs to the same partition.
- * <p>
- * Returns null if:
- * <ul>
- * <li>there are no more keys</li>
- * <li>the next key is beyond the upper bound</li>
- * <li>the next key belongs to a different partition</li>
- * </ul>
- * </p>
+ * Retrieves the next batch of primary keys (i.e. up to {@link #partitionRowBatchSize} of them) that belong to
+ * the given partition and are selected by the query controller, advancing the underlying iterator only while
+ * the next key belongs to that partition.
+ *
+ * @return a list of up to {@link #partitionRowBatchSize} primary keys within the given partition and data range
*/
- private @Nullable PrimaryKey nextSelectedKeyInPartition(DecoratedKey partitionKey)
+ private List<PrimaryKey> nextSelectedKeysInPartition(DecoratedKey partitionKey)
Review Comment:
so, for this wide schema:
```
createTable("CREATE TABLE %s (pk int, ck int, v1 int, primary key(pk, ck))");
executeNet("CREATE INDEX index_1 ON %s(v1) USING 'sai'");
waitForTableIndexesQueryable();
execute("INSERT INTO %s (pk, ck, v1) VALUES(1, 1, 1)");
execute("INSERT INTO %s (pk, ck, v1) VALUES(1, 2, 1)");
execute("INSERT INTO %s (pk, ck, v1) VALUES(1, 3, 1)");
execute("INSERT INTO %s (pk, ck, v1) VALUES(1, 4, 1)");
execute("INSERT INTO %s (pk, ck, v1) VALUES(1, 5, 1)");
flush();
ResultSet rows = executeNet("SELECT * FROM %s WHERE v1 = 1");
```
`queryStorageAndFilter` is called twice:
* first time reading with pk=1 and ck=1 - PrimaryKey is fetched from `nextSelectedKeyInRange`
* second time reading with pk=1 and ck in [2,3,4,5] - PrimaryKeys are fetched from `nextSelectedKeysInPartition`
can we improve it to execute one local read?
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "jasonstack (via GitHub)" <gi...@apache.org>.
jasonstack commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1832222320
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -412,15 +433,15 @@ private UnfilteredRowIterator applyIndexFilter(PrimaryKey key, UnfilteredRowIter
{
queryContext.rowsFiltered++;
- if (tree.isSatisfiedBy(key.partitionKey(), staticRow, staticRow))
+ if (tree.isSatisfiedBy(partition.partitionKey(), staticRow, staticRow))
hasMatch = true;
}
if (!hasMatch)
{
// shadowed by expired TTL or row tombstone or range tombstone
if (topK)
- queryContext.vectorContext().recordShadowedPrimaryKey(key);
+ queryContext.vectorContext().recordShadowedPrimaryKey(keys);
Review Comment:
```
private UnfilteredRowIterator applyIndexFilter(List<PrimaryKey> keys, UnfilteredRowIterator partition, FilterTree tree)
{
Row staticRow = partition.staticRow();
List<Unfiltered> matchingRows = new ArrayList<>();
boolean hasMatch = false;
Set<PrimaryKey> keysToShadow = new HashSet<>(keys);
// We need to filter the partition rows before filtering on the static row. If this is done in the other
// order then we get incorrect results if we are filtering on a partition key index on a table with a
// composite partition key.
while (partition.hasNext())
{
Unfiltered unfiltered = partition.next();
if (unfiltered.isRow())
{
queryContext.rowsFiltered++;
if (tree.isSatisfiedBy(partition.partitionKey(), (Row) unfiltered, staticRow))
{
matchingRows.add(unfiltered);
hasMatch = true;
PrimaryKey key = keyFactory.create(partition.partitionKey(), ((Row) unfiltered).clustering());
keysToShadow.remove(key);
}
}
}
if (!hasMatch)
{
queryContext.rowsFiltered++;
if (tree.isSatisfiedBy(partition.partitionKey(), staticRow, staticRow))
{
hasMatch = true;
keysToShadow.clear();
}
}
// shadowed by expired TTL or row tombstone or range tombstone
if (topK && !keysToShadow.isEmpty())
queryContext.vectorContext().recordShadowedPrimaryKey(keysToShadow);
if (!hasMatch)
{
// If there are no matches, return an empty partition. If reconciliation is required at the
// coordinator, replica filtering protection may make a second round trip to complete its view
// of the partition.
return null;
}
// Return all matches found, along with the static row...
return new PartitionIterator(partition, staticRow, matchingRows.iterator());
}
```
this might work.. but we need some tests...
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "maedhroz (via GitHub)" <gi...@apache.org>.
maedhroz commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1833400112
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -164,33 +183,75 @@ public UnfilteredRowIterator computeNext()
// saying this iterator must not return the same partition twice.
skipToNextPartition();
- UnfilteredRowIterator iterator = nextRowIterator(this::nextSelectedKeyInRange);
- return iterator != null
- ? iteratePartition(iterator)
- : endOfData();
+ UnfilteredRowIterator iterator = nextRowIterator(this::nextSelectedKeysInRange);
+ return iterator != null ? iteratePartition(iterator) : endOfData();
}
/**
- * Tries to obtain a row iterator for one of the supplied keys by repeatedly calling
+ * Tries to obtain a row iterator for the supplied keys by repeatedly calling
* {@link ResultRetriever#queryStorageAndFilter} until it gives a non-null result.
- * The keySupplier should return the next key with every call to get() and
- * null when there are no more keys to try.
+ * The keysSupplier should return the next batch of keys with every call to get()
+ * and null when there are no more keys to try.
*
* @return an iterator or null if all keys were tried with no success
*/
- private @Nullable UnfilteredRowIterator nextRowIterator(@Nonnull Supplier<PrimaryKey> keySupplier)
+ private @Nullable UnfilteredRowIterator nextRowIterator(@Nonnull Supplier<List<PrimaryKey>> keysSupplier)
{
UnfilteredRowIterator iterator = null;
while (iterator == null)
{
- PrimaryKey key = keySupplier.get();
- if (key == null)
+ List<PrimaryKey> keys = keysSupplier.get();
+ if (keys.isEmpty())
return null;
- iterator = queryStorageAndFilter(key);
+ iterator = queryStorageAndFilter(keys);
}
return iterator;
}
+ /**
+ * Retrieves the next batch of primary keys (i.e. up to {@link #partitionRowBatchSize} of them) that are
+ * contained by one of the query key ranges and selected by the {@link QueryController}. If the next key falls
+ * out of the current key range, it skips to the next key range, and so on. If no more keys accepted by
+ * the controller are available, and empty list is returned.
+ *
+ * @return a list of up to {@link #partitionRowBatchSize} primary keys
+ */
+ private List<PrimaryKey> nextSelectedKeysInRange()
+ {
+ List<PrimaryKey> threadLocalNextKeys = nextKeys.get();
+ threadLocalNextKeys.clear();
+ PrimaryKey firstKey;
+
+ do
+ {
+ firstKey = nextKeyInRange();
+
+ if (firstKey == null)
+ return Collections.emptyList();
+ }
+ while (queryController.doesNotSelect(firstKey) || firstKey.equals(lastKey));
+
+ lastKey = firstKey;
+ threadLocalNextKeys.add(firstKey);
+ fillNextSelectedKeysInPartition(firstKey.partitionKey(), threadLocalNextKeys);
Review Comment:
@jasonstack The first iterator now batches, so we'll be able to ensure a single partition read when there are PARTIITON_ROW_BATCH_SIZE matches or fewer.
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "jasonstack (via GitHub)" <gi...@apache.org>.
jasonstack commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1830631527
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -222,45 +234,64 @@ public UnfilteredRowIterator computeNext()
/**
* Returns the next available key contained by one of the keyRanges and selected by the queryController.
* If the next key falls out of the current key range, it skips to the next key range, and so on.
- * If no more keys acceptd by the controller are available, returns null.
+ * If no more keys acceptd by the controller are available, returns an empty list.
*/
- private @Nullable PrimaryKey nextSelectedKeyInRange()
+ private List<PrimaryKey> nextSelectedKeyInRange()
{
+ List<PrimaryKey> threadLocalNextKeys = nextKeys.get();
+ threadLocalNextKeys.clear();
PrimaryKey key;
+
do
{
key = nextKeyInRange();
+
+ if (key == null)
+ return Collections.emptyList();
}
- while (key != null && queryController.doesNotSelect(key));
- return key;
+ while (queryController.doesNotSelect(key) || key.equals(lastKey));
+
+ lastKey = key;
+ threadLocalNextKeys.add(key);
+ return threadLocalNextKeys;
}
/**
+ * TODO: update this description...
Review Comment:
leftover
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "maedhroz (via GitHub)" <gi...@apache.org>.
maedhroz commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1833115338
##########
src/java/org/apache/cassandra/utils/InsertionOrderedNavigableSet.java:
##########
@@ -0,0 +1,297 @@
+/*
+ * 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.utils;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.NavigableSet;
+import java.util.NoSuchElementException;
+import java.util.Objects;
+import java.util.SortedSet;
+
+import com.google.common.base.Preconditions;
+
+/**
+ * A {@link NavigableSet} that enforces in-order insertion of elements. This is helpful when we
+ * have an already-ordered collection with no duplicates and want constant time insertion.
+ * <p>
+ * Note: Not all methods of {@link NavigableSet} are implemented.
+ *
+ * @param <E> the type of elements maintained by this set
+ */
+public class InsertionOrderedNavigableSet<E> implements NavigableSet<E>
+{
+ private final ArrayList<E> elements;
+ private final Comparator<? super E> comparator;
+
+ public InsertionOrderedNavigableSet(Comparator<? super E> comparator)
+ {
+ this.elements = new ArrayList<>();
+ this.comparator = comparator;
+ }
+
+ @Override
+ public E lower(E e)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public E floor(E e)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public E ceiling(E e)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public E higher(E e)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public E pollFirst()
+ {
+ if (isEmpty())
+ return null;
+
+ return elements.remove(0);
+ }
+
+ @Override
+ public E pollLast()
+ {
+ if (isEmpty())
+ return null;
+
+ return elements.remove(size() - 1);
+ }
+
+ @Override
+ public int size()
+ {
+ return elements.size();
+ }
+
+ @Override
+ public boolean isEmpty()
+ {
+ return elements.isEmpty();
+ }
+
+ @Override
+ public boolean contains(Object o)
+ {
+ return elements.contains(o);
+ }
+
+ @Override
+ public Iterator<E> iterator()
+ {
+ return elements.iterator();
+ }
+
+ @Override
+ public Object[] toArray()
+ {
+ return elements.toArray();
+ }
+
+ @Override
+ public <T> T[] toArray(T[] a)
+ {
+ return elements.toArray(a);
+ }
+
+ @Override
+ public boolean add(E e)
+ {
+ if (!isEmpty() && comparator.compare(e, last()) <= 0)
+ throw new IllegalStateException("Cannot add element less than or equal to current last element");
+
+ return elements.add(e);
+ }
+
+ @Override
+ public boolean remove(Object o)
+ {
+ return elements.remove(o);
+ }
+
+ @Override
+ public boolean containsAll(Collection<?> c)
+ {
+ return elements.containsAll(c);
+ }
+
+ @Override
+ public boolean addAll(Collection<? extends E> c)
+ {
+ boolean modified = false;
+ for (E element : c)
+ if (add(element))
+ modified = true;
+ return modified;
+ }
+
+ @Override
+ public boolean retainAll(Collection<?> c)
+ {
+ return elements.retainAll(c);
+ }
+
+ @Override
+ public boolean removeAll(Collection<?> c)
+ {
+ return elements.removeAll(c);
+ }
+
+ @Override
+ public void clear()
+ {
+ elements.clear();
+ }
+
+ @Override
+ public NavigableSet<E> descendingSet()
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public Iterator<E> descendingIterator()
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public NavigableSet<E> headSet(E toElement, boolean inclusive)
+ {
+ Preconditions.checkNotNull(toElement);
+
+ if (isEmpty())
+ return Collections.emptyNavigableSet();
+
+ NavigableSet<E> head = new InsertionOrderedNavigableSet<>(comparator);
+
+ for (E element : elements)
+ {
+ int comparison = comparator.compare(element, toElement);
+ if (comparison > 0 || comparison == 0 && inclusive )
Review Comment:
Yikes. Good catch.
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "maedhroz (via GitHub)" <gi...@apache.org>.
maedhroz commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1833155123
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -222,45 +236,57 @@ public UnfilteredRowIterator computeNext()
/**
* Returns the next available key contained by one of the keyRanges and selected by the queryController.
* If the next key falls out of the current key range, it skips to the next key range, and so on.
- * If no more keys acceptd by the controller are available, returns null.
+ * If no more keys acceptd by the controller are available, returns an empty list.
*/
- private @Nullable PrimaryKey nextSelectedKeyInRange()
+ private List<PrimaryKey> nextSelectedKeyInRange()
{
+ List<PrimaryKey> threadLocalNextKeys = nextKeys.get();
+ threadLocalNextKeys.clear();
PrimaryKey key;
+
do
{
key = nextKeyInRange();
+
+ if (key == null)
+ return Collections.emptyList();
}
- while (key != null && queryController.doesNotSelect(key));
- return key;
+ while (queryController.doesNotSelect(key) || key.equals(lastKey));
+
+ lastKey = key;
+ threadLocalNextKeys.add(key);
+ return threadLocalNextKeys;
}
/**
- * Retrieves the next primary key that belongs to the given partition and is selected by the query controller.
- * The underlying key iterator is advanced only if the key belongs to the same partition.
- * <p>
- * Returns null if:
- * <ul>
- * <li>there are no more keys</li>
- * <li>the next key is beyond the upper bound</li>
- * <li>the next key belongs to a different partition</li>
- * </ul>
- * </p>
+ * Retrieves the next batch of primary keys (i.e. up to {@link #partitionRowBatchSize} of them) that belong to
+ * the given partition and are selected by the query controller, advancing the underlying iterator only while
+ * the next key belongs to that partition.
+ *
+ * @return a list of up to {@link #partitionRowBatchSize} primary keys within the given partition and data range
*/
- private @Nullable PrimaryKey nextSelectedKeyInPartition(DecoratedKey partitionKey)
+ private List<PrimaryKey> nextSelectedKeysInPartition(DecoratedKey partitionKey)
Review Comment:
Right. As it stands, a query that matches 100 rows in a partition doesn't go down to 1 local read, but 2. It might be easy to fix this by using `nextSelectedKeysInPartition()` at the end of `nextSelectedKeyInRange()`...will push something...
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "maedhroz (via GitHub)" <gi...@apache.org>.
maedhroz closed pull request #3649: CASSANDRA-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads
URL: https://github.com/apache/cassandra/pull/3649
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "maedhroz (via GitHub)" <gi...@apache.org>.
maedhroz commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1833139387
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -383,7 +404,7 @@ private UnfilteredRowIterator queryStorageAndFilter(PrimaryKey key)
}
}
- private UnfilteredRowIterator applyIndexFilter(PrimaryKey key, UnfilteredRowIterator partition, FilterTree tree)
Review Comment:
Possibly. Let's see what happens in `applyIndexFilter()` below. There might be a version of that that doesn't require the list of keys as an argument...
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "maedhroz (via GitHub)" <gi...@apache.org>.
maedhroz commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1833407074
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -400,36 +430,43 @@ private UnfilteredRowIterator applyIndexFilter(PrimaryKey key, UnfilteredRowIter
{
queryContext.rowsFiltered++;
- if (tree.isSatisfiedBy(partition.partitionKey(), (Row) unfiltered, staticRow))
+ if (tree.isSatisfiedBy(partitionKey, (Row) unfiltered, staticRow))
{
- matchingRows.add(unfiltered);
+ matches.add(unfiltered);
hasMatch = true;
+
+ if (topK)
+ {
+ PrimaryKey shadowed = keyFactory.hasClusteringColumns()
+ ? keyFactory.create(partitionKey, ((Row) unfiltered).clustering())
+ : keyFactory.create(partitionKey);
+ keysToShadow.remove(shadowed);
+ }
}
}
}
- if (!hasMatch)
+ if (topK)
{
- queryContext.rowsFiltered++;
+ // If any rows match the filter, there should be no need to shadow the static primary key:
+ if (hasMatch && keyFactory.hasClusteringColumns())
+ keysToShadow.remove(keyFactory.create(partitionKey, Clustering.STATIC_CLUSTERING));
- if (tree.isSatisfiedBy(key.partitionKey(), staticRow, staticRow))
- hasMatch = true;
+ // Record primary keys shadowed by expired TTLs, row tombstones, or range tombstones:
+ if (!keysToShadow.isEmpty())
+ queryContext.vectorContext().recordShadowedPrimaryKeys(keysToShadow);
Review Comment:
@jasonstack It looks like `VectorUpdateDeleteTest` does touch every codepath in this method. Indeed, it did break down a couple times during my refactor. What I've done here is loosely inspired by your suggestion, albeit with some protections to avoid allocations in the non-topK case.
WDYT?
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "jasonstack (via GitHub)" <gi...@apache.org>.
jasonstack commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1832222320
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -412,15 +433,15 @@ private UnfilteredRowIterator applyIndexFilter(PrimaryKey key, UnfilteredRowIter
{
queryContext.rowsFiltered++;
- if (tree.isSatisfiedBy(key.partitionKey(), staticRow, staticRow))
+ if (tree.isSatisfiedBy(partition.partitionKey(), staticRow, staticRow))
hasMatch = true;
}
if (!hasMatch)
{
// shadowed by expired TTL or row tombstone or range tombstone
if (topK)
- queryContext.vectorContext().recordShadowedPrimaryKey(key);
+ queryContext.vectorContext().recordShadowedPrimaryKey(keys);
Review Comment:
```
private UnfilteredRowIterator applyIndexFilter(List<PrimaryKey> keys, UnfilteredRowIterator partition, FilterTree tree)
{
Row staticRow = partition.staticRow();
List<Unfiltered> matchingRows = new ArrayList<>();
boolean hasMatch = false;
Set<PrimaryKey> keysToShadow = new HashSet<>(keys);
// We need to filter the partition rows before filtering on the static row. If this is done in the other
// order then we get incorrect results if we are filtering on a partition key index on a table with a
// composite partition key.
while (partition.hasNext())
{
Unfiltered unfiltered = partition.next();
if (unfiltered.isRow())
{
queryContext.rowsFiltered++;
if (tree.isSatisfiedBy(partition.partitionKey(), (Row) unfiltered, staticRow))
{
matchingRows.add(unfiltered);
hasMatch = true;
PrimaryKey key = keyFactory.create(partition.partitionKey(), ((Row) unfiltered).clustering());
keysToShadow.remove(key);
}
}
}
if (!hasMatch)
{
queryContext.rowsFiltered++;
if (tree.isSatisfiedBy(partition.partitionKey(), staticRow, staticRow))
{
hasMatch = true;
keysToShadow.clear();
}
}
// shadowed by expired TTL or row tombstone or range tombstone
if (topK)
queryContext.vectorContext().recordShadowedPrimaryKey(keysToShadow);
if (!hasMatch)
{
// If there are no matches, return an empty partition. If reconciliation is required at the
// coordinator, replica filtering protection may make a second round trip to complete its view
// of the partition.
return null;
}
// Return all matches found, along with the static row...
return new PartitionIterator(partition, staticRow, matchingRows.iterator());
}
```
this might work.. but we need some tests...
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "jasonstack (via GitHub)" <gi...@apache.org>.
jasonstack commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1832210646
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -383,7 +404,7 @@ private UnfilteredRowIterator queryStorageAndFilter(PrimaryKey key)
}
}
- private UnfilteredRowIterator applyIndexFilter(PrimaryKey key, UnfilteredRowIterator partition, FilterTree tree)
Review Comment:
nit: how about `keysInTheSamePartition`
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "maedhroz (via GitHub)" <gi...@apache.org>.
maedhroz commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1833127194
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -222,45 +236,57 @@ public UnfilteredRowIterator computeNext()
/**
* Returns the next available key contained by one of the keyRanges and selected by the queryController.
* If the next key falls out of the current key range, it skips to the next key range, and so on.
- * If no more keys acceptd by the controller are available, returns null.
+ * If no more keys acceptd by the controller are available, returns an empty list.
*/
- private @Nullable PrimaryKey nextSelectedKeyInRange()
+ private List<PrimaryKey> nextSelectedKeyInRange()
{
+ List<PrimaryKey> threadLocalNextKeys = nextKeys.get();
+ threadLocalNextKeys.clear();
PrimaryKey key;
+
do
{
key = nextKeyInRange();
+
+ if (key == null)
+ return Collections.emptyList();
}
- while (key != null && queryController.doesNotSelect(key));
- return key;
+ while (queryController.doesNotSelect(key) || key.equals(lastKey));
Review Comment:
So we don't _need_ `threadLocalNextKeys`, but I wanted to keep the return type of both suppliers (`nextSelectedKeyInRange()` and `nextSelectedKeysInPartition()`) the same to simplify `nextRowIterator()`, and using the thread-local avoids having to create a singleton collection for the one key.
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "maedhroz (via GitHub)" <gi...@apache.org>.
maedhroz commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1831512007
##########
src/java/org/apache/cassandra/index/sai/plan/QueryController.java:
##########
@@ -409,21 +414,29 @@ private KeyRangeIterator createRowIdIterator(Pair<Expression, Collection<SSTable
// Note: This method assumes that the selects method has already been called for the
// key to avoid having to (potentially) call selects twice
- private ClusteringIndexFilter makeFilter(PrimaryKey key)
+ private ClusteringIndexFilter makeFilter(List<PrimaryKey> keys)
{
- ClusteringIndexFilter clusteringIndexFilter = command.clusteringIndexFilter(key.partitionKey());
+ PrimaryKey firstKey = keys.get(0);
- assert cfs.metadata().comparator.size() == 0 && !key.kind().hasClustering ||
- cfs.metadata().comparator.size() > 0 && key.kind().hasClustering :
- "PrimaryKey " + key + " clustering does not match table. There should be a clustering of size " + cfs.metadata().comparator.size();
+ assert cfs.metadata().comparator.size() == 0 && !firstKey.kind().hasClustering ||
+ cfs.metadata().comparator.size() > 0 && firstKey.kind().hasClustering :
+ "PrimaryKey " + firstKey + " clustering does not match table. There should be a clustering of size " + cfs.metadata().comparator.size();
+ ClusteringIndexFilter clusteringIndexFilter = command.clusteringIndexFilter(firstKey.partitionKey());
+
// If we have skinny partitions or the key is for a static row then we need to get the partition as
// requested by the original query.
- if (cfs.metadata().comparator.size() == 0 || key.kind() == PrimaryKey.Kind.STATIC)
+ if (cfs.metadata().comparator.size() == 0 || firstKey.kind() == PrimaryKey.Kind.STATIC)
+ {
return clusteringIndexFilter;
+ }
else
- return new ClusteringIndexNamesFilter(FBUtilities.singleton(key.clustering(), cfs.metadata().comparator),
- clusteringIndexFilter.isReversed());
+ {
+ nextClusterings.clear();
Review Comment:
I think I'm going to test with and without the allocation, but we create a new `QueryController` for every query. I only didn't use a thread-local here because I wouldn't know the comparator in a static context. Does that make sense?
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "maedhroz (via GitHub)" <gi...@apache.org>.
maedhroz commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1831825412
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -412,15 +433,15 @@ private UnfilteredRowIterator applyIndexFilter(PrimaryKey key, UnfilteredRowIter
{
queryContext.rowsFiltered++;
- if (tree.isSatisfiedBy(key.partitionKey(), staticRow, staticRow))
+ if (tree.isSatisfiedBy(partition.partitionKey(), staticRow, staticRow))
hasMatch = true;
}
if (!hasMatch)
{
// shadowed by expired TTL or row tombstone or range tombstone
if (topK)
- queryContext.vectorContext().recordShadowedPrimaryKey(key);
+ queryContext.vectorContext().recordShadowedPrimaryKey(keys);
Review Comment:
I don't seem have broken any tests w/ this change, and I can only suspect that's because all the existing testing for Vector Search use single-row partitions?
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "jasonstack (via GitHub)" <gi...@apache.org>.
jasonstack commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1832198700
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -222,45 +236,57 @@ public UnfilteredRowIterator computeNext()
/**
* Returns the next available key contained by one of the keyRanges and selected by the queryController.
* If the next key falls out of the current key range, it skips to the next key range, and so on.
- * If no more keys acceptd by the controller are available, returns null.
+ * If no more keys acceptd by the controller are available, returns an empty list.
*/
- private @Nullable PrimaryKey nextSelectedKeyInRange()
+ private List<PrimaryKey> nextSelectedKeyInRange()
{
+ List<PrimaryKey> threadLocalNextKeys = nextKeys.get();
+ threadLocalNextKeys.clear();
PrimaryKey key;
+
do
{
key = nextKeyInRange();
+
+ if (key == null)
+ return Collections.emptyList();
}
- while (key != null && queryController.doesNotSelect(key));
- return key;
+ while (queryController.doesNotSelect(key) || key.equals(lastKey));
Review Comment:
in my understanding, `nextSelectedKeyInRange()` always returns 1 single PrimaryKey
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "jasonstack (via GitHub)" <gi...@apache.org>.
jasonstack commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1830473198
##########
src/java/org/apache/cassandra/index/sai/plan/QueryController.java:
##########
@@ -409,21 +414,29 @@ private KeyRangeIterator createRowIdIterator(Pair<Expression, Collection<SSTable
// Note: This method assumes that the selects method has already been called for the
// key to avoid having to (potentially) call selects twice
- private ClusteringIndexFilter makeFilter(PrimaryKey key)
+ private ClusteringIndexFilter makeFilter(List<PrimaryKey> keys)
{
- ClusteringIndexFilter clusteringIndexFilter = command.clusteringIndexFilter(key.partitionKey());
+ PrimaryKey firstKey = keys.get(0);
- assert cfs.metadata().comparator.size() == 0 && !key.kind().hasClustering ||
- cfs.metadata().comparator.size() > 0 && key.kind().hasClustering :
- "PrimaryKey " + key + " clustering does not match table. There should be a clustering of size " + cfs.metadata().comparator.size();
+ assert cfs.metadata().comparator.size() == 0 && !firstKey.kind().hasClustering ||
+ cfs.metadata().comparator.size() > 0 && firstKey.kind().hasClustering :
+ "PrimaryKey " + firstKey + " clustering does not match table. There should be a clustering of size " + cfs.metadata().comparator.size();
+ ClusteringIndexFilter clusteringIndexFilter = command.clusteringIndexFilter(firstKey.partitionKey());
+
// If we have skinny partitions or the key is for a static row then we need to get the partition as
// requested by the original query.
- if (cfs.metadata().comparator.size() == 0 || key.kind() == PrimaryKey.Kind.STATIC)
+ if (cfs.metadata().comparator.size() == 0 || firstKey.kind() == PrimaryKey.Kind.STATIC)
+ {
return clusteringIndexFilter;
+ }
else
- return new ClusteringIndexNamesFilter(FBUtilities.singleton(key.clustering(), cfs.metadata().comparator),
- clusteringIndexFilter.isReversed());
+ {
+ nextClusterings.clear();
Review Comment:
is it safe to re-use `nextClusterings`? extra allocations maybe fine..
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "maedhroz (via GitHub)" <gi...@apache.org>.
maedhroz commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1831510229
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -222,45 +234,64 @@ public UnfilteredRowIterator computeNext()
/**
* Returns the next available key contained by one of the keyRanges and selected by the queryController.
* If the next key falls out of the current key range, it skips to the next key range, and so on.
- * If no more keys acceptd by the controller are available, returns null.
+ * If no more keys acceptd by the controller are available, returns an empty list.
*/
- private @Nullable PrimaryKey nextSelectedKeyInRange()
+ private List<PrimaryKey> nextSelectedKeyInRange()
{
+ List<PrimaryKey> threadLocalNextKeys = nextKeys.get();
+ threadLocalNextKeys.clear();
PrimaryKey key;
+
do
{
key = nextKeyInRange();
+
+ if (key == null)
+ return Collections.emptyList();
}
- while (key != null && queryController.doesNotSelect(key));
- return key;
+ while (queryController.doesNotSelect(key) || key.equals(lastKey));
+
+ lastKey = key;
+ threadLocalNextKeys.add(key);
+ return threadLocalNextKeys;
}
/**
+ * TODO: update this description...
Review Comment:
Yup, need to update all of this when things settle...
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "maedhroz (via GitHub)" <gi...@apache.org>.
maedhroz commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1833148270
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -412,15 +433,15 @@ private UnfilteredRowIterator applyIndexFilter(PrimaryKey key, UnfilteredRowIter
{
queryContext.rowsFiltered++;
- if (tree.isSatisfiedBy(key.partitionKey(), staticRow, staticRow))
+ if (tree.isSatisfiedBy(partition.partitionKey(), staticRow, staticRow))
hasMatch = true;
}
if (!hasMatch)
{
// shadowed by expired TTL or row tombstone or range tombstone
if (topK)
- queryContext.vectorContext().recordShadowedPrimaryKey(key);
+ queryContext.vectorContext().recordShadowedPrimaryKey(keys);
Review Comment:
I'm actually not even sure if we need the explicit static filtering block after the `while` loop. That block was originally added before CASSANDRA-19034 as an optimization to short-circuit before the `while` loop. Removing it would make some things simpler. I'm going to try it out and push something...
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "jasonstack (via GitHub)" <gi...@apache.org>.
jasonstack commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1832203612
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -222,45 +236,57 @@ public UnfilteredRowIterator computeNext()
/**
* Returns the next available key contained by one of the keyRanges and selected by the queryController.
* If the next key falls out of the current key range, it skips to the next key range, and so on.
- * If no more keys acceptd by the controller are available, returns null.
+ * If no more keys acceptd by the controller are available, returns an empty list.
*/
- private @Nullable PrimaryKey nextSelectedKeyInRange()
+ private List<PrimaryKey> nextSelectedKeyInRange()
{
+ List<PrimaryKey> threadLocalNextKeys = nextKeys.get();
+ threadLocalNextKeys.clear();
PrimaryKey key;
+
do
{
key = nextKeyInRange();
+
+ if (key == null)
+ return Collections.emptyList();
}
- while (key != null && queryController.doesNotSelect(key));
- return key;
+ while (queryController.doesNotSelect(key) || key.equals(lastKey));
+
+ lastKey = key;
+ threadLocalNextKeys.add(key);
+ return threadLocalNextKeys;
}
/**
- * Retrieves the next primary key that belongs to the given partition and is selected by the query controller.
- * The underlying key iterator is advanced only if the key belongs to the same partition.
- * <p>
- * Returns null if:
- * <ul>
- * <li>there are no more keys</li>
- * <li>the next key is beyond the upper bound</li>
- * <li>the next key belongs to a different partition</li>
- * </ul>
- * </p>
+ * Retrieves the next batch of primary keys (i.e. up to {@link #partitionRowBatchSize} of them) that belong to
+ * the given partition and are selected by the query controller, advancing the underlying iterator only while
+ * the next key belongs to that partition.
+ *
+ * @return a list of up to {@link #partitionRowBatchSize} primary keys within the given partition and data range
*/
- private @Nullable PrimaryKey nextSelectedKeyInPartition(DecoratedKey partitionKey)
+ private List<PrimaryKey> nextSelectedKeysInPartition(DecoratedKey partitionKey)
Review Comment:
so, for this wide schema:
```
createTable("CREATE TABLE %s (pk int, ck int, v1 int, primary key(pk, ck))");
executeNet("CREATE INDEX index_1 ON %s(v1) USING 'sai'");
waitForTableIndexesQueryable();
execute("INSERT INTO %s (pk, ck, v1) VALUES(1, 1, 1)");
execute("INSERT INTO %s (pk, ck, v1) VALUES(1, 2, 1)");
execute("INSERT INTO %s (pk, ck, v1) VALUES(1, 3, 1)");
execute("INSERT INTO %s (pk, ck, v1) VALUES(1, 4, 1)");
execute("INSERT INTO %s (pk, ck, v1) VALUES(1, 5, 1)");
flush();
ResultSet rows = executeNet("SELECT * FROM %s WHERE v1 = 1");
```
`queryStorageAndFilter` is called twice:
* first time reading with pk=1 and ck=1 - PrimaryKey is fetched from `nextSelectedKeyInRange`
* second time reading with pk=1 and ck in [2,3,4,5] - PrimaryKeys are fetched from `nextSelectedKeysInPartition`
Same for partition-restricted SAI query.
can we improve it to execute one local read?
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "jasonstack (via GitHub)" <gi...@apache.org>.
jasonstack commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1832198700
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -222,45 +236,57 @@ public UnfilteredRowIterator computeNext()
/**
* Returns the next available key contained by one of the keyRanges and selected by the queryController.
* If the next key falls out of the current key range, it skips to the next key range, and so on.
- * If no more keys acceptd by the controller are available, returns null.
+ * If no more keys acceptd by the controller are available, returns an empty list.
*/
- private @Nullable PrimaryKey nextSelectedKeyInRange()
+ private List<PrimaryKey> nextSelectedKeyInRange()
{
+ List<PrimaryKey> threadLocalNextKeys = nextKeys.get();
+ threadLocalNextKeys.clear();
PrimaryKey key;
+
do
{
key = nextKeyInRange();
+
+ if (key == null)
+ return Collections.emptyList();
}
- while (key != null && queryController.doesNotSelect(key));
- return key;
+ while (queryController.doesNotSelect(key) || key.equals(lastKey));
Review Comment:
in my understanding, `nextSelectedKeyInRange()` always returns 1 single PrimaryKey. Do we need `threadLocalNextKeys` here?
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "jasonstack (via GitHub)" <gi...@apache.org>.
jasonstack commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1833632796
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -400,36 +430,56 @@ private UnfilteredRowIterator applyIndexFilter(PrimaryKey key, UnfilteredRowIter
{
queryContext.rowsFiltered++;
- if (tree.isSatisfiedBy(partition.partitionKey(), (Row) unfiltered, staticRow))
+ if (tree.isSatisfiedBy(partitionKey, (Row) unfiltered, staticRow))
{
- matchingRows.add(unfiltered);
+ matches.add(unfiltered);
hasMatch = true;
+
+ if (topK)
+ {
+ PrimaryKey shadowed = keyFactory.hasClusteringColumns()
+ ? keyFactory.create(partitionKey, ((Row) unfiltered).clustering())
+ : keyFactory.create(partitionKey);
+ keysToShadow.remove(shadowed);
+ }
}
}
}
+ // If any non-static rows match the filter, there should be no need to shadow the static primary key:
+ if (topK && hasMatch && keyFactory.hasClusteringColumns())
+ keysToShadow.remove(keyFactory.create(partitionKey, Clustering.STATIC_CLUSTERING));
+
+ // We may not have any non-static row data to filter...
if (!hasMatch)
{
queryContext.rowsFiltered++;
- if (tree.isSatisfiedBy(key.partitionKey(), staticRow, staticRow))
+ if (tree.isSatisfiedBy(partitionKey, staticRow, staticRow))
+ {
hasMatch = true;
+
+ if (topK)
+ keysToShadow.remove(keyFactory.create(partitionKey, staticRow.clustering()));
Review Comment:
If a static row matches, it means all rows in the partition match. So, should we clear `keysToShadow` here?
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "maedhroz (via GitHub)" <gi...@apache.org>.
maedhroz commented on PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#issuecomment-2465717659
Committed as https://github.com/apache/cassandra/commit/fd4113d5fef09f6361bea88a35655db2ecb46427
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "jasonstack (via GitHub)" <gi...@apache.org>.
jasonstack commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1832177975
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -222,45 +236,57 @@ public UnfilteredRowIterator computeNext()
/**
* Returns the next available key contained by one of the keyRanges and selected by the queryController.
* If the next key falls out of the current key range, it skips to the next key range, and so on.
- * If no more keys acceptd by the controller are available, returns null.
+ * If no more keys acceptd by the controller are available, returns an empty list.
*/
- private @Nullable PrimaryKey nextSelectedKeyInRange()
+ private List<PrimaryKey> nextSelectedKeyInRange()
{
+ List<PrimaryKey> threadLocalNextKeys = nextKeys.get();
+ threadLocalNextKeys.clear();
PrimaryKey key;
+
do
{
key = nextKeyInRange();
+
+ if (key == null)
+ return Collections.emptyList();
}
- while (key != null && queryController.doesNotSelect(key));
- return key;
+ while (queryController.doesNotSelect(key) || key.equals(lastKey));
Review Comment:
when entering the loop for the 1st time, `lastKey` is null. It will exist the loop. `threadLocalNextKeys` will only have one element. Is it expected?
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "jasonstack (via GitHub)" <gi...@apache.org>.
jasonstack commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1832203612
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -222,45 +236,57 @@ public UnfilteredRowIterator computeNext()
/**
* Returns the next available key contained by one of the keyRanges and selected by the queryController.
* If the next key falls out of the current key range, it skips to the next key range, and so on.
- * If no more keys acceptd by the controller are available, returns null.
+ * If no more keys acceptd by the controller are available, returns an empty list.
*/
- private @Nullable PrimaryKey nextSelectedKeyInRange()
+ private List<PrimaryKey> nextSelectedKeyInRange()
{
+ List<PrimaryKey> threadLocalNextKeys = nextKeys.get();
+ threadLocalNextKeys.clear();
PrimaryKey key;
+
do
{
key = nextKeyInRange();
+
+ if (key == null)
+ return Collections.emptyList();
}
- while (key != null && queryController.doesNotSelect(key));
- return key;
+ while (queryController.doesNotSelect(key) || key.equals(lastKey));
+
+ lastKey = key;
+ threadLocalNextKeys.add(key);
+ return threadLocalNextKeys;
}
/**
- * Retrieves the next primary key that belongs to the given partition and is selected by the query controller.
- * The underlying key iterator is advanced only if the key belongs to the same partition.
- * <p>
- * Returns null if:
- * <ul>
- * <li>there are no more keys</li>
- * <li>the next key is beyond the upper bound</li>
- * <li>the next key belongs to a different partition</li>
- * </ul>
- * </p>
+ * Retrieves the next batch of primary keys (i.e. up to {@link #partitionRowBatchSize} of them) that belong to
+ * the given partition and are selected by the query controller, advancing the underlying iterator only while
+ * the next key belongs to that partition.
+ *
+ * @return a list of up to {@link #partitionRowBatchSize} primary keys within the given partition and data range
*/
- private @Nullable PrimaryKey nextSelectedKeyInPartition(DecoratedKey partitionKey)
+ private List<PrimaryKey> nextSelectedKeysInPartition(DecoratedKey partitionKey)
Review Comment:
so, for this wide schema:
```
createTable("CREATE TABLE %s (pk int, ck int, v1 int, primary key(pk, ck))");
executeNet("CREATE INDEX index_1 ON %s(v1) USING 'sai'");
waitForTableIndexesQueryable();
execute("INSERT INTO %s (pk, ck, v1) VALUES(1, 1, 1)");
execute("INSERT INTO %s (pk, ck, v1) VALUES(1, 2, 1)");
execute("INSERT INTO %s (pk, ck, v1) VALUES(1, 3, 1)");
execute("INSERT INTO %s (pk, ck, v1) VALUES(1, 5, 1)");
execute("INSERT INTO %s (pk, ck, v1) VALUES(1, 6, 1)");
flush();
ResultSet rows = executeNet("SELECT * FROM %s WHERE v1 = 1");
```
`queryStorageAndFilter` is called twice:
* first time reading with pk=1 and ck=1
* second time reading with pk=1 and ck in [2,3,4,5]
can we improve it to execute one local read?
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "maedhroz (via GitHub)" <gi...@apache.org>.
maedhroz commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1833110199
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -412,15 +433,15 @@ private UnfilteredRowIterator applyIndexFilter(PrimaryKey key, UnfilteredRowIter
{
queryContext.rowsFiltered++;
- if (tree.isSatisfiedBy(key.partitionKey(), staticRow, staticRow))
+ if (tree.isSatisfiedBy(partition.partitionKey(), staticRow, staticRow))
hasMatch = true;
}
if (!hasMatch)
{
// shadowed by expired TTL or row tombstone or range tombstone
if (topK)
- queryContext.vectorContext().recordShadowedPrimaryKey(key);
+ queryContext.vectorContext().recordShadowedPrimaryKey(keys);
Review Comment:
Yeah, that's more or less what I had imagined, modulo fixing it up to avoid allocations for the topK case, etc.
It's unfortunate that there are no tests that seem to cover this case, and I don't quite know where to start. Would `VectorUpdateDeleteTest` be a place to look?
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "maedhroz (via GitHub)" <gi...@apache.org>.
maedhroz commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1833148270
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -412,15 +433,15 @@ private UnfilteredRowIterator applyIndexFilter(PrimaryKey key, UnfilteredRowIter
{
queryContext.rowsFiltered++;
- if (tree.isSatisfiedBy(key.partitionKey(), staticRow, staticRow))
+ if (tree.isSatisfiedBy(partition.partitionKey(), staticRow, staticRow))
hasMatch = true;
}
if (!hasMatch)
{
// shadowed by expired TTL or row tombstone or range tombstone
if (topK)
- queryContext.vectorContext().recordShadowedPrimaryKey(key);
+ queryContext.vectorContext().recordShadowedPrimaryKey(keys);
Review Comment:
I'm actually not even sure if we need the explicit static filtering block after the `while` loop. That block was originally added before CASSANDRA-19034 as an optimization to short-circuit before the `while` loop. Removing it would make some things simpler. I'm going to try it out and push something...
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "maedhroz (via GitHub)" <gi...@apache.org>.
maedhroz commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1833407074
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -400,36 +430,43 @@ private UnfilteredRowIterator applyIndexFilter(PrimaryKey key, UnfilteredRowIter
{
queryContext.rowsFiltered++;
- if (tree.isSatisfiedBy(partition.partitionKey(), (Row) unfiltered, staticRow))
+ if (tree.isSatisfiedBy(partitionKey, (Row) unfiltered, staticRow))
{
- matchingRows.add(unfiltered);
+ matches.add(unfiltered);
hasMatch = true;
+
+ if (topK)
+ {
+ PrimaryKey shadowed = keyFactory.hasClusteringColumns()
+ ? keyFactory.create(partitionKey, ((Row) unfiltered).clustering())
+ : keyFactory.create(partitionKey);
+ keysToShadow.remove(shadowed);
+ }
}
}
}
- if (!hasMatch)
+ if (topK)
{
- queryContext.rowsFiltered++;
+ // If any rows match the filter, there should be no need to shadow the static primary key:
+ if (hasMatch && keyFactory.hasClusteringColumns())
+ keysToShadow.remove(keyFactory.create(partitionKey, Clustering.STATIC_CLUSTERING));
- if (tree.isSatisfiedBy(key.partitionKey(), staticRow, staticRow))
- hasMatch = true;
+ // Record primary keys shadowed by expired TTLs, row tombstones, or range tombstones:
+ if (!keysToShadow.isEmpty())
+ queryContext.vectorContext().recordShadowedPrimaryKeys(keysToShadow);
Review Comment:
@jasonstack It looks like `VectorUpdateDeleteTest` does touch every codepath in this method. Indeed, it did break down a couple times during my refactor. What I've done here is loosely inspired by your suggestion, albeit with some protections to avoid allocations in the non-topK case.
I've also removed what really does look like an unnecessary second round of `isSatisfiedBy()` calls using just the static row. Before CASSANDRA-19034, this actually happened before the `while` loop that filters the rows, but it was never strictly necessary. I suppose I'll see if CI disagrees, but I think this make sense.
WDYT?
--
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-19497 ResultRetriever should batch clusterings/rows during SAI post-filtering reads [cassandra]
Posted by "jasonstack (via GitHub)" <gi...@apache.org>.
jasonstack commented on code in PR #3649:
URL: https://github.com/apache/cassandra/pull/3649#discussion_r1833637087
##########
src/java/org/apache/cassandra/index/sai/plan/StorageAttachedIndexSearcher.java:
##########
@@ -164,33 +183,75 @@ public UnfilteredRowIterator computeNext()
// saying this iterator must not return the same partition twice.
skipToNextPartition();
- UnfilteredRowIterator iterator = nextRowIterator(this::nextSelectedKeyInRange);
- return iterator != null
- ? iteratePartition(iterator)
- : endOfData();
+ UnfilteredRowIterator iterator = nextRowIterator(this::nextSelectedKeysInRange);
+ return iterator != null ? iteratePartition(iterator) : endOfData();
}
/**
- * Tries to obtain a row iterator for one of the supplied keys by repeatedly calling
+ * Tries to obtain a row iterator for the supplied keys by repeatedly calling
* {@link ResultRetriever#queryStorageAndFilter} until it gives a non-null result.
- * The keySupplier should return the next key with every call to get() and
- * null when there are no more keys to try.
+ * The keysSupplier should return the next batch of keys with every call to get()
+ * and null when there are no more keys to try.
*
* @return an iterator or null if all keys were tried with no success
*/
- private @Nullable UnfilteredRowIterator nextRowIterator(@Nonnull Supplier<PrimaryKey> keySupplier)
+ private @Nullable UnfilteredRowIterator nextRowIterator(@Nonnull Supplier<List<PrimaryKey>> keysSupplier)
{
UnfilteredRowIterator iterator = null;
while (iterator == null)
{
- PrimaryKey key = keySupplier.get();
- if (key == null)
+ List<PrimaryKey> keys = keysSupplier.get();
+ if (keys.isEmpty())
return null;
- iterator = queryStorageAndFilter(key);
+ iterator = queryStorageAndFilter(keys);
}
return iterator;
}
+ /**
+ * Retrieves the next batch of primary keys (i.e. up to {@link #partitionRowBatchSize} of them) that are
+ * contained by one of the query key ranges and selected by the {@link QueryController}. If the next key falls
+ * out of the current key range, it skips to the next key range, and so on. If no more keys accepted by
+ * the controller are available, and empty list is returned.
+ *
+ * @return a list of up to {@link #partitionRowBatchSize} primary keys
+ */
+ private List<PrimaryKey> nextSelectedKeysInRange()
+ {
+ List<PrimaryKey> threadLocalNextKeys = nextKeys.get();
+ threadLocalNextKeys.clear();
+ PrimaryKey firstKey;
+
+ do
+ {
+ firstKey = nextKeyInRange();
+
+ if (firstKey == null)
+ return Collections.emptyList();
+ }
+ while (queryController.doesNotSelect(firstKey) || firstKey.equals(lastKey));
+
+ lastKey = firstKey;
+ threadLocalNextKeys.add(firstKey);
+ fillNextSelectedKeysInPartition(firstKey.partitionKey(), threadLocalNextKeys);
Review Comment:
nice!
--
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