question Re: What heuristics does Impala use for cardinality estimation in Archives of Support Questions (Read Only)

What heuristics does Impala use for cardinality estimation

jamiet — Fri, 16 Sep 2022 10:49:16 GMT

I've got a query running that scans a table that has 17.7billion rows in it. I have some (non-partition-pruning) filters on that table.

If I look at the query plan the cardinality estimate of the scan is 1.7billion rows, exactly one tenth of the total number of rows in the table.

I'm simply intrigued as to why Impala estimates cardinality of the query to be exactly one tenth. What heuristics does Impala use (if any) to determine this? Or is this simply an arbitrary rule of "if there are filters on the table then make an assumption that one tenth of the data is returned".

Just interested to know that's all.

Regards

Jamie

P.S. here is the section of the explain plan pertinent to the scan:

00:SCAN HDFS [tuk_sseft.cu0pr0cafw_cu0pr1cafw_cu0cafw_pr0cafw_current, RANDOM]
   partitions=1/1 files=5184 size=1.21TB
   predicates: tuk_sseft.cu0pr0cafw_cu0pr1cafw_cu0cafw_pr0cafw_current.cu0cafw_bsk_custperpurch_52w_cnt > 0, (tuk_sseft.cu0pr0cafw_cu0pr1cafw_cu0cafw_pr0cafw_current.cu0pr0cafw_bsk_custprodperpurch_56w_cnt > 0 OR tuk_sseft.cu0pr0cafw_cu0pr1cafw_cu0cafw_pr0cafw_current.cu0pr0cafw_bsk_custprodperpurch_101w107w_cnt > 0 OR tuk_sseft.cu0pr0cafw_cu0pr1cafw_cu0cafw_pr0cafw_current.cu0pr0cafw_bsk_custprodperpurch_153w159w_cnt > 0 OR tuk_sseft.cu0pr0cafw_cu0pr1cafw_cu0cafw_pr0cafw_current.cu0pr0cafw_bsk_custprodperpurch_205w211w_cnt > 0)
   runtime filters: RF000 -> Cu0Pr0Cafw_product
   table stats: 17738533540 rows total
   column stats: all
   hosts=18 per-host-mem=5.24GB
   tuple-ids=0 row-size=612B cardinality=1773853354

Re: What heuristics does Impala use for cardinality estimation

Tim Armstrong — Wed, 23 Nov 2016 17:18:34 GMT

You're absolutely right - we use 10% as the default estimate for selectivity for scan predicates when we don't have a better estimate. One case where we have a better estimate is when the predicate is something like id = 100. In that case we can estimate that the selectivity is 1 / (num distinct values).

There's also some logic to handle combining the estimates when there are multiple conditions.

If you're curious, the code is here: https://github.com/apache/incubator-impala/blob/4db330e69a2dbb4a23f46e34b484da0d6b9ef29b/fe/src/main/java/org/apache/impala/planner/PlanNode.java#L518

Re: What heuristics does Impala use for cardinality estimation

jamiet — Wed, 23 Nov 2016 22:05:17 GMT

Nice, thanks Tim. Appreciate the reply and, even more so, the link to the source.

Re: What heuristics does Impala use for cardinality estimation

jamiet — Wed, 23 Nov 2016 22:07:53 GMT

Any chance we might one day have the ability to override DEFAULT_SELECTIVITY via a query hint?

Re: What heuristics does Impala use for cardinality estimation

Tim Armstrong — Wed, 23 Nov 2016 23:32:55 GMT

We had an issue filed for this a while back: https://issues.cloudera.org/browse/IMPALA-3293 . It seems fairly reasonable but I think will depend on how much demand there is for it (or if someone contributes a patch for it).