This is an automated email from the ASF dual-hosted git repository.
jackietien 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 c6b7b5444f [IOTDB-4465] Add interface for PatternTreeMap to optimize
getOverlapped (#7465)
c6b7b5444f is described below
commit c6b7b5444f4112387bb8b1260819ed6e8ac2b01d
Author: Chen YZ <[email protected]>
AuthorDate: Wed Sep 28 17:36:58 2022 +0800
[IOTDB-4465] Add interface for PatternTreeMap to optimize getOverlapped
(#7465)
---
.../apache/iotdb/commons/path/PatternTreeMap.java | 50 ++++++++++++++++-
.../iotdb/db/metadata/path/PatternTreeMapTest.java | 64 ++++++++++++++++++----
2 files changed, 103 insertions(+), 11 deletions(-)
diff --git
a/node-commons/src/main/java/org/apache/iotdb/commons/path/PatternTreeMap.java
b/node-commons/src/main/java/org/apache/iotdb/commons/path/PatternTreeMap.java
index 7cff90f7a7..2d701dd2c0 100644
---
a/node-commons/src/main/java/org/apache/iotdb/commons/path/PatternTreeMap.java
+++
b/node-commons/src/main/java/org/apache/iotdb/commons/path/PatternTreeMap.java
@@ -135,7 +135,7 @@ public class PatternTreeMap<V, VSerializer extends
PathPatternNode.Serializer<V>
* @param pos current index of pathNodes
* @param resultList result list
*/
- public void searchOverlapped(
+ private void searchOverlapped(
PathPatternNode<V, VSerializer> node, String[] pathNodes, int pos,
List<V> resultList) {
if (pos == pathNodes.length - 1) {
resultList.addAll(node.getValues());
@@ -148,4 +148,52 @@ public class PatternTreeMap<V, VSerializer extends
PathPatternNode.Serializer<V>
searchOverlapped(child, pathNodes, pos + 1, resultList);
}
}
+
+ /**
+ * Get a list of value lists related to PathPattern that overlapped with
measurements under the
+ * same device.
+ *
+ * @param devicePath device path without wildcard
+ * @param measurements list of measurements
+ * @return value list
+ */
+ public List<List<V>> getOverlapped(PartialPath devicePath, List<String>
measurements) {
+ List<List<V>> res = new ArrayList<>();
+ for (int i = 0; i < measurements.size(); i++) {
+ res.add(new ArrayList<>());
+ }
+ searchOverlapped(root, devicePath.getNodes(), 0, measurements, res);
+ return res;
+ }
+
+ /**
+ * Recursive method for search overlapped pattern.
+ *
+ * @param node current PathPatternNode
+ * @param deviceNodes pathNodes of device
+ * @param pos current index of pathNodes
+ * @param measurements list of measurements under device
+ * @param resultList result list
+ */
+ private void searchOverlapped(
+ PathPatternNode<V, VSerializer> node,
+ String[] deviceNodes,
+ int pos,
+ List<String> measurements,
+ List<List<V>> resultList) {
+ if (pos == deviceNodes.length - 1) {
+ for (int i = 0; i < measurements.size(); i++) {
+ for (PathPatternNode<V, VSerializer> child :
node.getMatchChildren(measurements.get(i))) {
+ resultList.get(i).addAll(child.getValues());
+ }
+ }
+ return;
+ }
+ if (node.isMultiLevelWildcard()) {
+ searchOverlapped(node, deviceNodes, pos + 1, measurements, resultList);
+ }
+ for (PathPatternNode<V, VSerializer> child :
node.getMatchChildren(deviceNodes[pos + 1])) {
+ searchOverlapped(child, deviceNodes, pos + 1, measurements, resultList);
+ }
+ }
}
diff --git
a/server/src/test/java/org/apache/iotdb/db/metadata/path/PatternTreeMapTest.java
b/server/src/test/java/org/apache/iotdb/db/metadata/path/PatternTreeMapTest.java
index 3a301f125a..3a328cc359 100644
---
a/server/src/test/java/org/apache/iotdb/db/metadata/path/PatternTreeMapTest.java
+++
b/server/src/test/java/org/apache/iotdb/db/metadata/path/PatternTreeMapTest.java
@@ -55,17 +55,31 @@ public class PatternTreeMapTest {
checkOverlapped(
patternTreeMap,
new PartialPath("root.sg1.d1.s1"),
- new HashSet(Arrays.asList("A", "B", "C", "D", "E", "G", "H", "I",
"J")));
+ new HashSet<>(Arrays.asList("A", "B", "C", "D", "E", "G", "H", "I",
"J")));
checkOverlapped(
- patternTreeMap, new PartialPath("root.sg2.s1"), new
HashSet(Arrays.asList("B", "J")));
+ patternTreeMap, new PartialPath("root.sg2.s1"), new
HashSet<>(Arrays.asList("B", "J")));
checkOverlapped(
patternTreeMap,
new PartialPath("root.sg1.d1.s2"),
- new HashSet(Arrays.asList("E", "F", "G", "H", "I", "J")));
+ new HashSet<>(Arrays.asList("E", "F", "G", "H", "I", "J")));
checkOverlapped(
patternTreeMap,
new PartialPath("root.sg1.d1.v1.s1"),
- new HashSet(Arrays.asList("B", "E", "H", "I", "J")));
+ new HashSet<>(Arrays.asList("B", "E", "H", "I", "J")));
+ checkOverlappedByDeviceMeasurements(
+ patternTreeMap,
+ new PartialPath("root.sg1.d1"),
+ Arrays.asList("s1", "s2"),
+ Arrays.asList(
+ new HashSet<>(Arrays.asList("A", "B", "C", "D", "E", "G", "H",
"I", "J")),
+ new HashSet<>(Arrays.asList("E", "F", "G", "H", "I", "J"))));
+ checkOverlappedByDeviceMeasurements(
+ patternTreeMap,
+ new PartialPath("root.sg1.d2"),
+ Arrays.asList("s1", "s2"),
+ Arrays.asList(
+ new HashSet<>(Arrays.asList("B", "C", "E", "G", "H", "I", "J")),
+ new HashSet<>(Arrays.asList("E", "F", "G", "H", "I", "J"))));
// delete leaf node with common parent
patternTreeMap.delete(new PartialPath("root.**.d1.*"), "G");
// only delete value, no delete leaf node
@@ -75,15 +89,29 @@ public class PatternTreeMapTest {
checkOverlapped(
patternTreeMap,
new PartialPath("root.sg1.d1.s1"),
- new HashSet(Arrays.asList("A", "B", "C", "E", "H", "I")));
+ new HashSet<>(Arrays.asList("A", "B", "C", "E", "H", "I")));
checkOverlapped(
patternTreeMap,
new PartialPath("root.sg1.d1.s2"),
- new HashSet(Arrays.asList("E", "F", "H", "I")));
+ new HashSet<>(Arrays.asList("E", "F", "H", "I")));
checkOverlapped(
patternTreeMap,
new PartialPath("root.sg1.d1.v1.s1"),
- new HashSet(Arrays.asList("B", "E", "H", "I")));
+ new HashSet<>(Arrays.asList("B", "E", "H", "I")));
+ checkOverlappedByDeviceMeasurements(
+ patternTreeMap,
+ new PartialPath("root.sg1.d1"),
+ Arrays.asList("s1", "s2"),
+ Arrays.asList(
+ new HashSet<>(Arrays.asList("A", "B", "C", "E", "H", "I")),
+ new HashSet<>(Arrays.asList("E", "F", "H", "I"))));
+ checkOverlappedByDeviceMeasurements(
+ patternTreeMap,
+ new PartialPath("root.sg1.d2"),
+ Arrays.asList("s1", "s2"),
+ Arrays.asList(
+ new HashSet<>(Arrays.asList("B", "C", "E", "H", "I")),
+ new HashSet<>(Arrays.asList("E", "F", "H", "I"))));
}
@Test
@@ -112,7 +140,7 @@ public class PatternTreeMapTest {
checkOverlapped(
patternTreeMap,
new PartialPath("root.sg1.d1.s1"),
- new HashSet(
+ new HashSet<>(
Arrays.asList(
new Deletion(new PartialPath("root.sg1.d1.s1"), 1, 1, 3),
new Deletion(new PartialPath("root.sg1.d1.s1"), 1, 6, 10),
@@ -123,7 +151,7 @@ public class PatternTreeMapTest {
checkOverlapped(
patternTreeMap,
new PartialPath("root.sg1.d2.s1"),
- new HashSet(
+ new HashSet<>(
Arrays.asList(
new Deletion(new PartialPath("root.**.s1"), 5, 10, 100),
new Deletion(new PartialPath("root.**.s1"), 10, 100, 200),
@@ -132,7 +160,7 @@ public class PatternTreeMapTest {
checkOverlapped(
patternTreeMap,
new PartialPath("root.sg1.d1.s2"),
- new HashSet(
+ new HashSet<>(
Collections.singletonList(new Deletion(new PartialPath("root.**"),
5, 10, 100))));
}
@@ -144,4 +172,20 @@ public class PatternTreeMapTest {
Assert.assertTrue(resultSet.contains(o));
}
}
+
+ private <T> void checkOverlappedByDeviceMeasurements(
+ PatternTreeMap<T, ?> patternTreeMap,
+ PartialPath devicePath,
+ List<String> measurements,
+ List<Set<T>> resultSet) {
+ List<List<T>> list = patternTreeMap.getOverlapped(devicePath,
measurements);
+ Assert.assertEquals(resultSet.size(), list.size());
+ for (int i = 0; i < measurements.size(); i++) {
+ List<T> subList = list.get(i);
+ Set<T> subSet = resultSet.get(i);
+ for (T o : subList) {
+ Assert.assertTrue(subSet.contains(o));
+ }
+ }
+ }
}
