Uploaded image for project: 'IMPALA'
  1. IMPALA
  2. IMPALA-2165

Avoid estimating cardinality 0 in SCAN node

    XMLWordPrintableJSON

    Details

      Description

      Often times when the cardinality of a small (dimension) table is small, which is common, and there are some predicates on this table, the planner ends up estimating the cardinality of the scan to be equal to 0. For example:

      [localhost.localdomain:21000] > explain select count(*) from nation where n_name = 'BRAZIL' and n_regionkey = 1;
      Query: explain select count(*) from nation where n_name = 'BRAZIL' and n_regionkey = 1
      +-----------------------------------------------------+
      | Explain String                                      |
      +-----------------------------------------------------+
      | Estimated Per-Host Requirements: Memory=0B VCores=0 |
      |                                                     |
      | 01:AGGREGATE [FINALIZE]                             |
      | |  output: count(*)                                 |
      | |  hosts=1 per-host-mem=unavailable                 |
      | |  tuple-ids=1 row-size=8B cardinality=0            |
      | |                                                   |
      | 00:SCAN HDFS [tpch_parquet.nation]                  |
      |    partitions=1/1 files=1 size=2.17KB               |
      |    predicates: n_name = 'BRAZIL', n_regionkey = 1   |
      |    table stats: 25 rows total                       |
      |    column stats: all                                |
      |    hosts=1 per-host-mem=unavailable                 |
      |    tuple-ids=0 row-size=25B cardinality=0           | <== Cardinality = 25 * 1/10 * 1/10, rounds to 0. 
      +-----------------------------------------------------+
      Fetched 14 row(s) in 0.02s
      

      Once we have a cardinality estimate of 0, then we may end up misestimating all subsequent operators, because we may multiply with 0. For example, say we have the following query that has a CROSS JOIN.

      [localhost.localdomain:21000] > explain select count(*) from (select * from customer cross join nation where n_name = 'BRAZIL' and n_regionkey = 1) cn left outer join region on n_regionkey = r_regionkey;
      Query: explain select count(*) from (select * from customer cross join nation where n_name = 'BRAZIL' and n_regionkey = 1) cn left outer join region on n_regionkey = r_regionkey
      +-------------------------------------------------------------------+
      | Explain String                                                    |
      +-------------------------------------------------------------------+
      | Estimated Per-Host Requirements: Memory=256.00MB VCores=3         |
      |                                                                   |
      | 10:AGGREGATE [FINALIZE]                                           |
      | |  output: count:merge(*)                                         |
      | |  hosts=1 per-host-mem=unavailable                               |
      | |  tuple-ids=4 row-size=8B cardinality=1                          |
      | |                                                                 |
      | 09:EXCHANGE [UNPARTITIONED]                                       |
      | |  hosts=1 per-host-mem=unavailable                               |
      | |  tuple-ids=4 row-size=8B cardinality=1                          |
      | |                                                                 |
      | 05:AGGREGATE                                                      |
      | |  output: count(*)                                               |
      | |  hosts=1 per-host-mem=10.00MB                                   |
      | |  tuple-ids=4 row-size=8B cardinality=1                          |
      | |                                                                 |
      | 04:HASH JOIN [RIGHT OUTER JOIN, PARTITIONED]                      |
      | |  hash predicates: r_regionkey = tpch_parquet.nation.n_regionkey |
      | |  hosts=1 per-host-mem=0B                                        |
      | |  tuple-ids=3N,0,1 row-size=27B cardinality=1                    |
      | |                                                                 |
      | |--08:EXCHANGE [HASH(tpch_parquet.nation.n_regionkey)]            |
      | |  |  hosts=1 per-host-mem=0B                                     |
      | |  |  tuple-ids=0,1 row-size=25B cardinality=0                    |
      | |  |                                                              |
      | |  02:CROSS JOIN [BROADCAST]                                      |
      | |  |  hosts=1 per-host-mem=0B                                     |
      | |  |  tuple-ids=0,1 row-size=25B cardinality=0                    | <== Cross join estimates cardinality 0, because right input is 0.
      | |  |                                                              |
      | |  |--06:EXCHANGE [BROADCAST]                                     |
      | |  |  |  hosts=1 per-host-mem=0B                                  |
      | |  |  |  tuple-ids=1 row-size=25B cardinality=0                   |
      | |  |  |                                                           |
      | |  |  01:SCAN HDFS [tpch_parquet.nation, RANDOM]                  |
      | |  |     partitions=1/1 files=1 size=2.17KB                       |
      | |  |     predicates: n_name = 'BRAZIL', n_regionkey = 1           |
      | |  |     table stats: 25 rows total                               |
      | |  |     column stats: all                                        |
      | |  |     hosts=1 per-host-mem=64.00MB                             |
      | |  |     tuple-ids=1 row-size=25B cardinality=0                   | <== We should avoid having cardinality == 0.
      | |  |                                                              |
      | |  00:SCAN HDFS [tpch_parquet.customer, RANDOM]                   |
      | |     partitions=1/1 files=1 size=12.47MB                         |
      | |     table stats: 150000 rows total                              |
      | |     column stats: all                                           |
      | |     hosts=1 per-host-mem=192.00MB                               |
      | |     tuple-ids=0 row-size=0B cardinality=150000                  |
      | |                                                                 |
      | 07:EXCHANGE [HASH(r_regionkey)]                                   |
      | |  hosts=1 per-host-mem=0B                                        |
      | |  tuple-ids=3 row-size=2B cardinality=1                          |
      | |                                                                 |
      | 03:SCAN HDFS [tpch_parquet.region, RANDOM]                        |
      |    partitions=1/1 files=1 size=900B                               |
      |    predicates: tpch_parquet.region.r_regionkey = 1                |
      |    table stats: 5 rows total                                      |
      |    column stats: all                                              |
      |    hosts=1 per-host-mem=16.00MB                                   |
      |    tuple-ids=3 row-size=2B cardinality=1                          |
      +-------------------------------------------------------------------+
      Fetched 59 row(s) in 0.05s
      

      The optimizer decides to use a ROJ because believes that the result of the CROSS JOIN is 0. But we end up having 150K tuples on the right and only 1 tuple on the left side.

      [localhost.localdomain:21000] > summary;
      +--------------------+--------+----------+----------+---------+------------+-----------+---------------+---------------------------------------+
      | Operator           | #Hosts | Avg Time | Max Time | #Rows   | Est. #Rows | Peak Mem  | Est. Peak Mem | Detail                                |
      +--------------------+--------+----------+----------+---------+------------+-----------+---------------+---------------------------------------+
      | 10:AGGREGATE       | 1      | 239.13ms | 239.13ms | 1       | 1          | 16.00 KB  | -1 B          | FINALIZE                              |
      | 09:EXCHANGE        | 1      | 33.22us  | 33.22us  | 1       | 1          | 0 B       | -1 B          | UNPARTITIONED                         |
      | 05:AGGREGATE       | 1      | 237.90ms | 237.90ms | 1       | 1          | 40.00 KB  | 10.00 MB      |                                       |
      | 04:HASH JOIN       | 1      | 386.61ms | 386.61ms | 150.00K | 1          | 258.57 MB | 0 B           | RIGHT OUTER JOIN, PARTITIONED         |
      | |--08:EXCHANGE     | 1      | 23.40ms  | 23.40ms  | 150.00K | 0          | 0 B       | 0 B           | HASH(tpch_parquet.nation.n_regionkey) |
      | |  02:CROSS JOIN   | 1      | 53.04ms  | 53.04ms  | 150.00K | 0          | 28.00 KB  | 0 B           | BROADCAST                             |
      | |  |--06:EXCHANGE  | 1      | 90.73us  | 90.73us  | 1       | 0          | 0 B       | 0 B           | BROADCAST                             |
      | |  |  01:SCAN HDFS | 1      | 8.70ms   | 8.70ms   | 1       | 0          | 50.00 KB  | 64.00 MB      | tpch_parquet.nation                   |
      | |  00:SCAN HDFS    | 1      | 170.50ms | 170.50ms | 150.00K | 150.00K    | 1.23 MB   | 192.00 MB     | tpch_parquet.customer                 |
      | 07:EXCHANGE        | 1      | 62.17us  | 62.17us  | 1       | 1          | 0 B       | 0 B           | HASH(r_regionkey)                     |
      | 03:SCAN HDFS       | 1      | 17.13ms  | 17.13ms  | 1       | 1          | 33.00 KB  | 16.00 MB      | tpch_parquet.region                   |
      +--------------------+--------+----------+----------+---------+------------+-----------+---------------+---------------------------------------+
      

      A potential fix is simple. In the scanner cardinality estimation to use:

      card = max(1, card);
      

        Attachments

          Activity

            People

            • Assignee:
              ippokratis Ippokratis Pandis
              Reporter:
              ippokratis Ippokratis Pandis
            • Votes:
              0 Vote for this issue
              Watchers:
              4 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: