You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ignite.apache.org by ti...@apache.org on 2021/12/02 14:15:10 UTC
[ignite] branch master updated: IGNITE-15515 Add exclusive find for BPlusTree (#9613)
This is an automated email from the ASF dual-hosted git repository.
timoninmaxim pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/ignite.git
The following commit(s) were added to refs/heads/master by this push:
new ec614d0 IGNITE-15515 Add exclusive find for BPlusTree (#9613)
ec614d0 is described below
commit ec614d0a84b447ac52b1fdf1e50b4c6ed6469e04
Author: Maksim Timonin <ti...@gmail.com>
AuthorDate: Thu Dec 2 17:14:40 2021 +0300
IGNITE-15515 Add exclusive find for BPlusTree (#9613)
---
.../cache/query/index/IndexQueryProcessor.java | 32 +++++++++-
.../query/index/sorted/SortedSegmentedIndex.java | 24 ++++----
.../query/index/sorted/inline/InlineIndexImpl.java | 9 +--
.../cache/persistence/tree/BPlusTree.java | 71 +++++++++++++++++-----
.../processors/query/h2/database/H2TreeIndex.java | 4 +-
.../query/h2/index/client/ClientInlineIndex.java | 17 +++---
.../cache/query/MultifieldIndexQueryTest.java | 10 +++
7 files changed, 121 insertions(+), 46 deletions(-)
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/cache/query/index/IndexQueryProcessor.java b/modules/core/src/main/java/org/apache/ignite/internal/cache/query/index/IndexQueryProcessor.java
index e0abac1..b812cf6 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/cache/query/index/IndexQueryProcessor.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/cache/query/index/IndexQueryProcessor.java
@@ -509,10 +509,17 @@ public class IndexQueryProcessor {
LinkedHashMap<String, IndexKeyDefinition> idxDef = idxProc.indexDefinition(idx.id()).indexKeyDefinitions();
- // Step 1. Traverse index.
- GridCursor<IndexRow> findRes = idx.find(qry.lower, qry.upper, segment, qryCtx);
+ boolean lowIncl = inclBoundary(qry, true);
+ boolean upIncl = inclBoundary(qry, false);
- // Step 2. Scan and filter.
+ // Step 1. Traverse index and find index boundaries.
+ GridCursor<IndexRow> findRes = idx.find(qry.lower, qry.upper, lowIncl, upIncl, segment, qryCtx);
+
+ // No need in the additional filter step for queries with 0 or 1 criteria.
+ if (qry.criteria.length <= 1)
+ return findRes;
+
+ // Step 2. Filter range if the criteria apply to multiple fields.
return new GridCursor<IndexRow>() {
/** */
private final IndexRowComparator rowCmp = ((SortedIndexDefinition)idxProc.indexDefinition(idx.id())).rowComparator();
@@ -580,6 +587,25 @@ public class IndexQueryProcessor {
}
/**
+ * Checks whether index thraversing should include boundary or not. Includes a boundary for unbounded searches, for
+ * others it checks user criteria.
+ *
+ * @param lower {@code true} for lower bound and {@code false} for upper bound.
+ * @return {@code true} for inclusive boundary, otherwise {@code false}.
+ */
+ private boolean inclBoundary(IndexRangeQuery qry, boolean lower) {
+ for (RangeIndexQueryCriterion c: qry.criteria) {
+ if (c == null || (lower ? c.lower() : c.upper()) == null)
+ break;
+
+ if (!(lower ? c.lowerIncl() : c.upperIncl()))
+ return false;
+ }
+
+ return true;
+ }
+
+ /**
* @param isNull {@code true} if user explicitly set {@code null} with a query argument.
*/
private IndexKey key(Object val, boolean isNull, IndexKeyDefinition def, IndexKeyTypeSettings settings, CacheObjectContext coctx) {
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/cache/query/index/sorted/SortedSegmentedIndex.java b/modules/core/src/main/java/org/apache/ignite/internal/cache/query/index/sorted/SortedSegmentedIndex.java
index 3c6e8c7..e119f0c 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/cache/query/index/sorted/SortedSegmentedIndex.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/cache/query/index/sorted/SortedSegmentedIndex.java
@@ -28,26 +28,24 @@ import org.jetbrains.annotations.Nullable;
*/
public interface SortedSegmentedIndex extends Index {
/**
- * Finds index rows by specified range in specified tree segment. Range can be bound or unbound.
- *
- * @param lower Nullable lower bound.
- * @param upper Nullable upper bound.
- * @param segment Number of tree segment to find.
- * @return Cursor of found index rows.
- */
- public GridCursor<IndexRow> find(@Nullable IndexRow lower, @Nullable IndexRow upper, int segment) throws IgniteCheckedException;
-
- /**
* Finds index rows by specified range in specifed tree segment with cache filtering. Range can be bound or unbound.
*
* @param lower Nullable lower bound.
* @param upper Nullable upper bound.
+ * @param lowerIncl {@code true} for inclusive lower bound, otherwise {@code false}.
+ * @param upperIncl {@code true} for inclusive upper bound, otherwise {@code false}.
* @param segment Number of tree segment to find.
- * @param qryCtx External index qyery context.
+ * @param qryCtx External index query context.
* @return Cursor of found index rows.
*/
- public GridCursor<IndexRow> find(IndexRow lower, IndexRow upper, int segment, IndexQueryContext qryCtx)
- throws IgniteCheckedException;
+ public GridCursor<IndexRow> find(
+ @Nullable IndexRow lower,
+ @Nullable IndexRow upper,
+ boolean lowerIncl,
+ boolean upperIncl,
+ int segment,
+ IndexQueryContext qryCtx
+ ) throws IgniteCheckedException;
/**
* Finds first index row for specified tree segment and cache filter.
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/cache/query/index/sorted/inline/InlineIndexImpl.java b/modules/core/src/main/java/org/apache/ignite/internal/cache/query/index/sorted/inline/InlineIndexImpl.java
index 7bf3fc4..e320670 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/cache/query/index/sorted/inline/InlineIndexImpl.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/cache/query/index/sorted/inline/InlineIndexImpl.java
@@ -83,14 +83,11 @@ public class InlineIndexImpl extends AbstractIndex implements InlineIndex {
}
/** {@inheritDoc} */
- @Override public GridCursor<IndexRow> find(IndexRow lower, IndexRow upper, int segment) throws IgniteCheckedException {
- return find(lower, upper, segment, null);
- }
-
- /** {@inheritDoc} */
@Override public GridCursor<IndexRow> find(
IndexRow lower,
IndexRow upper,
+ boolean lowIncl,
+ boolean upIncl,
int segment,
IndexQueryContext qryCtx
) throws IgniteCheckedException {
@@ -106,7 +103,7 @@ public class InlineIndexImpl extends AbstractIndex implements InlineIndex {
return new SingleCursor<>(row);
}
- return segments[segment].find(lower, upper, closure, null);
+ return segments[segment].find(lower, upper, lowIncl, upIncl, closure, null);
}
/** {@inheritDoc} */
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/BPlusTree.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/BPlusTree.java
index 49dc924..4d769a0 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/BPlusTree.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/BPlusTree.java
@@ -1038,13 +1038,14 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
/**
* @param upper Upper bound.
+ * @param upIncl {@code true} if upper bound is inclusive.
* @param c Filter closure.
* @param x Implementation specific argument, {@code null} always means that we need to return full detached data row.
* @return Cursor.
* @throws IgniteCheckedException If failed.
*/
- private GridCursor<T> findLowerUnbounded(L upper, TreeRowClosure<L, T> c, Object x) throws IgniteCheckedException {
- ForwardCursor cursor = new ForwardCursor(null, upper, c, x);
+ private GridCursor<T> findLowerUnbounded(L upper, boolean upIncl, TreeRowClosure<L, T> c, Object x) throws IgniteCheckedException {
+ ForwardCursor cursor = new ForwardCursor(upper, upIncl, c, x);
long firstPageId;
@@ -1107,13 +1108,33 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
* @throws IgniteCheckedException If failed.
*/
public GridCursor<T> find(L lower, L upper, TreeRowClosure<L, T> c, Object x) throws IgniteCheckedException {
+ return find(lower, upper, true, true, c, x);
+ }
+
+ /**
+ * @param lower Lower bound or {@code null} if unbounded.
+ * @param upper Upper bound or {@code null} if unbounded.
+ * @param lowIncl {@code true} if lower bound is inclusive.
+ * @param upIncl {@code true} if upper bound is inclusive.
+ * @param c Filter closure.
+ * @param x Implementation specific argument, {@code null} always means that we need to return full detached data row.
+ * @return Cursor.
+ * @throws IgniteCheckedException If failed.
+ */
+ public GridCursor<T> find(
+ L lower,
+ L upper,
+ boolean lowIncl,
+ boolean upIncl,
+ TreeRowClosure<L, T> c, Object x
+ ) throws IgniteCheckedException {
checkDestroyed();
- ForwardCursor cursor = new ForwardCursor(lower, upper, c, x);
+ ForwardCursor cursor = new ForwardCursor(lower, upper, lowIncl, upIncl, c, x);
try {
if (lower == null)
- return findLowerUnbounded(upper, c, x);
+ return findLowerUnbounded(upper, upIncl, c, x);
cursor.find();
@@ -5496,22 +5517,30 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
/** */
L lowerBound;
- /** */
- private int lowerShift = -1; // Initially it is -1 to handle multiple equal rows.
+ /** Handle multiple equal rows on lower side. */
+ private int lowerShift;
/** */
final L upperBound;
+ /** Handle multiple equal rows on upper side. */
+ private final int upperShift;
+
/** Cached value for retrieving diagnosting info in case of failure. */
public GetCursor getCursor;
/**
* @param lowerBound Lower bound.
* @param upperBound Upper bound.
+ * @param lowIncl {@code true} if lower bound is inclusive.
+ * @param upIncl {@code true} if upper bound is inclusive.
*/
- AbstractForwardCursor(L lowerBound, L upperBound) {
+ AbstractForwardCursor(L lowerBound, L upperBound, boolean lowIncl, boolean upIncl) {
this.lowerBound = lowerBound;
this.upperBound = upperBound;
+
+ lowerShift = lowIncl ? -1 : 1;
+ upperShift = upIncl ? 1 : -1;
}
/**
@@ -5602,8 +5631,8 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
// Compare with the last row on the page.
int cmp = compare(0, io, pageAddr, cnt - 1, upperBound);
- if (cmp > 0) {
- int idx = findInsertionPoint(0, io, pageAddr, low, cnt, upperBound, 1);
+ if (cmp > 0 || (cmp == 0 && upperShift == -1)) {
+ int idx = findInsertionPoint(0, io, pageAddr, low, cnt, upperBound, upperShift);
assert idx < 0;
@@ -5734,12 +5763,12 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
private L lastRow;
/**
- * @param lowerBound Lower bound.
- * @param upperBound Upper bound.
+ * @param lowerBound Lower bound inclusive.
+ * @param upperBound Upper bound inclusive.
* @param p Row predicate.
*/
ClosureCursor(L lowerBound, L upperBound, TreeRowClosure<L, T> p) {
- super(lowerBound, upperBound);
+ super(lowerBound, upperBound, true, true);
assert lowerBound != null;
assert upperBound != null;
@@ -5835,13 +5864,27 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
private final TreeRowClosure<L, T> c;
/**
+ * Lower unbound cursor.
+ *
+ * @param upperBound Upper bound.
+ * @param upIncl {@code true} if upper bound is inclusive.
+ * @param c Filter closure.
+ * @param x Implementation specific argument, {@code null} always means that we need to return full detached data row.
+ */
+ ForwardCursor(L upperBound, boolean upIncl, TreeRowClosure<L, T> c, Object x) {
+ this(null, upperBound, true, upIncl, c, x);
+ }
+
+ /**
* @param lowerBound Lower bound.
* @param upperBound Upper bound.
+ * @param lowIncl {@code true} if lower bound is inclusive.
+ * @param upIncl {@code true} if upper bound is inclusive.
* @param c Filter closure.
* @param x Implementation specific argument, {@code null} always means that we need to return full detached data row.
*/
- ForwardCursor(L lowerBound, L upperBound, TreeRowClosure<L, T> c, Object x) {
- super(lowerBound, upperBound);
+ ForwardCursor(L lowerBound, L upperBound, boolean lowIncl, boolean upIncl, TreeRowClosure<L, T> c, Object x) {
+ super(lowerBound, upperBound, lowIncl, upIncl);
this.c = c;
this.x = x;
diff --git a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/H2TreeIndex.java b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/H2TreeIndex.java
index 18baad6..ed1f366 100644
--- a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/H2TreeIndex.java
+++ b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/H2TreeIndex.java
@@ -204,7 +204,7 @@ public class H2TreeIndex extends H2TreeIndexBase {
QueryContext qctx = ses != null ? H2Utils.context(ses) : null;
- GridCursor<IndexRow> cursor = queryIndex.find(key.get1(), key.get2(), segment(qctx), idxQryContext(qctx));
+ GridCursor<IndexRow> cursor = queryIndex.find(key.get1(), key.get2(), true, true, segment(qctx), idxQryContext(qctx));
GridCursor<H2Row> h2cursor = new IndexValueCursor<>(cursor, this::mapIndexRow);
@@ -579,7 +579,7 @@ public class H2TreeIndex extends H2TreeIndexBase {
T2<IndexRow, IndexRow> key = prepareIndexKeys(lower, upper);
try {
- GridCursor<IndexRow> range = queryIndex.find(key.get1(), key.get2(), segment, qryCtx);
+ GridCursor<IndexRow> range = queryIndex.find(key.get1(), key.get2(), true, true, segment, qryCtx);
if (range == null)
range = IndexValueCursor.EMPTY;
diff --git a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/index/client/ClientInlineIndex.java b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/index/client/ClientInlineIndex.java
index d1f0154..14ff58a 100644
--- a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/index/client/ClientInlineIndex.java
+++ b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/index/client/ClientInlineIndex.java
@@ -31,7 +31,7 @@ import org.apache.ignite.internal.util.lang.GridCursor;
import org.jetbrains.annotations.Nullable;
/**
- * We need indexes on an not affinity nodes. The index shouldn't contains any data.
+ * We need indexes on non-affinity nodes. This index does not contain any data.
*/
public class ClientInlineIndex implements InlineIndex {
/** */
@@ -65,13 +65,14 @@ public class ClientInlineIndex implements InlineIndex {
}
/** {@inheritDoc} */
- @Override public GridCursor<IndexRow> find(IndexRow lower, IndexRow upper, int segment) throws IgniteCheckedException {
- throw unsupported();
- }
-
- /** {@inheritDoc} */
- @Override public GridCursor<IndexRow> find(IndexRow lower, IndexRow upper, int segment,
- IndexQueryContext qryCtx) throws IgniteCheckedException {
+ @Override public GridCursor<IndexRow> find(
+ IndexRow lower,
+ IndexRow upper,
+ boolean lowIncl,
+ boolean upIncl,
+ int segment,
+ IndexQueryContext qryCtx
+ ) throws IgniteCheckedException {
throw unsupported();
}
diff --git a/modules/indexing/src/test/java/org/apache/ignite/cache/query/MultifieldIndexQueryTest.java b/modules/indexing/src/test/java/org/apache/ignite/cache/query/MultifieldIndexQueryTest.java
index 951529c..de502da 100644
--- a/modules/indexing/src/test/java/org/apache/ignite/cache/query/MultifieldIndexQueryTest.java
+++ b/modules/indexing/src/test/java/org/apache/ignite/cache/query/MultifieldIndexQueryTest.java
@@ -35,6 +35,8 @@ import org.apache.ignite.cache.CacheAtomicityMode;
import org.apache.ignite.cache.query.annotations.QuerySqlField;
import org.apache.ignite.configuration.CacheConfiguration;
import org.apache.ignite.configuration.IgniteConfiguration;
+import org.apache.ignite.internal.util.tostring.GridToStringInclude;
+import org.apache.ignite.internal.util.typedef.internal.S;
import org.apache.ignite.testframework.GridTestUtils;
import org.apache.ignite.testframework.junits.common.GridCommonAbstractTest;
import org.junit.Test;
@@ -499,6 +501,7 @@ public class MultifieldIndexQueryTest extends GridCommonAbstractTest {
/** */
private static class Person {
/** */
+ @GridToStringInclude
@QuerySqlField(orderedGroups = {
@QuerySqlField.Group(name = INDEX, order = 0),
@QuerySqlField.Group(name = DESC_INDEX, order = 0)}
@@ -506,10 +509,12 @@ public class MultifieldIndexQueryTest extends GridCommonAbstractTest {
final int id;
/** */
+ @GridToStringInclude
@QuerySqlField(orderedGroups = @QuerySqlField.Group(name = INDEX, order = 1))
final int secId;
/** */
+ @GridToStringInclude
@QuerySqlField(orderedGroups = @QuerySqlField.Group(name = DESC_INDEX, order = 1, descending = true))
final int descId;
@@ -544,5 +549,10 @@ public class MultifieldIndexQueryTest extends GridCommonAbstractTest {
@Override public int hashCode() {
return Objects.hash(id, secId);
}
+
+ /** {@inheritDoc} */
+ @Override public String toString() {
+ return S.toString(Person.class, this);
+ }
}
}