Function tdigest_compact

pg_documentdb/src/aggregation/bson_tdigest.c:316–424

* Perform compaction of the t-digest, i.e. merge the centroids as required * by the compression parameter. * * We always keep the data sorted in ascending order. This way we can reuse * the sort between compactions, and also when computing the quantiles. * * XXX Switch the direction regularly, to eliminate possible bias and improve * accuracy, as mentioned in the paper. * * XXX This initi

 * [1] https://github.com/ajwerner/tdigestc/blob/master/go/tdigest.c
 */
static void
tdigest_compact(tdigest_aggstate_t *state)
{
	int i;

	int cur;            /* current centroid */
	int64 count_so_far;
	int64 total_count;
	double denom;
	double normalizer;
	int start;
	int step;
	int n;

	/* if the digest is fully compacted, it's been already compacted */
	if (state->ncompacted == state->ncentroids)
	{
		return;
	}

	tdigest_sort(state);

	state->ncompactions++;

	if (state->ncompactions % 2 == 0)
	{
		start = 0;
		step = 1;
	}
	else
	{
		start = state->ncentroids - 1;
		step = -1;
	}

	total_count = state->count;
	denom = 2 * M_PI * total_count * log(total_count);
	normalizer = state->compression / denom;

	cur = start;
	count_so_far = 0;
	n = 1;

	for (i = start + step; (i >= 0) && (i < state->ncentroids); i += step)
	{
		int64 proposed_count;
		double q0;
		double q2;
		double z;
		bool should_add;

		proposed_count = state->centroids[cur].count + state->centroids[i].count;

		z = proposed_count * normalizer;
		q0 = count_so_far / (double) total_count;
		q2 = (count_so_far + proposed_count) / (double) total_count;

		should_add = (z <= (q0 * (1 - q0))) && (z <= (q2 * (1 - q2)));