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

Missing, redundant or non-evaluable predicates due to buggy equivalence classes.

    Details

    • Type: Bug
    • Status: Resolved
    • Priority: Blocker
    • Resolution: Fixed
    • Affects Version/s: Impala 2.3.0, Impala 2.5.0, Impala 2.4.0, Impala 2.6.0, Impala 2.7.0, Impala 2.8.0
    • Fix Version/s: Impala 2.9.0
    • Component/s: Frontend
    • Labels:

      Description

      Impala's equivalence class computation has a subtle bug which can lead to:
      1. omitting predicates
      2. adding redundant predicates
      3. adding predicates that are non-evaluable at that point in the plan

      In most queries, the bug has no effect on the final plan.
      However, in case (1) incorrect results may be returned, and in case (3) a crash will occur.

      Unfortunately, it is extremely difficult to determine from a query when this bug is being hit because the bug may or may not trigger depending on the specific implementation of Java's HashMap which has a tendency to slightly change across JVM versions. It also depends on the total number of columns (including virtual view columns) in the query.
      For queries hitting this bug, even minor changes that do not affect the end result are enough to make them not hit this bug (e.g., changing a '*" to an explicit list of fewer columns).

      The root cause is a bug in Impala's DisjointSet implementation which is used for computing equivalence classes.

      Workaround
      Even minor query modifications that do not affect the query result might be enough to fix a query. For example, changing a '*' to an explicit list of (fewer) columns may be enough. Likewise, adding column references in places where they are not needed, e.g., in a EXISTS or NOT EXISTS subquery may fix the problem.

        Activity

        Hide
        alex.behm Alexander Behm added a comment -

        commit ffd297bdea5d58db3d1791a2528b7f1009a459c6
        Author: Alex Behm <alex.behm@cloudera.com>
        Date: Fri Feb 10 07:05:07 2017 -0800

        IMPALA-4916: Fix maintenance of set of item sets in DisjointSet.

        The bug: The DisjointSet maintains a set of unique item sets
        using a HashSet<Set<T>>. The problem is that we modified
        the Set<T> elements after inserting them into the HashSet.
        This caused the removal of elements from the HashSet to fail.
        Removal is required for maintaining a consistent DisjointSet.
        The removal could even fail for the same Set<T> instance because
        the hashCode() changed from when the Set<T> was originally
        inserted to when the removal was attempted due to mutation
        of the Set<T>.
        An inconsistent DisjointSet can lead to incorrect equivalence
        classes, which can lead to missing, redundant and even
        non-executable predicates. Incorrect results and crashes are
        possible.

        For most queries, an inconsistent DisjointSet does not alter
        the equivalence classes, and even fewer queries have incorrect
        plans.
        In fact, many of our existing planner tests trigger this bug,
        but only 3 of them lead to an incorrect value transfer graph,
        and all 3 had correct plans.

        The fix: Use an IdentityHashMap to store the set of item sets.
        It does not rely on the hashCode() and equals() of the stored
        elements, so the same object can be added and later removed,
        even when mutated in the meantime.

        Testing:

        • Added a Preconditions check in DisjointSet that asserts
          correct removal of an item set. Many of our existing tests
          hit the check before this fix.
        • Added a new unit test for DisjointSet which triggers
          the bug.
        • Augmented DisjointSet.checkConsistency() to check for
          inconsistency in the set of item sets.
        • Added validation of the value-transfer graph in
          single-node planner tests.
        • A private core/hdfs run succeeded.

        Change-Id: I609c8795c09becd78815605ea8e82e2f99e82212
        Reviewed-on: http://gerrit.cloudera.org:8080/5980
        Reviewed-by: Alex Behm <alex.behm@cloudera.com>
        Tested-by: Impala Public Jenkins

        Show
        alex.behm Alexander Behm added a comment - commit ffd297bdea5d58db3d1791a2528b7f1009a459c6 Author: Alex Behm <alex.behm@cloudera.com> Date: Fri Feb 10 07:05:07 2017 -0800 IMPALA-4916 : Fix maintenance of set of item sets in DisjointSet. The bug: The DisjointSet maintains a set of unique item sets using a HashSet<Set<T>>. The problem is that we modified the Set<T> elements after inserting them into the HashSet. This caused the removal of elements from the HashSet to fail. Removal is required for maintaining a consistent DisjointSet. The removal could even fail for the same Set<T> instance because the hashCode() changed from when the Set<T> was originally inserted to when the removal was attempted due to mutation of the Set<T>. An inconsistent DisjointSet can lead to incorrect equivalence classes, which can lead to missing, redundant and even non-executable predicates. Incorrect results and crashes are possible. For most queries, an inconsistent DisjointSet does not alter the equivalence classes, and even fewer queries have incorrect plans. In fact, many of our existing planner tests trigger this bug, but only 3 of them lead to an incorrect value transfer graph, and all 3 had correct plans. The fix: Use an IdentityHashMap to store the set of item sets. It does not rely on the hashCode() and equals() of the stored elements, so the same object can be added and later removed, even when mutated in the meantime. Testing: Added a Preconditions check in DisjointSet that asserts correct removal of an item set. Many of our existing tests hit the check before this fix. Added a new unit test for DisjointSet which triggers the bug. Augmented DisjointSet.checkConsistency() to check for inconsistency in the set of item sets. Added validation of the value-transfer graph in single-node planner tests. A private core/hdfs run succeeded. Change-Id: I609c8795c09becd78815605ea8e82e2f99e82212 Reviewed-on: http://gerrit.cloudera.org:8080/5980 Reviewed-by: Alex Behm <alex.behm@cloudera.com> Tested-by: Impala Public Jenkins

          People

          • Assignee:
            alex.behm Alexander Behm
            Reporter:
            alex.behm Alexander Behm
          • Votes:
            0 Vote for this issue
            Watchers:
            2 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development