You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ignite.apache.org by ib...@apache.org on 2022/10/07 12:23:08 UTC
[ignite-3] branch main updated: IGNITE-17818 Optimize sorted index scan (#1172)
This is an automated email from the ASF dual-hosted git repository.
ibessonov pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/ignite-3.git
The following commit(s) were added to refs/heads/main by this push:
new b8a9cd55e0 IGNITE-17818 Optimize sorted index scan (#1172)
b8a9cd55e0 is described below
commit b8a9cd55e02ecbe8ebd9c736bb8f617318bae0be
Author: Alexander Polovtcev <al...@gmail.com>
AuthorDate: Fri Oct 7 15:23:04 2022 +0300
IGNITE-17818 Optimize sorted index scan (#1172)
---
.../internal/binarytuple/BinaryTupleCommon.java | 26 ++-
.../apache/ignite/internal/util/CursorUtils.java | 187 ---------------------
.../ignite/internal/util/CursorUtilsTest.java | 43 -----
.../ignite/internal/pagememory/tree/BplusTree.java | 6 +-
.../internal/schema/BinaryTuplePrefixTest.java | 2 +-
.../storage/index/BinaryTupleComparator.java | 28 ++-
.../storage/index/BinaryTupleComparatorTest.java | 23 ++-
.../storage/index/impl/TestSortedIndexStorage.java | 52 +++---
.../index/sorted/PageMemorySortedIndexStorage.java | 74 +++++---
.../index/sorted/io/SortedIndexTreeIo.java | 4 +-
.../index/RocksDbBinaryTupleComparator.java | 17 +-
.../rocksdb/index/RocksDbSortedIndexStorage.java | 68 +++-----
12 files changed, 159 insertions(+), 371 deletions(-)
diff --git a/modules/binary-tuple/src/main/java/org/apache/ignite/internal/binarytuple/BinaryTupleCommon.java b/modules/binary-tuple/src/main/java/org/apache/ignite/internal/binarytuple/BinaryTupleCommon.java
index f09b7fa199..afaf712a2d 100644
--- a/modules/binary-tuple/src/main/java/org/apache/ignite/internal/binarytuple/BinaryTupleCommon.java
+++ b/modules/binary-tuple/src/main/java/org/apache/ignite/internal/binarytuple/BinaryTupleCommon.java
@@ -17,7 +17,6 @@
package org.apache.ignite.internal.binarytuple;
-import java.nio.ByteBuffer;
import java.time.Duration;
import java.time.Instant;
import java.time.LocalDate;
@@ -38,14 +37,22 @@ public class BinaryTupleCommon {
public static final int VARSIZE_MASK = 0b011;
/** Flag that indicates null map presence. */
- public static final int NULLMAP_FLAG = 0b100;
+ public static final int NULLMAP_FLAG = 1 << 2;
/**
* Flag that indicates that a Binary Tuple is instead a Binary Tuple Prefix.
*
* @see BinaryTuplePrefixBuilder
*/
- public static final int PREFIX_FLAG = 0b1000;
+ public static final int PREFIX_FLAG = 1 << 3;
+
+ /**
+ * Flag, which indicates how to interpret situations when Binary Tuple Prefix columns are equal to
+ * first N columns of a Binary Tuple (where N is the length of the prefix).
+ *
+ * <p>This flag is used by some index implementations for internal optimizations.
+ */
+ public static final int EQUALITY_FLAG = 1 << 4;
/** Default value for UUID elements. */
public static final UUID DEFAULT_UUID = new UUID(0, 0);
@@ -126,17 +133,4 @@ public class BinaryTupleCommon {
public static byte nullMask(int index) {
return (byte) (1 << (index % 8));
}
-
- /**
- * Returns {@code true} if the given {@code buffer} represents a Binary Tuple Prefix.
- *
- * @param buffer Buffer containing a serialized Binary Tuple or Binary Tuple Prefix.
- * @return {@code true} if the given {@code buffer} represents a Binary Tuple Prefix or {@code false} otherwise.
- * @see BinaryTuplePrefixBuilder
- */
- public static boolean isPrefix(ByteBuffer buffer) {
- byte flags = buffer.get(0);
-
- return (flags & PREFIX_FLAG) != 0;
- }
}
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/util/CursorUtils.java b/modules/core/src/main/java/org/apache/ignite/internal/util/CursorUtils.java
index 6ae560ed76..acb63c03fa 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/util/CursorUtils.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/util/CursorUtils.java
@@ -18,10 +18,7 @@
package org.apache.ignite.internal.util;
import java.util.Collections;
-import java.util.NoSuchElementException;
import java.util.function.Function;
-import java.util.function.Predicate;
-import org.jetbrains.annotations.Nullable;
/**
* Utility class for working with cursors.
@@ -40,153 +37,6 @@ public class CursorUtils {
return (Cursor<T>) EMPTY;
}
- /**
- * Cursor wrapper that discards elements while they match a given predicate. As soon as any element does not match the predicate,
- * no more elements will be discarded.
- *
- * @param <T> Cursor element type.
- */
- private static class DropWhileCursor<T> implements Cursor<T> {
- private final Cursor<T> cursor;
-
- @Nullable
- private Predicate<T> predicate;
-
- @Nullable
- private T firstNotMatchedElement;
-
- DropWhileCursor(Cursor<T> cursor, Predicate<T> predicate) {
- this.cursor = cursor;
- this.predicate = predicate;
- }
-
- @Override
- public void close() throws Exception {
- cursor.close();
- }
-
- @Override
- public boolean hasNext() {
- if (predicate == null) {
- return firstNotMatchedElement != null || cursor.hasNext();
- }
-
- while (cursor.hasNext()) {
- firstNotMatchedElement = cursor.next();
-
- if (!predicate.test(firstNotMatchedElement)) {
- predicate = null;
-
- break;
- }
- }
-
- return predicate == null;
- }
-
- @Override
- public T next() {
- if (!hasNext()) {
- throw new NoSuchElementException();
- }
-
- if (firstNotMatchedElement != null) {
- T next = firstNotMatchedElement;
-
- firstNotMatchedElement = null;
-
- return next;
- } else {
- return cursor.next();
- }
- }
- }
-
- /**
- * Creates a cursor wrapper that discards elements while they match a given predicate. As soon as any element does not match the
- * predicate, no more elements will be discarded.
- *
- * @param cursor Underlying cursor with data.
- * @param predicate Predicate for elements to be discarded.
- * @param <T> Cursor element type.
- * @return Cursor wrapper.
- */
- public static <T> Cursor<T> dropWhile(Cursor<T> cursor, Predicate<T> predicate) {
- return new DropWhileCursor<>(cursor, predicate);
- }
-
- /**
- * Cursor wrapper that discards elements if they don't match a given predicate. As soon as any element does not match the predicate,
- * all following elements will be discarded.
- *
- * @param <T> Cursor element type.
- */
- private static class TakeWhileCursor<T> implements Cursor<T> {
- private final Cursor<T> cursor;
-
- @Nullable
- private Predicate<T> predicate;
-
- @Nullable
- private T next;
-
- TakeWhileCursor(Cursor<T> cursor, Predicate<T> predicate) {
- this.cursor = cursor;
- this.predicate = predicate;
- }
-
- @Override
- public void close() throws Exception {
- cursor.close();
- }
-
- @Override
- public boolean hasNext() {
- if (next != null) {
- return true;
- } else if (predicate == null || !cursor.hasNext()) {
- return false;
- }
-
- next = cursor.next();
-
- if (predicate.test(next)) {
- return true;
- } else {
- predicate = null;
- next = null;
-
- return false;
- }
- }
-
- @Override
- public T next() {
- if (!hasNext()) {
- throw new NoSuchElementException();
- }
-
- T result = next;
-
- next = null;
-
- return result;
- }
- }
-
- /**
- * Creates a cursor wrapper that discards elements if they don't match a given predicate. As soon as any element does not match the
- * predicate, all following elements will be discarded.
- *
- * @param cursor Underlying cursor with data.
- * @param predicate Predicate for elements to be kept.
- * @param <T> Cursor element type.
- * @return Cursor wrapper.
- */
- public static <T> Cursor<T> takeWhile(Cursor<T> cursor, Predicate<T> predicate) {
- return new TakeWhileCursor<>(cursor, predicate);
- }
-
/**
* Cursor wrapper that transforms the underlying cursor's data using the provided mapping function.
*
@@ -231,41 +81,4 @@ public class CursorUtils {
public static <T, U> Cursor<U> map(Cursor<T> cursor, Function<T, U> mapper) {
return new MapCursor<>(cursor, mapper);
}
-
- /**
- * Creates a cursor that iterates over both given cursors.
- *
- * @param a First cursor.
- * @param b Second cursor.
- * @param <T> Cursor element type.
- * @return Cursor that iterates over both given cursors.
- */
- public static <T> Cursor<T> concat(Cursor<T> a, Cursor<T> b) {
- return new Cursor<>() {
- private Cursor<T> currentCursor = a;
-
- @Override
- public void close() throws Exception {
- IgniteUtils.closeAll(a, b);
- }
-
- @Override
- public boolean hasNext() {
- if (currentCursor.hasNext()) {
- return true;
- } else if (currentCursor == b) {
- return false;
- } else {
- currentCursor = b;
-
- return currentCursor.hasNext();
- }
- }
-
- @Override
- public T next() {
- return currentCursor.next();
- }
- };
- }
}
diff --git a/modules/core/src/test/java/org/apache/ignite/internal/util/CursorUtilsTest.java b/modules/core/src/test/java/org/apache/ignite/internal/util/CursorUtilsTest.java
index 7b888461ab..05f27f0b7e 100644
--- a/modules/core/src/test/java/org/apache/ignite/internal/util/CursorUtilsTest.java
+++ b/modules/core/src/test/java/org/apache/ignite/internal/util/CursorUtilsTest.java
@@ -17,10 +17,7 @@
package org.apache.ignite.internal.util;
-import static org.apache.ignite.internal.util.CursorUtils.concat;
-import static org.apache.ignite.internal.util.CursorUtils.dropWhile;
import static org.apache.ignite.internal.util.CursorUtils.map;
-import static org.apache.ignite.internal.util.CursorUtils.takeWhile;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.Matchers.contains;
import static org.hamcrest.Matchers.emptyIterable;
@@ -33,24 +30,6 @@ import org.junit.jupiter.api.Test;
* Class for testing {@link CursorUtils}.
*/
public class CursorUtilsTest {
- @Test
- public void testDropWhile() {
- Cursor<Integer> actual = dropWhile(cursor(1, 2, 5, 14, 20, 1), i -> i < 10);
-
- assertThat(actual, contains(14, 20, 1));
-
- assertThat(dropWhile(cursor(), i -> i.hashCode() < 10), is(emptyIterable()));
- }
-
- @Test
- public void testTakeWhile() {
- Cursor<Integer> actual = takeWhile(cursor(1, 2, 5, 14, 20, 1), i -> i < 10);
-
- assertThat(actual, contains(1, 2, 5));
-
- assertThat(takeWhile(cursor(), i -> i.hashCode() < 10), is(emptyIterable()));
- }
-
@Test
public void testMap() {
Cursor<String> actual = map(cursor(1, 2, 5, 14, 20), i -> "foo" + i);
@@ -60,28 +39,6 @@ public class CursorUtilsTest {
assertThat(map(cursor(), Object::toString), is(emptyIterable()));
}
- @Test
- public void testConcat() {
- Cursor<Integer> actual = concat(cursor(1, 2, 5), cursor(5, 2, 1));
-
- assertThat(actual, contains(1, 2, 5, 5, 2, 1));
-
- assertThat(concat(cursor(), cursor()), is(emptyIterable()));
- }
-
- @Test
- public void testCombination() {
- Cursor<Integer> dropWhile = dropWhile(cursor(1, 5, 8, 10, 42), i -> i <= 8);
-
- Cursor<Integer> takeWhile = takeWhile(dropWhile, i -> i >= 10);
-
- Cursor<Integer> concat = concat(takeWhile, cursor(1, 2, 3));
-
- Cursor<String> map = map(concat, String::valueOf);
-
- assertThat(map, contains("10", "42", "1", "2", "3"));
- }
-
@SafeVarargs
private static <T> Cursor<T> cursor(T... elements) {
return Cursor.fromIterator(Arrays.asList(elements).iterator());
diff --git a/modules/page-memory/src/main/java/org/apache/ignite/internal/pagememory/tree/BplusTree.java b/modules/page-memory/src/main/java/org/apache/ignite/internal/pagememory/tree/BplusTree.java
index ee5f63726b..2a35c478cf 100644
--- a/modules/page-memory/src/main/java/org/apache/ignite/internal/pagememory/tree/BplusTree.java
+++ b/modules/page-memory/src/main/java/org/apache/ignite/internal/pagememory/tree/BplusTree.java
@@ -1245,13 +1245,13 @@ public abstract class BplusTree<L, T extends L> extends DataStructure implements
/** {@inheritDoc} */
@Override
- public final Cursor<T> find(L lower, L upper) throws IgniteInternalCheckedException {
+ public final Cursor<T> find(@Nullable L lower, @Nullable L upper) throws IgniteInternalCheckedException {
return find(lower, upper, null);
}
/** {@inheritDoc} */
@Override
- public final Cursor<T> find(L lower, L upper, Object x) throws IgniteInternalCheckedException {
+ public final Cursor<T> find(@Nullable L lower, @Nullable L upper, Object x) throws IgniteInternalCheckedException {
return find(lower, upper, null, x);
}
@@ -1265,7 +1265,7 @@ public abstract class BplusTree<L, T extends L> extends DataStructure implements
* @return Cursor.
* @throws IgniteInternalCheckedException If failed.
*/
- public Cursor<T> find(L lower, L upper, TreeRowClosure<L, T> c, Object x) throws IgniteInternalCheckedException {
+ public Cursor<T> find(@Nullable L lower, @Nullable L upper, TreeRowClosure<L, T> c, Object x) throws IgniteInternalCheckedException {
return find(lower, upper, true, true, c, x);
}
diff --git a/modules/schema/src/test/java/org/apache/ignite/internal/schema/BinaryTuplePrefixTest.java b/modules/schema/src/test/java/org/apache/ignite/internal/schema/BinaryTuplePrefixTest.java
index 993feb92e1..97cf53f587 100644
--- a/modules/schema/src/test/java/org/apache/ignite/internal/schema/BinaryTuplePrefixTest.java
+++ b/modules/schema/src/test/java/org/apache/ignite/internal/schema/BinaryTuplePrefixTest.java
@@ -56,7 +56,7 @@ public class BinaryTuplePrefixTest {
.appendDate(date)
.build();
- assertTrue(BinaryTupleCommon.isPrefix(tuple));
+ assertTrue((tuple.get(0) & BinaryTupleCommon.PREFIX_FLAG) != 0);
var prefix = new BinaryTuplePrefix(schema, tuple);
diff --git a/modules/storage-api/src/main/java/org/apache/ignite/internal/storage/index/BinaryTupleComparator.java b/modules/storage-api/src/main/java/org/apache/ignite/internal/storage/index/BinaryTupleComparator.java
index baf8aabaa9..f86b3d678e 100644
--- a/modules/storage-api/src/main/java/org/apache/ignite/internal/storage/index/BinaryTupleComparator.java
+++ b/modules/storage-api/src/main/java/org/apache/ignite/internal/storage/index/BinaryTupleComparator.java
@@ -17,7 +17,8 @@
package org.apache.ignite.internal.storage.index;
-import static org.apache.ignite.internal.binarytuple.BinaryTupleCommon.isPrefix;
+import static org.apache.ignite.internal.binarytuple.BinaryTupleCommon.EQUALITY_FLAG;
+import static org.apache.ignite.internal.binarytuple.BinaryTupleCommon.PREFIX_FLAG;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
@@ -52,10 +53,8 @@ public class BinaryTupleComparator implements Comparator<ByteBuffer> {
assert buffer1.order() == ByteOrder.LITTLE_ENDIAN;
assert buffer2.order() == ByteOrder.LITTLE_ENDIAN;
- boolean isBuffer1Prefix = isPrefix(buffer1);
- boolean isBuffer2Prefix = isPrefix(buffer2);
-
- assert !(isBuffer1Prefix && isBuffer2Prefix);
+ boolean isBuffer1Prefix = isFlagSet(buffer1, PREFIX_FLAG);
+ boolean isBuffer2Prefix = isFlagSet(buffer2, PREFIX_FLAG);
BinaryTupleSchema schema = descriptor.binaryTupleSchema();
@@ -76,7 +75,16 @@ public class BinaryTupleComparator implements Comparator<ByteBuffer> {
}
}
- return 0;
+ // We use the EQUALITY FLAG to determine the outcome of the comparison operation: if the flag is set, the prefix is considered
+ // larger than the tuple and if the flag is not set, the prefix is considered smaller than the tuple. This is needed to include
+ // or exclude the scan bounds.
+ if (isBuffer1Prefix == isBuffer2Prefix) {
+ return 0;
+ } else if (isBuffer1Prefix) {
+ return equalityFlag(buffer1);
+ } else {
+ return -equalityFlag(buffer2);
+ }
}
/**
@@ -141,4 +149,12 @@ public class BinaryTupleComparator implements Comparator<ByteBuffer> {
));
}
}
+
+ private static boolean isFlagSet(ByteBuffer tuple, int flag) {
+ return (tuple.get(0) & flag) != 0;
+ }
+
+ private static int equalityFlag(ByteBuffer tuple) {
+ return isFlagSet(tuple, EQUALITY_FLAG) ? 1 : -1;
+ }
}
diff --git a/modules/storage-api/src/test/java/org/apache/ignite/internal/storage/index/BinaryTupleComparatorTest.java b/modules/storage-api/src/test/java/org/apache/ignite/internal/storage/index/BinaryTupleComparatorTest.java
index 14e70d71f5..3c929ba1d8 100644
--- a/modules/storage-api/src/test/java/org/apache/ignite/internal/storage/index/BinaryTupleComparatorTest.java
+++ b/modules/storage-api/src/test/java/org/apache/ignite/internal/storage/index/BinaryTupleComparatorTest.java
@@ -33,6 +33,7 @@ import java.util.BitSet;
import java.util.List;
import java.util.UUID;
import org.apache.ignite.internal.binarytuple.BinaryTupleBuilder;
+import org.apache.ignite.internal.binarytuple.BinaryTupleCommon;
import org.apache.ignite.internal.binarytuple.BinaryTuplePrefixBuilder;
import org.apache.ignite.internal.schema.NativeType;
import org.apache.ignite.internal.schema.NativeTypes;
@@ -408,7 +409,13 @@ public class BinaryTupleComparatorTest {
.appendInt(1)
.build();
- assertThat(comparator.compare(tuple1, tuple2), is(0));
+ assertThat(comparator.compare(tuple2, tuple1), is(lessThanOrEqualTo(-1)));
+ assertThat(comparator.compare(tuple1, tuple2), is(greaterThanOrEqualTo(1)));
+
+ setEqualityFlag(tuple2);
+
+ assertThat(comparator.compare(tuple2, tuple1), is(lessThanOrEqualTo(1)));
+ assertThat(comparator.compare(tuple1, tuple2), is(greaterThanOrEqualTo(-1)));
}
@Test
@@ -438,6 +445,18 @@ public class BinaryTupleComparatorTest {
.appendInt(null)
.build();
- assertThat(comparator.compare(tuple1, tuple2), is(0));
+ assertThat(comparator.compare(tuple2, tuple1), is(lessThanOrEqualTo(-1)));
+ assertThat(comparator.compare(tuple1, tuple2), is(greaterThanOrEqualTo(1)));
+
+ setEqualityFlag(tuple2);
+
+ assertThat(comparator.compare(tuple2, tuple1), is(lessThanOrEqualTo(1)));
+ assertThat(comparator.compare(tuple1, tuple2), is(greaterThanOrEqualTo(-1)));
+ }
+
+ private static void setEqualityFlag(ByteBuffer buffer) {
+ byte flags = buffer.get(0);
+
+ buffer.put(0, (byte) (flags | BinaryTupleCommon.EQUALITY_FLAG));
}
}
diff --git a/modules/storage-api/src/testFixtures/java/org/apache/ignite/internal/storage/index/impl/TestSortedIndexStorage.java b/modules/storage-api/src/testFixtures/java/org/apache/ignite/internal/storage/index/impl/TestSortedIndexStorage.java
index 1dce63c58c..878af7a0f2 100644
--- a/modules/storage-api/src/testFixtures/java/org/apache/ignite/internal/storage/index/impl/TestSortedIndexStorage.java
+++ b/modules/storage-api/src/testFixtures/java/org/apache/ignite/internal/storage/index/impl/TestSortedIndexStorage.java
@@ -20,15 +20,14 @@ package org.apache.ignite.internal.storage.index.impl;
import static org.apache.ignite.internal.util.IgniteUtils.capacity;
import java.nio.ByteBuffer;
-import java.util.Comparator;
+import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
-import java.util.Map;
import java.util.Set;
+import java.util.SortedMap;
import java.util.concurrent.ConcurrentNavigableMap;
import java.util.concurrent.ConcurrentSkipListMap;
-import java.util.function.ToIntFunction;
-import java.util.stream.Stream;
+import org.apache.ignite.internal.binarytuple.BinaryTupleCommon;
import org.apache.ignite.internal.schema.BinaryTuple;
import org.apache.ignite.internal.schema.BinaryTuplePrefix;
import org.apache.ignite.internal.storage.RowId;
@@ -47,8 +46,6 @@ import org.jetbrains.annotations.Nullable;
public class TestSortedIndexStorage implements SortedIndexStorage {
private final ConcurrentNavigableMap<ByteBuffer, Set<RowId>> index;
- private final Comparator<ByteBuffer> binaryTupleComparator;
-
private final SortedIndexDescriptor descriptor;
/**
@@ -56,8 +53,7 @@ public class TestSortedIndexStorage implements SortedIndexStorage {
*/
public TestSortedIndexStorage(SortedIndexDescriptor descriptor) {
this.descriptor = descriptor;
- this.binaryTupleComparator = new BinaryTupleComparator(descriptor);
- this.index = new ConcurrentSkipListMap<>(binaryTupleComparator);
+ this.index = new ConcurrentSkipListMap<>(new BinaryTupleComparator(descriptor));
}
@Override
@@ -118,21 +114,31 @@ public class TestSortedIndexStorage implements SortedIndexStorage {
boolean includeLower = (flags & GREATER_OR_EQUAL) != 0;
boolean includeUpper = (flags & LESS_OR_EQUAL) != 0;
- Stream<Map.Entry<ByteBuffer, Set<RowId>>> data = index.entrySet().stream();
-
- if (lowerBound != null) {
- ToIntFunction<ByteBuffer> lowerCmp = boundComparator(lowerBound, includeLower ? 0 : -1);
-
- data = data.dropWhile(e -> lowerCmp.applyAsInt(e.getKey()) < 0);
+ if (!includeLower && lowerBound != null) {
+ setEqualityFlag(lowerBound);
}
- if (upperBound != null) {
- ToIntFunction<ByteBuffer> upperCmp = boundComparator(upperBound, includeUpper ? 0 : 1);
+ if (includeUpper && upperBound != null) {
+ setEqualityFlag(upperBound);
+ }
- data = data.takeWhile(e -> upperCmp.applyAsInt(e.getKey()) <= 0);
+ SortedMap<ByteBuffer, Set<RowId>> data;
+
+ if (lowerBound == null && upperBound == null) {
+ data = index;
+ } else if (lowerBound == null) {
+ data = index.headMap(upperBound.byteBuffer());
+ } else if (upperBound == null) {
+ data = index.tailMap(lowerBound.byteBuffer());
+ } else {
+ try {
+ data = index.subMap(lowerBound.byteBuffer(), upperBound.byteBuffer());
+ } catch (IllegalArgumentException e) {
+ data = Collections.emptySortedMap();
+ }
}
- Iterator<? extends IndexRow> iterator = data
+ Iterator<? extends IndexRow> iterator = data.entrySet().stream()
.flatMap(e -> {
var tuple = new BinaryTuple(descriptor.binaryTupleSchema(), e.getKey());
@@ -143,13 +149,11 @@ public class TestSortedIndexStorage implements SortedIndexStorage {
return Cursor.fromIterator(iterator);
}
- private ToIntFunction<ByteBuffer> boundComparator(BinaryTuplePrefix bound, int equals) {
- ByteBuffer boundBuffer = bound.byteBuffer();
+ private static void setEqualityFlag(BinaryTuplePrefix prefix) {
+ ByteBuffer buffer = prefix.byteBuffer();
- return tuple -> {
- int compare = binaryTupleComparator.compare(tuple, boundBuffer);
+ byte flags = buffer.get(0);
- return compare == 0 ? equals : compare;
- };
+ buffer.put(0, (byte) (flags | BinaryTupleCommon.EQUALITY_FLAG));
}
}
diff --git a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/PageMemorySortedIndexStorage.java b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/PageMemorySortedIndexStorage.java
index c6e8f9e108..9decc68e50 100644
--- a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/PageMemorySortedIndexStorage.java
+++ b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/PageMemorySortedIndexStorage.java
@@ -17,6 +17,10 @@
package org.apache.ignite.internal.storage.pagememory.index.sorted;
+import static org.apache.ignite.internal.util.CursorUtils.map;
+
+import java.nio.ByteBuffer;
+import org.apache.ignite.internal.binarytuple.BinaryTupleCommon;
import org.apache.ignite.internal.schema.BinaryTuple;
import org.apache.ignite.internal.schema.BinaryTuplePrefix;
import org.apache.ignite.internal.storage.RowId;
@@ -28,7 +32,6 @@ import org.apache.ignite.internal.storage.index.SortedIndexStorage;
import org.apache.ignite.internal.storage.pagememory.index.freelist.IndexColumns;
import org.apache.ignite.internal.storage.pagememory.index.freelist.IndexColumnsFreeList;
import org.apache.ignite.internal.util.Cursor;
-import org.apache.ignite.internal.util.CursorUtils;
import org.apache.ignite.lang.IgniteInternalCheckedException;
import org.jetbrains.annotations.Nullable;
@@ -48,6 +51,12 @@ public class PageMemorySortedIndexStorage implements SortedIndexStorage {
/** Partition id. */
private final int partitionId;
+ /** Lowest possible RowId according to signed long ordering. */
+ private final RowId lowestRowId;
+
+ /** Highest possible RowId according to signed long ordering. */
+ private final RowId highestRowId;
+
/**
* Constructor.
*
@@ -61,6 +70,10 @@ public class PageMemorySortedIndexStorage implements SortedIndexStorage {
this.sortedIndexTree = sortedIndexTree;
partitionId = sortedIndexTree.partitionId();
+
+ lowestRowId = new RowId(partitionId, Long.MIN_VALUE, Long.MIN_VALUE);
+
+ highestRowId = new RowId(partitionId, Long.MAX_VALUE, Long.MAX_VALUE);
}
@Override
@@ -70,27 +83,21 @@ public class PageMemorySortedIndexStorage implements SortedIndexStorage {
@Override
public Cursor<RowId> get(BinaryTuple key) throws StorageException {
- BinaryTuplePrefix prefix = BinaryTuplePrefix.fromBinaryTuple(key);
+ SortedIndexRowKey lowerBound = toSortedIndexRow(key, lowestRowId);
- SortedIndexRowKey prefixKey = toSortedIndexRowKey(prefix);
-
- Cursor<SortedIndexRow> cursor;
+ SortedIndexRowKey upperBound = toSortedIndexRow(key, highestRowId);
try {
- cursor = sortedIndexTree.find(prefixKey, prefixKey);
+ return map(sortedIndexTree.find(lowerBound, upperBound), SortedIndexRow::rowId);
} catch (IgniteInternalCheckedException e) {
throw new StorageException("Failed to create scan cursor", e);
}
-
- return CursorUtils.map(cursor, SortedIndexRow::rowId);
}
@Override
public void put(IndexRow row) {
- IndexColumns indexColumns = new IndexColumns(partitionId, row.indexColumns().byteBuffer());
-
try {
- SortedIndexRow sortedIndexRow = new SortedIndexRow(indexColumns, row.rowId());
+ SortedIndexRow sortedIndexRow = toSortedIndexRow(row.indexColumns(), row.rowId());
var insert = new InsertSortedIndexRowInvokeClosure(sortedIndexRow, freeList);
@@ -102,14 +109,12 @@ public class PageMemorySortedIndexStorage implements SortedIndexStorage {
@Override
public void remove(IndexRow row) {
- IndexColumns indexColumns = new IndexColumns(partitionId, row.indexColumns().byteBuffer());
-
try {
- SortedIndexRow hashIndexRow = new SortedIndexRow(indexColumns, row.rowId());
+ SortedIndexRow sortedIndexRow = toSortedIndexRow(row.indexColumns(), row.rowId());
- var remove = new RemoveSortedIndexRowInvokeClosure(hashIndexRow, freeList);
+ var remove = new RemoveSortedIndexRowInvokeClosure(sortedIndexRow, freeList);
- sortedIndexTree.invoke(hashIndexRow, null, remove);
+ sortedIndexTree.invoke(sortedIndexRow, null, remove);
// Performs actual deletion from freeList if necessary.
remove.afterCompletion();
@@ -120,26 +125,39 @@ public class PageMemorySortedIndexStorage implements SortedIndexStorage {
@Override
public Cursor<IndexRow> scan(@Nullable BinaryTuplePrefix lowerBound, @Nullable BinaryTuplePrefix upperBound, int flags) {
- Cursor<SortedIndexRow> cursor;
+ boolean includeLower = (flags & GREATER_OR_EQUAL) != 0;
+ boolean includeUpper = (flags & LESS_OR_EQUAL) != 0;
+
+ SortedIndexRowKey lower = createBound(lowerBound, !includeLower);
+
+ SortedIndexRowKey upper = createBound(upperBound, includeUpper);
try {
- cursor = sortedIndexTree.find(
- toSortedIndexRowKey(lowerBound),
- toSortedIndexRowKey(upperBound),
- (flags & GREATER_OR_EQUAL) != 0,
- (flags & LESS_OR_EQUAL) != 0,
- null,
- null
- );
+ return map(sortedIndexTree.find(lower, upper), this::toIndexRowImpl);
} catch (IgniteInternalCheckedException e) {
throw new StorageException("Failed to create scan cursor", e);
}
+ }
+
+ @Nullable
+ private SortedIndexRowKey createBound(@Nullable BinaryTuplePrefix bound, boolean setEqualityFlag) {
+ if (bound == null) {
+ return null;
+ }
+
+ ByteBuffer buffer = bound.byteBuffer();
+
+ if (setEqualityFlag) {
+ byte flags = buffer.get(0);
+
+ buffer.put(0, (byte) (flags | BinaryTupleCommon.EQUALITY_FLAG));
+ }
- return CursorUtils.map(cursor, this::toIndexRowImpl);
+ return new SortedIndexRowKey(new IndexColumns(partitionId, buffer));
}
- private @Nullable SortedIndexRowKey toSortedIndexRowKey(@Nullable BinaryTuplePrefix binaryTuple) {
- return binaryTuple == null ? null : new SortedIndexRowKey(new IndexColumns(partitionId, binaryTuple.byteBuffer()));
+ private SortedIndexRow toSortedIndexRow(BinaryTuple tuple, RowId rowId) {
+ return new SortedIndexRow(new IndexColumns(partitionId, tuple.byteBuffer()), rowId);
}
private IndexRowImpl toIndexRowImpl(SortedIndexRow sortedIndexRow) {
diff --git a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/io/SortedIndexTreeIo.java b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/io/SortedIndexTreeIo.java
index ed0f197545..dd5cdbc922 100644
--- a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/io/SortedIndexTreeIo.java
+++ b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/io/SortedIndexTreeIo.java
@@ -18,7 +18,6 @@
package org.apache.ignite.internal.storage.pagememory.index.sorted.io;
import static java.nio.ByteOrder.LITTLE_ENDIAN;
-import static org.apache.ignite.internal.binarytuple.BinaryTupleCommon.isPrefix;
import static org.apache.ignite.internal.pagememory.util.PageUtils.getLong;
import static org.apache.ignite.internal.pagememory.util.PageUtils.putLong;
import static org.apache.ignite.internal.pagememory.util.PartitionlessLinks.PARTITIONLESS_LINK_SIZE_BYTES;
@@ -132,8 +131,7 @@ public interface SortedIndexTreeIo {
int cmp = binaryTupleComparator.compare(firstBinaryTupleBuffer, secondBinaryTupleBuffer);
- // Binary Tuple Prefixes don't have row IDs, so they can't be compared.
- if (cmp != 0 || isPrefix(secondBinaryTupleBuffer)) {
+ if (cmp != 0) {
return cmp;
}
diff --git a/modules/storage-rocksdb/src/main/java/org/apache/ignite/internal/storage/rocksdb/index/RocksDbBinaryTupleComparator.java b/modules/storage-rocksdb/src/main/java/org/apache/ignite/internal/storage/rocksdb/index/RocksDbBinaryTupleComparator.java
index f2cb91bee6..6a97f22ddd 100644
--- a/modules/storage-rocksdb/src/main/java/org/apache/ignite/internal/storage/rocksdb/index/RocksDbBinaryTupleComparator.java
+++ b/modules/storage-rocksdb/src/main/java/org/apache/ignite/internal/storage/rocksdb/index/RocksDbBinaryTupleComparator.java
@@ -17,8 +17,6 @@
package org.apache.ignite.internal.storage.rocksdb.index;
-import static org.apache.ignite.internal.binarytuple.BinaryTupleCommon.isPrefix;
-
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import org.apache.ignite.internal.storage.index.BinaryTupleComparator;
@@ -58,7 +56,7 @@ public class RocksDbBinaryTupleComparator extends AbstractComparator {
@Override
public int compare(ByteBuffer a, ByteBuffer b) {
- int comparePartitionId = Short.compare(a.getShort(), b.getShort());
+ int comparePartitionId = Short.compareUnsigned(a.getShort(), b.getShort());
if (comparePartitionId != 0) {
return comparePartitionId;
@@ -69,18 +67,7 @@ public class RocksDbBinaryTupleComparator extends AbstractComparator {
int compareTuples = comparator.compare(firstBinaryTupleBuffer, secondBinaryTupleBuffer);
- if (compareTuples != 0) {
- return compareTuples;
- }
-
- // Binary Tuple Prefixes don't have row IDs, so they can't be compared further.
- if (isPrefix(firstBinaryTupleBuffer)) {
- return -1;
- } else if (isPrefix(secondBinaryTupleBuffer)) {
- return 1;
- } else {
- return compareRowIds(a, b);
- }
+ return compareTuples == 0 ? compareRowIds(a, b) : compareTuples;
}
private static int compareRowIds(ByteBuffer a, ByteBuffer b) {
diff --git a/modules/storage-rocksdb/src/main/java/org/apache/ignite/internal/storage/rocksdb/index/RocksDbSortedIndexStorage.java b/modules/storage-rocksdb/src/main/java/org/apache/ignite/internal/storage/rocksdb/index/RocksDbSortedIndexStorage.java
index 603bb6b7bb..99539633a6 100644
--- a/modules/storage-rocksdb/src/main/java/org/apache/ignite/internal/storage/rocksdb/index/RocksDbSortedIndexStorage.java
+++ b/modules/storage-rocksdb/src/main/java/org/apache/ignite/internal/storage/rocksdb/index/RocksDbSortedIndexStorage.java
@@ -18,21 +18,17 @@
package org.apache.ignite.internal.storage.rocksdb.index;
import static org.apache.ignite.internal.util.ArrayUtils.BYTE_EMPTY_ARRAY;
-import static org.apache.ignite.internal.util.CursorUtils.concat;
-import static org.apache.ignite.internal.util.CursorUtils.dropWhile;
import static org.apache.ignite.internal.util.CursorUtils.map;
-import static org.apache.ignite.internal.util.CursorUtils.takeWhile;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
-import java.util.function.Predicate;
+import org.apache.ignite.internal.binarytuple.BinaryTupleCommon;
import org.apache.ignite.internal.rocksdb.ColumnFamily;
import org.apache.ignite.internal.rocksdb.RocksIteratorAdapter;
import org.apache.ignite.internal.schema.BinaryTuple;
import org.apache.ignite.internal.schema.BinaryTuplePrefix;
import org.apache.ignite.internal.storage.RowId;
import org.apache.ignite.internal.storage.StorageException;
-import org.apache.ignite.internal.storage.index.BinaryTupleComparator;
import org.apache.ignite.internal.storage.index.IndexRow;
import org.apache.ignite.internal.storage.index.IndexRowImpl;
import org.apache.ignite.internal.storage.index.SortedIndexDescriptor;
@@ -135,36 +131,33 @@ public class RocksDbSortedIndexStorage implements SortedIndexStorage {
boolean includeLower,
boolean includeUpper
) {
- byte[] lowerBoundBytes = lowerBound == null ? null : rocksPrefix(lowerBound);
+ byte[] lowerBoundBytes;
+
+ if (lowerBound == null) {
+ lowerBoundBytes = null;
+ } else {
+ lowerBoundBytes = rocksPrefix(lowerBound);
+
+ // Skip the lower bound, if needed (RocksDB includes the lower bound by default).
+ if (!includeLower) {
+ setEqualityFlag(lowerBoundBytes);
+ }
+ }
byte[] upperBoundBytes;
if (upperBound == null) {
upperBoundBytes = null;
- } else if (lowerBound == upperBound) {
- upperBoundBytes = lowerBoundBytes;
} else {
upperBoundBytes = rocksPrefix(upperBound);
- }
-
- Cursor<ByteBuffer> cursor = createScanCursor(lowerBoundBytes, upperBoundBytes);
-
- // Skip the lower bound, if needed (RocksDB includes the lower bound by default).
- if (!includeLower && lowerBound != null) {
- cursor = dropWhile(cursor, startsWith(lowerBound));
- }
-
- // Include the upper bound, if needed (RocksDB excludes the upper bound by default).
- if (includeUpper && upperBound != null) {
- Cursor<ByteBuffer> upperBoundCursor = takeWhile(
- createScanCursor(upperBoundBytes, null),
- startsWith(upperBound)
- );
- cursor = concat(cursor, upperBoundCursor);
+ // Include the upper bound, if needed (RocksDB excludes the upper bound by default).
+ if (includeUpper) {
+ setEqualityFlag(upperBoundBytes);
+ }
}
- return cursor;
+ return createScanCursor(lowerBoundBytes, upperBoundBytes);
}
private Cursor<ByteBuffer> createScanCursor(byte @Nullable [] lowerBound, byte @Nullable [] upperBound) {
@@ -195,6 +188,13 @@ public class RocksDbSortedIndexStorage implements SortedIndexStorage {
};
}
+ private static void setEqualityFlag(byte[] prefix) {
+ // Flags start after the partition ID.
+ byte flags = prefix[Short.BYTES];
+
+ prefix[Short.BYTES] = (byte) (flags | BinaryTupleCommon.EQUALITY_FLAG);
+ }
+
private IndexRow decodeRow(ByteBuffer bytes) {
assert bytes.getShort(0) == partitionStorage.partitionId();
@@ -233,24 +233,6 @@ public class RocksDbSortedIndexStorage implements SortedIndexStorage {
.array();
}
- private Predicate<ByteBuffer> startsWith(BinaryTuplePrefix prefix) {
- var comparator = new BinaryTupleComparator(descriptor);
-
- ByteBuffer prefixBuffer = prefix.byteBuffer();
-
- return key -> {
- // First, compare the partitionIDs.
- boolean partitionIdCompare = key.getShort(0) == partitionStorage.partitionId();
-
- if (!partitionIdCompare) {
- return false;
- }
-
- // Finally, compare the remaining parts of the tuples.
- return comparator.compare(prefixBuffer, binaryTupleSlice(key)) == 0;
- };
- }
-
private static ByteBuffer binaryTupleSlice(ByteBuffer key) {
return key.duplicate()
// Discard partition ID.