What about less accurate but more efficient percentile calculation?

[tisba]

I was wondering, what your opinion is about offering a less accurate, but way more efficient method for percentile calculation.

AFAIK influx currently calculates percentiles in a naive way. There are more efficient (and way faster approaches) to do this (t-DIGESTS used in Elasticsearch e.g.). If you have many events, distributed over your cluster, then it might be nice to offer the user a way to trace accuracy for speed.

I have to deal with millions of events that I'd like to run percentile (actually I calculate entire percentile ranges) calculations over. The performance is okay-isch right now, but not very good for an interactive use case.

[jvshahid]

Sounds interesting. We've talking about this for a while. I'll read the paper and try to get something out there soon for you to try.

[tisba]

Did you had any time to take a look at this, @jvshahid? Performance of percentile calculation is starting to give me a little headache.

[tisba]

Just FYI

I've read the t-DIGESTS paper during my vacation multiple times and I think it's a great fit for InfluxDB. I will have to take a closer look at this algorithm for a project (most probably in Erlang), but I'm happy to share my remarks regarding a possible implementation in Go.

Why I think t-DIGESTS is a good fit:

• it's very easy (and efficiently) parallelizable
• precision (error) can be easily configured and there are very few parameters to configure tradeoffs (sample amount, compression ratio and size for digest data structures)

[jvshahid]

@tisba that would be great

[seiflotfy]

I am looking through the right place in the code to implement it.
Also I am considering adding some new SQL statement like in Redshift: SELECT APPROXIMATE DISTINCT(COUNT()) ... Which implements a hyperloglog++. Should be faster

[beckettsean]

As mentioned in my post to the mailing list we are experimenting with simplifying our open GitHub Issues. This feature request has been rolled into an aggregate issue for all function requests, so that we can close this issue until we are ready to work on it.

You may continue to make comments here. Closing the issue does not mean we are rejecting this idea.