Support Questions
Find answers, ask questions, and share your expertise
Announcements
Alert: Welcome to the Unified Cloudera Community. Former HCC members be sure to read and learn how to activate your account here.

What heuristics does Impala use for cardinality estimation

Solved Go to solution
Highlighted

What heuristics does Impala use for cardinality estimation

Explorer

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

 

1 ACCEPTED SOLUTION

Accepted Solutions

Re: What heuristics does Impala use for cardinality estimation

Master Collaborator

 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...

4 REPLIES 4

Re: What heuristics does Impala use for cardinality estimation

Master Collaborator

 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...

Re: What heuristics does Impala use for cardinality estimation

Explorer

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

Re: What heuristics does Impala use for cardinality estimation

Explorer

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

Master Collaborator

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).

Don't have an account?
Coming from Hortonworks? Activate your account here