VGalaxies commented on code in PR #16789:
URL: https://github.com/apache/iotdb/pull/16789#discussion_r2609401743
##########
iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/pipe/datastructure/pattern/TreePattern.java:
##########
@@ -649,4 +758,86 @@ public static int[] checkAndLogPatternCoverage(
return new int[] {coveredCount, inclusionPaths.size()};
}
+
+ /** A specialized Trie to efficiently check path coverage. */
+ private static class PatternTrie {
+ private final TrieNode root = new TrieNode();
+
+ private static class TrieNode {
+ // Children nodes mapped by path segment
+ Map<String, TrieNode> children = new HashMap<>();
+ // Marks if a pattern ends here (e.g., "root.sg" is a set path)
+ boolean isLeaf = false;
+ // Special flags for optimization
+ boolean isMultiLevelWildcard = false; // Ends with **
+ }
+
+ /** Adds a path to the Trie. */
+ public void add(final PartialPath path) {
+ TrieNode node = root;
+ final String[] nodes = path.getNodes();
+
+ for (final String segment : nodes) {
+ // If we are at a node that is already a MultiLevelWildcard (**),
+ // everything below is already covered. We can stop adding.
+ if (node.isMultiLevelWildcard) {
+ return;
+ }
+
+ node = node.children.computeIfAbsent(segment, k -> new TrieNode());
+
+ // If this segment is **, mark it.
+ // Note: In IoTDB PartialPath, ** is usually the last node or specific
wildcard.
+ if (segment.equals(IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD)) {
+ node.isMultiLevelWildcard = true;
+ // Optimization: clear children as ** covers everything
+ node.children.clear();
Review Comment:
done
##########
iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/pipe/datastructure/pattern/TreePattern.java:
##########
@@ -395,6 +437,37 @@ private static List<TreePattern> pruneInclusionPatterns(
return prunedInclusion;
}
+ /**
+ * Prunes patterns from the exclusion list that do NOT overlap with any of
the remaining inclusion
+ * patterns.
+ */
+ private static List<TreePattern> pruneIrrelevantExclusions(
+ final List<TreePattern> inclusion, final List<TreePattern> exclusion) {
+ if (exclusion == null || exclusion.isEmpty()) {
+ return new ArrayList<>();
+ }
+ if (inclusion == null || inclusion.isEmpty()) {
+ // If inclusion is empty, exclusion is irrelevant anyway, but usually
this case
+ // throws exception earlier.
+ return new ArrayList<>();
+ }
+
+ final List<TreePattern> relevantExclusion = new ArrayList<>();
+ for (final TreePattern exc : exclusion) {
+ boolean overlapsWithAnyInclusion = false;
+ for (final TreePattern inc : inclusion) {
+ if (overlaps(exc, inc)) {
+ overlapsWithAnyInclusion = true;
+ break;
+ }
+ }
+ if (overlapsWithAnyInclusion) {
+ relevantExclusion.add(exc);
+ }
+ }
Review Comment:
done
##########
iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/pipe/datastructure/pattern/TreePattern.java:
##########
@@ -329,40 +357,54 @@ private static List<TreePattern> optimizePatterns(final
List<TreePattern> patter
return patterns;
}
+ // 1. Sort patterns by "Broadness"
+ // Heuristic: Shorter paths and paths with wildcards should come first.
+ // This allows us to insert 'root.**' first, so we can quickly skip
'root.sg.d1' later.
+ final List<TreePattern> sortedPatterns = new ArrayList<>(patterns);
+ sortedPatterns.sort(
+ (o1, o2) -> {
+ // We can only approximate comparison here since TreePattern
represents multiple paths.
+ // We use the first inclusion path as a representative.
+ final PartialPath p1 = o1.getBaseInclusionPaths().get(0);
+ final PartialPath p2 = o2.getBaseInclusionPaths().get(0);
+
+ // 1. Length: Shorter is generally broader (e.g., root.** vs
root.sg.d1)
+ final int lenCompare = Integer.compare(p1.getNodeLength(),
p2.getNodeLength());
+ if (lenCompare != 0) return lenCompare;
Review Comment:
done
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
