---
title: "The bucket allocation scheme"
url: "https://docs.yugabyte.com/stable/api/ysql/exprs/window_functions/analyzing-a-normal-distribution/bucket-allocation/"
---

# The bucket allocation scheme

The bucket allocation scheme. Part of the code kit for the "Analyzing a normal distribution" section within the YSQL window functions documentation.

It might seem that the built-in function `width_bucket()` ([here](https://www.postgresql.org/docs/15/functions-math.html#FUNCTIONS-MATH-FUNC-TABLE "here") in the PostgreSQL documentation) is tailor-made for this task. But there's a snag.

The values in the column *t4.dp\_score"* lie in this so-called closed-closed interval `[0, 100]`—expressed like this in SQL:

```
dp_score is between 0 and 100
```

**Note:** [This Wikipedia article](https://en.wikipedia.org/wiki/Interval_%28mathematics%29 "This Wikipedia article") explains the terminology used to characterize intervals. For example:

> The open-closed interval (0,1] means greater than 0 and less than or equal to 1. And the closed-open interval [0,1) means greater than or equal to 0 and less than 1.

The values returned both by [`percent_rank()`](/stable/api/ysql/exprs/window_functions/function-syntax-semantics/percent-rank-cume-dist-ntile/#percent-rank "percent_rank()") and by [`cume_dist()`](/stable/api/ysql/exprs/window_functions/function-syntax-semantics/percent-rank-cume-dist-ntile/#cume-dist "cume_dist()"), when scaled so that they are percentages, also lie in this same range.

Here is the signature (using sensibly chosen names for the formal parameters) of the `double precision` overload of `width_bucket()`:

```
function width_bucket(
  val    in double precision,  -- the value to be allocated
  lb     in double precision,  -- the lower bound of the overall closed-open interval
  ub     in double precision,  -- the upper bound of the overall closed-open interval
  n_vals in int)               -- the required number of buckets
  returns int
```

If you invoke `width_bucket()` to allocate a value `$1` with `lb = 0`, `ub = 100`, and `n_vals = 10`, like this:

```
width_bucket($1, 0, 100, 10)
```

then the buckets are defined as these *closed-open* intervals:

```
[ 0,  10)  ->  bucket  1
[10,  20)  ->  bucket  2
[20,  30)  ->  bucket  3
...
[80,  90)  ->  bucket  9
[90, 100)  ->  bucket 10
```

Any value that is less than *0* is allocated to the lower overflow bucket *0*. And any value that is greater than or equal to the value *100* is allocated to the upper overflow bucket *11*. Here is an example:

```plpgsql
do $body$
declare
  lb     constant double precision := 0;
  ub     constant double precision := 100;
  n_vals constant int              := 10;
begin
  assert width_bucket( -0.0000000001, lb, ub, n_vals) =  0, 'unexpected';
  assert width_bucket(  0,            lb, ub, n_vals) =  1, 'unexpected';
  assert width_bucket( 99.9999999999, lb, ub, n_vals) = 10, 'unexpected';
  assert width_bucket(100,            lb, ub, n_vals) = 11, 'unexpected';
end;
$body$;
```

This means that attention has to be paid to the special case when the value to be allocated is *100* in order that it is allocated to bucket *10*, and *not* to the upper overflow bucket *11*. However, this is not the main snag. Rather, it's this:

- Pen-and-paper analysis, and some empirical testing, show that [`ntile()`](/stable/api/ysql/exprs/window_functions/function-syntax-semantics/percent-rank-cume-dist-ntile/#ntile "ntile()"), [`percent_rank()`](/stable/api/ysql/exprs/window_functions/function-syntax-semantics/percent-rank-cume-dist-ntile/#percent-rank "percent_rank()"), and [`cume_dist()`](/stable/api/ysql/exprs/window_functions/function-syntax-semantics/percent-rank-cume-dist-ntile/#cume-dist "cume_dist()") can produce the same results only when these *open-closed* intervals are used:

```
( 0,  10]  ->  bucket  1
(10,  20]  ->  bucket  2
(20,  30]  ->  bucket  3
...
(80,  90]  ->  bucket  9
(90, 100]  ->  bucket 10
```

This means that attention has to be paid to the special case at the other end of the *closed-closed* interval of possible input values: when the value to be allocated is *0*, it must be allocated to bucket *1*, and *not* to the lower overflow bucket *0*.

The consequence is that `width_bucket()` cannot be used *as is*. This leaves two choices. Each relies on implementing a new function `bucket()` with the same signature as `width_bucket()` but with a different implementation.

- The first choice is to implement `bucket` as a wrapper around `width_bucket()` to change its behavior at the bucket boundaries, See [cr\_bucket\_using\_width\_bucket.sql](/stable/api/ysql/exprs/window_functions/analyzing-a-normal-distribution/cr-bucket-using-width-bucket/ "cr_bucket_using_width_bucket.sql").
- The second choice is to implement `bucket` from scratch. See [`cr_bucket_dedicated_code.sql`](/stable/api/ysql/exprs/window_functions/analyzing-a-normal-distribution/cr-bucket-dedicated-code/ "cr_bucket_dedicated_code.sql").

See [do\_assert\_bucket\_ok.sql](/stable/api/ysql/exprs/window_functions/analyzing-a-normal-distribution/do-assert-bucket-ok/ "do_assert_bucket_ok.sql") for the acceptance test that each must pass.