Rolling (moving) Median In Greenplum

I would like to calculate the rolling median for a column in Greenplum, i.e. as below: | x | rolling_median_x | | -- + ---------------- | | 4 | 4 | | 1 |

Solution 1:

One remark - a citate from Wikipedia: ORDER BY

ORDER BY is the only way to sort the rows in the result set. Without this clause, the relational database system may return the rows in any order. If an ordering is required, the ORDER BY must be provided in the SELECT statement sent by the application. Although some database systems allow the specification of an ORDER BY clause in subselects or view definitions, the presence there has no effect. A view is a logical relational table, and the relational model mandates that a table is a set of rows, implying no sort order whatsoever.

---

Since you need to calculate the median for the current and preceding rows, you must have in the table an additional row that defines the order of rows and can be used to determine which rows precede given row and which ones come after. Let say some id column like this:

| id | x | rolling_median_x |
|----|---|------------------|
|  1 | 4 |                4 |
|  2 | 1 |              2.5 |
|  3 | 3 |                3 |
|  4 | 2 |              2.5 |
|  5 | 1 |                2 |
|  6 | 6 |              2.5 |
|  7 | 9 |                3 |

---

If you cannot use analytic functions, then try pure SQL. This article shows various methods of computing the Median with SQL. I think the Henderson’s Median would be best for our needs:

SELECTCASECOUNT(*) %2WHEN0-- even sized tableTHEN (P1.part_wgt +MIN(CASEWHEN P2.part_wgt > P1.part_wgt
                                  THEN P2.part_wgt
                                  ELSENULLEND))/2.0ELSE P1.part_wgt --odd sized tableENDAS median 
  FROM Parts AS P1, Parts AS P2
 GROUPBY P1.part_wgt
HAVINGCOUNT(CASEWHEN P1.part_wgt >= P2.part_wgt
                  THEN1ELSENULLEND)
       = (COUNT(*) +1) /2;

---

Just run this query for each row as a dependent subquery, a general idea is like this:

SELECT t.*, (
        SELECT .... Henderson's query FROM table xWHERE x.id <= t.id
        ......
       ) As our_median
FROM table t

---

You can find an example implementation in this demo

SELECT t.*, (
    SELECTCASECOUNT(*) %2WHEN0-- even sized tableTHEN (P1.x +MIN(CASEWHEN P2.x > P1.x
                                      THEN P2.x
                                      ELSENULLEND))/2.0ELSE P1.x --odd sized tableENDAS median 
      FROM Table333 AS P1, Table333 AS P2
      WHERE p1.id <= t.id AND p2.id <= t.id
     GROUPBY P1.x
    HAVINGCOUNT(CASEWHEN P1.x >= P2.x
                      THEN1ELSENULLEND)
           = (COUNT(*) +1) /2
    ) as Our_median
FROM Table333 t;

| id | x | rolling_median_x | our_median ||----|---|------------------|------------||1|4|4|4||2|1|2.5|2.5||3|3|3|3||4|2|2.5|2.5||5|1|2|2||6|6|2.5|2.5||7|9|3|3|

This query will probably be slow - this is a price you must pay for having ancient version of PostgreSQL

Solution 2:

I'm using psql 8.2.15 and updating is not an option unfortunately.

Ouch.

If it was the rolling mean, things would be simple, but the rolling median will be very slow due to the need for sorting. The way to avoid this is to insert the values into a heap or a btree as they come which allows to get the rolling median without sorting on each new value. But this needs custom code.

I would use plpython to implement this:

Rolling median algorithm in C