[IMPALA-7560] Better selectivity estimate for != (not equals) binary predicate

• Type: Bug
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Affects Version/s: Impala 2.8.0, Impala 2.9.0, Impala 2.10.0, Impala 2.12.0, Impala 2.13.0
• Fix Version/s: Impala 4.1.0, Impala 4.0.1
• Component/s: Frontend
• Epic Color: ghx-label-5
• Assignee: liuyao
• Reporter: Bharath Vissapragada
• Created: 11/Sep/18 17:57
• Updated: 27/Sep/21 09:57
• Resolved: 24/Jun/21 03:13

Description

Currently we use the default selectivity estimate for any binary predicate with op other than EQ / NON_DISTINCT.

// Determine selectivity
    // TODO: Compute selectivity for nested predicates.
    // TODO: Improve estimation using histograms.
    Reference<SlotRef> slotRefRef = new Reference<SlotRef>();
    if ((op_ == Operator.EQ || op_ == Operator.NOT_DISTINCT)
        && isSingleColumnPredicate(slotRefRef, null)) {
      long distinctValues = slotRefRef.getRef().getNumDistinctValues();
      if (distinctValues > 0) {
        selectivity_ = 1.0 / distinctValues;
        selectivity_ = Math.max(0, Math.min(1, selectivity_));
      }
    }

This can give very conservative estimates. For example:

[localhost:21000] tpch> select * from nation where n_regionkey != 1;
[localhost:21000] tpch> summary;
+--------------+--------+----------+----------+-------+------------+-----------+---------------+-------------+
| Operator     | #Hosts | Avg Time | Max Time | *#Rows* | *Est. #Rows* | Peak Mem  | Est. Peak Mem | Detail      |
+--------------+--------+----------+----------+-------+------------+-----------+---------------+-------------+
| 00:SCAN HDFS | 1      | 3.32ms   | 3.32ms   | *20*    | *3*          | 143.00 KB | 16.00 MB      | tpch.nation |
+--------------+--------+----------+----------+-------+------------+-----------+---------------+-------------+
[localhost:21000] tpch> 

Ideally we could've inversed the selecitivity to 4/5 (=1 - 1/5) that can give better estimate.

Issue Links

• is duplicated by: IMPALA-8039 Incorrect selectivity estimate for not-equals predicate
• is part of: IMPALA-7601 Improve cardinality and selectivity estimates