Optimizer improvements for TPCDS

[aaneja]

A comparative run for TPCDS was performed with the below setup -

Workload : TPCDS power run
Scale factor : 1000
Cluster setup : 1 coordinator + 8 workers. Instances were AWS r6i.4xlarge (vCPU: 16, Memory: 128)
Trino version : 448 (TODO : link to config/catalog props for setup)
Prestissimo : 0.289, commit f4d5afd (TODO : link to config/catalog props for setup)

Grafana deeplink

Latency comparison

query_id	trino_latency	prestissimo_latency	times_faster
query_01.sql	12.3 s	17.6 s	0.699
query_02.sql	14.8 s	14.4 s	1.03
query_03.sql	11.9 s	14.1 s	0.845
query_04.sql	1.08 min	45.4 s	1.43
query_05.sql	20.0 s	30.8 s	0.65
query_06.sql	4.78 s	2.60 s	1.84
query_07.sql	21.8 s	25.6 s	0.851
query_08.sql	4.29 s	2.76 s	1.56
query_09.sql	25.4 s	6.61 s	3.85
query_10.sql	7.40 s	4.87 s	1.52
query_11.sql	32.5 s	18.0 s	1.81
query_12.sql	2.62 s	2.49 s	1.05
query_13.sql	24.3 s	12.1 s	2.01
query_14.sql	1.66 min	20.3 s	4.91
query_15.sql	5.01 s	3.19 s	1.57
query_16.sql	19.0 s	20.4 s	0.933
query_17.sql	14.2 s	16.2 s	0.878
query_18.sql	12.2 s	9.75 s	1.25
query_19.sql	6.99 s	1.38 s	5.06
query_20.sql	4.51 s	1.70 s	2.66
query_21.sql	6.44 s	22.9 s	0.281
query_22.sql	10.0 s	33.5 s	0.299
query_23.sql	1.88 min	1.21 min	1.55
query_24.sql	19.1 s	3.56 s	5.35
query_25.sql	13.6 s	3.68 s	3.69
query_26.sql	12.4 s	4.53 s	2.73
query_27.sql	17.1 s	4.48 s	3.82
query_28.sql	22.5 s	8.26 s	2.72
query_29.sql	18.4 s	3.51 s	5.25
query_30.sql	12.6 s	2.60 s	4.86
query_31.sql	15.9 s	4.61 s	3.46
query_32.sql	5.10 s	2.73 s	1.86
query_33.sql	9.80 s	6.38 s	1.54
query_34.sql	7.56 s	5.13 s	1.47
query_35.sql	6.62 s	2.10 s	3.16
query_36.sql	6.09 s	2.14 s	2.85
query_37.sql	15.8 s	1.85 s	8.58
query_38.sql	12 s	6.67 s	1.8
query_39.sql	6.46 s	1.40 s	4.63
query_40.sql	11.3 s	16.9 s	0.668
query_41.sql	697 ms	202 ms	3.45
query_42.sql	4.61 s	955 ms	4.83
query_43.sql	6.50 s	1.74 s	3.74
query_44.sql	2.68 s	1.07 s	2.51
query_45.sql	3.34 s	3.38 s	0.989
query_46.sql	11.4 s	1.61 s	7.1
query_47.sql	39.0 s	16.5 s	2.36
query_48.sql	10.4 s	2.65 s	3.93
query_49.sql	22.6 s	13.0 s	1.73
query_50.sql	9.17 s	4.99 s	1.84
query_51.sql	11.9 s	18.3 s	0.65
query_52.sql	3.74 s	1.56 s	2.39
query_53.sql	4.34 s	2.06 s	2.11
query_54.sql	25.7 s	5.60 s	4.59
query_55.sql	3.55 s	741 ms	4.79
query_56.sql	11.7 s	2.81 s	4.16
query_57.sql	23.7 s	11.2 s	2.12
query_58.sql	6.33 s	10.7 s	0.59
query_59.sql	24.9 s	16.6 s	1.5
query_60.sql	11.3 s	3.86 s	2.94
query_61.sql	10.2 s	2.57 s	3.98
query_62.sql	4.17 s	4.23 s	0.986
query_63.sql	4.69 s	827 ms	5.67
query_64.sql	1.75 min	44.6 s	2.36
query_65.sql	15.8 s	14.2 s	1.12
query_66.sql	15.0 s	8.84 s	1.69
query_67.sql	1.35 min	6.66 min	0.203
query_68.sql	21.3 s	10.4 s	2.04
query_69.sql	7.94 s	1.31 s	6.09
query_70.sql	48.5 s	6.58 s	7.37
query_71.sql	15.4 s	9.57 s	1.61
query_72.sql	37.8 s	13.8 s	2.75
query_73.sql	8.89 s	2.38 s	3.73
query_74.sql	25.7 s	12.0 s	2.14
query_75.sql	36.8 s	12.8 s	2.89
query_76.sql	8.77 s	2.40 s	3.66
query_77.sql	18.1 s	2.91 s	6.23
query_78.sql	56.4 s	57.6 s	0.98
query_79.sql	15.5 s	2.52 s	6.17
query_80.sql	42.1 s	59.3 s	0.711
query_81.sql	8.31 s	2.99 s	2.78
query_82.sql	25.9 s	666 ms	38.8
query_83.sql	2.47 s	2.16 s	1.14
query_84.sql	6.23 s	2.30 s	2.71
query_85.sql	7.84 s	6.95 s	1.13
query_86.sql	3.70 s	802 ms	4.61
query_87.sql	13.0 s	6.69 s	1.94
query_88.sql	25.8 s	5.44 s	4.75
query_89.sql	6.93 s	982 ms	7.05
query_90.sql	3.82 s	521 ms	7.34
query_91.sql	4.66 s	434 ms	10.7
query_92.sql	3.43 s	478 ms	7.17
query_93.sql	18.3 s	3.32 s	5.5
query_94.sql	28.7 s	6.90 s	4.15
query_95.sql	12.7 s	16.0 s	0.794
query_96.sql	4.47 s	1.56 s	2.87
query_97.sql	15.9 s	16.5 s	0.967
query_98.sql	7.63 s	1.36 s	5.62
query_99.sql	7.43 s	2.34 s	3.18
Total	29.6 min	22.4 min	1.32

Plan diffs

Plan diffs were generated from a custom tool that canonicalizes JSON plans (i.e plans obtained from EXPLAIN (TYPE DISTRIBUTED, FORMAT JSON) xxx) to a tree representation and then diff-ed

With all operators

Join only diff

Join+Agg diff

Deep dive of planner issues identified from top 5 heavy hitters

Query	Root cause	Tracking issue
Q67	Trino modified the TopNRowNumber operator/plan-node to work with Rank/DenseRank as well. The new planner node is called TopNRanking. This improved Q67 drastically. Improving this in Prestissimo should help cut down total latency by ~5.5 min	Add support for streaming TopN rank #23477
Q22	Trino added a rule AddExchangesBelowPartialAggregationOverGroupIdRuleSet that makes pre-agg more effective	Add Exchange before GroupId to improve Partial Aggregation #23475
Q51	Trino added a generic optimization to reduce total number of remote exchanges. This benefited Q51 among other queries. The root cause however, IMO, is that remote exchange operator in Prestissimo needs to be more performant	Exchange improvements in Velox
Q58	Trino added a rule TransformFilteringSemiJoinToInnerJoin to convert a SemiJoin to an InnerJoin. This specifically helped Q58. Presto does converts an Apply node to a SemiJoin, and the TransformUncorrelatedInPredicateSubqueryToDistinctInnerJoin manages to convert this to a InnerJoin, but then we undo all this by running TransformDistinctInnerJoinToLeftEarlyOutJoin. TransformFilteringSemiJoinToInnerJoin opens up the join space for reordering and this results in a better plan for Q58	N/A
Q05	Trino does a better job with UNION ALL when the result of the union is REPLICATE joined with another table. They do this by adding the ability to schedule multiple TableScan’s in a single stage	Add a new scheduler + exchange rules to support multiple table scans in a single stage #23476

[aaneja]

In addition, @jaystarshot identified these possible improvements as well -

Q64 planning time improvement

Sequential stage execution policy - likely helpful for DS runs with concurrent queries

Q24 improvement due to incorrect output size calculation

Improvement for partitioned DS runs increasing default partition cache size