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

Add histogram-based column statistics

    XMLWordPrintableJSON

Details

    Description

      Hive does not support histogram statistics, which are particularly useful for skewed data (which is very common in practice) and range predicates.

      Hive's current selectivity estimation for range predicates is based on a hard-coded value of 1/3 (see FilterSelectivityEstimator.java#L138-L144).])

      The current proposal aims at integrating histogram as an additional column statistics, stored into the Hive metastore at the table (or partition) level.

      The main requirements for histogram integration are the following:

      • efficiency: the approach must scale and support billions of rows
      • merge-ability: partition-level histograms have to be merged to form table-level histograms
      • explicit and configurable trade-off between memory footprint and accuracy

      Hive already integrates KLL data sketches UDAF. Datasketches are small, stateful programs that process massive data-streams and can provide approximate answers, with mathematical guarantees, to computationally difficult queries orders-of-magnitude faster than traditional, exact methods.

      We propose to use KLL, and more specifically the cumulative distribution function (CDF), as the underlying data structure for our histogram statistics.

      The current proposal targets numeric data types (float, integer and numeric families) and temporal data types (date and timestamp).

      Attachments

        Issue Links

          Activity

            People

              asolimando Alessandro Solimando
              asolimando Alessandro Solimando
              Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

                Created:
                Updated:

                Time Tracking

                  Estimated:
                  Original Estimate - Not Specified
                  Not Specified
                  Remaining:
                  Remaining Estimate - 0h
                  0h
                  Logged:
                  Time Spent - 20m
                  20m