search

prestodb / presto

The official home of the Presto distributed SQL query engine for big data
http://prestodb.io
Apache License 2.0
16.05k stars 5.38k forks source link

Better estimates needed for outputs of function calls #20513

Open aaneja opened 1 year ago

aaneja commented 1 year ago

While debugging missing join orders for TPCDS Q24, I observed that Presto has a hard time estimating variable stats for variables computed through a function call. Consider the below query + plan :

presto:tpcds_sf1_parquet> explain select 1 FROM customer, customer_address WHERE c_birth_country = upper(ca_country);
                                                                                                                                                                    Query Plan                          >
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------->
 - Output[_col0] => [expr:integer]                                                                                                                                                                      >
         Estimates: {source: CostBasedSourceInfo, rows: ? (?), cpu: ?, memory: 2240933.00, network: ?}                                                                                                  >
         _col0 := expr (1:16)                                                                                                                                                                           >
     - RemoteStreamingExchange[GATHER] => [expr:integer]                                                                                                                                                >
             Estimates: {source: CostBasedSourceInfo, rows: ? (?), cpu: ?, memory: 2240933.00, network: ?}                                                                                              >
         - Project[projectLocality = LOCAL] => [expr:integer]                                                                                                                                           >
                 Estimates: {source: CostBasedSourceInfo, rows: ? (?), cpu: ?, memory: 2240933.00, network: 2240933.00}                                                                                 >
                 expr := INTEGER'1'                                                                                                                                                                     >
             - InnerJoin[("upper" = "c_birth_country")][$hashvalue, $hashvalue_6] => []                                                                                                                 >
                     Estimates: {source: CostBasedSourceInfo, rows: ? (?), cpu: 18093907.00, memory: 2240933.00, network: 2240933.00}                                                                   >
                     Distribution: REPLICATED                                                                                                                                                           >
                 - Project[projectLocality = LOCAL] => [upper:varchar(20), $hashvalue:bigint]                                                                                                           >
                         Estimates: {source: CostBasedSourceInfo, rows: 50000 (244.14kB), cpu: 6830175.00, memory: 0.00, network: 0.00}                                                                 >
                         $hashvalue := combine_hash(BIGINT'0', COALESCE($operator$hash_code(upper), BIGINT'0')) (1:34)                                                                                  >
                     - ScanProject[table = TableHandle {connectorId='local_hms', connectorHandle='HiveTableHandle{schemaName=tpcds_sf1_parquet, tableName=customer_address, analyzePartitionValues=Optio>
                             Estimates: {source: CostBasedSourceInfo, rows: 50000 (244.14kB), cpu: 880175.00, memory: 0.00, network: 0.00}/{source: CostBasedSourceInfo, rows: 50000 (244.14kB), cpu: 36>
                             upper := upper(ca_country) (1:34)                                                                                                                                          >
                             LAYOUT: tpcds_sf1_parquet.customer_address{}                                                                                                                               >
                             ca_country := ca_country:varchar(20):10:REGULAR (1:33)                                                                                                                     >
                 - LocalExchange[HASH][$hashvalue_6] (c_birth_country) => [c_birth_country:varchar(20), $hashvalue_6:bigint]                                                                            >
                         Estimates: {source: CostBasedSourceInfo, rows: 100000 (488.28kB), cpu: 5822799.00, memory: 0.00, network: 2240933.00}                                                          >
                     - RemoteStreamingExchange[REPLICATE] => [c_birth_country:varchar(20), $hashvalue_7:bigint]                                                                                         >
                             Estimates: {source: CostBasedSourceInfo, rows: 100000 (488.28kB), cpu: 3581866.00, memory: 0.00, network: 2240933.00}                                                      >
                         - ScanProject[table = TableHandle {connectorId='local_hms', connectorHandle='HiveTableHandle{schemaName=tpcds_sf1_parquet, tableName=customer, analyzePartitionValues=Optional.>
                                 Estimates: {source: CostBasedSourceInfo, rows: 100000 (488.28kB), cpu: 1340933.00, memory: 0.00, network: 0.00}/{source: CostBasedSourceInfo, rows: 100000 (488.28kB), >
                                 $hashvalue_8 := combine_hash(BIGINT'0', COALESCE($operator$hash_code(c_birth_country), BIGINT'0')) (1:23)                                                              >
                                 LAYOUT: tpcds_sf1_parquet.customer{}                                                                                                                                   >
                                 c_birth_country := c_birth_country:varchar(20):14:REGULAR (1:23)                                                                                                       >
                                                                                                                                                                                                        >
(1 row)

The reason we see the ? for the row count estimate on the join node is because during stats calcuation in ScalarStatsCalculator, Presto fails to estimate the stats for the upper(ca_country) node.

Unknown_stats

Because of this, queries like TPCDS Q24 which use these functions in join predicates miss out on join orders since the cost returned for these join node ends up as UNKNOWN_COST_RESULT

IMO, we need a way to figure out better estimates for deterministic scalar functions; especially for string functions (TRIM, SUBSTR, LOWER, UPPER) that are likely to get used in datalake scenarios

aaneja commented 9 months ago

Full call stack for easier debugging (from a related example) :

visitCall:143, ScalarStatsCalculator$RowExpressionStatsVisitor (com.facebook.presto.cost)
visitCall:104, ScalarStatsCalculator$RowExpressionStatsVisitor (com.facebook.presto.cost)
accept:131, CallExpression (com.facebook.presto.spi.relation)
calculate:96, ScalarStatsCalculator (com.facebook.presto.cost)
doCalculate:59, ProjectStatsRule (com.facebook.presto.cost)
doCalculate:30, ProjectStatsRule (com.facebook.presto.cost)
calculate:39, SimpleStatsRule (com.facebook.presto.cost)
calculateStats:80, ComposableStatsCalculator (com.facebook.presto.cost)
calculateStats:70, ComposableStatsCalculator (com.facebook.presto.cost)
calculateStats:79, HistoryBasedPlanStatisticsCalculator (com.facebook.presto.cost)
getStats:80, CachingStatsProvider (com.facebook.presto.cost)
getStats:372, CostCalculatorUsingExchanges$CostEstimator (com.facebook.presto.cost)
visitProject:162, CostCalculatorUsingExchanges$CostEstimator (com.facebook.presto.cost)
visitProject:85, CostCalculatorUsingExchanges$CostEstimator (com.facebook.presto.cost)
accept:108, ProjectNode (com.facebook.presto.spi.plan)
calculateCost:82, CostCalculatorUsingExchanges (com.facebook.presto.cost)
calculateCost:65, CostCalculatorWithEstimatedExchanges (com.facebook.presto.cost)
calculateCost:106, CachingCostProvider (com.facebook.presto.cost)
getGroupCost:98, CachingCostProvider (com.facebook.presto.cost)
getCost:67, CachingCostProvider (com.facebook.presto.cost)
apply:-1, 2131136600 (com.facebook.presto.cost.CostCalculatorUsingExchanges$CostEstimator$$Lambda$2871)
accept:193, ReferencePipeline$3$1 (java.util.stream)
tryAdvance:4719, Collections$2 (java.util)
forEachRemaining:4727, Collections$2 (java.util)
copyInto:482, AbstractPipeline (java.util.stream)
wrapAndCopyInto:472, AbstractPipeline (java.util.stream)
evaluateSequential:708, ReduceOps$ReduceOp (java.util.stream)
evaluate:234, AbstractPipeline (java.util.stream)
reduce:541, ReferencePipeline (java.util.stream)
costForAccumulation:330, CostCalculatorUsingExchanges$CostEstimator (com.facebook.presto.cost)
visitEnforceSingleRow:282, CostCalculatorUsingExchanges$CostEstimator (com.facebook.presto.cost)
visitEnforceSingleRow:85, CostCalculatorUsingExchanges$CostEstimator (com.facebook.presto.cost)
accept:79, EnforceSingleRowNode (com.facebook.presto.sql.planner.plan)
accept:36, InternalPlanNode (com.facebook.presto.sql.planner.plan)
calculateCost:82, CostCalculatorUsingExchanges (com.facebook.presto.cost)
calculateCost:65, CostCalculatorWithEstimatedExchanges (com.facebook.presto.cost)
calculateCost:106, CachingCostProvider (com.facebook.presto.cost)
getGroupCost:98, CachingCostProvider (com.facebook.presto.cost)
getCost:67, CachingCostProvider (com.facebook.presto.cost)
createJoinEnumerationResult:586, ReorderJoins$JoinEnumerator (com.facebook.presto.sql.planner.iterative.rule)
getJoinSource:427, ReorderJoins$JoinEnumerator (com.facebook.presto.sql.planner.iterative.rule)
createJoin:344, ReorderJoins$JoinEnumerator (com.facebook.presto.sql.planner.iterative.rule)
createJoinAccordingToPartitioning:291, ReorderJoins$JoinEnumerator (com.facebook.presto.sql.planner.iterative.rule)
chooseJoinOrder:235, ReorderJoins$JoinEnumerator (com.facebook.presto.sql.planner.iterative.rule)
access$000:190, ReorderJoins$JoinEnumerator (com.facebook.presto.sql.planner.iterative.rule)
apply:168, ReorderJoins (com.facebook.presto.sql.planner.iterative.rule)
apply:103, ReorderJoins (com.facebook.presto.sql.planner.iterative.rule)
transform:226, IterativeOptimizer (com.facebook.presto.sql.planner.iterative)
exploreNode:187, IterativeOptimizer (com.facebook.presto.sql.planner.iterative)
exploreGroup:149, IterativeOptimizer (com.facebook.presto.sql.planner.iterative)
exploreChildren:270, IterativeOptimizer (com.facebook.presto.sql.planner.iterative)
exploreGroup:151, IterativeOptimizer (com.facebook.presto.sql.planner.iterative)
exploreChildren:270, IterativeOptimizer (com.facebook.presto.sql.planner.iterative)
exploreGroup:151, IterativeOptimizer (com.facebook.presto.sql.planner.iterative)
optimize:136, IterativeOptimizer (com.facebook.presto.sql.planner.iterative)
validateAndOptimizePlan:117, Optimizer (com.facebook.presto.sql)
lambda$getLogicalPlan$1:232, QueryExplainer (com.facebook.presto.sql.analyzer)
get:-1, 382733738 (com.facebook.presto.sql.analyzer.QueryExplainer$$Lambda$2601)
profileNanos:136, RuntimeStats (com.facebook.presto.common)
getLogicalPlan:230, QueryExplainer (com.facebook.presto.sql.analyzer)
getLogicalPlan:197, QueryExplainer (com.facebook.presto.sql.analyzer)
getPlan:136, QueryExplainer (com.facebook.presto.sql.analyzer)
getQueryPlan:140, ExplainRewrite$Visitor (com.facebook.presto.sql.rewrite)
visitExplain:123, ExplainRewrite$Visitor (com.facebook.presto.sql.rewrite)
visitExplain:68, ExplainRewrite$Visitor (com.facebook.presto.sql.rewrite)
accept:80, Explain (com.facebook.presto.sql.tree)
process:27, AstVisitor (com.facebook.presto.sql.tree)
rewrite:65, ExplainRewrite (com.facebook.presto.sql.rewrite)
rewrite:58, StatementRewrite (com.facebook.presto.sql.rewrite)
analyzeSemantic:112, Analyzer (com.facebook.presto.sql.analyzer)
analyze:93, BuiltInQueryAnalyzer (com.facebook.presto.sql.analyzer)
<init>:205, SqlQueryExecution (com.facebook.presto.execution)
<init>:109, SqlQueryExecution (com.facebook.presto.execution)
createQueryExecution:961, SqlQueryExecution$SqlQueryExecutionFactory (com.facebook.presto.execution)
lambda$createDispatchQuery$0:167, LocalDispatchQueryFactory (com.facebook.presto.dispatcher)
call:-1, 1091021176 (com.facebook.presto.dispatcher.LocalDispatchQueryFactory$$Lambda$2429)
runInterruptibly:125, TrustedListenableFutureTask$TrustedFutureInterruptibleTask (com.google.common.util.concurrent)
run:57, InterruptibleTask (com.google.common.util.concurrent)
run:78, TrustedListenableFutureTask (com.google.common.util.concurrent)
runWorker:1149, ThreadPoolExecutor (java.util.concurrent)
run:624, ThreadPoolExecutor$Worker (java.util.concurrent)
run:750, Thread (java.lang)