Skip to content

Commit 6d2b951

Browse files
committed
[fix](ivm) Estimate a stream read's row count from what the read answers with
### What problem does this PR solve? Issue Number: None Related PR: None Problem Summary: A scan that reads a table stream is planned over a lightweight wrapper of the base table: OlapTableWrapper for the base-table reads (stream@reset, and the base part of a snapshot read), OlapChangelogTableWrapper for the changelog part. The wrapper delegates partition lookups but holds no partitions of its own, while OlapTable derives a row count by iterating that map. Every scan over a wrapper was therefore estimated at zero rows, which StatsCalculator.computeOlapScan raises to one: a read of a four-billion-row table looked like a one-row scan, and the optimizer could pick the real large side as the broadcast build, exhausting the task memory limit of an incremental view maintenance refresh. In cloud mode NormalizeOlapTableStreamScan wraps the base table for every read once the cloud read states are installed, so both stream@reset() and stream@snapshot() were estimated at one row. Fix, part one -- ask the table the wrapper reads: - OlapTableWrapper delegates getRowCountForIndex, getRowCountForPartitionIndex, getPartitionNum and getPartitionItemOrAnalysisException to the table it wraps. A reset read, and a snapshot read whose offsets already reached the end, see exactly that table's content; a snapshot read of an older offset is bounded by it. With the partition count in place, a partition-pruned scan takes the statistics calculator's per-partition path, which looks up the selected partitions' items to tighten the partition-key min/max. - StatsCalculator.getOlapTableRowCount asks a wrapper which records its own estimate before it reads the statistics record: that record describes the base index of the table, and for a changelog read it has no entry at all, which would leave the read at the one-row floor. Fix, part two -- record what a stream read answers with: An incremental read answers with the change rows written after the stream's offset, and a snapshot read with the image at that offset. Neither is the row count of the table, and the frontend cannot derive either from the metadata: the changelog index of a partition holds the change rows of every offset range. - OlapTableStream records, next to each partition's offset, a PartitionStreamState: the row count of the partition's changelog index (P) and of its base index (Q) at the moment the offset advanced (Gson field "ps", written by initializeLocalOffsets and by unprotectedUpdateStreamUpdate; in cloud mode TableStreamManager.recordPartitionStreamStates records it after the commit RPC succeeds). - A changelog read is estimated with max(P_now - P_stored, P_now when the counters are unusable): a read of an empty range is recognized by the TSOs, which do not lag behind like the row counts, and everything else takes a value which bounds the read rather than the one-row floor. - A snapshot read is estimated with max(Q, current base rows), or base rows plus the change rows of the range for a unique or aggregating table, whose image also holds the rows deleted after the offset. Every rule errs on the large side: over-estimating only makes the optimizer plan the read differently, while under-estimating lets a large read become the build side of a broadcast join. The estimate relies on the tablet row counts the frontend holds, so it is a bound once the backends have reported them (a stream records its counters from those reports, and the regression waits for them); a load followed by a refresh before the report arrives still falls back to a value of the right order of magnitude rather than to one row. ### Release note Fix stream reads (including incremental view maintenance refreshes) estimating every scan at one row, which could make the optimizer broadcast a very large build side and exhaust memory during a refresh. An incremental read of a stream is now estimated with the change rows after its offset, and a snapshot read with the image at that offset. ### Check List (For Author) - Test: Unit test / Regression test / Manual test - Unit test: OlapTableWrapperTest (row count delegation; the changelog wrapper falls back to the changelog row count; a recorded estimate overrides the wrapped table; partition item lookup delegation). - Unit test: PartitionStreamStateTest (the estimate rules: an empty range, a normal delta, no baseline, counters moving backwards, unreported counts, an unknown range, both snapshot rules). - Unit test: StreamScanRowCountTest (TestWithFeService: a changelog table, a stream over it and a row count injected as ALTER TABLE ... SET STATS does; the whole planner runs and the stream scan is estimated at the injected row count for both a snapshot and a reset read, inside a join). - Regression test: changelog_p0/test_stream_scan_row_count, which runs in both the shared-nothing and the cloud P0 pipelines: reset and snapshot estimates, then consuming the stream and checking that the incremental read is planned as an empty relation when nothing was written and at three rows after three more are loaded. - Manual test: the reproduction below, verified through query profiles on a local cloud cluster, and the regression suite run against a local shared-nothing cluster. - Behavior changed: Yes. Scans over a stream read are estimated from what the read answers with instead of one row; an incremental read is no longer unknown to the optimizer. - Does this need documentation: No
1 parent 2a4191c commit 6d2b951

13 files changed

Lines changed: 1035 additions & 19 deletions

File tree

‎fe/fe-core/src/main/java/org/apache/doris/catalog/OlapChangelogTableWrapper.java‎

Lines changed: 19 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -35,6 +35,19 @@
3535

3636
/**
3737
* A lightweight wrapper base for read changelog of table
38+
*
39+
* <p>A changelog scan reads the change rows of an offset range, not the table, and neither the
40+
* range nor the changelog index reports how many change rows it holds: a read that starts at the
41+
* beginning of the stream returns about the table's rows while a delta returns a few, and FE
42+
* cannot tell the two apart.
43+
*
44+
* <p>A stream read knows better: it records, next to the offset it reads from, the row count of
45+
* the partition's changelog index, and hands the difference to this wrapper as the per-partition
46+
* estimate (see {@link org.apache.doris.catalog.stream.PartitionStreamState}). Without such an
47+
* estimate the wrapper answers with the row count of the changelog index, i.e. the size of the
48+
* whole changelog: that over-estimates a delta, but a value in the right order of magnitude keeps
49+
* the optimizer from treating the read as an empty relation, which is the direction that costs
50+
* memory.
3851
*/
3952
public class OlapChangelogTableWrapper extends OlapTableWrapper {
4053

@@ -50,8 +63,13 @@ public OlapChangelogTableWrapper(OlapTable originTable, Map<Long, Pair<Long, Lon
5063

5164
public OlapChangelogTableWrapper(OlapTable originTable, Map<Long, Pair<Long, Long>> partitionOffsetMap,
5265
Map<Long, Long> partitionVisibleVersionMap) {
66+
this(originTable, partitionOffsetMap, partitionVisibleVersionMap, Collections.emptyMap());
67+
}
68+
69+
public OlapChangelogTableWrapper(OlapTable originTable, Map<Long, Pair<Long, Long>> partitionOffsetMap,
70+
Map<Long, Long> partitionVisibleVersionMap, Map<Long, Long> partitionRowCounts) {
5371
super(originTable, originTable.getName(), originTable.getChangelogIndexMeta().getSchema(), KeysType.DUP_KEYS,
54-
partitionOffsetMap, partitionVisibleVersionMap);
72+
partitionOffsetMap, partitionVisibleVersionMap, partitionRowCounts);
5573
this.changelogIndexMeta = originTable.getChangelogIndexMeta();
5674
Preconditions.checkNotNull(changelogIndexMeta, "changelog meta is null, table=%s", originTable.getName());
5775
this.setBaseIndexId(changelogIndexMeta.getIndexId());

‎fe/fe-core/src/main/java/org/apache/doris/catalog/OlapTableWrapper.java‎

Lines changed: 79 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,7 @@
1818
package org.apache.doris.catalog;
1919

2020
import org.apache.doris.catalog.stream.StreamReadMode;
21+
import org.apache.doris.common.AnalysisException;
2122
import org.apache.doris.common.Pair;
2223

2324
import com.google.common.collect.ImmutableMap;
@@ -43,22 +44,37 @@ public class OlapTableWrapper extends OlapTable {
4344
protected final OlapTable originTable;
4445
private final Map<Long, Pair<Long, Long>> partitionOffsetMap; // partitionId -> (startOffset, endOffset)
4546
private final Map<Long, Long> partitionVisibleVersionMap;
47+
// Per-partition row counts the scan is estimated with, when the caller knows better than the
48+
// table it wraps can answer: a stream read returns the rows of a range, or the image at an
49+
// offset, which neither the changelog index nor the base table reports. Empty means that the
50+
// table it wraps answers, which is the case for every wrapper outside a stream read.
51+
private final Map<Long, Long> partitionRowCounts;
4652

4753
protected OlapTableWrapper(OlapTable originTable, String wrapperName, List<Column> baseSchema, KeysType keysType,
4854
Map<Long, Pair<Long, Long>> partitionOffsetMap) {
49-
this(originTable, wrapperName, baseSchema, keysType, partitionOffsetMap, Collections.emptyMap());
55+
this(originTable, wrapperName, baseSchema, keysType, partitionOffsetMap, Collections.emptyMap(),
56+
Collections.emptyMap());
5057
}
5158

5259
protected OlapTableWrapper(OlapTable originTable, String wrapperName, List<Column> baseSchema, KeysType keysType,
5360
Map<Long, Pair<Long, Long>> partitionOffsetMap,
5461
Map<Long, Long> partitionVisibleVersionMap) {
62+
this(originTable, wrapperName, baseSchema, keysType, partitionOffsetMap, partitionVisibleVersionMap,
63+
Collections.emptyMap());
64+
}
65+
66+
protected OlapTableWrapper(OlapTable originTable, String wrapperName, List<Column> baseSchema, KeysType keysType,
67+
Map<Long, Pair<Long, Long>> partitionOffsetMap,
68+
Map<Long, Long> partitionVisibleVersionMap,
69+
Map<Long, Long> partitionRowCounts) {
5570
super(originTable.getId(), wrapperName, baseSchema,
5671
keysType, originTable.getPartitionInfo(), originTable.getDefaultDistributionInfo());
5772
this.originTable = originTable;
5873
this.setBaseIndexId(originTable.getBaseIndexId());
5974
this.setQualifiedDbName(originTable.getQualifiedDbName());
6075
this.partitionOffsetMap = partitionOffsetMap;
6176
this.partitionVisibleVersionMap = ImmutableMap.copyOf(partitionVisibleVersionMap);
77+
this.partitionRowCounts = ImmutableMap.copyOf(partitionRowCounts);
6278
}
6379

6480
public OlapTableWrapper(OlapTable originTable, Map<Long, Pair<Long, Long>> partitionOffsetMap) {
@@ -67,13 +83,19 @@ public OlapTableWrapper(OlapTable originTable, Map<Long, Pair<Long, Long>> parti
6783

6884
public OlapTableWrapper(OlapTable originTable, Map<Long, Pair<Long, Long>> partitionOffsetMap,
6985
Map<Long, Long> partitionVisibleVersionMap) {
86+
this(originTable, partitionOffsetMap, partitionVisibleVersionMap, Collections.emptyMap());
87+
}
88+
89+
public OlapTableWrapper(OlapTable originTable, Map<Long, Pair<Long, Long>> partitionOffsetMap,
90+
Map<Long, Long> partitionVisibleVersionMap, Map<Long, Long> partitionRowCounts) {
7091
super(originTable.getId(), originTable.getName(), originTable.getBaseSchema(),
7192
originTable.getKeysType(), originTable.getPartitionInfo(), originTable.getDefaultDistributionInfo());
7293
this.originTable = originTable;
7394
this.setBaseIndexId(originTable.getBaseIndexId());
7495
this.setQualifiedDbName(originTable.getQualifiedDbName());
7596
this.partitionOffsetMap = partitionOffsetMap;
7697
this.partitionVisibleVersionMap = ImmutableMap.copyOf(partitionVisibleVersionMap);
98+
this.partitionRowCounts = ImmutableMap.copyOf(partitionRowCounts);
7799
}
78100

79101
protected OlapTableWrapper(OlapTable originTable) {
@@ -149,6 +171,11 @@ public Partition getPartition(long partitionId) {
149171
return originTable.getPartition(partitionId);
150172
}
151173

174+
@Override
175+
public PartitionItem getPartitionItemOrAnalysisException(String partitionName) throws AnalysisException {
176+
return originTable.getPartitionItemOrAnalysisException(partitionName);
177+
}
178+
152179
@Override
153180
public Set<String> getPartitionNames() {
154181
return originTable.getPartitionNames();
@@ -190,6 +217,57 @@ public MaterializedIndex getBaseIndex() {
190217
return originTable.getBaseIndex();
191218
}
192219

220+
/**
221+
* Row counts are derived from the partitions of the table, and this wrapper holds none of its
222+
* own -- it only delegates partition lookups to the table it wraps. The inherited methods
223+
* iterate the wrapper's private partition map, so every scan over a wrapper would be estimated
224+
* at zero rows, which the statistics calculator raises to one; a reset read of a
225+
* four-billion-row table would then look like a one-row build side to the optimizer.
226+
*
227+
* <p>Delegating answers the read with the table it is over: a reset read, and a snapshot read
228+
* whose offsets already reached the end, see exactly that table's content, and a snapshot read
229+
* of an older offset is bounded by it (the table only grows for the duplicate-key tables this
230+
* wrapper serves in that way).
231+
*
232+
* <p>A caller which knows what the read returns records it per partition and overrides this:
233+
* a stream read answers with a range of change rows, or with the image at an offset, and
234+
* neither is the row count of the table it reads.
235+
*/
236+
@Override
237+
public long getRowCountForIndex(long indexId, boolean strict) {
238+
long estimate = getRowCountEstimate();
239+
return estimate < 0 ? originTable.getRowCountForIndex(indexId, strict) : estimate;
240+
}
241+
242+
@Override
243+
public long getRowCountForPartitionIndex(long partitionId, long indexId, boolean strict) {
244+
Long rowCount = partitionRowCounts.get(partitionId);
245+
if (rowCount != null) {
246+
return rowCount;
247+
}
248+
return originTable.getRowCountForPartitionIndex(partitionId, indexId, strict);
249+
}
250+
251+
/**
252+
* The row count the caller recorded for this scan, or {@code -1} when the table it wraps
253+
* answers instead.
254+
*/
255+
public long getRowCountEstimate() {
256+
if (partitionRowCounts.isEmpty()) {
257+
return TableIf.UNKNOWN_ROW_COUNT;
258+
}
259+
long total = 0;
260+
for (long rowCount : partitionRowCounts.values()) {
261+
total += rowCount;
262+
}
263+
return total;
264+
}
265+
266+
@Override
267+
public int getPartitionNum() {
268+
return originTable.getPartitionNum();
269+
}
270+
193271
public Pair<Long, Long> getPartitionOffset(long partitionId) {
194272
return partitionOffsetMap.get(partitionId);
195273
}

‎fe/fe-core/src/main/java/org/apache/doris/catalog/stream/OlapTableStream.java‎

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -32,18 +32,22 @@
3232

3333
import com.google.common.base.Preconditions;
3434
import com.google.common.collect.ImmutableList;
35+
import com.google.common.collect.ImmutableMap;
3536
import com.google.gson.annotations.SerializedName;
3637

3738
import java.io.DataInput;
3839
import java.io.DataOutput;
3940
import java.io.IOException;
4041
import java.util.ArrayList;
42+
import java.util.Collection;
4143
import java.util.HashMap;
4244
import java.util.HashSet;
4345
import java.util.List;
4446
import java.util.Map;
4547
import java.util.Set;
48+
import java.util.concurrent.ConcurrentHashMap;
4649
import java.util.function.Predicate;
50+
import java.util.stream.Collectors;
4751

4852
public class OlapTableStream extends BaseTableStream {
4953

@@ -56,6 +60,13 @@ public class OlapTableStream extends BaseTableStream {
5660
@SerializedName("hpt")
5761
private Map<Long, Long> historicalPartitionTSO;
5862

63+
// Row counts of the changelog index and of the base index of each partition at the moment its
64+
// offset advanced. They give a stream read a baseline to estimate the rows it will return:
65+
// the row count of the changelog index alone is the size of the whole changelog, not of the
66+
// range being read. See PartitionStreamState.
67+
@SerializedName("ps")
68+
private Map<Long, PartitionStreamState> partitionStates;
69+
5970
// for persist
6071
public OlapTableStream() {
6172
super();
@@ -128,6 +139,58 @@ public void setPropertiesWithoutOffsetInitialization(Map<String, String> propert
128139
super.setProperties(properties);
129140
}
130141

142+
private synchronized Map<Long, PartitionStreamState> partitionStates() {
143+
if (!(partitionStates instanceof ConcurrentHashMap)) {
144+
// A record read back from an image holds whatever map the deserialization built, which
145+
// is not safe for the concurrent reads and the replacement the planner and the offset
146+
// advance do on it.
147+
partitionStates = partitionStates == null
148+
? new ConcurrentHashMap<>() : new ConcurrentHashMap<>(partitionStates);
149+
}
150+
return partitionStates;
151+
}
152+
153+
@Override
154+
public void gsonPostProcess() throws IOException {
155+
super.gsonPostProcess();
156+
partitionStates();
157+
}
158+
159+
public PartitionStreamState getPartitionStreamState(long partitionId) {
160+
return partitionStates().get(partitionId);
161+
}
162+
163+
public Map<Long, PartitionStreamState> getPartitionStates() {
164+
return ImmutableMap.copyOf(partitionStates());
165+
}
166+
167+
/**
168+
* Record, for each of the given partitions, the row counts the estimate of a read is built
169+
* from. Called whenever the offsets of those partitions move, so that the recorded state and
170+
* the offset describe the same point in time: the counters are the ones the FE holds when the
171+
* offset advances, and a backend report which arrives later only makes the next estimate
172+
* larger, never smaller.
173+
*/
174+
public void unprotectedRecordPartitionStreamStates(Collection<Long> partitionIds) {
175+
OlapTable baseTable = getBaseTableNullable();
176+
if (baseTable == null || partitionIds.isEmpty()) {
177+
return;
178+
}
179+
long changelogIndexId = baseTable.hasChangelog() ? baseTable.getChangelogIndexMeta().getIndexId() : -1;
180+
Map<Long, PartitionStreamState> states = partitionStates();
181+
for (Long partitionId : partitionIds) {
182+
if (baseTable.getPartition(partitionId) == null) {
183+
continue;
184+
}
185+
long changelogRowCount = changelogIndexId > 0
186+
? baseTable.getRowCountForPartitionIndex(partitionId, changelogIndexId, false)
187+
: PartitionStreamState.UNKNOWN_ROW_COUNT;
188+
long baseRowCount = baseTable.getRowCountForPartitionIndex(partitionId,
189+
baseTable.getBaseIndexId(), false);
190+
states.put(partitionId, new PartitionStreamState(changelogRowCount, baseRowCount));
191+
}
192+
}
193+
131194
private void initializeLocalOffsets() {
132195
// set offset according to baseTable
133196
OlapTable baseTable = getBaseTableNullable();
@@ -147,6 +210,10 @@ private void initializeLocalOffsets() {
147210
}
148211
);
149212
}
213+
// Both cases start from the partition TSO the stream was created at, so the counters have
214+
// the same baseline in both.
215+
unprotectedRecordPartitionStreamStates(baseTable.getPartitions().stream()
216+
.map(Partition::getId).collect(Collectors.toList()));
150217
}
151218

152219
public static OlapTableStream read(DataInput in) throws IOException {
@@ -318,6 +385,7 @@ public void unprotectedUpdateStreamUpdate(AbstractTableStreamUpdate update, Long
318385
partitionOffset.put(entry.getKey(), entry.getValue());
319386
partitionConsumptionTime.put(entry.getKey(), ts);
320387
}
388+
unprotectedRecordPartitionStreamStates(next.keySet());
321389
}
322390

323391
Set<Long> unprotectedCollectStalePartitionOffsetIds(Set<Long> validPartitionIds) {
@@ -341,6 +409,11 @@ Set<Long> unprotectedCollectStalePartitionOffsetIds(Set<Long> validPartitionIds)
341409
}
342410
}
343411
}
412+
for (Long partitionId : partitionStates().keySet()) {
413+
if (!validPartitionIds.contains(partitionId)) {
414+
stalePartitionIds.add(partitionId);
415+
}
416+
}
344417
return stalePartitionIds;
345418
}
346419

@@ -353,6 +426,7 @@ void unprotectedPrunePartitionOffsets(Set<Long> partitionIds) {
353426
if (historicalPartitionTSO != null) {
354427
historicalPartitionTSO.remove(partitionId);
355428
}
429+
partitionStates().remove(partitionId);
356430
}
357431
}
358432
}

0 commit comments

Comments
 (0)