yujun777 commented on code in PR #68648:
URL: https://github.com/apache/doris/pull/68648#discussion_r4225794971
##########
fe/fe-core/src/main/java/org/apache/doris/mtmv/MTMVRelatedPartitionDescTransferGenerator.java:
##########
@@ -46,23 +48,119 @@ public class MTMVRelatedPartitionDescTransferGenerator
implements MTMVRelatedPar
public void apply(MTMVPartitionInfo mvPartitionInfo, Map<String, String>
mvProperties,
RelatedPartitionDescResult lastResult, List<Column>
partitionColumns,
Map<List<String>, Set<String>> queryUsedPartitionMap)
throws AnalysisException {
- Map<MTMVRelatedTableIf, Map<PartitionKeyDesc, Set<String>>> descs =
lastResult.getDescs();
+ Map<PartitionKeyDesc, Map<MTMVRelatedTableIf, Set<String>>> res =
+ mergeOverlappingListDescs(lastResult.getDescs());
+ if (mvPartitionInfo.getPctInfos().size() > 1) {
+ checkIntersect(res.keySet(), partitionColumns);
+ }
+ lastResult.setRes(res);
+ }
+
+ /**
+ * One MV partition per set of keys that meet, whichever table wrote them
down.
+ *
+ * <p>A partition of a list partitioned base table can hold several keys
of the MV's partition column, so
+ * two partitions -- of one table or of two -- can describe keys that
meet: an expired partition holding a
+ * key a retained partition also holds, for instance. An MV's own
partitions cannot overlap, so descs
+ * whose keys meet are one partition whose keys are the union of theirs,
and it names the partitions of
+ * every table whose keys are in it, which is what a refresh reads and
records for those keys.
+ *
+ * <p>Merging across tables, not within each of them, is what keeps the MV
buildable: two tables of a
+ * multi-table MV have to come out with the same descs, or one table's
merged desc repeats a key another
+ * table's desc holds and `checkIntersect` (or the partition creation
itself) rejects the MV.
+ *
+ * <p>Descs whose keys are disjoint stay as they are, and so does a desc
that is the only one in its
+ * group, so an MV whose base partitions do not meet keeps its partitions
and their names.
+ */
+ private Map<PartitionKeyDesc, Map<MTMVRelatedTableIf, Set<String>>>
mergeOverlappingListDescs(
+ Map<MTMVRelatedTableIf, Map<PartitionKeyDesc, Set<String>>> descs)
{
+ // A union-find over the keys: two descs whose keys meet end up in one
group, transitively, and each
+ // key is looked up once -- walking the groups per desc would be
quadratic in the number of partitions.
+ Map<List<PartitionValue>, List<PartitionValue>> groupOfKey =
Maps.newHashMap();
+ for (Map<PartitionKeyDesc, Set<String>> onePctDescs : descs.values()) {
+ for (PartitionKeyDesc desc : onePctDescs.keySet()) {
+ if (!desc.hasInValues()) {
+ continue;
+ }
+ List<PartitionValue> first =
desc.getInValues().iterator().next();
+ groupOfKey.putIfAbsent(first, first);
+ for (List<PartitionValue> key : desc.getInValues()) {
+ groupOfKey.putIfAbsent(key, key);
+ union(groupOfKey, first, key);
+ }
+ }
+ }
+ Map<List<PartitionValue>, Set<List<PartitionValue>>> keysOfGroup =
Maps.newHashMap();
+ for (List<PartitionValue> key : groupOfKey.keySet()) {
+ keysOfGroup.computeIfAbsent(find(groupOfKey, key), k ->
Sets.newHashSet()).add(key);
+ }
+ Map<PartitionKeyDesc, List<PartitionValue>> groupOfDesc =
Maps.newHashMap();
+ Map<List<PartitionValue>, PartitionKeyDesc> onlyDescOfGroup =
Maps.newHashMap();
+ for (Map<PartitionKeyDesc, Set<String>> onePctDescs : descs.values()) {
+ for (PartitionKeyDesc desc : onePctDescs.keySet()) {
+ if (!desc.hasInValues()) {
+ continue;
+ }
+ List<PartitionValue> group = find(groupOfKey,
desc.getInValues().iterator().next());
+ groupOfDesc.put(desc, group);
+ if (onlyDescOfGroup.put(group, desc) != null) {
Review Comment:
Fixed in 49f19a9a3ef. The bug was exactly the marker you describe: "this
group has one desc, keep it as it is" was a nullable value that each desc
overwrote, so the third desc in a group put itself back and the group was read
as that desc's keys alone -- the MV partition then held a subset of the keys it
was recorded with, and a committed key had no MV partition to be read into. The
count is now kept separately from the single desc.
Pinned by a chain of three: t11's partitions project to 2020-2021, 2021-2022
and 2022-2023, and the unit test asserts one MV partition with all four keys,
naming all three base partitions.
##########
fe/fe-core/src/main/java/org/apache/doris/mtmv/MTMVRelatedPartitionDescTransferGenerator.java:
##########
@@ -46,23 +48,119 @@ public class MTMVRelatedPartitionDescTransferGenerator
implements MTMVRelatedPar
public void apply(MTMVPartitionInfo mvPartitionInfo, Map<String, String>
mvProperties,
RelatedPartitionDescResult lastResult, List<Column>
partitionColumns,
Map<List<String>, Set<String>> queryUsedPartitionMap)
throws AnalysisException {
- Map<MTMVRelatedTableIf, Map<PartitionKeyDesc, Set<String>>> descs =
lastResult.getDescs();
+ Map<PartitionKeyDesc, Map<MTMVRelatedTableIf, Set<String>>> res =
+ mergeOverlappingListDescs(lastResult.getDescs());
+ if (mvPartitionInfo.getPctInfos().size() > 1) {
+ checkIntersect(res.keySet(), partitionColumns);
+ }
+ lastResult.setRes(res);
+ }
+
+ /**
+ * One MV partition per set of keys that meet, whichever table wrote them
down.
+ *
+ * <p>A partition of a list partitioned base table can hold several keys
of the MV's partition column, so
+ * two partitions -- of one table or of two -- can describe keys that
meet: an expired partition holding a
+ * key a retained partition also holds, for instance. An MV's own
partitions cannot overlap, so descs
+ * whose keys meet are one partition whose keys are the union of theirs,
and it names the partitions of
+ * every table whose keys are in it, which is what a refresh reads and
records for those keys.
+ *
+ * <p>Merging across tables, not within each of them, is what keeps the MV
buildable: two tables of a
+ * multi-table MV have to come out with the same descs, or one table's
merged desc repeats a key another
+ * table's desc holds and `checkIntersect` (or the partition creation
itself) rejects the MV.
+ *
+ * <p>Descs whose keys are disjoint stay as they are, and so does a desc
that is the only one in its
+ * group, so an MV whose base partitions do not meet keeps its partitions
and their names.
+ */
+ private Map<PartitionKeyDesc, Map<MTMVRelatedTableIf, Set<String>>>
mergeOverlappingListDescs(
+ Map<MTMVRelatedTableIf, Map<PartitionKeyDesc, Set<String>>> descs)
{
+ // A union-find over the keys: two descs whose keys meet end up in one
group, transitively, and each
+ // key is looked up once -- walking the groups per desc would be
quadratic in the number of partitions.
+ Map<List<PartitionValue>, List<PartitionValue>> groupOfKey =
Maps.newHashMap();
+ for (Map<PartitionKeyDesc, Set<String>> onePctDescs : descs.values()) {
+ for (PartitionKeyDesc desc : onePctDescs.keySet()) {
+ if (!desc.hasInValues()) {
+ continue;
+ }
+ List<PartitionValue> first =
desc.getInValues().iterator().next();
+ groupOfKey.putIfAbsent(first, first);
+ for (List<PartitionValue> key : desc.getInValues()) {
+ groupOfKey.putIfAbsent(key, key);
+ union(groupOfKey, first, key);
+ }
+ }
+ }
+ Map<List<PartitionValue>, Set<List<PartitionValue>>> keysOfGroup =
Maps.newHashMap();
+ for (List<PartitionValue> key : groupOfKey.keySet()) {
+ keysOfGroup.computeIfAbsent(find(groupOfKey, key), k ->
Sets.newHashSet()).add(key);
+ }
+ Map<PartitionKeyDesc, List<PartitionValue>> groupOfDesc =
Maps.newHashMap();
+ Map<List<PartitionValue>, PartitionKeyDesc> onlyDescOfGroup =
Maps.newHashMap();
+ for (Map<PartitionKeyDesc, Set<String>> onePctDescs : descs.values()) {
+ for (PartitionKeyDesc desc : onePctDescs.keySet()) {
+ if (!desc.hasInValues()) {
+ continue;
+ }
+ List<PartitionValue> group = find(groupOfKey,
desc.getInValues().iterator().next());
+ groupOfDesc.put(desc, group);
+ if (onlyDescOfGroup.put(group, desc) != null) {
+ // A second desc in this group: its keys are the group's
from here on.
+ onlyDescOfGroup.put(group, null);
+ }
+ }
+ }
Map<PartitionKeyDesc, Map<MTMVRelatedTableIf, Set<String>>> res =
Maps.newHashMap();
for (Entry<MTMVRelatedTableIf, Map<PartitionKeyDesc, Set<String>>>
entry : descs.entrySet()) {
- MTMVRelatedTableIf pctTable = entry.getKey();
- Map<PartitionKeyDesc, Set<String>> onePctDescs = entry.getValue();
- for (Entry<PartitionKeyDesc, Set<String>> onePctEntry :
onePctDescs.entrySet()) {
- PartitionKeyDesc partitionKeyDesc = onePctEntry.getKey();
- Set<String> partitionNames = onePctEntry.getValue();
- Map<MTMVRelatedTableIf, Set<String>> partitionKeyDescMap =
res.computeIfAbsent(partitionKeyDesc,
- k -> new HashMap<>());
- partitionKeyDescMap.put(pctTable, partitionNames);
+ for (Entry<PartitionKeyDesc, Set<String>> onePctEntry :
entry.getValue().entrySet()) {
+ PartitionKeyDesc desc = onePctEntry.getKey();
+ if (desc.hasInValues()) {
+ List<PartitionValue> group = groupOfDesc.get(desc);
+ PartitionKeyDesc only = onlyDescOfGroup.get(group);
+ desc = only == null
Review Comment:
Fixed in 49f19a9a3ef, along the line you point at. The descs of every
partition of a table are grouped first, and the query filter is applied to
which MV partitions are named rather than to which descs exist: a query pruned
to `p_single` now comes out with the merged desc `{2020,2038}` that `CREATE`
stored, with only the queried partition named in it, so
`calculatePartitionMappings` matches the MV partition the MV holds and
`getMtmvPartitionsByRelatedPartitions` does not reject the rewrite.
The grouping helper is shared by both generators now
(`MTMVPartitionUtil#mergedListDescs`), which is what made the ordering
possible: it is the same computation, run once over the partitions of a table
before the filter and once across the tables of the MV.
Test: the added `t8` shape with `queryUsed = {p_single}` asserts the emitted
desc holds both keys and the name is the queried partition only.
##########
fe/fe-core/src/main/java/org/apache/doris/mtmv/MTMVRelatedPartitionDescTransferGenerator.java:
##########
@@ -46,23 +48,119 @@ public class MTMVRelatedPartitionDescTransferGenerator
implements MTMVRelatedPar
public void apply(MTMVPartitionInfo mvPartitionInfo, Map<String, String>
mvProperties,
RelatedPartitionDescResult lastResult, List<Column>
partitionColumns,
Map<List<String>, Set<String>> queryUsedPartitionMap)
throws AnalysisException {
- Map<MTMVRelatedTableIf, Map<PartitionKeyDesc, Set<String>>> descs =
lastResult.getDescs();
+ Map<PartitionKeyDesc, Map<MTMVRelatedTableIf, Set<String>>> res =
+ mergeOverlappingListDescs(lastResult.getDescs());
+ if (mvPartitionInfo.getPctInfos().size() > 1) {
+ checkIntersect(res.keySet(), partitionColumns);
+ }
+ lastResult.setRes(res);
+ }
+
+ /**
+ * One MV partition per set of keys that meet, whichever table wrote them
down.
+ *
+ * <p>A partition of a list partitioned base table can hold several keys
of the MV's partition column, so
+ * two partitions -- of one table or of two -- can describe keys that
meet: an expired partition holding a
+ * key a retained partition also holds, for instance. An MV's own
partitions cannot overlap, so descs
+ * whose keys meet are one partition whose keys are the union of theirs,
and it names the partitions of
+ * every table whose keys are in it, which is what a refresh reads and
records for those keys.
+ *
+ * <p>Merging across tables, not within each of them, is what keeps the MV
buildable: two tables of a
+ * multi-table MV have to come out with the same descs, or one table's
merged desc repeats a key another
+ * table's desc holds and `checkIntersect` (or the partition creation
itself) rejects the MV.
+ *
+ * <p>Descs whose keys are disjoint stay as they are, and so does a desc
that is the only one in its
+ * group, so an MV whose base partitions do not meet keeps its partitions
and their names.
+ */
+ private Map<PartitionKeyDesc, Map<MTMVRelatedTableIf, Set<String>>>
mergeOverlappingListDescs(
+ Map<MTMVRelatedTableIf, Map<PartitionKeyDesc, Set<String>>> descs)
{
+ // A union-find over the keys: two descs whose keys meet end up in one
group, transitively, and each
+ // key is looked up once -- walking the groups per desc would be
quadratic in the number of partitions.
+ Map<List<PartitionValue>, List<PartitionValue>> groupOfKey =
Maps.newHashMap();
+ for (Map<PartitionKeyDesc, Set<String>> onePctDescs : descs.values()) {
+ for (PartitionKeyDesc desc : onePctDescs.keySet()) {
+ if (!desc.hasInValues()) {
+ continue;
+ }
+ List<PartitionValue> first =
desc.getInValues().iterator().next();
+ groupOfKey.putIfAbsent(first, first);
+ for (List<PartitionValue> key : desc.getInValues()) {
+ groupOfKey.putIfAbsent(key, key);
+ union(groupOfKey, first, key);
+ }
+ }
+ }
+ Map<List<PartitionValue>, Set<List<PartitionValue>>> keysOfGroup =
Maps.newHashMap();
+ for (List<PartitionValue> key : groupOfKey.keySet()) {
+ keysOfGroup.computeIfAbsent(find(groupOfKey, key), k ->
Sets.newHashSet()).add(key);
+ }
+ Map<PartitionKeyDesc, List<PartitionValue>> groupOfDesc =
Maps.newHashMap();
+ Map<List<PartitionValue>, PartitionKeyDesc> onlyDescOfGroup =
Maps.newHashMap();
+ for (Map<PartitionKeyDesc, Set<String>> onePctDescs : descs.values()) {
+ for (PartitionKeyDesc desc : onePctDescs.keySet()) {
+ if (!desc.hasInValues()) {
+ continue;
+ }
+ List<PartitionValue> group = find(groupOfKey,
desc.getInValues().iterator().next());
+ groupOfDesc.put(desc, group);
+ if (onlyDescOfGroup.put(group, desc) != null) {
+ // A second desc in this group: its keys are the group's
from here on.
+ onlyDescOfGroup.put(group, null);
+ }
+ }
+ }
Map<PartitionKeyDesc, Map<MTMVRelatedTableIf, Set<String>>> res =
Maps.newHashMap();
for (Entry<MTMVRelatedTableIf, Map<PartitionKeyDesc, Set<String>>>
entry : descs.entrySet()) {
- MTMVRelatedTableIf pctTable = entry.getKey();
- Map<PartitionKeyDesc, Set<String>> onePctDescs = entry.getValue();
- for (Entry<PartitionKeyDesc, Set<String>> onePctEntry :
onePctDescs.entrySet()) {
- PartitionKeyDesc partitionKeyDesc = onePctEntry.getKey();
- Set<String> partitionNames = onePctEntry.getValue();
- Map<MTMVRelatedTableIf, Set<String>> partitionKeyDescMap =
res.computeIfAbsent(partitionKeyDesc,
- k -> new HashMap<>());
- partitionKeyDescMap.put(pctTable, partitionNames);
+ for (Entry<PartitionKeyDesc, Set<String>> onePctEntry :
entry.getValue().entrySet()) {
+ PartitionKeyDesc desc = onePctEntry.getKey();
+ if (desc.hasInValues()) {
+ List<PartitionValue> group = groupOfDesc.get(desc);
+ PartitionKeyDesc only = onlyDescOfGroup.get(group);
+ desc = only == null
+ ?
PartitionKeyDesc.createIn(sortedKeys(keysOfGroup.get(group))) : only;
+ }
+ res.computeIfAbsent(desc, k -> new HashMap<>())
+ .merge(entry.getKey(),
Sets.newHashSet(onePctEntry.getValue()), (left, right) -> {
+ left.addAll(right);
+ return left;
+ });
}
}
- if (mvPartitionInfo.getPctInfos().size() > 1) {
- checkIntersect(res.keySet(), partitionColumns);
+ return res;
+ }
+
+ private void union(Map<List<PartitionValue>, List<PartitionValue>>
groupOfKey, List<PartitionValue> left,
+ List<PartitionValue> right) {
+ List<PartitionValue> leftGroup = find(groupOfKey, left);
+ List<PartitionValue> rightGroup = find(groupOfKey, right);
+ if (leftGroup != rightGroup) {
+ groupOfKey.put(rightGroup, leftGroup);
}
- lastResult.setRes(res);
+ }
+
+ private List<PartitionValue> find(Map<List<PartitionValue>,
List<PartitionValue>> groupOfKey,
+ List<PartitionValue> key) {
+ List<PartitionValue> group =
Preconditions.checkNotNull(groupOfKey.get(key),
+ "a key is registered before it is looked up: %s", key);
+ while (group != groupOfKey.get(group)) {
+ group = groupOfKey.get(group);
+ }
+ List<PartitionValue> root = group;
+ // Path compression, so that the walk is not repeated for the rest of
this group's keys.
+ group = groupOfKey.get(key);
+ while (group != root) {
+ List<PartitionValue> next = groupOfKey.get(group);
+ groupOfKey.put(group, root);
+ group = next;
+ }
+ return root;
+ }
+
+ /** The group's keys, in the order the base partition values sort in, so a
partition name is stable. */
+ private List<List<PartitionValue>> sortedKeys(Set<List<PartitionValue>>
keys) {
+ List<List<PartitionValue>> res = Lists.newArrayList(keys);
+ res.sort(Comparator.comparing(key -> key.get(0).getStringValue()));
Review Comment:
Fixed in 49f19a9a3ef. You are right that `PartitionKeyDesc.equals` compares
the key list, so the sorted order I wrote merged keys in was a *different desc*
from the one the same key set gets from `ListPartitionItem#toPartitionKeyDesc`
-- which is a list of a hash set. `ADD PARTITION` over a covered key turned the
MV partition's desc into that other desc, alignment dropped the partition it
held (rows included) and added an empty one under a new name, and with
`grace_period` the empty replacement's fresh `visibleVersionTime` let the
rewriter answer from it.
The keys are now written out the way the partition items write them, so a
set of keys is one desc wherever it is computed, and the singleton path keeps
its own desc unchanged. Pinned by a unit test on the shape you describe: one
table holding three keys in one partition, and a second holding them plus a
partition whose key is one of them -- both compute the same desc now, and
`assertEquals` on the two descs is what says so.
--
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]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
