[Enhancement] Compare mv rowCount when both mv dimensions contains query dimensions

[kaijianding]

Why I'm doing:

-- rows: 100 mv1: 
select sum(v1) from t1 group by a, b, c, f; 

-- rows: 10000 mv2: 
select sum(v1) from t1 group by a, b, d; 

query: select sum(v1) from t1 where b = 'a' group by a;

Before: prefer mv with less dimensions -> mv2, but mv2 has more rows which is not expected.
After: when many mvs satisfy query, prefer mv with less rows, so choose mv1.

What I'm doing:

1. MaterializationContext.RewriteOrdering decides which MVs are retained in case too many MV candidates and candidate list should be truncated. MaterializationContext.RewriteOrdering should compare MV's maxPartitionRowCount rather than MV's total row count, in case a MV is with less partitions and total row count but maxPartitionRowCount is large.
2. BestMvSelector is the actually place to decide which MV should be chose. The comparator in BestMvSelector should consider row count first if MV's outputRowCount is not zero in statistics.

Fixes #issue

What type of PR is this:

• BugFix
• Feature
• Enhancement
• Refactor
• UT
• Doc
• Tool

Does this PR entail a change in behavior?

• Yes, this PR will result in a change in behavior.
• No, this PR will not result in a change in behavior.

Checklist:

• I have added test cases for my bug fix or my new feature
• This pr needs user documentation (for new or modified features or behaviors)
  • I have added documentation for my new feature or new function
• This is a backport pr

Bugfix cherry-pick branch check:

• I have checked the version labels which the pr will be auto-backported to the target branch
  • 3.3
  • 3.2
  • 3.1
  • 3.0
  • 2.5

[LiShuMing]

eg:

-- rows: 100
mv1:  select sum(v1) from t1 group by a, b, c;
-- rows: 10000
mv2: select sum(v1) from t1 group by a, b;

query: select sum(v1) from t1 where b = 'a' group by a;

Before: prefer mv with less dimensions -> mv2, but mv2 has more rows which is not expected.
After: when many mvs satisfy query, prefer mv with less rows, so choose mv1.

am I right? can you add more comments about this?

[LiShuMing]

And can you move this codes into orderingAggregation to make it more clear?

[kaijianding]

Yes，this is what I expect。but mv definition is a little different.

-- rows: 100 mv1: 
select sum(v1) from t1 group by a, b, c, f; 

-- rows: 10000 mv2: 
select sum(v1) from t1 group by a, b, d; 

query: select sum(v1) from t1 where b = 'a' group by a;

[kaijianding]

orderingAggregation is about single MV, while these codes are about 2 MVs, so I don't change logic in orderingAggregation

[LiShuMing]

Seems solid.
Can you add this example into comments?

[LiShuMing]

Seems solid.
Can you add this example into comments?

[satanson]

is this policy too sensitive? for an exmaple, MV0 and MV1 have N rows and N+1 rows respectively, MV1 may be a promising one for the certain query? so mvHasDifferentRows should introduce an epsilon(ε) so that |MV1-MV1|/max(|MV1|,|MV2|) > ε, then we consider that the larger one is superior to the smaller one significantly.

[kaijianding]

But we don't have enough clue to tell if MV1 is actually better than MV0 or not here.
if mvHasDifferentRows is set to false when MV0 and MV1 have similar row number, the later code still compares the dimension diff number and later the row number.

My point is that we can't exactlly tell which mv is better for a particular query, we can only believe that comparing row count is more promising than comparing dimension diff number.

[satanson]

rowCount is promising only when there is a significant gap between two MVs' rowcounts. if the row counts are almost the same, we also can not tell out which MV is better. I show an exmaple:

1. MV0: [d0,d1,d2, sum(m0)];
2. MV1: [d1,d0,d3, sum(m0)];
   we suppose that |MV0| = N, |MV1|= M, N>M and N-M is small;

for query: select d1, sum(m0) from t where predicate(d0) group by d1;
if MV0 has short key on d0, this query fetches data from IO layer quickly.
so I think only two MV's rowcount are different drastically, the one of smaller rowcount is promissing. if they are close, we should not use the rowcounts.

[kaijianding]

I understand your scenario and the limitation of exactly comparing mv row count.

What I do in this PR is prefering comparing mv rount to comparing the deminsion diff number, I get that this is not the most perfect solution. But it is much better than current logic.

Current we don't have enough information(eg: the key columns used in query's predicate and how many rows can be reduced by this predicate, etc) to make sure that MV1 is better choice than MV0 when MV1 has larger row count, other than not choosing MV0 when MV0 has less row count.

My point is that we can't tell which mv is better when the two mv have similar row count according to the current information from the context at current stage, it's still better comparing row count than comparing dimension diff number.

[kaijianding]

I have changed the logic in BestMvSeclector which is the actually class choosing mv according to your comment

[sonarcloud]

Quality Gate passed

Issues
5 New issues
0 Accepted issues

Measures
0 Security Hotspots
0.0% Coverage on New Code
0.0% Duplication on New Code

See analysis details on SonarCloud

[github-actions]

[Java-Extensions Incremental Coverage Report]

✅ pass : 0 / 0 (0%)

[github-actions]

[FE Incremental Coverage Report]

✅ pass : 21 / 22 (95.45%)

file detail

	path	covered_line	new_line	coverage	not_covered_line_detail
🔵	com/starrocks/sql/optimizer/rule/transformation/materialization/BestMvSelector.java	8	9	88.89%	[155]
🔵	com/starrocks/catalog/MaterializedView.java	5	5	100.00%	[]
🔵	com/starrocks/sql/optimizer/MaterializationContext.java	8	8	100.00%	[]

[github-actions]

[BE Incremental Coverage Report]

✅ pass : 0 / 0 (0%)