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 955e835503e IGNITE-27198 Optimize hash index lookup (#7092)
955e835503e is described below
commit 955e835503e761d247fe5263c11eae1ab2b14073
Author: Ivan Bessonov <[email protected]>
AuthorDate: Tue Dec 2 17:58:38 2025 +0300
IGNITE-27198 Optimize hash index lookup (#7092)
---
.../storage/index/AbstractIndexStorageTest.java | 54 ----------------------
.../index/AbstractPageMemoryIndexStorage.java | 43 +++++++++++++++++
.../pagememory/index/hash/HashIndexRowKey.java | 10 ++++
.../index/hash/PageMemoryHashIndexStorage.java | 27 ++++++-----
.../pagememory/index/hash/io/HashIndexTreeIo.java | 18 ++++----
.../index/sorted/PageMemorySortedIndexStorage.java | 40 +++-------------
6 files changed, 82 insertions(+), 110 deletions(-)
diff --git
a/modules/storage-api/src/testFixtures/java/org/apache/ignite/internal/storage/index/AbstractIndexStorageTest.java
b/modules/storage-api/src/testFixtures/java/org/apache/ignite/internal/storage/index/AbstractIndexStorageTest.java
index e024580b54c..439ede71095 100644
---
a/modules/storage-api/src/testFixtures/java/org/apache/ignite/internal/storage/index/AbstractIndexStorageTest.java
+++
b/modules/storage-api/src/testFixtures/java/org/apache/ignite/internal/storage/index/AbstractIndexStorageTest.java
@@ -34,11 +34,9 @@ import static org.hamcrest.Matchers.notNullValue;
import static org.hamcrest.Matchers.nullValue;
import static org.junit.jupiter.api.Assertions.assertDoesNotThrow;
import static org.junit.jupiter.api.Assertions.assertEquals;
-import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertNotNull;
import static org.junit.jupiter.api.Assertions.assertNull;
import static org.junit.jupiter.api.Assertions.assertThrows;
-import static org.junit.jupiter.api.Assertions.assertTrue;
import static org.mockito.ArgumentMatchers.eq;
import static org.mockito.Mockito.mock;
import static org.mockito.Mockito.when;
@@ -46,7 +44,6 @@ import static org.mockito.Mockito.when;
import it.unimi.dsi.fastutil.ints.IntList;
import java.util.Collection;
import java.util.List;
-import java.util.NoSuchElementException;
import java.util.Random;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Stream;
@@ -244,57 +241,6 @@ public abstract class AbstractIndexStorageTest<S extends
IndexStorage, D extends
assertThat(getAll(index, row4), is(empty()));
}
- @Test
- public void testGetConcurrentPut() {
- S index = createIndexStorage(INDEX_NAME, ColumnType.INT32,
ColumnType.STRING);
- var serializer = new BinaryTupleRowSerializer(indexDescriptor(index));
-
- Object[] columnValues = { 1, "foo" };
- IndexRow row1 = serializer.serializeRow(columnValues, new
RowId(TEST_PARTITION, 1, 1));
- IndexRow row2 = serializer.serializeRow(columnValues, new
RowId(TEST_PARTITION, 2, 2));
-
- try (Cursor<RowId> cursor = index.get(row1.indexColumns())) {
- put(index, row1);
-
- assertTrue(cursor.hasNext());
- assertEquals(row1.rowId(), cursor.next());
-
- put(index, row2);
-
- assertTrue(cursor.hasNext());
- assertEquals(row2.rowId(), cursor.next());
-
- assertFalse(cursor.hasNext());
- assertThrows(NoSuchElementException.class, cursor::next);
- }
- }
-
- @Test
- public void testGetConcurrentReplace() {
- S index = createIndexStorage(INDEX_NAME, ColumnType.INT32,
ColumnType.STRING);
- var serializer = new BinaryTupleRowSerializer(indexDescriptor(index));
-
- Object[] columnValues = { 1, "foo" };
- IndexRow row1 = serializer.serializeRow(columnValues, new
RowId(TEST_PARTITION, 1, 1));
- IndexRow row2 = serializer.serializeRow(columnValues, new
RowId(TEST_PARTITION, 2, 2));
-
- put(index, row1);
-
- try (Cursor<RowId> cursor = index.get(row1.indexColumns())) {
- assertTrue(cursor.hasNext());
- assertEquals(row1.rowId(), cursor.next());
-
- remove(index, row1);
- put(index, row2);
-
- assertTrue(cursor.hasNext());
- assertEquals(row2.rowId(), cursor.next());
-
- assertFalse(cursor.hasNext());
- assertThrows(NoSuchElementException.class, cursor::next);
- }
- }
-
/**
* Tests that {@link IndexStorage#put} does not create row ID duplicates.
*/
diff --git
a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/AbstractPageMemoryIndexStorage.java
b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/AbstractPageMemoryIndexStorage.java
index eb04d336451..3048327b322 100644
---
a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/AbstractPageMemoryIndexStorage.java
+++
b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/AbstractPageMemoryIndexStorage.java
@@ -49,6 +49,7 @@ import
org.apache.ignite.internal.storage.pagememory.index.meta.IndexMetaTree;
import
org.apache.ignite.internal.storage.pagememory.index.meta.UpdateLastRowIdUuidToBuildInvokeClosure;
import org.apache.ignite.internal.storage.util.StorageState;
import org.apache.ignite.internal.storage.util.StorageUtils;
+import org.apache.ignite.internal.util.Cursor;
import org.apache.ignite.internal.util.IgniteSpinBusyLock;
import org.jetbrains.annotations.Nullable;
@@ -441,6 +442,48 @@ public abstract class AbstractPageMemoryIndexStorage<K
extends IndexRowKey, V ex
}
}
+ /**
+ * Wrapper to the cursor that's returned from B+Tree.
+ *
+ * @param <E> Type of elements in the cursor.
+ * @param <R> Type of result.
+ */
+ protected abstract class ReadOnlyScanCursor<E, R> implements Cursor<R> {
+ private final Cursor<E> treeCursor;
+
+ protected ReadOnlyScanCursor(Cursor<E> treeCursor) {
+ this.treeCursor = treeCursor;
+ }
+
+ /**
+ * Maps value from the index tree into the required result.
+ */
+ protected abstract R map(E value);
+
+ @Override
+ public boolean hasNext() {
+ return busyDataRead(() -> {
+ throwExceptionIfStorageInProgressOfRebalance(state.get(),
AbstractPageMemoryIndexStorage.this::createStorageInfo);
+
+ return treeCursor.hasNext();
+ });
+ }
+
+ @Override
+ public R next() {
+ return busyDataRead(() -> {
+ throwExceptionIfStorageInProgressOfRebalance(state.get(),
AbstractPageMemoryIndexStorage.this::createStorageInfo);
+
+ return map(treeCursor.next());
+ });
+ }
+
+ @Override
+ public void close() {
+ treeCursor.close();
+ }
+ }
+
protected void throwExceptionIfIndexIsNotBuilt() {
StorageUtils.throwExceptionIfIndexIsNotBuilt(nextRowIdToBuild,
this::createStorageInfo);
}
diff --git
a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/hash/HashIndexRowKey.java
b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/hash/HashIndexRowKey.java
index 3e3566f2515..2d224a52dda 100644
---
a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/hash/HashIndexRowKey.java
+++
b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/hash/HashIndexRowKey.java
@@ -20,6 +20,7 @@ package
org.apache.ignite.internal.storage.pagememory.index.hash;
import org.apache.ignite.internal.storage.pagememory.index.common.IndexRowKey;
import
org.apache.ignite.internal.storage.pagememory.index.freelist.IndexColumns;
import org.apache.ignite.internal.tostring.S;
+import org.apache.ignite.internal.util.HashUtils;
/**
* Key to search for a {@link HashIndexRow} in the {@link HashIndexTree}.
@@ -29,6 +30,15 @@ public class HashIndexRowKey implements IndexRowKey {
private final IndexColumns indexColumns;
+ /**
+ * Constructor.
+ *
+ * @param indexColumns Index columns.
+ */
+ HashIndexRowKey(IndexColumns indexColumns) {
+ this(HashUtils.hash32(indexColumns.valueBuffer()), indexColumns);
+ }
+
/**
* Constructor.
*
diff --git
a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/hash/PageMemoryHashIndexStorage.java
b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/hash/PageMemoryHashIndexStorage.java
index 27100b5325d..da3d4ba5072 100644
---
a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/hash/PageMemoryHashIndexStorage.java
+++
b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/hash/PageMemoryHashIndexStorage.java
@@ -19,7 +19,6 @@ package
org.apache.ignite.internal.storage.pagememory.index.hash;
import static
org.apache.ignite.internal.storage.util.StorageUtils.throwExceptionIfStorageInProgressOfRebalance;
-import java.util.Objects;
import org.apache.ignite.internal.lang.IgniteInternalCheckedException;
import org.apache.ignite.internal.pagememory.freelist.FreeListImpl;
import org.apache.ignite.internal.pagememory.util.GradualTask;
@@ -99,19 +98,19 @@ public class PageMemoryHashIndexStorage extends
AbstractPageMemoryIndexStorage<H
IndexColumns indexColumns = new IndexColumns(partitionId,
key.byteBuffer());
- HashIndexRow lowerBound = new HashIndexRow(indexColumns,
lowestRowId);
-
- return new ScanCursor<RowId>(lowerBound) {
- @Override
- protected RowId map(HashIndexRow value) {
- return value.rowId();
- }
-
- @Override
- protected boolean exceedsUpperBound(HashIndexRow value) {
- return !Objects.equals(value.indexColumns().valueBuffer(),
key.byteBuffer());
- }
- };
+ HashIndexRowKey bound = new HashIndexRowKey(indexColumns);
+ try {
+ Cursor<HashIndexRow> cursor = indexTree.find(bound, bound);
+
+ return new ReadOnlyScanCursor<HashIndexRow, RowId>(cursor) {
+ @Override
+ protected RowId map(HashIndexRow value) {
+ return value.rowId();
+ }
+ };
+ } catch (IgniteInternalCheckedException e) {
+ throw new StorageException("Couldn't get index tree cursor",
e);
+ }
});
}
diff --git
a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/hash/io/HashIndexTreeIo.java
b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/hash/io/HashIndexTreeIo.java
index 131e14156ff..5b4208e9b96 100644
---
a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/hash/io/HashIndexTreeIo.java
+++
b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/hash/io/HashIndexTreeIo.java
@@ -174,13 +174,9 @@ public interface HashIndexTreeIo {
*/
default int compare(DataPageReader dataPageReader, int partitionId, long
pageAddr, int idx, HashIndexRowKey rowKey)
throws IgniteInternalCheckedException {
- assert rowKey instanceof HashIndexRow;
-
- HashIndexRow row = (HashIndexRow) rowKey;
-
final int off = offset(idx);
- int cmp = Integer.compare(getInt(pageAddr + off, HASH_OFFSET),
row.indexColumnsHash());
+ int cmp = Integer.compare(getInt(pageAddr + off, HASH_OFFSET),
rowKey.indexColumnsHash());
if (cmp != 0) {
return cmp;
@@ -193,7 +189,7 @@ public interface HashIndexTreeIo {
ByteBuffer indexColumnsBuffer = wrapPointer(pageAddr + off +
TUPLE_OFFSET, indexColumnsSize);
- ByteBuffer rowIndexColumnsCopyForComparison =
row.indexColumns().valueBuffer().rewind().duplicate();
+ ByteBuffer rowIndexColumnsCopyForComparison =
rowKey.indexColumns().valueBuffer().rewind().duplicate();
if (rowIndexColumnsCopyForComparison.capacity() >
indexColumnsSize) {
rowIndexColumnsCopyForComparison.limit(indexColumnsSize);
@@ -209,19 +205,25 @@ public interface HashIndexTreeIo {
CompareIndexColumnsValue compareIndexColumnsValue = new
CompareIndexColumnsValue();
- dataPageReader.traverse(link, compareIndexColumnsValue,
row.indexColumns().valueBuffer().rewind().duplicate());
+ dataPageReader.traverse(link, compareIndexColumnsValue,
rowKey.indexColumns().valueBuffer().rewind().duplicate());
cmp = compareIndexColumnsValue.compareResult();
} else {
ByteBuffer indexColumnsBuffer = wrapPointer(pageAddr + off +
TUPLE_OFFSET, indexColumnsSize);
- cmp =
indexColumnsBuffer.compareTo(row.indexColumns().valueBuffer().rewind());
+ cmp =
indexColumnsBuffer.compareTo(rowKey.indexColumns().valueBuffer().rewind());
}
if (cmp != 0) {
return cmp;
}
+ if (!(rowKey instanceof HashIndexRow)) {
+ return 0;
+ }
+
+ HashIndexRow row = (HashIndexRow) rowKey;
+
long rowIdMsb = getLong(pageAddr + off, rowIdMsbOffset());
cmp = Long.compare(rowIdMsb, row.rowId().mostSignificantBits());
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 13e635e6517..d34f63a2f71 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
@@ -170,7 +170,12 @@ public class PageMemorySortedIndexStorage extends
AbstractPageMemoryIndexStorage
try {
Cursor<SortedIndexRow> cursor = indexTree.find(lower, upper);
- return new ReadOnlyScanCursor(cursor);
+ return new ReadOnlyScanCursor<SortedIndexRow,
IndexRow>(cursor) {
+ @Override
+ protected IndexRow map(SortedIndexRow value) {
+ return toIndexRowImpl(value);
+ }
+ };
} catch (IgniteInternalCheckedException e) {
throw new StorageException("Couldn't get index tree cursor",
e);
}
@@ -268,37 +273,4 @@ public class PageMemorySortedIndexStorage extends
AbstractPageMemoryIndexStorage
};
});
}
-
- private class ReadOnlyScanCursor implements Cursor<IndexRow> {
- private final Cursor<SortedIndexRow> treeCursor;
-
- private ReadOnlyScanCursor(Cursor<SortedIndexRow> treeCursor) {
- this.treeCursor = treeCursor;
- }
-
- @Override
- public boolean hasNext() {
- return busyDataRead(() -> {
- throwExceptionIfStorageInProgressOfRebalance(state.get(),
PageMemorySortedIndexStorage.this::createStorageInfo);
-
- return treeCursor.hasNext();
- });
- }
-
- @Override
- public IndexRow next() {
- return busyDataRead(() -> {
- throwExceptionIfStorageInProgressOfRebalance(state.get(),
PageMemorySortedIndexStorage.this::createStorageInfo);
-
- SortedIndexRow next = treeCursor.next();
-
- return toIndexRowImpl(next);
- });
- }
-
- @Override
- public void close() {
- treeCursor.close();
- }
- }
}
