Fix out of bounds in tdigest_compute_quantiles - Githubissues

tvondra / tdigest

PostgreSQL extension for estimating percentiles using t-digest

PostgreSQL License

87 stars 13 forks source link

Fix out of bounds in tdigest_compute_quantiles #2

Closed thanodnl closed 4 years ago

thanodnl commented 4 years ago

During our integration within Citus we ran into an edge case where certain quantile lookups would cause out of bounds access to the centroids array.

The cases happened when you are looking up a quantile that is on the right side of the last centroid or on the left of the first.

The algorithm linked from the readme had an extra check that would prevent these cases: https://github.com/ajwerner/tdigestc/blob/a2a61e660188bffabf687f2fce1785439c994936/go/tdigest.c#L195-L199

This PR consists of the following changes;

Adding an assert that verifies our access to the centroids array is within bounds
Adding a simple test case that triggers both errors described above
A fix that returns the current centroids mean to prevent out of bounds access. This fix is inline with the original algorithms check linked above.

Special thanks to @min-mwei for pointing this out to us and pointing to where he thought the culprit was; https://github.com/min-mwei/tdigest/commit/9869a334e394f9411bdecdb37cf7c968c6629690

tvondra commented 4 years ago

Merged, thanks!