Hive
  1. Hive
  2. HIVE-4435

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

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major 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.

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

        Activity

        Shreepadma Venugopalan created issue -
        Shreepadma Venugopalan made changes -
        Field Original Value New Value
        Status Open [ 1 ] Patch Available [ 10002 ]
        Shreepadma Venugopalan made changes -
        Attachment HIVE-4435.1.patch [ 12581033 ]
        Shreepadma Venugopalan made changes -
        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.
        Shreepadma Venugopalan made changes -
        Attachment chart_1(1).png [ 12581038 ]
        Ashutosh Chauhan made changes -
        Status Patch Available [ 10002 ] Open [ 1 ]
        Affects Version/s 0.11.0 [ 12323587 ]
        Shreepadma Venugopalan made changes -
        Status Open [ 1 ] Patch Available [ 10002 ]
        Shreepadma Venugopalan made changes -
        Attachment HIVE-4435.2.patch [ 12586388 ]
        Ashutosh Chauhan made changes -
        Status Patch Available [ 10002 ] Resolved [ 5 ]
        Fix Version/s 0.12.0 [ 12324312 ]
        Resolution Fixed [ 1 ]
        Ashutosh Chauhan made changes -
        Status Resolved [ 5 ] Closed [ 6 ]

          People

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

            Dates

            • Created:
              Updated:
              Resolved:

              Development