Cockroach: sql: `percentile() within group (order by)`

[wcharczuk]

1. As far as I know there isn't a request for this yet, I tried searching but 100% could have missed something.

2. I am trying to port some basic dashboarding code from postgres to cockroachdb, but it is missing the aggregate / math function percentile.

3. This is not a blocker for most of our workloads, but it is for this particular one.

Detail:

Typically percentile is determined by the following golang code:

// Percentile yields the value at the given ntile, where
// percent is [0,100.0]
func Percentile(percent float64, values ...float64) (percentile float64) {
    v := make([]float64, len(values))
    copy(v, values)  // expensive: O(n)
    sort.Float64s(v) // also expensive: O(n*logn)
    index := (percent / 100.0) * float64(len(v))
    i := int(math.RoundToEven(index))
    if index == float64(int64(index)) {
        percentile = (v[i-1] + v[i]) / 2
    } else {
        percentile = v[i-1]
    }
    return
}

This could be implemented in a simliar fashion to avg, min, max etc. if it's preferable to divert from the PostgreSQL implementation (i.e. implicit ascending order)

The syntax would then be something like:

select percentile(99.0, elapsed) as percentile99 from history;

[a-robinson]

Thanks for the detailed request, @wcharczuk! Handing off to @jordanlewis and @awoods187 for prioritization.

[knz]

For reference, this feature requires sorted aggregations.
pg docs:
https://www.postgresql.org/docs/10/static/functions-aggregate.html#FUNCTIONS-ORDEREDSET-TABLE

[jordanlewis]

This is now possible, since we support ordered aggregations.

[wcharczuk]

if no one else is keen on grabbing this i'm happy to.

what's the best place to get started with implementing this operator?

[knz]

I'd suggest looking at how the other windowing operators are implemented and follow the template

[jordanlewis]

@wcharczuk thanks for your interest! You can have a look at the file pkg/sql/sem/builtins/window_builtins.go for the other windowing operators that @knz mentions. There are tests in pkg/sql/logictest/testdata/logic_test/window that you can extend as well. Let me know if you have more questions, more than happy to help you!

[wcharczuk]

took a stab at percentile_disc at https://github.com/wcharczuk/cockroach, specifically added the opt, wired up some maps, and created the window type, you can use it in queries and it produces results.

one thing that is tricky looking at how postgres does this; they use WITHIN GROUP and return a single result for "ordered set aggregates", where cockroach afaik for functions like rank return a result per row in the window and you can get tricky and use FirstInPeerGroup and return null but it doesn't feel right. Is there a better way to have a window aggregate return (1) row result?

[yuzefovich]

@wcharczuk thanks for taking this on!

Indeed, window functions in CockroachDB always output a row for each input row, and it seems to be quite a big refactor to change that. Also, same as you, I don't like the idea of returning a null based on the output of FirstPeerInGroup.

I think the correct approach to implementing these ordered-set aggregate functions is to do what @ridwanmsharif did when implementing ordered aggregations in #38014. The main idea is to plan these percentiles as regular window functions (which return multiple rows) and then add a grouping stage (which will squash multiple rows into a single "final" row). See https://github.com/cockroachdb/cockroach/blob/master/pkg/sql/opt/optbuilder/window.go#L209 for an example.

Please let us know if you need more guidance or if any questions come up!

[wcharczuk]

i think i have all i need to move forward, will take a stab at this in the next couple days. thanks!

[yuzefovich]

Hey @wcharczuk, are you still interested in working on this issue? If not, I'd remove your assignment so that other interested folks could pick it up.

[wcharczuk]

hey! sorry got swamped at work an didn't have a ton of bandwidth; if someone else wants to tackle this by all means

[yuzefovich]

Cool, I'll keep this issue unassigned to see whether someone else wants to work on it.

[Anthuang]

Could I take this? Still a newbie here but happy to take a stab at it!

[yuzefovich]

@Anthuang please feel free to do so!

[Anthuang]

Awesome!

@wcharczuk mind if I base my work off of yours?

[Anthuang]

Any reason why math.RoundToEven is used? Seems to me from the PG implementation that math.Ceil makes more sense here.

postgres=# CREATE TABLE x(hi float);
CREATE TABLE
postgres=# INSERT INTO x SELECT * FROM generate_series(1, 10);
INSERT 0 10
postgres=# SELECT percentile_disc(0.49) WITHIN GROUP (ORDER BY hi) FROM x;
 percentile_disc
-----------------
               5
postgres=# SELECT percentile_disc(0.50) WITHIN GROUP (ORDER BY hi) FROM x;
 percentile_disc
-----------------
               5
postgres=# SELECT percentile_disc(0.51) WITHIN GROUP (ORDER BY hi) FROM x;
 percentile_disc
-----------------
               6
postgres=# SELECT percentile_disc(0.61) WITHIN GROUP (ORDER BY hi) FROM x;
 percentile_disc
-----------------
               7
postgres=# SELECT percentile_disc(0.66) WITHIN GROUP (ORDER BY hi) FROM x;
 percentile_disc
-----------------
               7

[yuzefovich]

On a quick glance math.Ceil also looks more reasonable to me, but feel free to pursue the approach that makes sense the most to you, and during code review we together can make the final decision.

[Anthuang]

I took a look at squashing output rows down, and it seems like multiple functions could use that. Should we track that in another issue, and then just add the percentile functionality here?

[yuzefovich]

I don't know of other use case for such squashing behavior off the top of my head, but if you think that the code written by Ridwan to support ordered aggregations can be refactored and then reused to address this issue, that sounds like a good idea to me.

[Anthuang]

I took a look at https://github.com/wcharczuk/cockroach/blob/master/docs/generated/sql/window_functions.md and functions like first_value, nth_value and rank are examples of functions where the output could be squashed to a single row.

[wcharczuk]

math.RoundToEven was used because of the nature of selecting elements by indices (*and averaging them), but if math.Ceil produces a better outcome by all means use it.

[yuzefovich]

Ok, I looked at this, and it does seem like WITHIN GROUP clause can be applied to multiple functions, and that could be implemented using the squashing behavior on top of the window functions. So I agree that it'd be beneficial to refactor existing code that supports ordered aggregations to support WITHIN GROUP as well.

Feel free to open another issue to track the addition of full support of WITHIN GROUP clause since I don't think we have any open for that. This will allow us to see whether it is a feature that's important to users. Also feel free to get started working on this as well if you feel like it :)

[Anthuang]

I'm running into this error when trying to add the percentile_cont function that takes in two floats and return a single float:

panic: counter already exists: sql.plan.builtins.percentile_cont(val: float, percentile: float) -> float

Do you know what might be causing this?

Here is the relevant code:

+   "percentile_cont": collectOverloads(winProps(), types.Scalar,
+       func(t *types.T) tree.Overload {
+           return makeWindowOverload(tree.ArgTypes{
+               {"val", types.Float}, {"percentile", types.Float}}, types.Float, newPercentileContinuousWindow,
+               "Discrete percentile: returns a value corresponding to the specified fraction in the ordering, "+
+                   "interpolating between adjacent input items if needed.")
+       }),

It works when I make the input val type and the return type generic t, but that's not desired since this should only work with intervals (not supported by cockroach) and floats.

[yuzefovich]

The error is coming from pkg/sql/sqltelemetry/features.go:GetCounterOnce and I think is caused due to my recent PR (#46009). Could you try this diff and see if it fixes the problem?

diff --git a/pkg/sql/sqltelemetry/planning.go b/pkg/sql/sqltelemetry/planning.go
index 8f2e7a35a6..14864a8ac7 100644
--- a/pkg/sql/sqltelemetry/planning.go
+++ b/pkg/sql/sqltelemetry/planning.go
@@ -192,7 +192,7 @@ func ReportJoinReorderLimit(value int) {
 // WindowFunctionCounter is to be incremented every time a window function is
 // being planned.
 func WindowFunctionCounter(wf string) telemetry.Counter {
-       return telemetry.GetCounter("sql.plan.window_function." + wf)
+       return telemetry.GetCounterOnce("sql.plan.window_function." + wf)
 }

 // OptNodeCounter should be incremented every time a node of the given

[Anthuang]

Unfortunately that didn't fix the problem, I think the counter is created here:
https://github.com/cockroachdb/cockroach/blob/d12543ac586e386c2cfefb59c6b75e25ec85a994/pkg/sql/sqltelemetry/scalar.go#L21-L23

[yuzefovich]

Oh yeah, looks like you're right, and I don't see immediately what's wrong with the code snippet you posted above. It's possible that the issue is that you're using winProps() but adding it to "aggregate builtins".