apache / apache/druid

[Proposal] Deprecating "approximate histogram" in favor of new sketches

Open
#6,869 11 comments 1 reaction 0 assignees View on GitHub
Proposal stale
Dominant language
Java
Stars
14.1k
Forks
3.8k
Avg merge
2d 58m
Merged PRs (30d)
233

Description

Deprecating "approximate histogram" in favor of new sketches
==========================

Motivation
----------------
Druid's "approximate histogram" aggregator has several significant drawbacks:
- No formal error bounds
- Accuracy is heavily data dependent
- Doesn't handle sorted data well
- Doesn't handle long tails well

It's not uncommon for users to get bad results using that aggregator, without any clear idea as to why, e.g. https://github.com/apache/incubator-druid/issues/6853.

Druid now has better options for quantile/histogram approximations:
- The quantiles sketch from the DataSketches extension (http://druid.io/docs/latest/development/extensions-core/datasketches-quantiles.html) is a better choice, with formal error bounds and a distribution independent algorithm.
- The upcoming moments sketch aggregator (https://github.com/apache/incubator-druid/pull/6581) is another option, using a distribution dependent algorithm with better performance/accuracy characteristics than Druid's "approximate histogram".

Proposed Changes
----------------
- Add a doc page containing the following guidance:
- Document the advantages of the sketch algorithms over "approximate histogram" to encourage users to transition
- Provide advice on how to choose between the quantiles sketch or the moments sketch
- Update docs to replace any examples/recommendations of "approximate histogram" as needed, mark "approximate histogram" as deprecated
- In line with what's being discussed in https://github.com/apache/incubator-druid/issues/6814 re: APPROX_COUNT_DISTINCT:
- Change the APPROX_QUANTILE Druid SQL function to use whatever aggregator type is stored in a segment, and use a default option when used on a numeric column
- Add individual APPROX_QUANTILE_* functions for each quantile estimation option

Changed Interfaces
----------------
The behavior of APPROX_QUANTILE in Druid SQL would change as described above.

Migration
----------------
Is it possible/valid for the newer sketch aggs to be able to operate on an old "approximate histogram"? If so, this would make migration easier for users.

If such migration is not possible, then users will need to reingest existing data, accept the discontinuity, or continue using the old aggregator.

Alternatives
----------------
We could try to make improvements to the "approximate histogram" aggregator, but I think there's little value in doing so since better alternatives already exist.

Contributor guide

Open the contributing guide

Research direction

Start with the documented quantiles sketch and moments sketch options, then review the existing approximate histogram documentation and APPROX_QUANTILE behavior. The work is complete when migration guidance, deprecation notices, and updated examples are documented, and the proposed SQL function behavior and migration limitations have been resolved.

Written by the indexing model from the issue text.

Assessment

Tech stack
sql
Domain
analytics, databases, documentation
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.