yujun777 commented on code in PR #68648:
URL: https://github.com/apache/doris/pull/68648#discussion_r4225918262
##########
fe/fe-core/src/main/java/org/apache/doris/mtmv/MTMVPartitionUtil.java:
##########
@@ -303,6 +304,120 @@ public static Optional<Map<BaseTableInfo, Set<Long>>>
generateRelatedBasePartiti
return Optional.of(res);
}
+ /**
+ * The desc of the MV partition each of these descs belongs to: the keys
of a list partitioned base table
+ * can meet at the MV's partition column -- a partition holding several
keys of it, one of them shared with
+ * another partition -- and an MV's own partitions cannot overlap, so
descs whose keys meet are one
+ * partition whose keys are the union of theirs. A desc whose keys meet
nothing is answered with itself,
+ * and so is every desc that is not a list of keys.
+ *
+ * <p>The keys of a merged desc are written out the way
+ * {@link ListPartitionItem#toPartitionKeyDesc(int)} writes the same key
set -- as a list of a hash set --
+ * because {@link PartitionKeyDesc#equals} compares that list: the same
keys in another order are another
+ * desc, which would leave the MV partition an alignment computes
unmatchable to the one it holds.
+ */
+ public static Map<PartitionKeyDesc, PartitionKeyDesc>
mergedListDescs(Collection<PartitionKeyDesc> 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 (PartitionKeyDesc desc : descs) {
+ 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);
+ unionKey(groupOfKey, first, key);
+ }
+ }
+ Map<List<PartitionValue>, Set<List<PartitionValue>>> keysOfGroup =
Maps.newHashMap();
+ for (List<PartitionValue> key : groupOfKey.keySet()) {
+ keysOfGroup.computeIfAbsent(findKey(groupOfKey, key), k ->
Sets.newHashSet()).add(key);
+ }
+ Map<List<PartitionValue>, Integer> descCountOfGroup =
Maps.newHashMap();
+ Map<List<PartitionValue>, PartitionKeyDesc> onlyDescOfGroup =
Maps.newHashMap();
+ Map<PartitionKeyDesc, List<PartitionValue>> groupOfDesc =
Maps.newHashMap();
+ for (PartitionKeyDesc desc : descs) {
+ if (!desc.hasInValues()) {
+ continue;
+ }
+ List<PartitionValue> group = findKey(groupOfKey,
desc.getInValues().iterator().next());
+ groupOfDesc.put(desc, group);
+ descCountOfGroup.merge(group, 1, Integer::sum);
+ onlyDescOfGroup.putIfAbsent(group, desc);
+ }
+ Map<PartitionKeyDesc, PartitionKeyDesc> res = Maps.newHashMap();
+ for (PartitionKeyDesc desc : descs) {
+ if (!desc.hasInValues()) {
+ res.put(desc, desc);
+ continue;
+ }
+ List<PartitionValue> group = groupOfDesc.get(desc);
+ res.put(desc, descCountOfGroup.get(group) == 1
+ ? onlyDescOfGroup.get(group)
+ :
PartitionKeyDesc.createIn(Lists.newArrayList(keysOfGroup.get(group))));
Review Comment:
Fixed in eb0803f7a23: the merged desc is memoized by its group, so a group
of N descs builds its key set once rather than N times. The grouping itself is
one pass of key lookups (a union-find with path compression), so the cost of a
mapping is linear in the keys, not quadratic.
##########
fe/fe-core/src/main/java/org/apache/doris/mtmv/MTMVRelatedPartitionDescTransferGenerator.java:
##########
@@ -46,25 +46,46 @@ 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 =
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);
- }
- }
+ 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: 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, and an MV's own
partitions cannot overlap. The one
+ * partition that holds a group's keys names every table's partitions of
them, which is what a refresh
+ * reads and records for those keys (see {@link
MTMVPartitionUtil#mergedListDescs}).
+ *
+ * <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.
+ */
+ private Map<PartitionKeyDesc, Map<MTMVRelatedTableIf, Set<String>>>
mergeOverlappingListDescs(
+ Map<MTMVRelatedTableIf, Map<PartitionKeyDesc, Set<String>>> descs)
{
+ Set<PartitionKeyDesc> allDescs = Sets.newHashSet();
+ for (Map<PartitionKeyDesc, Set<String>> onePctDescs : descs.values()) {
+ allDescs.addAll(onePctDescs.keySet());
+ }
+ Map<PartitionKeyDesc, PartitionKeyDesc> mergedOfDesc =
MTMVPartitionUtil.mergedListDescs(allDescs);
+ Map<PartitionKeyDesc, Map<MTMVRelatedTableIf, Set<String>>> res =
Maps.newHashMap();
Review Comment:
Fixed in eb0803f7a23, and I confirmed your case fails first: as a unit test
with `t14_p12` projecting {1,2}, `t15_p1` projecting {1} and `t15_p23`
projecting {2,3}, a query over `t14_p12` and `t15_p1` came out with two keys
where `CREATE` stores three.
The cause was the one you name:
`MTMVRelatedPartitionDescOnePartitionColGenerator` filtered the query's
partitions before the keys were grouped, so `t15_p23` -- whose keys meet
`t14_p12`'s -- was gone before the component was formed. The filter now runs in
`MTMVRelatedPartitionDescTransferGenerator`, i.e. after the cross-table
grouping: it drops the partitions the query does not read per table and drops
an MV partition whole only when no table of it feeds the query, so every MV
partition a query is answered from keeps the desc the MV holds and the
partitions the query does not touch are still left out.
The within-table case from the earlier thread is covered by the same change
(`t8` pruned to `p_single` still emits the merged desc), and both are unit
tests now.
--
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]
