Did anyone ever notice a weird behavior in

APPROX_QUANTILE_DS

when requested for a single quantile vs multiple quantiles? After some weird results, I've wrote a small script to alternate queries between a single random percentile from a set and all percentiles in the set.

export ROUTER_URL=xxx
export MY_TABLE=xxx
export FIELD=xxx
export HEAD_JSON='Content-Type: application/json'

for ((i=1; i<=10; i++))
do
        per=`gshuf -n1 -e 10 25 50 75 90`
        curl "https://${ROUTER_URL}/druid/v2/sql" --header $HEAD_JSON --data '{"query": "SELECT COUNT(*) as \"records\", APPROX_QUANTILE_DS(\"'${FIELD}'\", 0.'${per}') as \"p'${per}'\" FROM \"'${MY_TABLE}'\"" }'
        curl "https://${ROUTER_URL}/druid/v2/sql" --header $HEAD_JSON --data '{"query": "SELECT COUNT(*) as \"records\", APPROX_QUANTILE_DS(\"'${FIELD}'\", 0.10) as \"p10\", APPROX_QUANTILE_DS(\"'${FIELD}'\", 0.25) as \"p25\", APPROX_QUANTILE_DS(\"'${FIELD}'\", 0.50) as \"p50\", APPROX_QUANTILE_DS(\"'${FIELD}'\", 0.75) as \"p75\", APPROX_QUANTILE_DS(\"'${FIELD}'\", 0.90) as \"p90\" FROM \"'${MY_TABLE}'\"" }'
done

Results:

[{"records":1071832,"p75":52.0}] 
[{"records":1071832,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]
[{"records":1071832,"p10":58.0}] <---- WRONG
[{"records":1071832,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]
[{"records":1071832,"p25":52.0}] <---- WRONG
[{"records":1071832,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]
[{"records":1071832,"p25":38.0}]
[{"records":1071832,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]
[{"records":1071832,"p25":52.0}] <---- WRONG
[{"records":1071832,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]
[{"records":1071832,"p25":38.0}]
[{"records":1071832,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]
[{"records":1071832,"p90":58.0}]
[{"records":1071832,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]
[{"records":1071832,"p75":38.0}] <---- WRONG
[{"records":1071832,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]
[{"records":1071832,"p25":52.0}] <---- WRONG
[{"records":1071832,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]
[{"records":1071832,"p50":38.0}] <---- WRONG
[{"records":1071832,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]

It's the same 1M records dataset in for queries. • multiple quantiles in a single query results are consistent • a single quantile in a query is not; in the example above the p25 is called 4 times in a row (all quantiles in between these calls) and it keeps changing between 38.0 and 52.0 What could explain this?

Hi Daniel, I am using the current Imply version and am seeing variation between query executions as well, using wikipedia (no ingestion happening therefore no fleeting real-time segments to consider):

select COUNT(*),
       avg(added) avgAdded,
       approx_quantile_ds(added, 0.90) p90,
       approx_quantile_ds(added, 0.98) p98
  from wikipedia

I will ask around ...

Thanks @John Kowtko!

Fyi I talked with folks internally and did some testing ... since the quantile function is a positional function, i.e it picks a row on a list and then returns the value in that row ... it looks like it is still selecting the row position with 99% accuracy. If there is lots of skew in your data then the result could change significantly from one row to the next. I suggest do the following: • run your P90 statement 10-20 times, record the high and low value it produces. • then count the number of records in your table that have values in that range. • divide that number by the overall record count in your table. That should give you the accuracy as a percentage • Then, for validation, find the value in your datasource that should be at the P90 record position, i.e. 1/10 of the record count in the table when sorting by that value descending.

Maybe I'm not understanding 100% your message, but I can't see how the function might be working with 99% accuracy with a variation that high.

[{"records":1071832,"p75":52.0}] 
[{"records":1071832,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]
[{"records":1071832,"p10":58.0}]             <--- here p10 returned what should be p90
[{"records":1071832,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]
[{"records":1071832,"p25":52.0}]             <--- in this one p25 returned p75 
[{"records":1071832,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]
[{"records":1071832,"p25":38.0}]
[{"records":1071832,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]
[{"records":1071832,"p25":52.0}]             <---- p25 returned again p75
[{"records":1071832,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]
[{"records":1071832,"p25":38.0}]
[{"records":1071832,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]
[{"records":1071832,"p90":58.0}]
[{"records":1071832,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]
[{"records":1071832,"p75":38.0}]             <---- now p75 returned p25
[{"records":1071832,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]
[{"records":1071832,"p25":52.0}]             <---- p25 returned p75 once more
[{"records":1071832,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]
[{"records":1071832,"p50":38.0}] 
[{"records":1071832,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]

If requesting for p25 returned me something like between p20 and p30 would be a significant-but-maybe-acceptable variation, but a p10 request returning p90 is just waaaay to much. I know this column values follow a normal distribution, I can even see it in Druid Explore tab. There's no big skew.

Can you try this out on the wikipedia dataset, use the "added" column for the quantiles, to see if you still see this issue? I don't see it on wikipedia myself.

I dont believe this is a good test case, John. Wikipedia dataset is super skewed.

Hi Daniel, I just tried your script ... (shuf isn't working for me so I hardcoded to P90) ... the variations still look the same to me ...

johnkowtko@John-Kowtko ~ % ./foo.sh 
[{"records":24433,"p90":675.0}]
[{"records":24433,"p10":0.0,"p25":0.0,"p50":4.0,"p75":78.0,"p90":786.0}]
[{"records":24433,"p90":635.0}]
[{"records":24433,"p10":0.0,"p25":0.0,"p50":4.0,"p75":74.0,"p90":722.0}]
[{"records":24433,"p90":616.0}]
[{"records":24433,"p10":0.0,"p25":0.0,"p50":4.0,"p75":74.0,"p90":648.0}]
[{"records":24433,"p90":718.0}]
[{"records":24433,"p10":0.0,"p25":0.0,"p50":3.0,"p75":75.0,"p90":617.0}]
[{"records":24433,"p90":798.0}]
[{"records":24433,"p10":0.0,"p25":0.0,"p50":4.0,"p75":81.0,"p90":725.0}]
[{"records":24433,"p90":722.0}]
[{"records":24433,"p10":0.0,"p25":0.0,"p50":4.0,"p75":74.0,"p90":762.0}]
[{"records":24433,"p90":728.0}]
[{"records":24433,"p10":0.0,"p25":0.0,"p50":4.0,"p75":74.0,"p90":620.0}]
[{"records":24433,"p90":722.0}]
[{"records":24433,"p10":0.0,"p25":0.0,"p50":4.0,"p75":80.0,"p90":725.0}]
[{"records":24433,"p90":808.0}]
[{"records":24433,"p10":0.0,"p25":0.0,"p50":4.0,"p75":72.0,"p90":626.0}]
[{"records":24433,"p90":675.0}]
[{"records":24433,"p10":0.0,"p25":0.0,"p50":4.0,"p75":78.0,"p90":648.0}]
johnkowtko@John-Kowtko ~ %

Yeah, you're seeing a huge variation as well... p90 returning 616, 617, 620, 626, 635, 648, 675, 718, 722, 725, 728, 762, 786, 798, 808 I was assuming

APPROX_QUANTILE_DS

as approximate, but kinda a deterministic approximation, so 20 repetitions would return the same value which would be in a ±3% range from the actual value you would get using an exact algorithm.

The function is not computing a value-based metric ... it is estimating the position of an entry on a sorted list. In wikipedia there are 24400k records, so P90 would be at record position 2440 from the top when sorted. The values that P90 is putting out range from ~600-800 ... when you check the list you see those values range across ~250 records ... so the error here is 250/24400, or about 1%. Which means the algorithm is 99% accurate. The fact that the values of the field across that 250 record range varies so much, is orthogonal ... that's the skew in the values, not the accuracy of the quantile function in finding the right record position on the list. For value based equivalents of a P90, wouldn't it be more related to standard deviations and sigmas?

I might understand this in the wikipedia dataset where I showed the distribution is very skewed. But in my dataset with a normal distribution how can I ask for a p10 and get in return the equivalent of p90?

fwiw,

APPROX_QUANTILE_DS

isn't guaranteed to be a stable approximation— the intended guarantee is that each result adheres to the advertised error bounds on the datasketches website, but will not necessarily be the same number from run to run. this is true of most datasketches operations

Uuuuh right on spot, @Gian Merlino! I've used the context thousands of times and forgot while writing the script. Adding both no cache instructions in the right place, the results are good.

[{"records":1373315,"p10":32.0,"p25":38.0,"p50":45.0,"p75":52.0,"p90":58.0}]
[{"records":1373315,"p10":32.0}]
[{"records":1373315,"p50":45.0}]
[{"records":1373315,"p25":38.0}]
[{"records":1373315,"p75":52.0}]
[{"records":1373315,"p90":58.0}]
[{"records":1373315,"p50":45.0}]
[{"records":1373315,"p25":38.0}]
[{"records":1373315,"p90":58.0}]
[{"records":1373315,"p10":32.0}]
[{"records":1373315,"p10":32.0}]
[{"records":1373315,"p25":38.0}]
[{"records":1373315,"p25":38.0}]
[{"records":1373315,"p90":58.0}]
[{"records":1373315,"p25":38.0}]
[{"records":1373315,"p10":32.0}]
[{"records":1373315,"p10":32.0}]
[{"records":1373315,"p25":38.0}]
[{"records":1373315,"p25":38.0}]
[{"records":1373315,"p10":32.0}]
[{"records":1373315,"p10":32.0}]

all as expected testing the combinations:

"context": { "useCache":"true", "useResultLevelCache":"true" }  --> bad results
"context": { "useCache":"false","useResultLevelCache":"true" }  --> bad results
"context": { "useCache":"true", "useResultLevelCache":"false" } --> OK
"context": { "useCache":"false","useResultLevelCache":"false" } --> OK

So it's the result level cache that's messing with the results

ok i think i see the problem

why would the result level cache be a problem?

there's a bug in how the keys are computed that can cause a collision

so its something to be fixed in Druid 30, I suppose. Is this bug around for a while or a new thing?

This is great, thanks for your help @Gian Merlino @John Kowtko! So for now I will turn result level cache off, to make sure we get consistent results.