yujun777 commented on code in PR #68648:
URL: https://github.com/apache/doris/pull/68648#discussion_r4226012336
##########
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:
Your sharper case is right and is fixed in b48827d477b: the order I was
writing merged keys in was a hash set's, and a hash set iterates in the order
it was filled in once two keys hash alike -- `Aa` and `BB` do -- so a merged
desc could still differ from the desc a base partition's projection produces
for the same keys.
Both paths write the keys in one canonical order now
(`PartitionKeyDesc#sortedInValues`, used by `ListPartitionItem`'s two desc
variants and by `MTMVPartitionUtil#mergedListDescs`), so the same set of keys
is the same desc wherever it is computed, and the partition name generated from
it is stable too.
Test: two tables holding the same two colliding keys, written down in either
order, compute one desc -- and it fails with the ordering reverted (as does the
earlier merged-vs-single-desc case). Regression: the
`partition_p0/list_partition` suite directory (default partitions, multi-column
default, `show create`) and the mtmv_p0 set are green.
--
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]
