Window Function for PostgreSQL Desgin Overview [v04]

this document is obsolete. newer version is here: http://umitanuki.net/pgsql/wfv05/design.html

Abstract

Window Function in SQL is an OLAP functionality that provides ranking, cumulative computation, and partitioning aggregation. Many commercial RDMBS such like Oracle, MS SQL Server and DB2 have implemented part of this specification, while open source RDMBS including PostgreSQL, MySQL and Firebird doesn't yet. To implement this functionality on PostgreSQL not only helps many users move from those RDBMS to PostgreSQL but encourages OLAP applications such as BI (Business Inteligence) to analyze large data set.

The first proposal: http://archives.postgresql.org/pgsql-hackers/2008-06/msg00380.php

The subsequent discussion: http://archives.postgresql.org/pgsql-hackers/2008-07/msg00232.php

patch v04: http://umitanuki.net/pgsql/wfv04/window_functions.patch.20080830

patch v04 applied source git: http://git.postgresql.org/git/~davidfetter/window_functions/.git

sample SQL: http://umitanuki.net/pgsql/wfv04/sample.sql

Below is a description of how it is designed in the patch so far.

Roeadmap

Below are dropped features for 8.4.

The first and second topics are difficult to implement currently. Because these features require random row access, it seems that tuplestore would be able to save multiple positions to mark/restore. This is fundamental change that is over my capability. Also, user defined window functions seem to have much more to decide. I think I can't put into shape the general needs of user's window functions now. Lacking these feature, this stage looks compatible to SQLServer 2005, while Oracle and DB2 have almost full of the specification.

Terminology

When posted and discussed in -hackers list, a bit confusing was about terminology. So be aware of these definitions.

window expression

An expression evaluated in a Window node, which contains both window function and window aggregate. In a Window node, only TargetEntry that has window expression is evaluated, while other entries are evaluated some outer (scans, joins, aggs) node.

window function

A half part of window expression. This type of function returns different or the same values row by row. Since this function needs to know and operate "current window", we will need to add new mechanism to PostgreSQL. This includes new spec function such as ROW_NUMBER(), RANK(), DENSE_RANK(), LEAD(), LAG(), etc.

window aggregate

The rest part of window expression. This type of function scans tuples along the specified window frame, then returns the same values as long as the window frame doesn't slide. We can use aggregate function we already have and there's no need to add/introduce anything new.

normal aggregate (group aggregate)

This is a normal aggregate that PostgreSQL has already. "Normal" means "not windowed". In some SQL spec documents, they call it "group aggregate".

sliding window

It indicates a window frame, which is represented in SQL syntax by "ROW BETWEEN...", "RANGE BETWEEN...", "CURRENT ROW...", etc. This range slides row by row in a partitoned window, thus we need to introduce some mechanism to optimize not to allocate wasting memory.

How it works

The sample table is like this.

sample=# SELECT * FROM empsalary;
  depname  | empno | salary | enroll_date 
-----------+-------+--------+-------------
 develop   |    10 |   5200 | 2007-08-01
 sales     |     1 |   5000 | 2006-10-01
 personnel |     5 |   3500 | 2007-12-10
 sales     |     4 |   4800 | 2007-08-08
 sales     |     6 |   5500 | 2007-01-02
 personnel |     2 |   3900 | 2006-12-23
 develop   |     7 |   4200 | 2008-01-01
 develop   |     9 |   4500 | 2008-01-01
 sales     |     3 |   4800 | 2007-08-01
 develop   |     8 |   6000 | 2006-10-01
 develop   |    11 |   5200 | 2007-08-15
(11 rows)

Now let's throw a windowed query.

sample=# SELECT 
sample-#   depname,
sample-#   empno,
sample-#   salary,
sample-#   sum(salary) OVER (PARTITION BY depname)
sample-# FROM 
sample-#   empsalary;
  depname  | empno | salary |  sum  
-----------+-------+--------+-------
 develop   |    10 |   5200 | 25100
 develop   |     7 |   4200 | 25100
 develop   |     9 |   4500 | 25100
 develop   |     8 |   6000 | 25100
 develop   |    11 |   5200 | 25100
 personnel |     2 |   3900 |  7400
 personnel |     5 |   3500 |  7400
 sales     |     3 |   4800 | 20100
 sales     |     1 |   5000 | 20100
 sales     |     4 |   4800 | 20100
 sales     |     6 |   5500 | 20100
(11 rows)

You may see dep_sum is the result of SUM() for each depname, and year_sum is the result of SUM() for each enrolling year, without rows aggregated.

The ranking function of window function works as:

sample=# SELECT
sample-#   depname,
sample-#   empno,
sample-#   salary,
sample-#   rank() OVER (PARTITION BY depname ORDER BY salary)
sample-# FROM
sample-#   empsalary;
  depname  | empno | salary | rank 
-----------+-------+--------+------
 develop   |     7 |   4200 |    1
 develop   |     9 |   4500 |    2
 develop   |    10 |   5200 |    3
 develop   |    11 |   5200 |    3
 develop   |     8 |   6000 |    5
 personnel |     5 |   3500 |    1
 personnel |     2 |   3900 |    2
 sales     |     4 |   4800 |    1
 sales     |     3 |   4800 |    1
 sales     |     1 |   5000 |    3
 sales     |     6 |   5500 |    4
(11 rows)

Another example shows a use in combination with GROUP BY clause.

sample=# SELECT
sample=#   y,
sample=#   m,
sample=#   SUM(SUM(people)) OVER (PARTITION BY y ORDER BY m),
sample=#   AVG(people)
sample=# FROM(
sample=#   SELECT
sample=#     EXTRACT(YEAR FROM accident_date) AS y,
sample=#     EXTRACT(MONTH FROM accident_date) AS m,
sample=#     *
sample=#   FROM
sample=#     accident
sample=# )s
sample=# GROUP BY y, m;
  y   | m  | sum  |        avg         
------+----+------+--------------------
 2005 |  1 | 1698 | 3.5161290322580645
 2005 |  2 | 1698 | 4.8928571428571429
 2005 |  3 | 1698 | 4.3870967741935484
 2005 |  4 | 1698 | 4.7333333333333333
 2005 |  5 | 1698 | 5.0967741935483871
 2005 |  6 | 1698 | 5.2666666666666667
 2005 |  7 | 1698 | 4.8709677419354839
 2005 |  8 | 1698 | 4.7419354838709677
 2005 |  9 | 1698 | 4.8000000000000000
 2005 | 10 | 1698 | 4.8709677419354839
 2005 | 11 | 1698 | 4.1333333333333333
 2005 | 12 | 1698 | 4.5483870967741935
 2006 |  1 | 1740 | 4.3870967741935484
 2006 |  2 | 1740 | 4.5000000000000000
 2006 |  3 | 1740 | 4.8387096774193548
 2006 |  4 | 1740 | 5.0333333333333333
 2006 |  5 | 1740 | 4.4838709677419355
 2006 |  6 | 1740 | 4.1333333333333333
 2006 |  7 | 1740 | 5.1935483870967742
 2006 |  8 | 1740 | 4.7419354838709677
 2006 |  9 | 1740 | 3.8333333333333333
 2006 | 10 | 1740 | 6.2258064516129032
 2006 | 11 | 1740 | 4.4333333333333333
 2006 | 12 | 1740 | 5.3225806451612903
(24 rows)

You can put any expressions as window function's arguments or PARTITION BY/ORDER BY clause as long as it satisfies condition that normal aggregate requires.

Now WINDOW clause is shown.

sample=# SELECT depname, empno, salary, sum(salary) OVER w FROM empsalary WINDOW w AS (PARTITION BY depname);
  depname  | empno | salary |  sum  
-----------+-------+--------+-------
 develop   |    11 |   5200 | 25100
 develop   |     7 |   4200 | 25100
 develop   |     9 |   4500 | 25100
 develop   |     8 |   6000 | 25100
 develop   |    10 |   5200 | 25100
 personnel |     5 |   3500 |  7400
 personnel |     2 |   3900 |  7400
 sales     |     3 |   4800 | 14600
 sales     |     1 |   5000 | 14600
 sales     |     4 |   4800 | 14600
(10 rows)

Note that a window definition which is not referred from any function is ignored.

Changes from v03

Limitation & TODO

Added entries for pg_proc (oid)

All above is defined in nodeWindow.c temporarily.

Added entries for pg_aggregate (oid)

Some of them doesn't have trans function for optimization, which means opr_sanity check fails.

Added files

Added nodes

primnode

parser

planner

executor

Added keywords in parsing

Plan

EXPLAIN
SELECT 
  sum(salary) OVER (PARTITION BY depname) AS dep_sum
  ,sum(salary) OVER (PARTITION BY extract(YEAR FROM enroll_date)) AS year_sum
  ,*
FROM 
  empsalary;
                                       QUERY PLAN                                        
-----------------------------------------------------------------------------------------
 Window  (cost=127.23..129.83 rows=1040 width=48)
   ->  Sort  (cost=127.23..129.83 rows=1040 width=48)
         Sort Key: (date_part('year'::text, (enroll_date)::timestamp without time zone))
         ->  Window  (cost=72.52..75.12 rows=1040 width=48)
               ->  Sort  (cost=72.52..75.12 rows=1040 width=48)
                     Sort Key: depname
                     ->  Seq Scan on empsalary  (cost=0.00..20.40 rows=1040 width=48)

This plan is quite ugly, because for each window a Window node is implicitly added with a Sort node. Probably all of window and sort process is packed into a Window node. For this current plan, Sort node uses Tuplesort as you expect then Window node uses Tuplestore to store each Partition tuples. This is supposed to be the worst plan. We are able to get it better somehow.

The design of window function

These shown below are ideas about how the window function is made up.

to extend current aggregate, posed by Simon Riggs

CREATE AGGREGATE window_func() 
(
	sfunc = ...
	stype = ...
	wfunc = ...
	initcond = 
)

For each row we would execute the transition function (sfunc) then, if
there is a window function (wfunc) then we call that to return a value
for this tuple (so in that case we execute two functions per tuple in
the window). If wfunc is not set then we return the transition datatype
itself.
http://archives.postgresql.org/pgsql-hackers/2008-07/msg00236.php

Objection: A window aggregate is same as a grouping aggregate. Also, some of window functions need full scan of rows *before* returning values.

to define them as non-user-defined functions, posed by Simon Riggs

So that would mean we don't provide a mechanism for user-defined
windowed aggregate functions at all. Which solves the discussion about
how to pass generic info through to them (at least long enough to get
the first implementation done).
http://archives.postgresql.org/pgsql-hackers/2008-07/msg00239.php

Objection: As mentioned, it hides the definition of functions from external user so that implementation is easier. However, it is odd as other function types is extensible and SQL spec may add more functions later. Some unification seems need.

to introduce Window Object and pass it to the functions, posed by Hitoshi Harada

Just idea, how about pass window object to a function? We'll provide
window operation API then in the function you take window object
through fcinfo:

Datum func(PG_FUNCTION_ARGS)
{
  Datum v;
  WindowObject w = get_window(fcinfo);
  HeapTuple htup_current = window_current_row(w);
  HeapTuple htup_prev = window_preceding(w, 1);
  /* do something */
  PG_RETURN_DATUM(v);
}
http://archives.postgresql.org/pgsql-hackers/2008-07/msg00254.php

Objection: You should consider about the performance. Some optimization mechanism is required.

Actual design in patch

And currently, the actual design inside the patch is as:

The rough process of normal aggregate function is described as:

trans_value = initialize_aggregate()
for input_rows
  trans_value = advance_aggregate(trans_value, input_row)

result = finalize_aggregate(trans_value)

while window function is described as:

while window_frame
  if frame_is_new
    trans_value = initialize_aggregate();
    for input_rows
      if agg_has_trans_fn
        trans_value = advance_aggregate(trans_value, input_row)
  result = finalize_aggregate(trans_value)
  preserved_pointer = fcinfo->flinfo->fn_extra

This code means final function is called multiple times so that multiple value is returned after scanning all the frame rows. For ranking system, how to know its boundary is a bit kludge using fcinfo->context. For more detail about ranking system, see nodeWindow.c.

Things to be discussed

Reference

this document is as of 2008/08/31, written by Hitoshi Harada (umi.tanuki@gmail.com)