You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ignite.apache.org by al...@apache.org on 2021/07/30 07:14:14 UTC
[ignite] branch sql-calcite updated: IGNITE-14816 Change TreeMap in
sorted IndexSpoolNode to ArrayList - Fixes #9234.
This is an automated email from the ASF dual-hosted git repository.
alexpl pushed a commit to branch sql-calcite
in repository https://gitbox.apache.org/repos/asf/ignite.git
The following commit(s) were added to refs/heads/sql-calcite by this push:
new 6bd1df9 IGNITE-14816 Change TreeMap in sorted IndexSpoolNode to ArrayList - Fixes #9234.
6bd1df9 is described below
commit 6bd1df953a7648c385d2f932ce85c859dbee6536
Author: Pavel Pereslegin <xx...@gmail.com>
AuthorDate: Fri Jul 30 10:07:17 2021 +0300
IGNITE-14816 Change TreeMap in sorted IndexSpoolNode to ArrayList - Fixes #9234.
Signed-off-by: Aleksey Plekhanov <pl...@gmail.com>
---
...ntimeTreeIndex.java => RuntimeSortedIndex.java} | 111 ++++++++++++---------
.../query/calcite/exec/rel/IndexSpoolNode.java | 4 +-
...eIndexTest.java => RuntimeSortedIndexTest.java} | 17 ++--
...est.java => SortedIndexSpoolExecutionTest.java} | 2 +-
.../ignite/testsuites/ExecutionTestSuite.java | 8 +-
5 files changed, 76 insertions(+), 66 deletions(-)
diff --git a/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/exec/RuntimeTreeIndex.java b/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/exec/RuntimeSortedIndex.java
similarity index 63%
rename from modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/exec/RuntimeTreeIndex.java
rename to modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/exec/RuntimeSortedIndex.java
index 6db5262..6d9677f 100644
--- a/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/exec/RuntimeTreeIndex.java
+++ b/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/exec/RuntimeSortedIndex.java
@@ -18,25 +18,21 @@ package org.apache.ignite.internal.processors.query.calcite.exec;
import java.util.ArrayList;
import java.util.Comparator;
-import java.util.Iterator;
import java.util.List;
-import java.util.Map;
import java.util.Objects;
-import java.util.SortedMap;
-import java.util.TreeMap;
import java.util.function.Predicate;
import java.util.function.Supplier;
import org.apache.calcite.rel.RelCollation;
import org.apache.calcite.rel.type.RelDataType;
-import org.apache.ignite.IgniteCheckedException;
import org.apache.ignite.internal.cache.query.index.sorted.inline.IndexQueryContext;
import org.apache.ignite.internal.util.lang.GridCursor;
import org.apache.ignite.internal.util.typedef.F;
+import org.jetbrains.annotations.Nullable;
/**
- * Runtime sorted index based on on-heap tree.
+ * Runtime sorted index.
*/
-public class RuntimeTreeIndex<Row> implements RuntimeIndex<Row>, TreeIndex<Row> {
+public class RuntimeSortedIndex<Row> implements RuntimeIndex<Row>, TreeIndex<Row> {
/** */
protected final ExecutionContext<Row> ectx;
@@ -47,12 +43,12 @@ public class RuntimeTreeIndex<Row> implements RuntimeIndex<Row>, TreeIndex<Row>
private final RelCollation collation;
/** Rows. */
- private TreeMap<Row, List<Row>> rows;
+ private final ArrayList<Row> rows = new ArrayList<>();
/**
*
*/
- public RuntimeTreeIndex(
+ public RuntimeSortedIndex(
ExecutionContext<Row> ectx,
RelCollation collation,
Comparator<Row> comp
@@ -63,19 +59,13 @@ public class RuntimeTreeIndex<Row> implements RuntimeIndex<Row>, TreeIndex<Row>
assert Objects.nonNull(collation);
this.collation = collation;
- rows = new TreeMap<>(comp);
}
/** {@inheritDoc} */
@Override public void push(Row r) {
- List<Row> newEqRows = new ArrayList<>();
+ assert rows.isEmpty() || comp.compare(r, rows.get(rows.size() - 1)) >= 0 : "Not sorted input";
- List<Row> eqRows = rows.putIfAbsent(r, newEqRows);
-
- if (eqRows != null)
- eqRows.add(r);
- else
- newEqRows.add(r);
+ rows.add(r);
}
/** {@inheritDoc} */
@@ -90,13 +80,13 @@ public class RuntimeTreeIndex<Row> implements RuntimeIndex<Row>, TreeIndex<Row>
int firstCol = F.first(collation.getKeys());
if (ectx.rowHandler().get(firstCol, lower) != null && ectx.rowHandler().get(firstCol, upper) != null)
- return new Cursor(rows.subMap(lower, true, upper, true));
+ return new Cursor(rows, lower, upper);
else if (ectx.rowHandler().get(firstCol, lower) == null && ectx.rowHandler().get(firstCol, upper) != null)
- return new Cursor(rows.headMap(upper, true));
+ return new Cursor(rows, null, upper);
else if (ectx.rowHandler().get(firstCol, lower) != null && ectx.rowHandler().get(firstCol, upper) == null)
- return new Cursor(rows.tailMap(lower, true));
+ return new Cursor(rows, lower, null);
else
- return new Cursor(rows);
+ return new Cursor(rows, null, null);
}
/**
@@ -113,49 +103,72 @@ public class RuntimeTreeIndex<Row> implements RuntimeIndex<Row>, TreeIndex<Row>
}
/**
- *
+ * Cursor to navigate through a sorted list with duplicates.
*/
private class Cursor implements GridCursor<Row> {
- /** Sub map iterator. */
- private final Iterator<Map.Entry<Row, List<Row>>> mapIt;
+ /** List of rows. */
+ private final List<Row> rows;
- /** Iterator over rows with equal index keys. */
- private Iterator<Row> listIt;
+ /** Upper bound. */
+ private final Row upper;
- /** */
+ /** Current row. */
private Row row;
- /** */
- Cursor(SortedMap<Row, List<Row>> subMap) {
- mapIt = subMap.entrySet().iterator();
- listIt = null;
- }
-
- /** {@inheritDoc} */
- @Override public boolean next() throws IgniteCheckedException {
- if (!hasNext())
- return false;
+ /** Current index of list element. */
+ private int idx;
- next0();
+ /**
+ * @param rows List of rows.
+ * @param lower Lower bound (inclusive).
+ * @param upper Upper bound (inclusive).
+ */
+ Cursor(List<Row> rows, @Nullable Row lower, @Nullable Row upper) {
+ this.rows = rows;
+ this.upper = upper;
- return true;
+ idx = lower == null ? 0 : lowerBound(rows, lower);
}
- /** */
- private boolean hasNext() {
- return listIt != null && listIt.hasNext() || mapIt.hasNext();
+ /**
+ * Searches the lower bound (skipping duplicates) using a binary search.
+ *
+ * @param rows List of rows.
+ * @param bound Lower bound.
+ * @return Lower bound position in the list.
+ */
+ private int lowerBound(List<Row> rows, Row bound) {
+ int low = 0, high = rows.size() - 1, idx = -1;
+
+ while (low <= high) {
+ int mid = (high - low) / 2 + low;
+ int compRes = comp.compare(rows.get(mid), bound);
+
+ if (compRes > 0)
+ high = mid - 1;
+ else if (compRes == 0) {
+ idx = mid;
+ high = mid - 1;
+ }
+ else
+ low = mid + 1;
+ }
+
+ return idx == -1 ? low : idx;
}
- /** */
- private void next0() {
- if (listIt == null || !listIt.hasNext())
- listIt = mapIt.next().getValue().iterator();
+ /** {@inheritDoc} */
+ @Override public boolean next() {
+ if (idx == rows.size() || (upper != null && comp.compare(upper, rows.get(idx)) < 0))
+ return false;
- row = listIt.next();
+ row = rows.get(idx++);
+
+ return true;
}
/** {@inheritDoc} */
- @Override public Row get() throws IgniteCheckedException {
+ @Override public Row get() {
return row;
}
}
@@ -177,7 +190,7 @@ public class RuntimeTreeIndex<Row> implements RuntimeIndex<Row>, TreeIndex<Row>
Predicate<Row> filter,
Supplier<Row> lowerBound,
Supplier<Row> upperBound) {
- super(RuntimeTreeIndex.this.ectx, rowType, idx, filter, lowerBound, upperBound, null);
+ super(RuntimeSortedIndex.this.ectx, rowType, idx, filter, lowerBound, upperBound, null);
}
/** {@inheritDoc} */
diff --git a/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/exec/rel/IndexSpoolNode.java b/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/exec/rel/IndexSpoolNode.java
index 6287688..e6b44dd 100644
--- a/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/exec/rel/IndexSpoolNode.java
+++ b/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/exec/rel/IndexSpoolNode.java
@@ -27,7 +27,7 @@ import org.apache.calcite.util.ImmutableBitSet;
import org.apache.ignite.internal.processors.query.calcite.exec.ExecutionContext;
import org.apache.ignite.internal.processors.query.calcite.exec.RuntimeHashIndex;
import org.apache.ignite.internal.processors.query.calcite.exec.RuntimeIndex;
-import org.apache.ignite.internal.processors.query.calcite.exec.RuntimeTreeIndex;
+import org.apache.ignite.internal.processors.query.calcite.exec.RuntimeSortedIndex;
import org.apache.ignite.internal.util.typedef.F;
/**
@@ -167,7 +167,7 @@ public class IndexSpoolNode<Row> extends AbstractNode<Row> implements SingleNode
Supplier<Row> lowerIdxBound,
Supplier<Row> upperIdxBound
) {
- RuntimeTreeIndex<Row> idx = new RuntimeTreeIndex<>(ctx, collation, comp);
+ RuntimeSortedIndex<Row> idx = new RuntimeSortedIndex<>(ctx, collation, comp);
ScanNode<Row> scan = new ScanNode<>(
ctx,
diff --git a/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/exec/RuntimeTreeIndexTest.java b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/exec/RuntimeSortedIndexTest.java
similarity index 92%
rename from modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/exec/RuntimeTreeIndexTest.java
rename to modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/exec/RuntimeSortedIndexTest.java
index 31a1d6a..62b62f1 100644
--- a/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/exec/RuntimeTreeIndexTest.java
+++ b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/exec/RuntimeSortedIndexTest.java
@@ -25,7 +25,6 @@ import java.util.Date;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.Collectors;
-
import org.apache.calcite.rel.RelCollations;
import org.apache.calcite.rel.type.RelDataType;
import org.apache.calcite.rel.type.RelDataTypeField;
@@ -41,7 +40,7 @@ import org.junit.Test;
/**
*
*/
-public class RuntimeTreeIndexTest extends GridCommonAbstractTest {
+public class RuntimeSortedIndexTest extends GridCommonAbstractTest {
/** */
private static final int UNIQUE_GROUPS = 10_000;
@@ -74,7 +73,7 @@ public class RuntimeTreeIndexTest extends GridCommonAbstractTest {
for (Pair<RelDataType, ImmutableIntList> testIdx : testIndexes) {
for (int notUnique : NOT_UNIQUE_ROWS_IN_GROUP) {
- RuntimeTreeIndex<Object[]> idx0 = generate(testIdx.getKey(), testIdx.getValue(), notUnique);
+ RuntimeSortedIndex<Object[]> idx0 = generate(testIdx.getKey(), testIdx.getValue(), notUnique);
int rowIdLow = ThreadLocalRandom.current().nextInt(UNIQUE_GROUPS * notUnique);
int rowIdUp = rowIdLow + ThreadLocalRandom.current().nextInt(UNIQUE_GROUPS * notUnique - rowIdLow);
@@ -102,8 +101,8 @@ public class RuntimeTreeIndexTest extends GridCommonAbstractTest {
}
/** */
- private RuntimeTreeIndex<Object[]> generate(RelDataType rowType, final List<Integer> idxCols, int notUnique) {
- RuntimeTreeIndex<Object[]> idx = new RuntimeTreeIndex<>(
+ private RuntimeSortedIndex<Object[]> generate(RelDataType rowType, final List<Integer> idxCols, int notUnique) {
+ RuntimeSortedIndex<Object[]> idx = new RuntimeSortedIndex<>(
new ExecutionContext<>(
null,
PlanningContext.builder()
@@ -129,11 +128,9 @@ public class RuntimeTreeIndexTest extends GridCommonAbstractTest {
// First random fill
for (int i = 0; i < UNIQUE_GROUPS * notUnique; ++i) {
- int rowId = ThreadLocalRandom.current().nextInt(UNIQUE_GROUPS);
-
- if (!rowIds.get(rowId)) {
- idx.push(generateRow(rowId, rowType, notUnique));
- rowIds.set(rowId);
+ if (!rowIds.get(i)) {
+ idx.push(generateRow(i, rowType, notUnique));
+ rowIds.set(i);
}
}
diff --git a/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/exec/rel/TreeIndexSpoolExecutionTest.java b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/exec/rel/SortedIndexSpoolExecutionTest.java
similarity index 98%
rename from modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/exec/rel/TreeIndexSpoolExecutionTest.java
rename to modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/exec/rel/SortedIndexSpoolExecutionTest.java
index 04c2ae7..736418e 100644
--- a/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/exec/rel/TreeIndexSpoolExecutionTest.java
+++ b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/exec/rel/SortedIndexSpoolExecutionTest.java
@@ -41,7 +41,7 @@ import org.junit.Test;
*/
@SuppressWarnings("TypeMayBeWeakened")
@WithSystemProperty(key = "calcite.debug", value = "true")
-public class TreeIndexSpoolExecutionTest extends AbstractExecutionTest {
+public class SortedIndexSpoolExecutionTest extends AbstractExecutionTest {
/**
* @throws Exception If failed.
*/
diff --git a/modules/calcite/src/test/java/org/apache/ignite/testsuites/ExecutionTestSuite.java b/modules/calcite/src/test/java/org/apache/ignite/testsuites/ExecutionTestSuite.java
index 3b4ad0b..0c22e32 100644
--- a/modules/calcite/src/test/java/org/apache/ignite/testsuites/ExecutionTestSuite.java
+++ b/modules/calcite/src/test/java/org/apache/ignite/testsuites/ExecutionTestSuite.java
@@ -17,7 +17,7 @@
package org.apache.ignite.testsuites;
-import org.apache.ignite.internal.processors.query.calcite.exec.RuntimeTreeIndexTest;
+import org.apache.ignite.internal.processors.query.calcite.exec.RuntimeSortedIndexTest;
import org.apache.ignite.internal.processors.query.calcite.exec.rel.ContinuousExecutionTest;
import org.apache.ignite.internal.processors.query.calcite.exec.rel.ExecutionTest;
import org.apache.ignite.internal.processors.query.calcite.exec.rel.HashAggregateExecutionTest;
@@ -28,8 +28,8 @@ import org.apache.ignite.internal.processors.query.calcite.exec.rel.MergeJoinExe
import org.apache.ignite.internal.processors.query.calcite.exec.rel.MinusExecutionTest;
import org.apache.ignite.internal.processors.query.calcite.exec.rel.NestedLoopJoinExecutionTest;
import org.apache.ignite.internal.processors.query.calcite.exec.rel.SortAggregateExecutionTest;
+import org.apache.ignite.internal.processors.query.calcite.exec.rel.SortedIndexSpoolExecutionTest;
import org.apache.ignite.internal.processors.query.calcite.exec.rel.TableSpoolExecutionTest;
-import org.apache.ignite.internal.processors.query.calcite.exec.rel.TreeIndexSpoolExecutionTest;
import org.junit.runner.RunWith;
import org.junit.runners.Suite;
@@ -43,14 +43,14 @@ import org.junit.runners.Suite;
MergeJoinExecutionTest.class,
NestedLoopJoinExecutionTest.class,
TableSpoolExecutionTest.class,
- TreeIndexSpoolExecutionTest.class,
+ SortedIndexSpoolExecutionTest.class,
HashIndexSpoolExecutionTest.class,
HashAggregateExecutionTest.class,
HashAggregateSingleGroupExecutionTest.class,
SortAggregateExecutionTest.class,
MinusExecutionTest.class,
IntersectExecutionTest.class,
- RuntimeTreeIndexTest.class,
+ RuntimeSortedIndexTest.class,
})
public class ExecutionTestSuite {
}