This is an automated email from the ASF dual-hosted git repository.
zyk 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 fa3612d96ad Optimize memory usage of fetchSchema when inserting data
(#11591)
fa3612d96ad is described below
commit fa3612d96ad7d3583457d1232cb7d3fcab658fe7
Author: Chen YZ <[email protected]>
AuthorDate: Fri Nov 24 10:09:25 2023 +0800
Optimize memory usage of fetchSchema when inserting data (#11591)
---
.../schemaRegion/SchemaRegionBasicTest.java | 39 +++++++++++
.../iotdb/commons/path/fa/dfa/PatternDFA.java | 18 ++----
.../iotdb/commons/path/fa/dfa/graph/DFAGraph.java | 75 ++++++++++++----------
.../apache/iotdb/commons/path/PatternDFATest.java | 10 +--
4 files changed, 88 insertions(+), 54 deletions(-)
diff --git
a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/metadata/schemaRegion/SchemaRegionBasicTest.java
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/metadata/schemaRegion/SchemaRegionBasicTest.java
index 1c2094b1bdb..536e6468717 100644
---
a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/metadata/schemaRegion/SchemaRegionBasicTest.java
+++
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/metadata/schemaRegion/SchemaRegionBasicTest.java
@@ -40,6 +40,7 @@ import org.apache.iotdb.tsfile.file.metadata.enums.TSEncoding;
import org.apache.commons.lang3.StringUtils;
import org.junit.Assert;
+import org.junit.Ignore;
import org.junit.Test;
import java.util.Arrays;
@@ -72,6 +73,44 @@ public class SchemaRegionBasicTest extends
AbstractSchemaRegionTest {
super(testParams);
}
+ @Test
+ @Ignore
+ public void testFetchSchemaPerfomance() throws Exception {
+ System.out.println(testParams.getTestModeName());
+ int deviceNum = 1000;
+ int measurementNum = 40;
+ ISchemaRegion schemaRegion = getSchemaRegion("root.sg", 0);
+ for (int i = 0; i < deviceNum; i++) {
+ for (int j = 0; j < measurementNum; j++) {
+ schemaRegion.createTimeseries(
+ SchemaRegionWritePlanFactory.getCreateTimeSeriesPlan(
+ new PartialPath("root.sg.d" + i + ".s" + j),
+ TSDataType.BOOLEAN,
+ TSEncoding.PLAIN,
+ CompressionType.SNAPPY,
+ null,
+ null,
+ null,
+ null),
+ -1);
+ }
+ }
+ PathPatternTree patternTree = new PathPatternTree();
+ for (int i = 0; i < deviceNum; i++) {
+ for (int j = 0; j < measurementNum; j++) {
+ patternTree.appendFullPath(new PartialPath("root.sg.d" + i + ".s" +
j));
+ }
+ }
+ patternTree.constructTree();
+ schemaRegion.fetchSchema(patternTree, Collections.EMPTY_MAP, false);
+ long startTime;
+ startTime = System.currentTimeMillis();
+ for (int i = 0; i < 10; i++) {
+ schemaRegion.fetchSchema(patternTree, Collections.EMPTY_MAP, false);
+ }
+ System.out.println("cost time: " + (System.currentTimeMillis() -
startTime));
+ }
+
@Test
public void testFetchSchema() throws Exception {
ISchemaRegion schemaRegion = getSchemaRegion("root.sg", 0);
diff --git
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/dfa/PatternDFA.java
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/dfa/PatternDFA.java
index d3b45111773..128f66d1c35 100644
---
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/dfa/PatternDFA.java
+++
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/dfa/PatternDFA.java
@@ -53,10 +53,8 @@ public class PatternDFA implements IPatternFA {
public PatternDFA(PartialPath pathPattern, boolean isPrefix) {
// 1. build transition
boolean wildcard = false;
- int cnt = 0;
AtomicInteger transitionIndex = new AtomicInteger();
for (String node : pathPattern.getNodes()) {
- cnt++;
if (IoTDBConstant.ONE_LEVEL_PATH_WILDCARD.equals(node)
|| IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD.equals(node)) {
wildcard = true;
@@ -83,7 +81,7 @@ public class PatternDFA implements IPatternFA {
NFAGraph nfaGraph = new NFAGraph(pathPattern, isPrefix, transitionMap);
// 3. NFA to DFA
- dfaGraph = new DFAGraph(nfaGraph, transitionMap.values(), cnt);
+ dfaGraph = new DFAGraph(nfaGraph, transitionMap.values());
preciseMatchTransitionCached = new HashMap[dfaGraph.getStateSize()];
batchMatchTransitionCached = new List[dfaGraph.getStateSize()];
}
@@ -96,9 +94,8 @@ public class PatternDFA implements IPatternFA {
public PatternDFA(PathPatternTree prefixOrFullPatternTree) {
// 1. build transition
AtomicInteger transitionIndex = new AtomicInteger();
- AtomicInteger count = new AtomicInteger(0);
- boolean wildcard = initTransitionMap(prefixOrFullPatternTree.getRoot(),
transitionIndex, count);
+ boolean wildcard = initTransitionMap(prefixOrFullPatternTree.getRoot(),
transitionIndex);
if (wildcard) {
IFATransition transition =
new DFAWildcardTransition(
@@ -108,19 +105,16 @@ public class PatternDFA implements IPatternFA {
// build NFA
NFAGraph nfaGraph = new NFAGraph(prefixOrFullPatternTree, transitionMap);
// NFA to DFA
- dfaGraph = new DFAGraph(nfaGraph, transitionMap.values(), count.get());
+ dfaGraph = new DFAGraph(nfaGraph, transitionMap.values());
} else {
- dfaGraph = new DFAGraph(prefixOrFullPatternTree, transitionMap,
count.get());
+ dfaGraph = new DFAGraph(prefixOrFullPatternTree, transitionMap);
}
preciseMatchTransitionCached = new HashMap[dfaGraph.getStateSize()];
batchMatchTransitionCached = new List[dfaGraph.getStateSize()];
}
private boolean initTransitionMap(
- PathPatternNode<Void, PathPatternNode.VoidSerializer> node,
- AtomicInteger transitionIndex,
- AtomicInteger count) {
- count.incrementAndGet();
+ PathPatternNode<Void, PathPatternNode.VoidSerializer> node,
AtomicInteger transitionIndex) {
boolean wildcard = true;
if (!IoTDBConstant.ONE_LEVEL_PATH_WILDCARD.equals(node.getName())
&& !IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD.equals(node.getName())) {
@@ -136,7 +130,7 @@ public class PatternDFA implements IPatternFA {
}
for (PathPatternNode<Void, PathPatternNode.VoidSerializer> child :
node.getChildren().values()) {
- wildcard |= initTransitionMap(child, transitionIndex, count);
+ wildcard |= initTransitionMap(child, transitionIndex);
}
return wildcard;
}
diff --git
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/dfa/graph/DFAGraph.java
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/dfa/graph/DFAGraph.java
index b3b82144861..644328aa424 100644
---
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/dfa/graph/DFAGraph.java
+++
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/dfa/graph/DFAGraph.java
@@ -39,11 +39,11 @@ import java.util.concurrent.atomic.AtomicInteger;
*/
public class DFAGraph {
private final List<IFAState> dfaStateList = new ArrayList<>();
+
// [stateIndex][transitionIndex]
- private IFAState[][] dfaTransitionTable;
+ private final Map<Integer, Map<Integer, IFAState>> dfaTransitionTable = new
HashMap<>();
- public DFAGraph(NFAGraph nfaGraph, Collection<IFATransition> transitions,
int patternNodesCount) {
- dfaTransitionTable = new IFAState[patternNodesCount *
2][transitions.size()];
+ public DFAGraph(NFAGraph nfaGraph, Collection<IFATransition> transitions) {
int closureSize = nfaGraph.getStateSize();
// init start state
int index = 0;
@@ -66,16 +66,17 @@ public class DFAGraph {
if (!isEmpty) {
if (closureStateMap.containsKey(nextClosure)) {
// closure already exist
-
dfaTransitionTable[closureStateMap.get(curClosure).getIndex()][transition.getIndex()]
=
- closureStateMap.get(nextClosure);
+ updateDfaTransitionTable(
+ closureStateMap.get(curClosure).getIndex(),
+ transition.getIndex(),
+ closureStateMap.get(nextClosure));
} else {
// new closure
DFAState newState = new DFAState(++index, nextClosure.isFinal());
dfaStateList.add(newState);
closureStateMap.put(nextClosure, newState);
- ensureCapacity();
-
dfaTransitionTable[closureStateMap.get(curClosure).getIndex()][transition.getIndex()]
=
- newState;
+ updateDfaTransitionTable(
+ closureStateMap.get(curClosure).getIndex(),
transition.getIndex(), newState);
closureStack.push(nextClosure);
}
}
@@ -83,25 +84,13 @@ public class DFAGraph {
}
}
- public DFAGraph(
- PathPatternTree patternTree,
- Map<String, IFATransition> transitionMap,
- int patternNodesCount) {
- dfaTransitionTable = new IFAState[patternNodesCount *
2][transitionMap.size()];
+ public DFAGraph(PathPatternTree patternTree, Map<String, IFATransition>
transitionMap) {
// init start state
IFAState curState = new DFAState(0);
dfaStateList.add(curState);
init(patternTree.getRoot(), transitionMap, curState, new AtomicInteger(0));
}
- private void ensureCapacity() {
- if (dfaStateList.size() > dfaTransitionTable.length) {
- IFAState[][] tmp = new IFAState[dfaTransitionTable.length *
2][dfaTransitionTable[0].length];
- System.arraycopy(dfaTransitionTable, 0, tmp, 0,
dfaTransitionTable.length);
- dfaTransitionTable = tmp;
- }
- }
-
private void init(
PathPatternNode<Void, PathPatternNode.VoidSerializer> node,
Map<String, IFATransition> transitionMap,
@@ -110,22 +99,18 @@ public class DFAGraph {
IFATransition transition = transitionMap.get(node.getName());
int stateIndex = curState.getIndex();
int transitionIndex = transition.getIndex();
- if (dfaTransitionTable[stateIndex][transitionIndex] == null) {
- DFAState newState = new DFAState(stateIndexGenerator.incrementAndGet());
+ DFAState newState = (DFAState) getFromDfaTransitionTable(stateIndex,
transitionIndex);
+ if (newState == null) {
+ newState = new DFAState(stateIndexGenerator.incrementAndGet());
dfaStateList.add(newState);
- ensureCapacity();
- dfaTransitionTable[stateIndex][transitionIndex] = newState;
+ updateDfaTransitionTable(stateIndex, transitionIndex, newState);
}
if (node.isPathPattern()) {
- ((DFAState)
dfaTransitionTable[stateIndex][transitionIndex]).setFinal(true);
+ newState.setFinal(true);
}
for (PathPatternNode<Void, PathPatternNode.VoidSerializer> child :
node.getChildren().values()) {
- init(
- child,
- transitionMap,
- dfaTransitionTable[stateIndex][transitionIndex],
- stateIndexGenerator);
+ init(child, transitionMap, newState, stateIndexGenerator);
}
}
@@ -147,7 +132,7 @@ public class DFAGraph {
stringBuilder = new StringBuilder();
stringBuilder.append(String.format("|%-15d|", i));
for (IFATransition transition : transitionMap.values()) {
- IFAState tmp = dfaTransitionTable[i][transition.getIndex()];
+ IFAState tmp = getFromDfaTransitionTable(i, transition.getIndex());
stringBuilder.append(String.format("%-15s|", tmp == null ? "" :
tmp.getIndex()));
}
stringBuilder.append(String.format("%-15s|",
dfaStateList.get(i).isFinal()));
@@ -181,7 +166,7 @@ public class DFAGraph {
IFAState state, Collection<IFATransition> transitions) {
Map<String, IFATransition> res = new HashMap<>();
for (IFATransition transition : transitions) {
- if (dfaTransitionTable[state.getIndex()][transition.getIndex()] != null)
{
+ if (getFromDfaTransitionTable(state.getIndex(), transition.getIndex())
!= null) {
res.put(transition.getAcceptEvent(), transition);
}
}
@@ -192,7 +177,7 @@ public class DFAGraph {
IFAState state, Collection<IFATransition> transitionList) {
List<IFATransition> res = new ArrayList<>();
for (IFATransition transition : transitionList) {
- if (dfaTransitionTable[state.getIndex()][transition.getIndex()] != null)
{
+ if (getFromDfaTransitionTable(state.getIndex(), transition.getIndex())
!= null) {
res.add(transition);
}
}
@@ -200,7 +185,7 @@ public class DFAGraph {
}
public IFAState getNextState(IFAState currentState, IFATransition
transition) {
- return dfaTransitionTable[currentState.getIndex()][transition.getIndex()];
+ return getFromDfaTransitionTable(currentState.getIndex(),
transition.getIndex());
}
public IFAState getInitialState() {
@@ -214,4 +199,24 @@ public class DFAGraph {
public IFAState getState(int index) {
return dfaStateList.get(index);
}
+
+ private void updateDfaTransitionTable(int stateIndex, int transitionIndex,
IFAState newState) {
+ dfaTransitionTable.compute(
+ stateIndex,
+ (k, v) -> {
+ if (v == null) {
+ v = new HashMap<>();
+ }
+ v.put(transitionIndex, newState);
+ return v;
+ });
+ }
+
+ private IFAState getFromDfaTransitionTable(int stateIndex, int
transitionIndex) {
+ if (dfaTransitionTable.containsKey(stateIndex)) {
+ return dfaTransitionTable.get(stateIndex).get(transitionIndex);
+ } else {
+ return null;
+ }
+ }
}
diff --git
a/iotdb-core/node-commons/src/test/java/org/apache/iotdb/commons/path/PatternDFATest.java
b/iotdb-core/node-commons/src/test/java/org/apache/iotdb/commons/path/PatternDFATest.java
index 9dd12c5a014..8e2c223d99a 100644
---
a/iotdb-core/node-commons/src/test/java/org/apache/iotdb/commons/path/PatternDFATest.java
+++
b/iotdb-core/node-commons/src/test/java/org/apache/iotdb/commons/path/PatternDFATest.java
@@ -51,10 +51,8 @@ public class PatternDFATest {
PartialPath pathPattern = new PartialPath("root.**.d.s1");
// 1. build transition
boolean wildcard = false;
- int cnt = 0;
AtomicInteger transitionIndex = new AtomicInteger();
for (String node : pathPattern.getNodes()) {
- cnt++;
if (IoTDBConstant.ONE_LEVEL_PATH_WILDCARD.equals(node)
|| IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD.equals(node)) {
wildcard = true;
@@ -73,7 +71,7 @@ public class PatternDFATest {
NFAGraph nfaGraph = new NFAGraph(pathPattern, false, transitionMap);
nfaGraph.print(transitionMap);
// 3. NFA to DFA
- DFAGraph dfaGraph = new DFAGraph(nfaGraph, transitionMap.values(), cnt);
+ DFAGraph dfaGraph = new DFAGraph(nfaGraph, transitionMap.values());
dfaGraph.print(transitionMap);
}
@@ -95,11 +93,9 @@ public class PatternDFATest {
patternTree.constructTree();
// 1. build transition
boolean wildcard = false;
- int cnt = 0;
AtomicInteger transitionIndex = new AtomicInteger();
for (PartialPath pathPattern : patternTree.getAllPathPatterns()) {
for (String node : pathPattern.getNodes()) {
- cnt++;
if (IoTDBConstant.ONE_LEVEL_PATH_WILDCARD.equals(node)
|| IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD.equals(node)) {
wildcard = true;
@@ -119,7 +115,7 @@ public class PatternDFATest {
NFAGraph nfaGraph = new NFAGraph(patternTree, transitionMap);
nfaGraph.print(transitionMap);
// 3. NFA to DFA
- DFAGraph dfaGraph = new DFAGraph(nfaGraph, transitionMap.values(), cnt);
+ DFAGraph dfaGraph = new DFAGraph(nfaGraph, transitionMap.values());
dfaGraph.print(transitionMap);
}
@@ -146,7 +142,7 @@ public class PatternDFATest {
}
patternTree.constructTree();
// build DFA directly
- DFAGraph dfaGraph = new DFAGraph(patternTree, transitionMap, 18);
+ DFAGraph dfaGraph = new DFAGraph(patternTree, transitionMap);
dfaGraph.print(transitionMap);
}
