You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@iotdb.apache.org by le...@apache.org on 2024/02/05 08:26:29 UTC
(iotdb) 09/30: acc_rectangle
This is an automated email from the ASF dual-hosted git repository.
leirui pushed a commit to branch research/LTS-visualization
in repository https://gitbox.apache.org/repos/asf/iotdb.git
commit 35e314136d0a3a0749cd28f3a8c220f0d0024615
Author: Lei Rui <10...@qq.com>
AuthorDate: Sun Jan 28 18:42:11 2024 +0800
acc_rectangle
---
.../resources/conf/iotdb-engine.properties | 4 +
.../java/org/apache/iotdb/db/conf/IoTDBConfig.java | 28 +++++++
.../org/apache/iotdb/db/conf/IoTDBDescriptor.java | 9 +++
.../groupby/LocalGroupByExecutorTri_ILTS.java | 93 ++++++++++++++++++++--
.../iotdb/db/integration/tri/MyTest_ILTS.java | 4 +
.../iotdb/tsfile/read/common/ChunkSuit4Tri.java | 3 +
.../iotdb/tsfile/read/common/IOMonitor2.java | 7 ++
7 files changed, 143 insertions(+), 5 deletions(-)
diff --git a/server/src/assembly/resources/conf/iotdb-engine.properties b/server/src/assembly/resources/conf/iotdb-engine.properties
index 4bbb732e4b3..417f7bca225 100644
--- a/server/src/assembly/resources/conf/iotdb-engine.properties
+++ b/server/src/assembly/resources/conf/iotdb-engine.properties
@@ -32,6 +32,10 @@ rps=4
numIterations=8
+acc_avg=true
+acc_rectangle=true
+acc_convex=true
+
####################
### enable CPV
####################
diff --git a/server/src/main/java/org/apache/iotdb/db/conf/IoTDBConfig.java b/server/src/main/java/org/apache/iotdb/db/conf/IoTDBConfig.java
index 9b2a255f732..d008f656bc5 100644
--- a/server/src/main/java/org/apache/iotdb/db/conf/IoTDBConfig.java
+++ b/server/src/main/java/org/apache/iotdb/db/conf/IoTDBConfig.java
@@ -452,6 +452,34 @@ public class IoTDBConfig {
private int numIterations = 8;
+ public boolean isAcc_avg() {
+ return acc_avg;
+ }
+
+ public void setAcc_avg(boolean acc_avg) {
+ this.acc_avg = acc_avg;
+ }
+
+ public boolean isAcc_rectangle() {
+ return acc_rectangle;
+ }
+
+ public void setAcc_rectangle(boolean acc_rectangle) {
+ this.acc_rectangle = acc_rectangle;
+ }
+
+ public boolean isAcc_convex() {
+ return acc_convex;
+ }
+
+ public void setAcc_convex(boolean acc_convex) {
+ this.acc_convex = acc_convex;
+ }
+
+ private boolean acc_avg = false;
+ private boolean acc_rectangle = true;
+ private boolean acc_convex = false;
+
public long getP1t() {
return p1t;
}
diff --git a/server/src/main/java/org/apache/iotdb/db/conf/IoTDBDescriptor.java b/server/src/main/java/org/apache/iotdb/db/conf/IoTDBDescriptor.java
index 7ce32d8b1be..96b4d496c01 100644
--- a/server/src/main/java/org/apache/iotdb/db/conf/IoTDBDescriptor.java
+++ b/server/src/main/java/org/apache/iotdb/db/conf/IoTDBDescriptor.java
@@ -550,6 +550,15 @@ public class IoTDBDescriptor {
conf.setNumIterations(
Integer.parseInt(
properties.getProperty("numIterations", Integer.toString(conf.getNumIterations()))));
+ conf.setAcc_avg(
+ Boolean.parseBoolean(
+ properties.getProperty("acc_avg", Boolean.toString(conf.isAcc_avg()))));
+ conf.setAcc_rectangle(
+ Boolean.parseBoolean(
+ properties.getProperty("acc_rectangle", Boolean.toString(conf.isAcc_rectangle()))));
+ conf.setAcc_convex(
+ Boolean.parseBoolean(
+ properties.getProperty("acc_convex", Boolean.toString(conf.isAcc_convex()))));
conf.setPerformanceStatDisplayInterval(
Long.parseLong(
diff --git a/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_ILTS.java b/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_ILTS.java
index e7c6a8f6f14..6261aae416a 100644
--- a/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_ILTS.java
+++ b/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_ILTS.java
@@ -126,7 +126,11 @@ public class LocalGroupByExecutorTri_ILTS implements GroupByExecutor {
ChunkMetadata chunkMetadata = chunkSuit4Tri.chunkMetadata;
long chunkMinTime = chunkMetadata.getStartTime();
long chunkMaxTime = chunkMetadata.getEndTime();
+ if (chunkMinTime >= endTime || chunkMaxTime < startTime) {
+ continue; // note futureChunkList is not sorted in advance, so not break, just skip
+ }
int idx1 = (int) Math.floor((chunkMinTime - startTime) * 1.0 / interval);
+ idx1 = Math.max(idx1, 0);
int idx2 = (int) Math.floor((chunkMaxTime - startTime) * 1.0 / interval);
idx2 = Math.min(idx2, N1 - 1);
for (int i = idx1; i <= idx2; i++) {
@@ -135,6 +139,16 @@ public class LocalGroupByExecutorTri_ILTS implements GroupByExecutor {
}
}
+ // // debug
+ // for (int i = 0; i < N1; i++) {
+ // List<ChunkSuit4Tri> chunkSuit4TriList = splitChunkList.get(i);
+ // if (chunkSuit4TriList != null) {
+ // for (ChunkSuit4Tri chunkSuit4Tri : chunkSuit4TriList) {
+ // System.out.println(i + "," + chunkSuit4Tri.chunkMetadata.getStartTime());
+ // }
+ // }
+ // }
+
} catch (IOException e) {
throw new QueryProcessException(e.getMessage());
}
@@ -191,6 +205,8 @@ public class LocalGroupByExecutorTri_ILTS implements GroupByExecutor {
throw new UnSupportedDataTypeException(String.valueOf(dataType));
}
// TODO: 用元数据sum&count加速
+ // 如果chunk没有被桶切开，可以直接用元数据里的sum和count
+
// 1. load page data if it hasn't been loaded
if (chunkSuit4Tri.pageReader == null) {
chunkSuit4Tri.pageReader =
@@ -227,19 +243,84 @@ public class LocalGroupByExecutorTri_ILTS implements GroupByExecutor {
}
}
// ========找到当前桶内距离lr连线最远的点========
- double maxArea = -1;
+ double maxDistance = -1;
long select_t = -1;
double select_v = -1;
List<ChunkSuit4Tri> chunkSuit4TriList = splitChunkList.get(b);
long localCurStartTime = startTime + (b) * interval;
long localCurEndTime = startTime + (b + 1) * interval;
+ if (CONFIG.isAcc_rectangle()) {
+ // TODO: 用元数据里落在桶内的FP&LP&BP&TP形成的rectangle加速
+ // 边点得到距离的紧致下限，角点得到距离的非紧致上限
+ // 先遍历一遍这些元数据，得到所有落在桶内的元数据点的最远点，更新maxDistance&select_t&select_v
+ // 然后遍历如果这个chunk的非紧致上限<=当前已知的maxDistance，那么整个chunk都不用管了
+ for (ChunkSuit4Tri chunkSuit4Tri : chunkSuit4TriList) {
+ long[] rect_t =
+ new long[] {
+ chunkSuit4Tri.chunkMetadata.getStartTime(), // FPt
+ chunkSuit4Tri.chunkMetadata.getEndTime(), // LPt
+ chunkSuit4Tri.chunkMetadata.getStatistics().getBottomTimestamp(), // BPt
+ chunkSuit4Tri.chunkMetadata.getStatistics().getTopTimestamp() // TPt
+ };
+ double[] rect_v =
+ new double[] {
+ (double) chunkSuit4Tri.chunkMetadata.getStatistics().getFirstValue(), // FPv
+ (double) chunkSuit4Tri.chunkMetadata.getStatistics().getLastValue(), // LPv
+ (double) chunkSuit4Tri.chunkMetadata.getStatistics().getMinValue(), // BPv
+ (double) chunkSuit4Tri.chunkMetadata.getStatistics().getMaxValue() // TPv
+ };
+ // 用落在桶内的元数据点（紧致下限）更新maxDistance&select_t&select_v
+ for (int i = 0; i < 4; i++) {
+ if (rect_t[i] >= localCurStartTime && rect_t[i] < localCurEndTime) {
+ double distance =
+ IOMonitor2.calculateDistance(lt, lv, rect_t[i], rect_v[i], rt, rv);
+ if (distance > maxDistance) {
+ maxDistance = distance;
+ select_t = rect_t[i];
+ select_v = rect_v[i];
+ }
+ }
+ }
+ // 用四个角点计算每个块的相对于当前固定线的非紧致上限
+ // 注意第一步是直接赋值而不是和旧的比较，因为距离是相对于线L的，每次迭代每个分桶下的L不同
+ chunkSuit4Tri.distance_loose_upper_bound =
+ IOMonitor2.calculateDistance(lt, lv, rect_t[0], rect_v[2], rt, rv); // FPt,BPv,左下角
+ chunkSuit4Tri.distance_loose_upper_bound =
+ Math.max(
+ chunkSuit4Tri.distance_loose_upper_bound,
+ IOMonitor2.calculateDistance(
+ lt, lv, rect_t[0], rect_v[3], rt, rv)); // FPt,TPv,左上角
+ chunkSuit4Tri.distance_loose_upper_bound =
+ Math.max(
+ chunkSuit4Tri.distance_loose_upper_bound,
+ IOMonitor2.calculateDistance(
+ lt, lv, rect_t[1], rect_v[2], rt, rv)); // LPt,BPv,右下角
+ chunkSuit4Tri.distance_loose_upper_bound =
+ Math.max(
+ chunkSuit4Tri.distance_loose_upper_bound,
+ IOMonitor2.calculateDistance(
+ lt, lv, rect_t[1], rect_v[3], rt, rv)); // LPt,TPv,右上角
+ }
+ }
// 遍历所有与当前桶overlap的chunks
for (ChunkSuit4Tri chunkSuit4Tri : chunkSuit4TriList) {
TSDataType dataType = chunkSuit4Tri.chunkMetadata.getDataType();
if (dataType != TSDataType.DOUBLE) {
throw new UnSupportedDataTypeException(String.valueOf(dataType));
}
- // TODO: 用FP&LP&BP&TP形成的rectangle加速
+ // TODO: (continue)用元数据里落在桶内的FP&LP&BP&TP形成的rectangle加速
+ // 边点得到距离的紧致下限，角点得到距离的非紧致上限
+ // 如果这个chunk的非紧致上限<=当前已知的maxDistance，那么整个chunk都不用管了
+ if (CONFIG.isAcc_rectangle()) {
+ // （当一个chunk的非紧致上限=紧致下限的时候，意味着有角点和边点重合，
+ // 如果这个上限是maxDistance，在“用元数据点/紧致下限更新maxDistance&select_t&select_v”
+ // 步骤中已经赋值了这个边点，所以这里跳过没关系）
+ if (chunkSuit4Tri.distance_loose_upper_bound <= maxDistance) {
+ // System.out.println("skip" + b + "," +
+ // chunkSuit4Tri.chunkMetadata.getStartTime());
+ continue;
+ }
+ }
// load page data if it hasn't been loaded
if (chunkSuit4Tri.pageReader == null) {
chunkSuit4Tri.pageReader =
@@ -253,6 +334,8 @@ public class LocalGroupByExecutorTri_ILTS implements GroupByExecutor {
}
PageReader pageReader = chunkSuit4Tri.pageReader;
// TODO: 用凸包bitmap加速
+ // 如果块被分桶边界切开，那还是逐点遍历
+ // 否则块完整落在桶内时，用凸包规则快速找到这个块中距离lr连线最远的点，最后和全局当前最远结果点比较
for (int j = 0; j < chunkSuit4Tri.chunkMetadata.getStatistics().getCount(); j++) {
long timestamp = pageReader.timeBuffer.getLong(j * 8);
if (timestamp < localCurStartTime) {
@@ -262,9 +345,9 @@ public class LocalGroupByExecutorTri_ILTS implements GroupByExecutor {
} else { // localCurStartTime<=t<localCurEndTime
ByteBuffer valueBuffer = pageReader.valueBuffer;
double v = valueBuffer.getDouble(pageReader.timeBufferLength + j * 8);
- double area = IOMonitor2.calculateTri(lt, lv, timestamp, v, rt, rv);
- if (area > maxArea) {
- maxArea = area;
+ double distance = IOMonitor2.calculateDistance(lt, lv, timestamp, v, rt, rv);
+ if (distance > maxDistance) {
+ maxDistance = distance;
select_t = timestamp;
select_v = v;
}
diff --git a/server/src/test/java/org/apache/iotdb/db/integration/tri/MyTest_ILTS.java b/server/src/test/java/org/apache/iotdb/db/integration/tri/MyTest_ILTS.java
index c46c691dac2..7f489adee45 100644
--- a/server/src/test/java/org/apache/iotdb/db/integration/tri/MyTest_ILTS.java
+++ b/server/src/test/java/org/apache/iotdb/db/integration/tri/MyTest_ILTS.java
@@ -74,6 +74,9 @@ public class MyTest_ILTS {
config.setEnableTri("ILTS");
// config.setNumIterations(4);
+ config.setAcc_avg(false);
+ config.setAcc_rectangle(true);
+ config.setAcc_convex(false);
config.setEnableCPV(false);
TSFileDescriptor.getInstance().getConfig().setEnableMinMaxLSM(false);
@@ -227,6 +230,7 @@ public class MyTest_ILTS {
@Test
public void test2_2() {
prepareData2();
+ // https://github.com/LeiRui/iotdb/assets/33376433/bca2de97-47ba-40b9-9e41-353de7a6ab0e
config.setNumIterations(1); // result equals LTTB
String res =
"-1.2079272[0],1.101946[200],-0.523204[300],0.145359[500],-1.014322[700],0.532565[900],"
diff --git a/tsfile/src/main/java/org/apache/iotdb/tsfile/read/common/ChunkSuit4Tri.java b/tsfile/src/main/java/org/apache/iotdb/tsfile/read/common/ChunkSuit4Tri.java
index 0f010917e93..5e2388debde 100644
--- a/tsfile/src/main/java/org/apache/iotdb/tsfile/read/common/ChunkSuit4Tri.java
+++ b/tsfile/src/main/java/org/apache/iotdb/tsfile/read/common/ChunkSuit4Tri.java
@@ -39,6 +39,9 @@ public class ChunkSuit4Tri {
// pageReader does not refer to the same deleteInterval as those in chunkMetadata
// after chunkMetadata executes insertIntoSortedDeletions
+ // not fixed, because the relative line L varies for each bucket in each iteration
+ public double distance_loose_upper_bound = -1;
+
public ChunkSuit4Tri(ChunkMetadata chunkMetadata) {
this.chunkMetadata = chunkMetadata;
this.lastReadPos = 0;
diff --git a/tsfile/src/main/java/org/apache/iotdb/tsfile/read/common/IOMonitor2.java b/tsfile/src/main/java/org/apache/iotdb/tsfile/read/common/IOMonitor2.java
index c55ee561655..e6a70882edf 100644
--- a/tsfile/src/main/java/org/apache/iotdb/tsfile/read/common/IOMonitor2.java
+++ b/tsfile/src/main/java/org/apache/iotdb/tsfile/read/common/IOMonitor2.java
@@ -261,6 +261,13 @@ public class IOMonitor2 {
return Math.abs((t1 - t3) * (v2 - v3) - (t2 - t3) * (v1 - v3)) / 2;
}
+ public static double calculateDistance(
+ double tl, double vl, double t, double v, double tr, double vr) {
+ double numerator = Math.abs((vr - vl) * t + (tl - tr) * v + tr * vl - tl * vr);
+ double denominator = Math.sqrt((vr - vl) * (vr - vl) + (tl - tr) * (tl - tr));
+ return numerator / denominator;
+ }
+
public static void addMeasure(Operation operation, long elapsedTimeInNanosecond) {
switch (operation) {
case DCP_Server_Query_Execute: