rolling sum in sql - window aggregates and CTE much faster than subquery or join

rolling_sum.sql

-- table
-- name       number
-- 1          10
-- 2          20
-- 3          10
-- 4          30
-- ...

-- result
-- name  amount
-- a          10
-- b          30
-- c          40
-- d          70
-- ...


-- 変数は使わないでsqlをかく     
-- write without stored proc/vars

-- postgres

CREATE TABLE roll_sum
(
  name integer NOT NULL,
  val integer NOT NULL
);

CREATE INDEX idx_roll_sum_name
  ON roll_sum
  USING btree
  (name);

CREATE INDEX idx_roll_sum_val
  ON roll_sum
  USING btree
  (val);


INSERT INTO roll_sum
  SELECT
    generate_series( 1, 10000 ),
    CEIL( RANDOM() * 10 );



-- window function

SELECT
  'val_' || name AS name,
  SUM( val ) OVER roll_win AS nr
FROM
  roll_sum
  WINDOW roll_win AS ( ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW );


-- cte

WITH RECURSIVE rolling_sum AS
(
  -- non-recursive term
  SELECT
    MAX( r.name ) AS name,
    SUM( r.val ) AS nr
  FROM roll_sum r

  UNION ALL

  -- recursive term
  SELECT
    rs.name - 1 AS name,
    s.nr - rs.val AS nr
  FROM
    roll_sum rs
    JOIN rolling_sum s
      ON rs.name = s.name
)
SELECT
  'val_' || s.name AS name,
  s.nr
FROM
  rolling_sum s
WHERE
  s.nr > 0
ORDER BY
  s.name ASC;


-- join

SELECT
  'val_' || l.name AS name,
  SUM( r.val ) AS nr
FROM
  roll_sum l
  JOIN roll_sum r
    ON r.name <= l.name
GROUP BY
  l.name
ORDER BY
  l.name

-- subquery

SELECT
  'val_' || o.name AS name,
  ( SELECT SUM( i.val ) FROM roll_sum i WHERE i.name <= o.name ) AS nr
FROM
  roll_sum o;



-- timings (DESC) on my machine with postgres 9.2.1 

-- with 10000 entries
-- join: ~16000ms
-- subquery: ~10000ms
-- recursive CTE: ~45ms
-- window function: ~16ms

-- with 20000 entries
-- join: ~52000ms
-- subquery: ~44000ms
-- recursive CTE: ~90ms
-- window function: ~30ms

-- with 1.000.000 entries i did not want to wait until join or subquery finish, but:
-- recursive CTE: ~5000ms
-- window function: ~850ms

-- 10.000.000 entries
-- recursive CTE: ~52000ms
-- window function: ~9300ms

-- NICE!