You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@ignite.apache.org by GitBox <gi...@apache.org> on 2022/09/13 11:26:09 UTC

[GitHub] [ignite-3] tkalkirill opened a new pull request, #1075: IGNITE-17670 Implementing a sorted index B+Tree

tkalkirill opened a new pull request, #1075:
URL: https://github.com/apache/ignite-3/pull/1075

   https://issues.apache.org/jira/browse/IGNITE-17670


-- 
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: notifications-unsubscribe@ignite.apache.org

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

[GitHub] [ignite-3] ibessonov commented on a diff in pull request #1075: IGNITE-17670 Implementing a sorted index B+Tree

Posted by GitBox <gi...@apache.org>.
ibessonov commented on code in PR #1075:
URL: https://github.com/apache/ignite-3/pull/1075#discussion_r969580735


##########
modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/io/SortedIndexTreeIo.java:
##########
@@ -0,0 +1,173 @@
+/*
+ * 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.ignite.internal.storage.pagememory.index.sorted.io;
+
+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;
+import static org.apache.ignite.internal.pagememory.util.PartitionlessLinks.readPartitionlessLink;
+import static org.apache.ignite.internal.pagememory.util.PartitionlessLinks.writePartitionlessLink;
+
+import java.nio.ByteBuffer;
+import java.util.UUID;
+import org.apache.ignite.internal.pagememory.datapage.DataPageReader;
+import org.apache.ignite.internal.pagememory.tree.io.BplusIo;
+import org.apache.ignite.internal.pagememory.util.PageUtils;
+import org.apache.ignite.internal.storage.RowId;
+import org.apache.ignite.internal.storage.pagememory.index.freelist.IndexColumns;
+import org.apache.ignite.internal.storage.pagememory.index.freelist.ReadIndexColumnsValue;
+import org.apache.ignite.internal.storage.pagememory.index.meta.IndexMeta;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.SortedIndexRow;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.SortedIndexRowKey;
+import org.apache.ignite.lang.IgniteInternalCheckedException;
+
+/**
+ * Interface for {@link IndexMeta} B+Tree-related IO.
+ *
+ * <p>Defines a following data layout:
+ * <ul>
+ *     <li>Index ID - {@link UUID} (16 bytes);</li>
+ *     <li>Index root page ID - long (8 bytes).</li>
+ * </ul>
+ */
+public interface SortedIndexTreeIo {
+    /** Offset of the index column link (6 bytes). */
+    int INDEX_COLUMNS_LINK_OFFSET = 0;
+
+    /** Offset of rowId's most significant bits, 8 bytes. */
+    int ROW_ID_MSB_OFFSET = INDEX_COLUMNS_LINK_OFFSET + PARTITIONLESS_LINK_SIZE_BYTES;
+
+    /** Offset of rowId's least significant bits, 8 bytes. */
+    int ROW_ID_LSB_OFFSET = ROW_ID_MSB_OFFSET + Long.BYTES;
+
+    /** Payload size in bytes. */
+    int SIZE_IN_BYTES = ROW_ID_LSB_OFFSET + Long.BYTES;
+
+    /**
+     * Returns an offset of the element inside the page.
+     *
+     * @see BplusIo#offset(int)
+     */
+    int offset(int idx);
+
+    /**
+     * Stores a sorted index row, copied from another page.
+     *
+     * @see BplusIo#store(long, int, BplusIo, long, int)
+     */
+    default void store(long dstPageAddr, int dstIdx, BplusIo<SortedIndexRowKey> srcIo, long srcPageAddr, int srcIdx) {
+        int dstOffset = offset(dstIdx);
+        int srcOffset = offset(srcIdx);
+
+        PageUtils.copyMemory(srcPageAddr, srcOffset, dstPageAddr, dstOffset, SIZE_IN_BYTES);
+    }
+
+    /**
+     * Stores a sorted index row in the page.
+     *
+     * @see BplusIo#storeByOffset(long, int, Object)
+     */
+    default void storeByOffset(long pageAddr, int off, SortedIndexRowKey rowKey) {
+        assert rowKey instanceof SortedIndexRow;
+
+        SortedIndexRow sortedIndexRow = (SortedIndexRow) rowKey;
+
+        writePartitionlessLink(pageAddr + off + INDEX_COLUMNS_LINK_OFFSET, sortedIndexRow.indexColumns().link());
+
+        RowId rowId = sortedIndexRow.rowId();
+
+        putLong(pageAddr, off + ROW_ID_MSB_OFFSET, rowId.mostSignificantBits());
+        putLong(pageAddr, off + ROW_ID_LSB_OFFSET, rowId.leastSignificantBits());
+    }
+
+    /**
+     * Compare the {@link SortedIndexRowKey} from the page with passed {@link SortedIndexRowKey}.
+     *
+     * @param pageAddr Page address.
+     * @param idx Element's index.
+     * @param rowKey Lookup index row key.
+     * @return Comparison result.
+     */
+    default int compare(DataPageReader dataPageReader, int partitionId, long pageAddr, int idx, SortedIndexRowKey rowKey)
+            throws IgniteInternalCheckedException {
+        assert rowKey instanceof SortedIndexRow;
+
+        SortedIndexRow sortedIndexRow = (SortedIndexRow) rowKey;
+
+        int off = offset(idx);
+
+        long link = readPartitionlessLink(partitionId, pageAddr, off + INDEX_COLUMNS_LINK_OFFSET);
+
+        //TODO Add in-place compare in IGNITE-17671
+        ReadIndexColumnsValue indexColumnsTraversal = new ReadIndexColumnsValue();
+
+        dataPageReader.traverse(link, indexColumnsTraversal, null);
+
+        ByteBuffer indexColumnsBuffer = ByteBuffer.wrap(indexColumnsTraversal.result());
+
+        int cmp = indexColumnsBuffer.compareTo(sortedIndexRow.indexColumns().valueBuffer());

Review Comment:
   Where's TODO? This comparison is wrong



##########
modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/io/SortedIndexTreeIo.java:
##########
@@ -0,0 +1,173 @@
+/*
+ * 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.ignite.internal.storage.pagememory.index.sorted.io;
+
+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;
+import static org.apache.ignite.internal.pagememory.util.PartitionlessLinks.readPartitionlessLink;
+import static org.apache.ignite.internal.pagememory.util.PartitionlessLinks.writePartitionlessLink;
+
+import java.nio.ByteBuffer;
+import java.util.UUID;
+import org.apache.ignite.internal.pagememory.datapage.DataPageReader;
+import org.apache.ignite.internal.pagememory.tree.io.BplusIo;
+import org.apache.ignite.internal.pagememory.util.PageUtils;
+import org.apache.ignite.internal.storage.RowId;
+import org.apache.ignite.internal.storage.pagememory.index.freelist.IndexColumns;
+import org.apache.ignite.internal.storage.pagememory.index.freelist.ReadIndexColumnsValue;
+import org.apache.ignite.internal.storage.pagememory.index.meta.IndexMeta;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.SortedIndexRow;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.SortedIndexRowKey;
+import org.apache.ignite.lang.IgniteInternalCheckedException;
+
+/**
+ * Interface for {@link IndexMeta} B+Tree-related IO.

Review Comment:
   This comment is wrong



-- 
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: notifications-unsubscribe@ignite.apache.org

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

[GitHub] [ignite-3] ibessonov merged pull request #1075: IGNITE-17670 Implementing a sorted index B+Tree

Posted by GitBox <gi...@apache.org>.
ibessonov merged PR #1075:
URL: https://github.com/apache/ignite-3/pull/1075


-- 
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: notifications-unsubscribe@ignite.apache.org

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

[GitHub] [ignite-3] tkalkirill commented on a diff in pull request #1075: IGNITE-17670 Implementing a sorted index B+Tree

Posted by GitBox <gi...@apache.org>.
tkalkirill commented on code in PR #1075:
URL: https://github.com/apache/ignite-3/pull/1075#discussion_r969685323


##########
modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/io/SortedIndexTreeIo.java:
##########
@@ -0,0 +1,173 @@
+/*
+ * 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.ignite.internal.storage.pagememory.index.sorted.io;
+
+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;
+import static org.apache.ignite.internal.pagememory.util.PartitionlessLinks.readPartitionlessLink;
+import static org.apache.ignite.internal.pagememory.util.PartitionlessLinks.writePartitionlessLink;
+
+import java.nio.ByteBuffer;
+import java.util.UUID;
+import org.apache.ignite.internal.pagememory.datapage.DataPageReader;
+import org.apache.ignite.internal.pagememory.tree.io.BplusIo;
+import org.apache.ignite.internal.pagememory.util.PageUtils;
+import org.apache.ignite.internal.storage.RowId;
+import org.apache.ignite.internal.storage.pagememory.index.freelist.IndexColumns;
+import org.apache.ignite.internal.storage.pagememory.index.freelist.ReadIndexColumnsValue;
+import org.apache.ignite.internal.storage.pagememory.index.meta.IndexMeta;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.SortedIndexRow;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.SortedIndexRowKey;
+import org.apache.ignite.lang.IgniteInternalCheckedException;
+
+/**
+ * Interface for {@link IndexMeta} B+Tree-related IO.

Review Comment:
   Fix it



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

To unsubscribe, e-mail: notifications-unsubscribe@ignite.apache.org

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

[GitHub] [ignite-3] tkalkirill commented on a diff in pull request #1075: IGNITE-17670 Implementing a sorted index B+Tree

Posted by GitBox <gi...@apache.org>.
tkalkirill commented on code in PR #1075:
URL: https://github.com/apache/ignite-3/pull/1075#discussion_r969678239


##########
modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/io/SortedIndexTreeIo.java:
##########
@@ -0,0 +1,173 @@
+/*
+ * 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.ignite.internal.storage.pagememory.index.sorted.io;
+
+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;
+import static org.apache.ignite.internal.pagememory.util.PartitionlessLinks.readPartitionlessLink;
+import static org.apache.ignite.internal.pagememory.util.PartitionlessLinks.writePartitionlessLink;
+
+import java.nio.ByteBuffer;
+import java.util.UUID;
+import org.apache.ignite.internal.pagememory.datapage.DataPageReader;
+import org.apache.ignite.internal.pagememory.tree.io.BplusIo;
+import org.apache.ignite.internal.pagememory.util.PageUtils;
+import org.apache.ignite.internal.storage.RowId;
+import org.apache.ignite.internal.storage.pagememory.index.freelist.IndexColumns;
+import org.apache.ignite.internal.storage.pagememory.index.freelist.ReadIndexColumnsValue;
+import org.apache.ignite.internal.storage.pagememory.index.meta.IndexMeta;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.SortedIndexRow;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.SortedIndexRowKey;
+import org.apache.ignite.lang.IgniteInternalCheckedException;
+
+/**
+ * Interface for {@link IndexMeta} B+Tree-related IO.
+ *
+ * <p>Defines a following data layout:
+ * <ul>
+ *     <li>Index ID - {@link UUID} (16 bytes);</li>
+ *     <li>Index root page ID - long (8 bytes).</li>
+ * </ul>
+ */
+public interface SortedIndexTreeIo {
+    /** Offset of the index column link (6 bytes). */
+    int INDEX_COLUMNS_LINK_OFFSET = 0;
+
+    /** Offset of rowId's most significant bits, 8 bytes. */
+    int ROW_ID_MSB_OFFSET = INDEX_COLUMNS_LINK_OFFSET + PARTITIONLESS_LINK_SIZE_BYTES;
+
+    /** Offset of rowId's least significant bits, 8 bytes. */
+    int ROW_ID_LSB_OFFSET = ROW_ID_MSB_OFFSET + Long.BYTES;
+
+    /** Payload size in bytes. */
+    int SIZE_IN_BYTES = ROW_ID_LSB_OFFSET + Long.BYTES;
+
+    /**
+     * Returns an offset of the element inside the page.
+     *
+     * @see BplusIo#offset(int)
+     */
+    int offset(int idx);
+
+    /**
+     * Stores a sorted index row, copied from another page.
+     *
+     * @see BplusIo#store(long, int, BplusIo, long, int)
+     */
+    default void store(long dstPageAddr, int dstIdx, BplusIo<SortedIndexRowKey> srcIo, long srcPageAddr, int srcIdx) {
+        int dstOffset = offset(dstIdx);
+        int srcOffset = offset(srcIdx);
+
+        PageUtils.copyMemory(srcPageAddr, srcOffset, dstPageAddr, dstOffset, SIZE_IN_BYTES);
+    }
+
+    /**
+     * Stores a sorted index row in the page.
+     *
+     * @see BplusIo#storeByOffset(long, int, Object)
+     */
+    default void storeByOffset(long pageAddr, int off, SortedIndexRowKey rowKey) {
+        assert rowKey instanceof SortedIndexRow;
+
+        SortedIndexRow sortedIndexRow = (SortedIndexRow) rowKey;
+
+        writePartitionlessLink(pageAddr + off + INDEX_COLUMNS_LINK_OFFSET, sortedIndexRow.indexColumns().link());
+
+        RowId rowId = sortedIndexRow.rowId();
+
+        putLong(pageAddr, off + ROW_ID_MSB_OFFSET, rowId.mostSignificantBits());
+        putLong(pageAddr, off + ROW_ID_LSB_OFFSET, rowId.leastSignificantBits());
+    }
+
+    /**
+     * Compare the {@link SortedIndexRowKey} from the page with passed {@link SortedIndexRowKey}.
+     *
+     * @param pageAddr Page address.
+     * @param idx Element's index.
+     * @param rowKey Lookup index row key.
+     * @return Comparison result.
+     */
+    default int compare(DataPageReader dataPageReader, int partitionId, long pageAddr, int idx, SortedIndexRowKey rowKey)
+            throws IgniteInternalCheckedException {
+        assert rowKey instanceof SortedIndexRow;
+
+        SortedIndexRow sortedIndexRow = (SortedIndexRow) rowKey;
+
+        int off = offset(idx);
+
+        long link = readPartitionlessLink(partitionId, pageAddr, off + INDEX_COLUMNS_LINK_OFFSET);
+
+        //TODO Add in-place compare in IGNITE-17671
+        ReadIndexColumnsValue indexColumnsTraversal = new ReadIndexColumnsValue();
+
+        dataPageReader.traverse(link, indexColumnsTraversal, null);
+
+        ByteBuffer indexColumnsBuffer = ByteBuffer.wrap(indexColumnsTraversal.result());
+
+        int cmp = indexColumnsBuffer.compareTo(sortedIndexRow.indexColumns().valueBuffer());

Review Comment:
   Fix it



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

To unsubscribe, e-mail: notifications-unsubscribe@ignite.apache.org

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

[GitHub] [ignite-3] ibessonov commented on a diff in pull request #1075: IGNITE-17670 Implementing a sorted index B+Tree

Posted by GitBox <gi...@apache.org>.
ibessonov commented on code in PR #1075:
URL: https://github.com/apache/ignite-3/pull/1075#discussion_r969742470


##########
modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/IndexPageTypes.java:
##########
@@ -41,4 +41,13 @@ public interface IndexPageTypes {
 
     /** Hash index tree meta IO type. */
     short T_HASH_INDEX_LEAF_IO = 10_002;
+
+    /** Sorted index tree meta IO type. */
+    short T_SORTED_INDEX_META_IO = 10_003;

Review Comment:
   For a future, I would advise using a constant like 20_000. Makes sense for visual clues in logs, makes sense for future improvements related to inlines.
   You don't need to change anything right now, that's just the info to think about.



##########
modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/hash/io/HashIndexTreeIo.java:
##########
@@ -35,16 +35,16 @@
 import org.apache.ignite.internal.storage.pagememory.index.freelist.ReadIndexColumnsValue;
 import org.apache.ignite.internal.storage.pagememory.index.hash.HashIndexRow;
 import org.apache.ignite.internal.storage.pagememory.index.hash.HashIndexRowKey;
-import org.apache.ignite.internal.storage.pagememory.index.meta.IndexMeta;
 import org.apache.ignite.lang.IgniteInternalCheckedException;
 
 /**
- * Interface for {@link IndexMeta} B+Tree-related IO.
+ * Interface for {@link HashIndexRow} B+Tree-related IO.

Review Comment:
   Thank you!



-- 
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: notifications-unsubscribe@ignite.apache.org

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