Druid: TopN with threshold 1 - is this super inaccurate?

[donpinkus]

A few of us are looking through the docs on TopN and trying to understand the threshold parameter.

(Note I will happily update the docs once I understand it myself)

Example:
I have a database with a row for each commit made on GitHub. How can I get the longest commit, for each minute? (1 minute intervals)

Example datasource "github_commits":

timestamp, commit_id, commit_length

TopN query, with a threshold of 1

{
  "queryType": "topN",
  "dataSource": "github_commits",
  "dimension": "commit_id",
  "threshold": 1,
  "metric": "commit_length",
  "aggregations": [
    { "type": "longMax", "name": "commit_length", "fieldName": "commit_length" }
  ],
  "intervals": ["2018-01-06T00:00:00.000Z/2018-01-07T00:00:00.000Z"],
  "granularity": "minute"
}

Is this query correct? It runs, and it only returns at most 1 record per interval... but the docs say "TopNs can be made more accurate by increasing the threshold."

So does a threshold of 1 mean "Give me the top 1 record"? In which case this query is fine, and the statement about higher thresholds doesn't make sense...
Or does it mean something else, like only bother sorting 1 record? (in which case I'm not getting the top one, I'm just getting the first one)

In SQL, if I do an ORDER BY and a LIMIT, the LIMIT is applied after the ORDER BY. That means ORDER BY commit_length DESC LIMIT 1 gives me the top 1 commit. I'm trying to understand if threshold is behaving the same way here.

[himanshug]

yes, threshold is behaving same way ... it is 'N' of the 'TopN' .

however the difference is that historicals will send their top 1000 results by default and top 1 would be chosen from the merged results of those... which may or may not be accurate depending upon your data.

if you wanted accurate behavior then you would use groupBy query with order-by and limit 1 .

[donpinkus]

@himanshug

however the difference is that historicals will send their top 1000 results by default and top 1 would be chosen from the merged results of those... which may or may not be accurate depending upon your data.

Ok, I'm going to translate this back to you - and let me know if I understand it correctly.

"Historicals" are a node in Druid that processes data when you run a query.
Data can be divided among historicals. (Not sure how, assuming by timestamp?)
When I run the "Get longest github commit" topN query the following happens:

1. each historical node will take a chunk of the data
2. each historical node sorts their chunk by my metric (bit confused on if its by metric or aggregation - both are required in the query)
3. each historical node takes the top 1000 results & sends it back to the master node
4. the master node merges the data from the historical nodes. Then it takes the top N (where N is my threshold value), and returns it as the result.

Is that correct?

If so, why would a low "threshold" decrease accuracy? It's just choosing the number of results to return in Step 4.

[himanshug]

Is that correct?

Yes. Step-3 is a bit more involved in that it would gather top-1000 for each chunk on that historical, then do a merging pass on historical itself to merge top-1000 from all chunks to create another top-1000 and that would be sent to broker.

If so, why would a low "threshold" decrease accuracy? It's just choosing the number of results to return in Step 4.

No, low "threshold" wouldn't decrease accuracy.

[himanshug]

also, http://druid.io/docs/0.11.0/misc/papers-and-talks.html has some good links to understand what various nodes are etc .

[pjain1]

@donpinkus - here's my understanding.

Lets take an example of when TopN can be approximate. Assume there are 100 segments present on 100 historical nodes. Now, lets say we want Top 1000 results (equivalent to default threshold value) for a dimension A using a metric M and the data in segments looks like this -

| segment1  | segment2  | ... | segment99 | segment100 |
|-----------|-----------|-----|-----------|------------|
| A   |   M | A   |   M |     | A   |   M | A   |   M  |
| a1  |   2 | a1  |   2 |     | a1  |   2 | a1  |   2  |
| a2  |   2 | a2  |   2 |     | a2  |   2 | a2  |   2  |
|     ...   |     ...   |     |    ...    |    ...     |
| a1000|  2 | a1000|  2 |     | a1000|  2 | a1000|  2  |
| a1001|  1 | a1001|  1 |     | a1001|  1 | a1001| 150 |

Looking at the data we can see that the Top 1000 results should contain a1001 as the sum of all metrics for this dimension is highest which is 249 and for other dimensions the sum would be 200.

Now lets see what will actually happen, each historical will return Top 1000 results for the segments they are serving. Therefore, for all segments (except for segment100) Top 1000 results will contain dimensions from a1 to a1000 with metric value as 2, where as for segment100 Top 1000 results will contain a1001 and some 999 other dimensions. Broker will merge all the metrics for all dimensions returned by historicals and calculate the final Top 1000 results but the results will not contain a1001 as the final sum for this dimension will be only 150 where for 998 dimensions it will be 200 and for the remaining one it will be 198.

In summary if the cardinality of a dimension is more than max(1000, threshold) then the results can be approximate and increasing threshold can improve accuracy. That's what the documentation means.

In your case, assuming the commit_id dimension always have unique values, therefore same dimension value can never be present in more than one segment. You will always get correct result with TopN query.

Note - The threshold mentioned above corresponds to the server parameter druid.query.topN.minTopNThreshold (server restart needed to take effect) or minTopNThreshold in the query context per query. Where as the threshold parameter in the query refers to the N in TopN (Indeed the docs are confusing).

[donpinkus]

@himanshug - cool thanks for the druid video resource.

So it says in the docs low thresholds decrease accuracy: "TopNs can be made more accurate by increasing the threshold."

However, you said No, low "threshold" wouldn't decrease accuracy.

Are you correct, or are the Druid docs, or am I missing something?

[donpinkus]

@pjain1 - ahhh that's a great explanation, thanks for taking the time to write it all out.

I'm going to close the issue - but that should probably be added to the docs, since the current explanation makes usage of "threshold" ambiguous.

[himanshug]

@donpinkus "TopNs can be made more accurate by increasing the threshold." comment in the document refers to increasing the the number druid.query.topN.minTopNThreshold (1000 by default) explained later in the doc. if that is true then document is misleading and needs to be corrected.

I don't think that increasing threshold param in the query would increase accuracy.

other devs can probably comment if there is something I'm missing.

[gianm]

I don't think that increasing threshold param in the query would increase accuracy.

Increasing it should not have an effect on accuracy until you increase it beyond the minTopNThreshold. Then it will have an effect for the reasons that @pjain1 laid out.

[pjain1]

@himanshug you are correct, added a note in the comment.

[glasser]

@pjain1 your comment https://github.com/apache/incubator-druid/issues/5236#issuecomment-357088879 is incredibly helpful, and belongs in the manual!