This is an automated email from the ASF dual-hosted git repository.
JackieTien97 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/iotdb.git
The following commit(s) were added to refs/heads/master by this push:
new f6a844d8191 Query: Optimize schema traversal for non-leading tag IN
predicates (#18369)
f6a844d8191 is described below
commit f6a844d8191f4d7bf550c22dc5bb8a5e4c7d5b60
Author: Caideyipi <[email protected]>
AuthorDate: Tue Aug 4 17:48:20 2026 +0800
Query: Optimize schema traversal for non-leading tag IN predicates (#18369)
---
.../schemaregion/mtree/traverser/Traverser.java | 6 +
.../SchemaRegionTableDevicePerformanceTest.java | 335 ++++++++++++++++++
.../metadata/fetcher/SchemaPredicateUtilTest.java | 125 +++++++
.../iotdb/commons/path/ExtendedPartialPath.java | 34 +-
.../apache/iotdb/commons/path/fa/IPatternFA.java | 8 +
.../iotdb/commons/path/fa/nfa/SimpleNFA.java | 102 +++++-
.../schema/filter/impl/DeviceFilterUtil.java | 261 +++++++++++++-
.../commons/schema/tree/AbstractTreeVisitor.java | 79 ++++-
.../schema/filter/impl/DeviceFilterUtilTest.java | 385 +++++++++++++++++++++
9 files changed, 1314 insertions(+), 21 deletions(-)
diff --git
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/schemaengine/schemaregion/mtree/traverser/Traverser.java
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/schemaengine/schemaregion/mtree/traverser/Traverser.java
index 99486fa5475..b9968a97c76 100644
---
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/schemaengine/schemaregion/mtree/traverser/Traverser.java
+++
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/schemaengine/schemaregion/mtree/traverser/Traverser.java
@@ -253,6 +253,12 @@ public abstract class Traverser<R, N extends IMNode<N>>
extends AbstractTreeVisi
};
}
+ @Override
+ protected int getChildrenSize(final N parent) {
+ // Only the memory MTree exposes the complete child key set without an
extra traversal.
+ return parent instanceof IMemMNode ? parent.getChildren().size() :
Integer.MAX_VALUE;
+ }
+
@Override
protected Iterator<N> getChildrenIterator(N parent) throws MetadataException
{
if (parent.isAboveDatabase()) {
diff --git
a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/metadata/schemaRegion/SchemaRegionTableDevicePerformanceTest.java
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/metadata/schemaRegion/SchemaRegionTableDevicePerformanceTest.java
new file mode 100644
index 00000000000..c3ee501426c
--- /dev/null
+++
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/metadata/schemaRegion/SchemaRegionTableDevicePerformanceTest.java
@@ -0,0 +1,335 @@
+/*
+ * 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.iotdb.db.metadata.schemaRegion;
+
+import org.apache.iotdb.commons.path.ExtendedPartialPath;
+import org.apache.iotdb.commons.path.PartialPath;
+import org.apache.iotdb.commons.queryengine.plan.planner.plan.node.PlanNodeId;
+import org.apache.iotdb.commons.schema.filter.SchemaFilter;
+import org.apache.iotdb.commons.schema.filter.impl.DeviceFilterUtil;
+import org.apache.iotdb.commons.schema.filter.impl.singlechild.TagFilter;
+import org.apache.iotdb.commons.schema.filter.impl.values.PreciseFilter;
+import
org.apache.iotdb.db.queryengine.plan.relational.planner.node.schema.CreateOrUpdateTableDeviceNode;
+import org.apache.iotdb.db.schemaengine.schemaregion.ISchemaRegion;
+import
org.apache.iotdb.db.schemaengine.schemaregion.read.resp.info.IDeviceSchemaInfo;
+import
org.apache.iotdb.db.schemaengine.schemaregion.read.resp.reader.ISchemaReader;
+import org.apache.iotdb.db.utils.ManualPerformanceTestUtils;
+import org.apache.iotdb.db.utils.ManualPerformanceTestUtils.Measurement;
+import org.apache.iotdb.db.utils.ManualPerformanceTestUtils.Summary;
+
+import org.junit.Assert;
+import org.junit.Assume;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.Locale;
+
+import static org.apache.iotdb.commons.conf.IoTDBConstant.PATH_ROOT;
+
+public class SchemaRegionTableDevicePerformanceTest extends
AbstractSchemaRegionTest {
+
+ private static final String ENABLED_PROPERTY =
"iotdb.schema.non.leading.in.perf.enabled";
+ private static final String METERS_PROPERTY =
"iotdb.schema.non.leading.in.perf.meters";
+ private static final String CHILDREN_PROPERTY =
+ "iotdb.schema.non.leading.in.perf.children.per.meter";
+ private static final String VALUES_PROPERTY =
"iotdb.schema.non.leading.in.perf.values";
+ private static final String HIT_VALUES_PROPERTY =
"iotdb.schema.non.leading.in.perf.hit.values";
+ private static final String BATCH_SIZE_PROPERTY =
"iotdb.schema.non.leading.in.perf.batch.size";
+ private static final String WARMUPS_PROPERTY =
"iotdb.schema.non.leading.in.perf.warmups";
+ private static final String ITERATIONS_PROPERTY =
"iotdb.schema.non.leading.in.perf.iterations";
+ private static final String ROUNDS_PROPERTY =
"iotdb.schema.non.leading.in.perf.rounds";
+
+ private static volatile long benchmarkBlackhole;
+
+ public SchemaRegionTableDevicePerformanceTest(final SchemaRegionTestParams
testParams) {
+ super(testParams);
+ }
+
+ @Test
+ public void benchmarkNonLeadingTagInTraversal() throws Exception {
+ Assume.assumeTrue(
+ String.format(
+ "Manual performance UT. Enable with -D%s=true; tune the other
iotdb.schema.non.leading.in.perf.* properties as needed.",
+ ENABLED_PROPERTY),
+ Boolean.getBoolean(ENABLED_PROPERTY));
+ Assume.assumeTrue(
+ "The table-device schema reader is available only in MemoryMode.",
+ testParams.getTestModeName().equals("MemoryMode"));
+ Assume.assumeTrue(
+ "Current-thread CPU time and allocation metrics are required.",
+ ManualPerformanceTestUtils.enableThreadMetrics());
+
+ final int meterCount = Integer.getInteger(METERS_PROPERTY, 20_000);
+ final int childrenPerMeter = Integer.getInteger(CHILDREN_PROPERTY, 8);
+ final List<Integer> valueCounts = getPositiveIntValues(VALUES_PROPERTY,
"6");
+ final int hitValueCount = Integer.getInteger(HIT_VALUES_PROPERTY, 0);
+ final int batchSize = Integer.getInteger(BATCH_SIZE_PROPERTY, 1_000);
+ final int warmups = Integer.getInteger(WARMUPS_PROPERTY, 2);
+ final int iterations = Integer.getInteger(ITERATIONS_PROPERTY, 1);
+ final int rounds = Integer.getInteger(ROUNDS_PROPERTY, 5);
+ Assert.assertTrue(meterCount > 0);
+ Assert.assertTrue(childrenPerMeter > 0);
+ Assert.assertTrue(hitValueCount >= 0);
+ Assert.assertTrue(hitValueCount <= childrenPerMeter);
+ Assert.assertTrue(batchSize > 0);
+ Assert.assertTrue(warmups >= 0);
+ Assert.assertTrue(iterations > 0);
+ Assert.assertTrue(rounds > 0);
+
+ final ISchemaRegion schemaRegion = getSchemaRegion("db", 0);
+ final String tableName = "non_leading_in_perf";
+ createBenchmarkDevices(schemaRegion, tableName, meterCount,
childrenPerMeter, batchSize);
+
+ for (final int valueCount : valueCounts) {
+ Assert.assertTrue(hitValueCount <= valueCount);
+ runBenchmarkScenario(
+ schemaRegion,
+ tableName,
+ meterCount,
+ childrenPerMeter,
+ valueCount,
+ hitValueCount,
+ warmups,
+ iterations,
+ rounds);
+ }
+ }
+
+ private static void runBenchmarkScenario(
+ final ISchemaRegion schemaRegion,
+ final String tableName,
+ final int meterCount,
+ final int childrenPerMeter,
+ final int valueCount,
+ final int hitValueCount,
+ final int warmups,
+ final int iterations,
+ final int rounds) {
+ final List<String> cardValues = new ArrayList<>(valueCount);
+ for (int i = 0; i < valueCount; ++i) {
+ cardValues.add(i < hitValueCount ? "card_" + i : "missing_card_" + i);
+ }
+
+ final List<PartialPath> legacyPatterns =
+ createLegacyExpandedPatterns(schemaRegion, tableName, cardValues);
+ final List<PartialPath> optimizedPatterns =
+ createOptimizedPatterns(schemaRegion, tableName, cardValues);
+ Assert.assertEquals(1, optimizedPatterns.size());
+
+ final long legacyMatches = scanPatterns(schemaRegion, legacyPatterns);
+ final long optimizedMatches = scanPatterns(schemaRegion,
optimizedPatterns);
+ Assert.assertEquals(legacyMatches, optimizedMatches);
+
+ for (int i = 0; i < warmups; ++i) {
+ if ((i & 1) == 0) {
+ benchmarkBlackhole = scanPatterns(schemaRegion, legacyPatterns);
+ benchmarkBlackhole = scanPatterns(schemaRegion, optimizedPatterns);
+ } else {
+ benchmarkBlackhole = scanPatterns(schemaRegion, optimizedPatterns);
+ benchmarkBlackhole = scanPatterns(schemaRegion, legacyPatterns);
+ }
+ }
+
+ final Measurement[] legacyMeasurements = new Measurement[rounds];
+ final Measurement[] optimizedMeasurements = new Measurement[rounds];
+ for (int i = 0; i < rounds; ++i) {
+ if ((i & 1) == 0) {
+ legacyMeasurements[i] =
+ ManualPerformanceTestUtils.measure(
+ iterations, () -> benchmarkBlackhole =
scanPatterns(schemaRegion, legacyPatterns));
+ optimizedMeasurements[i] =
+ ManualPerformanceTestUtils.measure(
+ iterations,
+ () -> benchmarkBlackhole = scanPatterns(schemaRegion,
optimizedPatterns));
+ } else {
+ optimizedMeasurements[i] =
+ ManualPerformanceTestUtils.measure(
+ iterations,
+ () -> benchmarkBlackhole = scanPatterns(schemaRegion,
optimizedPatterns));
+ legacyMeasurements[i] =
+ ManualPerformanceTestUtils.measure(
+ iterations, () -> benchmarkBlackhole =
scanPatterns(schemaRegion, legacyPatterns));
+ }
+ }
+
+ printTraversalBenchmark(
+ meterCount,
+ childrenPerMeter,
+ valueCount,
+ hitValueCount,
+ legacyMatches,
+ warmups,
+ iterations,
+ rounds,
+ ManualPerformanceTestUtils.summarize(legacyMeasurements, iterations),
+ ManualPerformanceTestUtils.summarize(optimizedMeasurements,
iterations));
+ }
+
+ private static List<Integer> getPositiveIntValues(
+ final String propertyName, final String defaultValue) {
+ final String[] rawValues = System.getProperty(propertyName,
defaultValue).split(",");
+ final List<Integer> values = new ArrayList<>(rawValues.length);
+ for (final String rawValue : rawValues) {
+ final int value = Integer.parseInt(rawValue.trim());
+ Assert.assertTrue(value > 0);
+ values.add(value);
+ }
+ return values;
+ }
+
+ private static void createBenchmarkDevices(
+ final ISchemaRegion schemaRegion,
+ final String tableName,
+ final int meterCount,
+ final int childrenPerMeter,
+ final int batchSize)
+ throws Exception {
+ final List<Object[]> deviceIds = new ArrayList<>(batchSize);
+ for (int meter = 0; meter < meterCount; ++meter) {
+ for (int child = 0; child < childrenPerMeter; ++child) {
+ deviceIds.add(new Object[] {"meter_" + meter, "card_" + child});
+ if (deviceIds.size() == batchSize) {
+ createBenchmarkDeviceBatch(schemaRegion, tableName, deviceIds);
+ deviceIds.clear();
+ }
+ }
+ }
+ if (!deviceIds.isEmpty()) {
+ createBenchmarkDeviceBatch(schemaRegion, tableName, deviceIds);
+ }
+ }
+
+ private static void createBenchmarkDeviceBatch(
+ final ISchemaRegion schemaRegion, final String tableName, final
List<Object[]> deviceIds)
+ throws Exception {
+ schemaRegion.createOrUpdateTableDevice(
+ new CreateOrUpdateTableDeviceNode(
+ new PlanNodeId("non-leading-in-performance"),
+ null,
+ tableName,
+ new ArrayList<>(deviceIds),
+ Collections.emptyList(),
+ Collections.nCopies(deviceIds.size(), new Object[0])));
+ }
+
+ private static List<PartialPath> createLegacyExpandedPatterns(
+ final ISchemaRegion schemaRegion, final String tableName, final
List<String> cardValues) {
+ final List<PartialPath> patterns = new ArrayList<>(cardValues.size());
+ for (final String cardValue : cardValues) {
+ patterns.add(
+ new ExtendedPartialPath(
+ new String[] {
+ PATH_ROOT, schemaRegion.getDatabaseFullPath(), tableName, "*",
cardValue
+ },
+ false));
+ }
+ return patterns;
+ }
+
+ private static List<PartialPath> createOptimizedPatterns(
+ final ISchemaRegion schemaRegion, final String tableName, final
List<String> cardValues) {
+ final List<List<SchemaFilter>> filterBranches = new
ArrayList<>(cardValues.size());
+ for (final String cardValue : cardValues) {
+ filterBranches.add(Collections.singletonList(new TagFilter(new
PreciseFilter(cardValue), 1)));
+ }
+ return DeviceFilterUtil.convertToDevicePattern(
+ new String[] {PATH_ROOT, schemaRegion.getDatabaseFullPath(),
tableName},
+ 2,
+ filterBranches,
+ false);
+ }
+
+ private static long scanPatterns(
+ final ISchemaRegion schemaRegion, final List<PartialPath> patterns) {
+ long count = 0;
+ for (final PartialPath pattern : patterns) {
+ try (final ISchemaReader<IDeviceSchemaInfo> reader =
+ schemaRegion.getTableDeviceReader(pattern)) {
+ while (reader.hasNext()) {
+ reader.next();
+ ++count;
+ }
+ } catch (final Exception e) {
+ throw new RuntimeException(e);
+ }
+ }
+ return count;
+ }
+
+ private static void printTraversalBenchmark(
+ final int meterCount,
+ final int childrenPerMeter,
+ final int valueCount,
+ final int hitValueCount,
+ final long matchCount,
+ final int warmups,
+ final int iterations,
+ final int rounds,
+ final Summary legacy,
+ final Summary optimized) {
+ System.out.printf(
+ Locale.ROOT,
+ "Non-leading TAG IN traversal benchmark: meters=%d, children/meter=%d,
devices=%d, IN values=%d, hit values=%d, matches=%d, warmups=%d,
iterations/round=%d, rounds=%d%n",
+ meterCount,
+ childrenPerMeter,
+ (long) meterCount * childrenPerMeter,
+ valueCount,
+ hitValueCount,
+ matchCount,
+ warmups,
+ iterations,
+ rounds);
+ System.out.printf(
+ Locale.ROOT,
+ " optimized strategy: %s (IN values=%d, child keys=%d)%n",
+ valueCount < childrenPerMeter ? "precise IN lookups" : "child-key
iteration",
+ valueCount,
+ childrenPerMeter);
+ printTraversalSummary("legacy-expanded", legacy);
+ printTraversalSummary("optimized", optimized);
+ System.out.printf(
+ Locale.ROOT,
+ " change: CPU speedup=%.2fx, allocation reduction=%.1f%%, peak-heap
reduction=%.1f%%%n",
+ ratio(legacy.getCpuNanosPerOperation(),
optimized.getCpuNanosPerOperation()),
+ reduction(
+ legacy.getAllocatedBytesPerOperation(),
optimized.getAllocatedBytesPerOperation()),
+ reduction(legacy.getPeakHeapDeltaBytes(),
optimized.getPeakHeapDeltaBytes()));
+ }
+
+ private static void printTraversalSummary(final String label, final Summary
summary) {
+ System.out.printf(
+ Locale.ROOT,
+ " %-15s CPU=%.3f ms/op, allocated=%.1f bytes/op, peak heap delta=%.3f
MiB%n",
+ label,
+ summary.getCpuNanosPerOperation() / 1_000_000.0,
+ summary.getAllocatedBytesPerOperation(),
+ summary.getPeakHeapDeltaBytes() / 1024.0 / 1024.0);
+ }
+
+ private static double ratio(final double baseline, final double optimized) {
+ return optimized == 0 ? Double.POSITIVE_INFINITY : baseline / optimized;
+ }
+
+ private static double reduction(final double baseline, final double
optimized) {
+ return baseline == 0 ? 0 : (baseline - optimized) * 100.0 / baseline;
+ }
+}
diff --git
a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/metadata/fetcher/SchemaPredicateUtilTest.java
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/metadata/fetcher/SchemaPredicateUtilTest.java
new file mode 100644
index 00000000000..10d21bfd2c8
--- /dev/null
+++
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/metadata/fetcher/SchemaPredicateUtilTest.java
@@ -0,0 +1,125 @@
+/*
+ * 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.iotdb.db.queryengine.plan.relational.metadata.fetcher;
+
+import org.apache.iotdb.commons.path.PartialPath;
+import
org.apache.iotdb.commons.queryengine.plan.relational.sql.ast.ComparisonExpression;
+import org.apache.iotdb.commons.queryengine.plan.relational.sql.ast.Expression;
+import
org.apache.iotdb.commons.queryengine.plan.relational.sql.ast.InListExpression;
+import
org.apache.iotdb.commons.queryengine.plan.relational.sql.ast.InPredicate;
+import
org.apache.iotdb.commons.queryengine.plan.relational.sql.ast.LogicalExpression;
+import
org.apache.iotdb.commons.queryengine.plan.relational.sql.ast.StringLiteral;
+import
org.apache.iotdb.commons.queryengine.plan.relational.sql.ast.SymbolReference;
+import org.apache.iotdb.commons.schema.filter.SchemaFilter;
+import org.apache.iotdb.commons.schema.filter.impl.DeviceFilterUtil;
+import org.apache.iotdb.commons.schema.table.TsTable;
+import org.apache.iotdb.commons.schema.table.column.TagColumnSchema;
+
+import org.apache.tsfile.enums.TSDataType;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+import java.util.Map;
+import java.util.concurrent.atomic.AtomicBoolean;
+
+public class SchemaPredicateUtilTest {
+
+ private static final String[] PREFIX = new String[] {"root", "db", "table"};
+
+ @Test
+ public void testCompactExpandedNonLeadingInAndOr() {
+ final TsTable table = createTable();
+
+ final AtomicBoolean inMayContainDuplicate = new AtomicBoolean(false);
+ final List<PartialPath> inPatterns =
+ convertToDevicePatterns(
+ table,
+ new InPredicate(
+ new SymbolReference("cardno"),
+ new InListExpression(
+ Arrays.asList(new StringLiteral("card1"), new
StringLiteral("card2")))),
+ inMayContainDuplicate);
+ Assert.assertFalse(inMayContainDuplicate.get());
+ Assert.assertEquals(1, inPatterns.size());
+
+ final AtomicBoolean orMayContainDuplicate = new AtomicBoolean(false);
+ final List<PartialPath> orPatterns =
+ convertToDevicePatterns(
+ table,
+ new LogicalExpression(
+ LogicalExpression.Operator.OR,
+ Arrays.asList(equal("cardno", "card1"), equal("cardno",
"card2"))),
+ orMayContainDuplicate);
+ Assert.assertTrue(orMayContainDuplicate.get());
+ Assert.assertEquals(1, orPatterns.size());
+ }
+
+ @Test
+ public void testKeepExpandedLeadingIn() {
+ final TsTable table = createTable();
+ final List<PartialPath> patterns =
+ convertToDevicePatterns(
+ table,
+ new InPredicate(
+ new SymbolReference("meterinfoid"),
+ new InListExpression(
+ Arrays.asList(new StringLiteral("meter1"), new
StringLiteral("meter2")))),
+ new AtomicBoolean(false));
+
+ Assert.assertEquals(2, patterns.size());
+ Assert.assertEquals("root.db.table.meter1.*",
patterns.get(0).getFullPath());
+ Assert.assertEquals("root.db.table.meter2.*",
patterns.get(1).getFullPath());
+ }
+
+ private static List<PartialPath> convertToDevicePatterns(
+ final TsTable table,
+ final Expression expression,
+ final AtomicBoolean mayContainDuplicateDevice) {
+ final List<Map<Integer, List<SchemaFilter>>> filterMaps =
+ SchemaPredicateUtil.convertTagPredicateToOrConcatList(
+ Collections.singletonList(expression), table,
mayContainDuplicateDevice);
+ Assert.assertEquals(2, filterMaps.size());
+
+ final List<List<SchemaFilter>> filterBranches = new
ArrayList<>(filterMaps.size());
+ for (final Map<Integer, List<SchemaFilter>> filterMap : filterMaps) {
+ final List<SchemaFilter> branch = new ArrayList<>();
+ filterMap.values().forEach(branch::addAll);
+ filterBranches.add(branch);
+ }
+ return DeviceFilterUtil.convertToDevicePattern(
+ PREFIX, table.getTagNum(), filterBranches, false);
+ }
+
+ private static ComparisonExpression equal(final String column, final String
value) {
+ return new ComparisonExpression(
+ ComparisonExpression.Operator.EQUAL, new SymbolReference(column), new
StringLiteral(value));
+ }
+
+ private static TsTable createTable() {
+ final TsTable table = new TsTable("table");
+ table.addColumnSchema(new TagColumnSchema("meterinfoid",
TSDataType.STRING));
+ table.addColumnSchema(new TagColumnSchema("cardno", TSDataType.STRING));
+ return table;
+ }
+}
diff --git
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/ExtendedPartialPath.java
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/ExtendedPartialPath.java
index 7976f44d8ef..0cf68f6918c 100644
---
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/ExtendedPartialPath.java
+++
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/ExtendedPartialPath.java
@@ -21,12 +21,15 @@ package org.apache.iotdb.commons.path;
import java.util.ArrayList;
import java.util.HashMap;
+import java.util.HashSet;
import java.util.List;
import java.util.Map;
+import java.util.Set;
import java.util.function.Function;
public class ExtendedPartialPath extends PartialPath {
private final Map<Integer, List<Function<String, Boolean>>> matchFunctions =
new HashMap<>();
+ private final Map<Integer, Set<String>> multiExactMatchNodes = new
HashMap<>();
private final boolean isRestrict;
public ExtendedPartialPath(final String[] nodes, final boolean isRestrict) {
@@ -39,6 +42,10 @@ public class ExtendedPartialPath extends PartialPath {
}
public boolean match(final int index, final String value) {
+ if (multiExactMatchNodes.containsKey(index)
+ && !multiExactMatchNodes.get(index).contains(value)) {
+ return false;
+ }
if (!matchFunctions.containsKey(index)) {
return true;
}
@@ -49,8 +56,31 @@ public class ExtendedPartialPath extends PartialPath {
matchFunctions.computeIfAbsent(index, k -> new
ArrayList<>()).add(matchFunction);
}
+ public void addMultiExactMatch(final int index, final Set<String> values) {
+ multiExactMatchNodes.compute(
+ index,
+ (key, existingValues) -> {
+ if (existingValues == null) {
+ final Set<String> copiedValues = new HashSet<>(values);
+ copiedValues.remove(null);
+ return copiedValues;
+ }
+ existingValues.retainAll(values);
+ existingValues.remove(null);
+ return existingValues;
+ });
+ }
+
+ public boolean hasMultiExactMatch(final int index) {
+ return multiExactMatchNodes.containsKey(index);
+ }
+
+ public Set<String> getMultiExactMatch(final int index) {
+ return multiExactMatchNodes.get(index);
+ }
+
public boolean isNormalPath() {
- return matchFunctions.isEmpty();
+ return matchFunctions.isEmpty() && multiExactMatchNodes.isEmpty();
}
@Override
@@ -60,6 +90,8 @@ public class ExtendedPartialPath extends PartialPath {
+ getFullPath()
+ ", matchFunctions="
+ matchFunctions
+ + ", multiExactMatchNodes="
+ + multiExactMatchNodes
+ ", isRestrict="
+ isRestrict
+ '}';
diff --git
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/IPatternFA.java
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/IPatternFA.java
index 30249cdf694..ffacb6106b2 100644
---
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/IPatternFA.java
+++
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/IPatternFA.java
@@ -58,6 +58,14 @@ public interface IPatternFA {
*/
int getFuzzyMatchTransitionSize(IFAState state);
+ /**
+ * @param state the source state of the transitions
+ * @return whether the precise transitions from this state represent a
multi-exact match
+ */
+ default boolean hasMultiExactMatchTransitions(IFAState state) {
+ return false;
+ }
+
/**
* @param sourceState source state
* @param transition transition that the source state has
diff --git
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/nfa/SimpleNFA.java
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/nfa/SimpleNFA.java
index 2a0304394ca..e7390801461 100644
---
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/nfa/SimpleNFA.java
+++
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/nfa/SimpleNFA.java
@@ -27,10 +27,12 @@ import org.apache.iotdb.commons.path.fa.IFATransition;
import org.apache.iotdb.commons.path.fa.IPatternFA;
import java.util.Collections;
+import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Objects;
+import java.util.Set;
import java.util.function.Function;
import java.util.regex.Pattern;
@@ -115,8 +117,16 @@ public class SimpleNFA implements IPatternFA {
return getNextNode((SinglePathPatternNode)
state).getPreNodeFuzzyMatchTransitionSize();
}
+ @Override
+ public boolean hasMultiExactMatchTransitions(final IFAState state) {
+ return getNextNode((SinglePathPatternNode) state) instanceof
MultiExactMatchNode;
+ }
+
@Override
public IFAState getNextState(IFAState sourceState, IFATransition transition)
{
+ if (transition instanceof MultiExactTransition) {
+ return ((MultiExactTransition) transition).targetNode;
+ }
return (SinglePathPatternNode) transition;
}
@@ -154,13 +164,21 @@ public class SimpleNFA implements IPatternFA {
} else if (rawNodes[nextIndex].equals(MULTI_LEVEL_PATH_WILDCARD)) {
patternNodes[nextIndex] = new MultiLevelWildcardMatchNode(nextIndex);
} else if (rawNodes[nextIndex].equals(ONE_LEVEL_PATH_WILDCARD)) {
+ final ExtendedPartialPath extendedPath =
+ pathPattern instanceof ExtendedPartialPath ? (ExtendedPartialPath)
pathPattern : null;
patternNodes[nextIndex] =
- new OneLevelWildcardMatchNode(
- nextIndex,
- currentNode.getTracebackNode(),
- pathPattern instanceof ExtendedPartialPath
- ? event -> ((ExtendedPartialPath)
pathPattern).match(nextIndex, event)
- : event -> true);
+ extendedPath != null && extendedPath.hasMultiExactMatch(nextIndex)
+ ? new MultiExactMatchNode(
+ nextIndex,
+ currentNode.getTracebackNode(),
+ extendedPath.getMultiExactMatch(nextIndex),
+ event -> extendedPath.match(nextIndex, event))
+ : new OneLevelWildcardMatchNode(
+ nextIndex,
+ currentNode.getTracebackNode(),
+ extendedPath != null
+ ? event -> extendedPath.match(nextIndex, event)
+ : event -> true);
} else if (PathPatternUtil.hasWildcard(rawNodes[nextIndex])) {
patternNodes[nextIndex] = new RegexMatchNode(nextIndex,
currentNode.getTracebackNode());
} else {
@@ -422,6 +440,78 @@ public class SimpleNFA implements IPatternFA {
}
}
+ /** The patternNode of a group of specified names. */
+ private class MultiExactMatchNode extends SinglePathPatternNode {
+
+ private final Map<String, IFATransition> preciseTransitions = new
HashMap<>();
+
+ private MultiExactMatchNode(
+ final int patternIndex,
+ final SinglePathPatternNode tracebackNode,
+ final Set<String> values,
+ final Function<String, Boolean> matchFunction) {
+ super(patternIndex, tracebackNode);
+ for (final String value : values) {
+ if (matchFunction.apply(value)) {
+ preciseTransitions.put(value, new MultiExactTransition(value, this));
+ }
+ }
+ }
+
+ @Override
+ public boolean isMatch(final String event) {
+ return preciseTransitions.containsKey(event);
+ }
+
+ @Override
+ protected Map<String, IFATransition> getPreNodePreciseMatchTransition() {
+ return preciseTransitions;
+ }
+
+ @Override
+ protected Iterator<IFATransition>
getPreNodePreciseMatchTransitionIterator() {
+ return preciseTransitions.values().iterator();
+ }
+
+ @Override
+ protected Iterator<IFATransition> getPreNodeFuzzyMatchTransitionIterator()
{
+ return tracebackNode == null
+ ? Collections.emptyIterator()
+ : new SingletonIterator<>(tracebackNode);
+ }
+
+ @Override
+ protected int getPreNodeFuzzyMatchTransitionSize() {
+ return tracebackNode == null ? 0 : 1;
+ }
+ }
+
+ private class MultiExactTransition implements IFATransition {
+
+ private final String acceptEvent;
+ private final MultiExactMatchNode targetNode;
+
+ private MultiExactTransition(final String acceptEvent, final
MultiExactMatchNode targetNode) {
+ this.acceptEvent = acceptEvent;
+ this.targetNode = targetNode;
+ }
+
+ @Override
+ public String getAcceptEvent() {
+ return acceptEvent;
+ }
+
+ @Override
+ public boolean isMatch(final String event) {
+ return Objects.equals(acceptEvent, event);
+ }
+
+ @Override
+ public int getIndex() {
+ return targetNode.getIndex();
+ }
+ }
+
/** The patternNode of the rawNode contains *, like d*. */
private class RegexMatchNode extends SinglePathPatternNode {
diff --git
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/schema/filter/impl/DeviceFilterUtil.java
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/schema/filter/impl/DeviceFilterUtil.java
index 1e49eb915d5..9786f2161cd 100644
---
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/schema/filter/impl/DeviceFilterUtil.java
+++
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/schema/filter/impl/DeviceFilterUtil.java
@@ -25,11 +25,19 @@ import org.apache.iotdb.commons.path.PartialPath;
import org.apache.iotdb.commons.schema.filter.SchemaFilter;
import org.apache.iotdb.commons.schema.filter.SchemaFilterType;
import org.apache.iotdb.commons.schema.filter.impl.singlechild.TagFilter;
+import org.apache.iotdb.commons.schema.filter.impl.values.InFilter;
import org.apache.iotdb.commons.schema.filter.impl.values.PreciseFilter;
import java.util.ArrayList;
import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.Set;
+import java.util.TreeMap;
import static
org.apache.iotdb.commons.conf.IoTDBConstant.ONE_LEVEL_PATH_WILDCARD;
@@ -49,7 +57,8 @@ public class DeviceFilterUtil {
final boolean isRestrict) {
final List<PartialPath> pathList = new ArrayList<>();
final int length = tagColumnNum + prefix.length;
- for (final List<SchemaFilter> tagFilterList : tagDeterminedFilterList) {
+ for (final List<SchemaFilter> tagFilterList :
+ compactNonLeadingPreciseFilters(tagColumnNum,
tagDeterminedFilterList)) {
final String[] nodes = new String[length];
Arrays.fill(nodes, ONE_LEVEL_PATH_WILDCARD);
System.arraycopy(prefix, 0, nodes, 0, prefix.length);
@@ -62,6 +71,8 @@ public class DeviceFilterUtil {
// If there is a precise filter, other filters on the same id are
processed and thus
// not exist here
nodes[index] = ((PreciseFilter) childFilter).getValue();
+ } else if
(childFilter.getSchemaFilterType().equals(SchemaFilterType.IN)) {
+ partialPath.addMultiExactMatch(index, ((InFilter)
childFilter).getValues());
} else {
partialPath.addMatchFunction(
index,
@@ -78,4 +89,252 @@ public class DeviceFilterUtil {
}
return pathList;
}
+
+ /**
+ * IN predicates and OR-connected equal predicates are expanded into precise
filter branches so
+ * that complete device IDs can use the device cache. If a precise filter is
behind an unfixed tag
+ * level, however, every expanded branch traverses the same wildcard
subtree. Compact branches
+ * that differ only at such a tag into one IN filter to avoid repeated
schema traversals.
+ */
+ private static List<List<SchemaFilter>> compactNonLeadingPreciseFilters(
+ final int tagColumnNum, final List<List<SchemaFilter>>
tagDeterminedFilterList) {
+ if (tagColumnNum <= 1 || tagDeterminedFilterList.size() <= 1) {
+ return tagDeterminedFilterList;
+ }
+ if (areAllBranchesFullyPrecise(tagColumnNum, tagDeterminedFilterList)) {
+ return tagDeterminedFilterList;
+ }
+
+ List<FilterBranch> filterBranches = new
ArrayList<>(tagDeterminedFilterList.size());
+ final Map<FilterSequenceKey, Integer> suffixSequenceIds = new HashMap<>();
+ for (final List<SchemaFilter> tagFilterList : tagDeterminedFilterList) {
+ final Map<Integer, List<SchemaFilter>> filterMap = new TreeMap<>();
+ for (final SchemaFilter schemaFilter : tagFilterList) {
+ if (!schemaFilter.getSchemaFilterType().equals(SchemaFilterType.TAG)) {
+ throw new IllegalStateException(
+ SchemaMessages.INPUT_SINGLE_FILTER_MUST_BE_DEVICE_ID_FILTER);
+ }
+ final int tagIndex = ((TagFilter) schemaFilter).getIndex();
+ filterMap.computeIfAbsent(tagIndex, key -> new
ArrayList<>()).add(schemaFilter);
+ }
+ filterBranches.add(new FilterBranch(filterMap, tagColumnNum,
suffixSequenceIds));
+ }
+
+ final Map<FilterSequenceKey, Integer> prefixSequenceIds = new HashMap<>();
+ for (final FilterBranch filterBranch : filterBranches) {
+ filterBranch.prefixSequenceId =
+ getSequenceId(prefixSequenceIds, 0, filterBranch.filterMap.get(0));
+ }
+ // A branch group is identified by everything before and after the current
tag. Canonical
+ // sequence IDs make both the eligibility check and the group-key
construction O(1) per branch
+ // at each tag, while prefix IDs are updated after earlier precise filters
are compacted to IN.
+ for (int tagIndex = 1; tagIndex < tagColumnNum; tagIndex++) {
+ filterBranches = compactPreciseFiltersAtIndex(filterBranches, tagIndex);
+ for (final FilterBranch filterBranch : filterBranches) {
+ final List<SchemaFilter> currentFilters =
filterBranch.filterMap.get(tagIndex);
+ filterBranch.prefixSequenceId =
+ getSequenceId(prefixSequenceIds, filterBranch.prefixSequenceId,
currentFilters);
+ filterBranch.hasNonPrecisePrefix |=
!isSinglePreciseTagFilter(currentFilters);
+ }
+ }
+
+ final List<List<SchemaFilter>> result = new
ArrayList<>(filterBranches.size());
+ for (final FilterBranch filterBranch : filterBranches) {
+ final List<SchemaFilter> filterList = new ArrayList<>();
+ filterBranch.filterMap.values().forEach(filterList::addAll);
+ result.add(filterList);
+ }
+ return result;
+ }
+
+ private static boolean areAllBranchesFullyPrecise(
+ final int tagColumnNum, final List<List<SchemaFilter>>
tagDeterminedFilterList) {
+ final int[] visitedTagIndexes = new int[tagColumnNum];
+ int branchId = 1;
+ for (final List<SchemaFilter> tagFilterList : tagDeterminedFilterList) {
+ if (tagFilterList.size() != tagColumnNum) {
+ return false;
+ }
+ for (final SchemaFilter schemaFilter : tagFilterList) {
+ if (!isPreciseTagFilter(schemaFilter)) {
+ return false;
+ }
+ final int tagIndex = ((TagFilter) schemaFilter).getIndex();
+ if (tagIndex < 0 || tagIndex >= tagColumnNum ||
visitedTagIndexes[tagIndex] == branchId) {
+ return false;
+ }
+ visitedTagIndexes[tagIndex] = branchId;
+ }
+ branchId++;
+ }
+ return true;
+ }
+
+ private static List<FilterBranch> compactPreciseFiltersAtIndex(
+ final List<FilterBranch> filterBranches, final int tagIndex) {
+ final Map<FilterBranchKey, List<FilterBranch>> filterGroupMap = new
HashMap<>();
+ for (final FilterBranch filterBranch : filterBranches) {
+ if (!filterBranch.hasNonPrecisePrefix
+ || !isSinglePreciseTagFilter(filterBranch.filterMap.get(tagIndex))) {
+ continue;
+ }
+ final FilterBranchKey filterBranchKey =
+ new FilterBranchKey(
+ filterBranch.prefixSequenceId,
filterBranch.suffixSequenceIds[tagIndex]);
+ filterGroupMap.computeIfAbsent(filterBranchKey, key -> new
ArrayList<>()).add(filterBranch);
+ }
+
+ if (filterGroupMap.isEmpty()) {
+ return filterBranches;
+ }
+
+ int removedBranchCount = 0;
+ for (final List<FilterBranch> filterGroup : filterGroupMap.values()) {
+ if (filterGroup.size() <= 1) {
+ continue;
+ }
+
+ final Set<String> preciseValues = new HashSet<>();
+ for (final FilterBranch filterBranch : filterGroup) {
+ preciseValues.add(
+ ((PreciseFilter) ((TagFilter)
filterBranch.filterMap.get(tagIndex).get(0)).getChild())
+ .getValue());
+ }
+ if (preciseValues.contains(null)) {
+ continue;
+ }
+
+ if (preciseValues.size() > 1) {
+ filterGroup
+ .get(0)
+ .filterMap
+ .put(
+ tagIndex,
+ Collections.singletonList(new TagFilter(new
InFilter(preciseValues), tagIndex)));
+ }
+ for (int i = 1; i < filterGroup.size(); i++) {
+ filterGroup.get(i).removed = true;
+ removedBranchCount++;
+ }
+ }
+
+ if (removedBranchCount == 0) {
+ return filterBranches;
+ }
+
+ final List<FilterBranch> result = new ArrayList<>(filterBranches.size() -
removedBranchCount);
+ for (final FilterBranch filterBranch : filterBranches) {
+ if (!filterBranch.removed) {
+ result.add(filterBranch);
+ }
+ }
+ return result;
+ }
+
+ private static int getSequenceId(
+ final Map<FilterSequenceKey, Integer> sequenceIds,
+ final int previousSequenceId,
+ final List<SchemaFilter> filters) {
+ final FilterSequenceKey key = new FilterSequenceKey(previousSequenceId,
filters);
+ final Integer existingSequenceId = sequenceIds.get(key);
+ if (existingSequenceId != null) {
+ return existingSequenceId;
+ }
+ final int newSequenceId = sequenceIds.size() + 1;
+ sequenceIds.put(key, newSequenceId);
+ return newSequenceId;
+ }
+
+ private static boolean isSinglePreciseTagFilter(final List<SchemaFilter>
filters) {
+ return filters != null && filters.size() == 1 &&
isPreciseTagFilter(filters.get(0));
+ }
+
+ private static boolean isPreciseTagFilter(final SchemaFilter schemaFilter) {
+ return schemaFilter.getSchemaFilterType().equals(SchemaFilterType.TAG)
+ && ((TagFilter) schemaFilter)
+ .getChild()
+ .getSchemaFilterType()
+ .equals(SchemaFilterType.PRECISE);
+ }
+
+ private static final class FilterBranch {
+
+ private final Map<Integer, List<SchemaFilter>> filterMap;
+ private final int[] suffixSequenceIds;
+ private int prefixSequenceId;
+ private boolean hasNonPrecisePrefix;
+ private boolean removed;
+
+ private FilterBranch(
+ final Map<Integer, List<SchemaFilter>> filterMap,
+ final int tagColumnNum,
+ final Map<FilterSequenceKey, Integer> suffixSequenceIdMap) {
+ this.filterMap = filterMap;
+ this.suffixSequenceIds = new int[tagColumnNum];
+ this.hasNonPrecisePrefix = !isSinglePreciseTagFilter(filterMap.get(0));
+
+ int suffixSequenceId = 0;
+ for (int tagIndex = tagColumnNum - 1; tagIndex >= 0; tagIndex--) {
+ suffixSequenceIds[tagIndex] = suffixSequenceId;
+ suffixSequenceId =
+ getSequenceId(suffixSequenceIdMap, suffixSequenceId,
filterMap.get(tagIndex));
+ }
+ }
+ }
+
+ private static final class FilterSequenceKey {
+
+ private final int previousSequenceId;
+ private final List<SchemaFilter> filters;
+
+ private FilterSequenceKey(final int previousSequenceId, final
List<SchemaFilter> filters) {
+ this.previousSequenceId = previousSequenceId;
+ this.filters = filters;
+ }
+
+ @Override
+ public boolean equals(final Object o) {
+ if (this == o) {
+ return true;
+ }
+ if (!(o instanceof FilterSequenceKey)) {
+ return false;
+ }
+ final FilterSequenceKey that = (FilterSequenceKey) o;
+ return previousSequenceId == that.previousSequenceId &&
Objects.equals(filters, that.filters);
+ }
+
+ @Override
+ public int hashCode() {
+ return 31 * previousSequenceId + Objects.hashCode(filters);
+ }
+ }
+
+ private static final class FilterBranchKey {
+
+ private final int prefixSequenceId;
+ private final int suffixSequenceId;
+
+ private FilterBranchKey(final int prefixSequenceId, final int
suffixSequenceId) {
+ this.prefixSequenceId = prefixSequenceId;
+ this.suffixSequenceId = suffixSequenceId;
+ }
+
+ @Override
+ public boolean equals(final Object o) {
+ if (this == o) {
+ return true;
+ }
+ if (!(o instanceof FilterBranchKey)) {
+ return false;
+ }
+ final FilterBranchKey that = (FilterBranchKey) o;
+ return prefixSequenceId == that.prefixSequenceId && suffixSequenceId ==
that.suffixSequenceId;
+ }
+
+ @Override
+ public int hashCode() {
+ return 31 * prefixSequenceId + suffixSequenceId;
+ }
+ }
}
diff --git
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/schema/tree/AbstractTreeVisitor.java
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/schema/tree/AbstractTreeVisitor.java
index 512270c379a..04f59402891 100644
---
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/schema/tree/AbstractTreeVisitor.java
+++
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/schema/tree/AbstractTreeVisitor.java
@@ -402,6 +402,14 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
protected abstract Iterator<N> getChildrenIterator(N parent,
Iterator<String> childrenName)
throws Exception;
+ /**
+ * Get the number of child keys that can be iterated directly. Return {@link
Integer#MAX_VALUE}
+ * when the number is unavailable, so precise transitions are preferred.
+ */
+ protected int getChildrenSize(final N parent) {
+ return Integer.MAX_VALUE;
+ }
+
/**
* Get current children iterator generated by {@link
AbstractTreeVisitor#getChildrenIterator}
*
@@ -551,40 +559,85 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
// the child can be got directly with the precise value of transition,
there's no traceback
private class PreciseMatchChildrenIterator extends AbstractChildrenIterator {
private final IFAState sourceState;
+ private final Map<String, IFATransition> preciseMatchTransitionMap;
private final Iterator<IFATransition> transitionIterator;
+ private final boolean iterateChildren;
+ private Iterator<N> childrenIterator;
private PreciseMatchChildrenIterator(N parent, IStateMatchInfo
stateMatchInfo) {
super(parent, stateMatchInfo.getScopeMatchedState());
this.sourceState = stateMatchInfo.getOneMatchedState();
- transitionIterator =
patternFA.getPreciseMatchTransitionIterator(sourceState);
+ this.preciseMatchTransitionMap =
patternFA.getPreciseMatchTransition(sourceState);
+ this.transitionIterator = preciseMatchTransitionMap.values().iterator();
+ // Candidate counts are a rough cost estimate. Iterate the smaller side
so this remains
+ // adaptive without relying on unstable wall-clock thresholds. Prefer
child iteration on a
+ // tie because it avoids a direct child lookup for every transition.
+ this.iterateChildren =
+ patternFA.hasMultiExactMatchTransitions(sourceState)
+ && getChildrenSize(parent) <= preciseMatchTransitionMap.size();
}
@Override
protected void getNext() throws Exception {
+ if (iterateChildren) {
+ if (childrenIterator == null) {
+ childrenIterator = initChildrenIterator();
+ }
+ while (childrenIterator.hasNext()) {
+ final N child = childrenIterator.next();
+ IFATransition transition =
preciseMatchTransitionMap.get(child.getName());
+ if (transition == null && child.getAlias() != null) {
+ transition = preciseMatchTransitionMap.get(child.getAlias());
+ }
+ if (transition == null) {
+ releaseNode(child);
+ continue;
+ }
+ if (trySaveResult(child, transition)) {
+ return;
+ }
+ }
+ return;
+ }
+
IFATransition transition;
while (transitionIterator.hasNext()) {
transition = transitionIterator.next();
- N child = getChild(parent, transition.getAcceptEvent());
+ final N child = getChild(parent, transition.getAcceptEvent());
if (child == null) {
continue;
}
- IFAState nextScopeState =
- allScope ? null : getNextMatchedScopeState(currentScopeState,
child);
- if (!allScope && nextScopeState == null) {
- releaseNode(child);
- continue;
+ if (trySaveResult(child, transition)) {
+ return;
}
- saveResult(
- child,
- new StateSingleMatchInfo(
- patternFA, patternFA.getNextState(sourceState, transition),
nextScopeState));
- return;
}
}
+ private boolean trySaveResult(final N child, final IFATransition
transition) {
+ final IFAState nextScopeState =
+ allScope ? null : getNextMatchedScopeState(currentScopeState, child);
+ if (!allScope && nextScopeState == null) {
+ releaseNode(child);
+ return false;
+ }
+ saveResult(
+ child,
+ new StateSingleMatchInfo(
+ patternFA, patternFA.getNextState(sourceState, transition),
nextScopeState));
+ return true;
+ }
+
@Override
public Iterator<N> getIterator() {
- return null;
+ return childrenIterator;
+ }
+
+ @Override
+ protected void close() {
+ super.close();
+ if (childrenIterator != null) {
+ releaseNodeIterator(childrenIterator);
+ }
}
}
diff --git
a/iotdb-core/node-commons/src/test/java/org/apache/iotdb/commons/schema/filter/impl/DeviceFilterUtilTest.java
b/iotdb-core/node-commons/src/test/java/org/apache/iotdb/commons/schema/filter/impl/DeviceFilterUtilTest.java
new file mode 100644
index 00000000000..b74d7f007fd
--- /dev/null
+++
b/iotdb-core/node-commons/src/test/java/org/apache/iotdb/commons/schema/filter/impl/DeviceFilterUtilTest.java
@@ -0,0 +1,385 @@
+/*
+ * 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.iotdb.commons.schema.filter.impl;
+
+import org.apache.iotdb.commons.path.ExtendedPartialPath;
+import org.apache.iotdb.commons.path.PartialPath;
+import org.apache.iotdb.commons.path.fa.IFAState;
+import org.apache.iotdb.commons.path.fa.IFATransition;
+import org.apache.iotdb.commons.path.fa.IPatternFA;
+import org.apache.iotdb.commons.schema.filter.SchemaFilter;
+import org.apache.iotdb.commons.schema.filter.impl.singlechild.NotFilter;
+import org.apache.iotdb.commons.schema.filter.impl.singlechild.TagFilter;
+import org.apache.iotdb.commons.schema.filter.impl.values.InFilter;
+import org.apache.iotdb.commons.schema.filter.impl.values.PreciseFilter;
+import org.apache.iotdb.commons.schema.tree.AbstractTreeVisitor;
+import org.apache.iotdb.commons.schema.tree.ITreeNode;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+public class DeviceFilterUtilTest {
+
+ private static final String[] PREFIX = new String[] {"root", "db", "table"};
+ private static final int TAG_COLUMN_NUM = 3;
+
+ @Test
+ public void testCompactExpandedInOrOnNonLeadingTag() {
+ final List<PartialPath> patterns =
+ convert(branch(precise(1, "card1")), branch(precise(1, "card2")));
+
+ Assert.assertEquals(1, patterns.size());
+ final ExtendedPartialPath pattern = (ExtendedPartialPath) patterns.get(0);
+ Assert.assertEquals("root.db.table.*.*.*", pattern.getFullPath());
+ Assert.assertTrue(pattern.match(PREFIX.length + 1, "card1"));
+ Assert.assertTrue(pattern.match(PREFIX.length + 1, "card2"));
+ Assert.assertFalse(pattern.match(PREFIX.length + 1, "card3"));
+ assertPreciseTransitionsAfterFirstTag(pattern, "card1", "card2");
+ }
+
+ @Test
+ public void testKeepLeadingTagBranchesSeparated() {
+ final List<PartialPath> patterns =
+ convert(branch(precise(0, "meter1")), branch(precise(0, "meter2")));
+
+ Assert.assertEquals(2, patterns.size());
+ Assert.assertEquals("root.db.table.meter1.*.*",
patterns.get(0).getFullPath());
+ Assert.assertEquals("root.db.table.meter2.*.*",
patterns.get(1).getFullPath());
+ }
+
+ @Test
+ public void testKeepBranchesSeparatedWithCompletePrefix() {
+ final List<PartialPath> patterns =
+ convert(
+ branch(precise(0, "meter1"), precise(1, "card1")),
+ branch(precise(0, "meter1"), precise(1, "card2")));
+
+ Assert.assertEquals(2, patterns.size());
+ Assert.assertEquals("root.db.table.meter1.card1.*",
patterns.get(0).getFullPath());
+ Assert.assertEquals("root.db.table.meter1.card2.*",
patterns.get(1).getFullPath());
+ }
+
+ @Test
+ public void testKeepFullyPreciseBranchesSeparatedWithManyTags() {
+ final int tagColumnNum = 32;
+ final List<SchemaFilter> firstBranch = new ArrayList<>(tagColumnNum);
+ final List<SchemaFilter> secondBranch = new ArrayList<>(tagColumnNum);
+ for (int i = 0; i < tagColumnNum; i++) {
+ firstBranch.add(precise(i, "value" + i));
+ secondBranch.add(precise(i, i == tagColumnNum - 1 ? "other" : "value" +
i));
+ }
+
+ final List<PartialPath> patterns = convert(tagColumnNum, firstBranch,
secondBranch);
+
+ Assert.assertEquals(2, patterns.size());
+ Assert.assertEquals("value31", patterns.get(0).getNodes()[PREFIX.length +
31]);
+ Assert.assertEquals("other", patterns.get(1).getNodes()[PREFIX.length +
31]);
+ }
+
+ @Test
+ public void testCompactPreciseBranchesAfterLongNonPrecisePrefix() {
+ final int tagColumnNum = 32;
+ final List<PartialPath> patterns =
+ convert(
+ tagColumnNum,
+ branch(precise(16, "common"), precise(31, "last1")),
+ branch(precise(16, "common"), precise(31, "last2")));
+
+ Assert.assertEquals(1, patterns.size());
+ final ExtendedPartialPath pattern = (ExtendedPartialPath) patterns.get(0);
+ Assert.assertTrue(pattern.match(PREFIX.length + 16, "common"));
+ Assert.assertTrue(pattern.match(PREFIX.length + 31, "last1"));
+ Assert.assertTrue(pattern.match(PREFIX.length + 31, "last2"));
+ Assert.assertFalse(pattern.match(PREFIX.length + 31, "last3"));
+ }
+
+ @Test
+ public void testCompactCartesianProductBehindWildcard() {
+ final List<PartialPath> patterns =
+ convert(
+ branch(precise(1, "card1"), precise(2, "device1")),
+ branch(precise(1, "card1"), precise(2, "device2")),
+ branch(precise(1, "card2"), precise(2, "device1")),
+ branch(precise(1, "card2"), precise(2, "device2")));
+
+ Assert.assertEquals(1, patterns.size());
+ final ExtendedPartialPath pattern = (ExtendedPartialPath) patterns.get(0);
+ Assert.assertTrue(pattern.match(PREFIX.length + 1, "card1"));
+ Assert.assertTrue(pattern.match(PREFIX.length + 1, "card2"));
+ Assert.assertTrue(pattern.match(PREFIX.length + 2, "device1"));
+ Assert.assertTrue(pattern.match(PREFIX.length + 2, "device2"));
+ }
+
+ @Test
+ public void testDoNotCompactCorrelatedOrBranches() {
+ final List<PartialPath> patterns =
+ convert(
+ branch(precise(1, "card1"), precise(2, "device1")),
+ branch(precise(1, "card2"), precise(2, "device2")));
+
+ Assert.assertEquals(2, patterns.size());
+ }
+
+ @Test
+ public void testDoNotCompactNullPreciseValue() {
+ final List<PartialPath> patterns =
+ convert(branch(precise(1, null)), branch(precise(1, "card1")));
+
+ Assert.assertEquals(2, patterns.size());
+ }
+
+ @Test
+ public void testCombineMultiExactAndOtherFilters() {
+ final List<PartialPath> patterns =
+ convert(
+ branch(
+ new TagFilter(new InFilter(new
HashSet<>(Arrays.asList("card1", "card2"))), 1),
+ new TagFilter(new NotFilter(new PreciseFilter("card2")), 1)));
+
+ Assert.assertEquals(1, patterns.size());
+ assertPreciseTransitionsAfterFirstTag(patterns.get(0), "card1");
+ }
+
+ @Test
+ public void testIterateMultiExactValuesWhenTheyAreFewer() {
+ final TestNode root = new TestNode("root");
+ final TestNode parent = new TestNode("meter");
+ root.addChild(parent);
+ parent.addChildren("card1", "card2", "card3", "card4");
+
+ final TestVisitor visitor =
+ new TestVisitor(root, createAdaptivePattern(Set.of("card1", "card2")),
parent);
+
+ Assert.assertEquals(Arrays.asList("card1", "card2"), collect(visitor));
+ Assert.assertEquals(2, visitor.getTargetDirectLookupCount());
+ Assert.assertEquals(0, visitor.getTargetChildrenIterationCount());
+ }
+
+ @Test
+ public void testIterateChildKeysWhenTheyAreFewer() {
+ final TestNode root = new TestNode("root");
+ final TestNode parent = new TestNode("meter");
+ root.addChild(parent);
+ parent.addChildren("card1", "card2");
+
+ final TestVisitor visitor =
+ new TestVisitor(
+ root,
+ createAdaptivePattern(Set.of("card1", "card2", "card3", "card4",
"card5")),
+ parent);
+
+ Assert.assertEquals(Arrays.asList("card1", "card2"), collect(visitor));
+ Assert.assertEquals(0, visitor.getTargetDirectLookupCount());
+ Assert.assertEquals(1, visitor.getTargetChildrenIterationCount());
+ }
+
+ @Test
+ public void testIterateChildKeysWhenCandidateCountsAreEqual() {
+ final TestNode root = new TestNode("root");
+ final TestNode parent = new TestNode("meter");
+ root.addChild(parent);
+ parent.addChildren("card1", "card2");
+
+ final TestVisitor visitor =
+ new TestVisitor(root, createAdaptivePattern(Set.of("card1", "card2")),
parent);
+
+ Assert.assertEquals(Arrays.asList("card1", "card2"), collect(visitor));
+ Assert.assertEquals(0, visitor.getTargetDirectLookupCount());
+ Assert.assertEquals(1, visitor.getTargetChildrenIterationCount());
+ }
+
+ private static ExtendedPartialPath createAdaptivePattern(final Set<String>
values) {
+ final ExtendedPartialPath pattern =
+ new ExtendedPartialPath(new String[] {"root", "*", "*"}, true);
+ pattern.addMultiExactMatch(2, values);
+ return pattern;
+ }
+
+ private static List<String> collect(final TestVisitor visitor) {
+ final List<String> result = new ArrayList<>();
+ try {
+ while (visitor.hasNext()) {
+ result.add(visitor.next());
+ }
+ } finally {
+ visitor.close();
+ }
+ Collections.sort(result);
+ return result;
+ }
+
+ @SafeVarargs
+ private static List<PartialPath> convert(final List<SchemaFilter>...
branches) {
+ return convert(TAG_COLUMN_NUM, branches);
+ }
+
+ @SafeVarargs
+ private static List<PartialPath> convert(
+ final int tagColumnNum, final List<SchemaFilter>... branches) {
+ return DeviceFilterUtil.convertToDevicePattern(
+ PREFIX, tagColumnNum, Arrays.asList(branches), false);
+ }
+
+ private static List<SchemaFilter> branch(final SchemaFilter... filters) {
+ return Arrays.asList(filters);
+ }
+
+ private static TagFilter precise(final int index, final String value) {
+ return new TagFilter(new PreciseFilter(value), index);
+ }
+
+ private static void assertPreciseTransitionsAfterFirstTag(
+ final PartialPath pattern, final String... expectedTransitions) {
+ final IPatternFA patternFA = new
IPatternFA.Builder().pattern(pattern).buildNFA();
+ IFAState state = patternFA.getInitialState();
+ for (final String prefixNode : PREFIX) {
+ final IFATransition transition =
patternFA.getPreciseMatchTransition(state).get(prefixNode);
+ Assert.assertNotNull(transition);
+ state = patternFA.getNextState(state, transition);
+ }
+ final IFATransition wildcardTransition =
+ patternFA.getFuzzyMatchTransitionIterator(state).next();
+ state = patternFA.getNextState(state, wildcardTransition);
+
+ final Set<String> expected = new
HashSet<>(Arrays.asList(expectedTransitions));
+ Assert.assertEquals(expected,
patternFA.getPreciseMatchTransition(state).keySet());
+ Assert.assertEquals(0, patternFA.getFuzzyMatchTransitionSize(state));
+ }
+
+ private static class TestVisitor extends AbstractTreeVisitor<TestNode,
String> {
+
+ private final TestNode targetParent;
+ private int targetDirectLookupCount;
+ private int targetChildrenIterationCount;
+
+ private TestVisitor(
+ final TestNode root, final ExtendedPartialPath pathPattern, final
TestNode targetParent) {
+ super(root, pathPattern, false);
+ this.targetParent = targetParent;
+ initStack();
+ }
+
+ @Override
+ protected TestNode getChild(final TestNode parent, final String childName)
{
+ if (parent == targetParent) {
+ targetDirectLookupCount++;
+ }
+ return parent.children.get(childName);
+ }
+
+ @Override
+ protected Iterator<TestNode> getChildrenIterator(final TestNode parent) {
+ if (parent == targetParent) {
+ targetChildrenIterationCount++;
+ }
+ return parent.children.values().iterator();
+ }
+
+ @Override
+ protected Iterator<TestNode> getChildrenIterator(
+ final TestNode parent, final Iterator<String> childrenName) {
+ final List<TestNode> children = new ArrayList<>();
+ childrenName.forEachRemaining(
+ name -> {
+ final TestNode child = parent.children.get(name);
+ if (child != null) {
+ children.add(child);
+ }
+ });
+ return children.iterator();
+ }
+
+ @Override
+ protected int getChildrenSize(final TestNode parent) {
+ return parent.children.keySet().size();
+ }
+
+ @Override
+ protected boolean shouldVisitSubtreeOfInternalMatchedNode(final TestNode
node) {
+ return true;
+ }
+
+ @Override
+ protected boolean shouldVisitSubtreeOfFullMatchedNode(final TestNode node)
{
+ return false;
+ }
+
+ @Override
+ protected boolean acceptInternalMatchedNode(final TestNode node) {
+ return false;
+ }
+
+ @Override
+ protected boolean acceptFullMatchedNode(final TestNode node) {
+ return true;
+ }
+
+ @Override
+ protected String generateResult(final TestNode nextMatchedNode) {
+ return nextMatchedNode.getName();
+ }
+
+ @Override
+ protected boolean mayTargetNodeType(final TestNode node) {
+ return true;
+ }
+
+ private int getTargetDirectLookupCount() {
+ return targetDirectLookupCount;
+ }
+
+ private int getTargetChildrenIterationCount() {
+ return targetChildrenIterationCount;
+ }
+ }
+
+ private static class TestNode implements ITreeNode {
+
+ private final String name;
+ private final Map<String, TestNode> children = new LinkedHashMap<>();
+
+ private TestNode(final String name) {
+ this.name = name;
+ }
+
+ private void addChild(final TestNode child) {
+ children.put(child.getName(), child);
+ }
+
+ private void addChildren(final String... childNames) {
+ Arrays.stream(childNames).map(TestNode::new).forEach(this::addChild);
+ }
+
+ @Override
+ public String getName() {
+ return name;
+ }
+ }
+}
