Uploaded image for project: 'Hive'
  1. Hive
  2. HIVE-4435

Column stats: Distinct value estimator should use hash functions that are pairwise independent

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: 0.10.0, 0.11.0
    • Fix Version/s: 0.12.0
    • Component/s: Statistics
    • Labels:
      None

      Description

      The current implementation of Flajolet-Martin estimator to estimate the number of distinct values doesn't use hash functions that are pairwise independent. This is problematic because the input values don't distribute uniformly. When run on large TPC-H data sets, this leads to a huge discrepancy for primary key columns. Primary key columns are typically a monotonically increasing sequence.

        Attachments

        1. HIVE-4435.2.patch
          7 kB
          Shreepadma Venugopalan
        2. chart_1(1).png
          19 kB
          Shreepadma Venugopalan
        3. HIVE-4435.1.patch
          5 kB
          Shreepadma Venugopalan

          Activity

            People

            • Assignee:
              shreepadma Shreepadma Venugopalan
              Reporter:
              shreepadma Shreepadma Venugopalan
            • Votes:
              1 Vote for this issue
              Watchers:
              6 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: