Inconsistencies in the result of the quantile aggregator

[jacktomcat]

I use the quantile aggregator, but many times the query results are inconsistent. The version of Druid is 0.12.1

Here's my script

{
  "queryType": "groupBy",
  "dataSource": {
    "type": "table",
    "name": "SVR_ACTION_DATA"
  },
  "intervals": {
    "type": "LegacySegmentSpec",
    "intervals": [
      "2018-04-30T00:00:00.000Z/2018-05-31T00:00:00.000Z"
    ]
  },
  "virtualColumns": [],
  "filter": {
    "type": "and",
    "fields": [
      {
        "type": "selector",
        "dimension": "biz_system_id",
        "value": "1",
        "extractionFn": null
      },
      {
        "type": "selector",
        "dimension": "data_type",
        "value": "APP",
        "extractionFn": null
      }
    ]
  },
  "granularity": "ALL",
  "dimensions": [],
  "context" : {
    "skipEmptyBuckets": "true"
  },
  "aggregations": [
    {
      "type": "longSum",
      "name": "respTime",
      "fieldName": "resp_time",
      "expression": null
    },
    {
      "type": "longSum",
      "name": "successCount",
      "fieldName": "success_count",
      "expression": null
    },
    {
      "type": "approxHistogramFold",
      "name": "resp_time_his",
      "fieldName": "resp_time_his",
      "resolution": 600,
      "numBuckets": 7,
      "lowerLimit": "-Infinity",
      "upperLimit": "Infinity"
    }
  ],
  "postAggregations": [
    {
      "type": "arithmetic",
      "name": "response",
      "fn": "/",
      "fields": [
        {
          "type": "fieldAccess",
          "name": "0-fieldaccess",
          "fieldName": "respTime"
        },
        {
          "type": "fieldAccess",
          "name": "1-fieldaccess",
          "fieldName": "successCount"
        }
      ],
      "ordering": null
    },
    {
      "type": "quantiles",
      "name": "respTimeHis",
      "fieldName": "resp_time_his",
      "probabilities": [
        0.5,0.6,0.7,0.8
      ]
    }
  ],
  "having": null,
  "limitSpec": {
    "type": "default",
    "columns": [],
    "limit": 2147483647
  },
  "descending": false
}

The following is the result of my running：

[
    {
        "version": "v1",
        "timestamp": "2018-04-30T00:00:00.000Z",
        "event": {
            "successCount": 1364670887,
            "resp_time_his": {
                "breaks": [
                    -124.83333587646484,
                    0,
                    124.83333587646484,
                    249.6666717529297,
                    374.5,
                    499.3333435058594,
                    624.1666870117188,
                    749
                ],
                "counts": [
                    0,
                    5772020,
                    5751136,
                    5755229,
                    5747462.5,
                    5748575,
                    5775551
                ]
            },
            "response": 9.481008641169906,
            "respTime": 12938456472,
            "respTimeHis": {
                "probabilities": [
                    0.5,
                    0.6,
                    0.7,
                    0.8
                ],
                "quantiles": [
                    373.30453,
                    448.30597,
                    523.41125,
                    598.38446
                ],
                "min": 0,
                "max": 749
            }
        }
    }
]

But quantiles array values have errors，examples:

quantiles: [373.30453, 448.30597, 523.41125, 598.38446 ]
quantiles: [373.64453, 449.40597, 509.42345, 573.23112 ]
.....

What is the cause of this ？ @fjy @gianm @xvrl @nishantmonu51 @drcrallen

[asdf2014]

Hi, @jacktomcat . This result is obtained because the quantile aggregator uses an approximate algorithm called sketch. You can find it in the Druid doc. A parper and blog are also available in the document to learn the algorithm deeply. BTW, there is a Table Guide for Quantiles DoublesSketch Size in Bytes and Approximate Error, which might help you.

[leerho]

The above code, and references to the Druid doc, the referenced paper, and blog all refer to the Druid built-in "Approximate Histogram". It is an empirical, heuristic algorithm and is very data sensitive and can produce significant errors. It should be noted that the authors of the paper, which describes the algorithm, specifically mention several caveats:

• “The second category, to which our algorithm belongs, consists of heuristics that work well empirically and demand low amounts of space, but lack any rigorous accuracy analysis.” Page 856, section 2.4.1.
• “…when the data distribution is highly skewed, the accuracy of [our] on-line histogram decays …[so] practitioners may prefer to resort to guaranteed accuracy algorithms.” Page 857, first paragraph.

Do not confuse this Druid built-in Approximate Histogram with the DataSketches Quantiles DoublesSketch, which can also produce approximate histograms. The above referenced error and size table is for the DataSketches Quantiles DoublesSketch and NOT for the Druid built-in Approximate Histogram.

Visit Druid Approximate Histogram Study to get an idea of how poorly it can perform on real data.

Visit Quantiles StreamA Study to compare how the DataSketches Quantiles DoublesSketch performs on the same data.

The Druid Approximate Histogram has no guarantees on error bounds. It does not qualify as a true "sketch", for this reason and several others. See discussion #6869 that proposes to deprecate the Druid built-in Approximate Histogram, and replace it with the newer and much more robust and accurate DataSketches Quantiles DoublesSketch.

[stale]

This issue has been marked as stale due to 280 days of inactivity. It will be closed in 4 weeks if no further activity occurs. If this issue is still relevant, please simply write any comment. Even if closed, you can still revive the issue at any time or discuss it on the dev@druid.apache.org list. Thank you for your contributions.

[stale]

This issue has been closed due to lack of activity. If you think that is incorrect, or the issue requires additional review, you can revive the issue at any time.