Условие

Таблица orders(order_id, ts, amount). Посчитать скользящую медиану amount за окно из последних 100 заказов для каждой строки.

Решение

PostgreSQL

PERCENTILE_CONT(0.5) — аналитический агрегат, но не window function в стандартном смысле. Нужен трюк:

SELECT
    order_id,
    ts,
    amount,
    PERCENTILE_CONT(0.5) WITHIN GROUP (ORDER BY amount)
        OVER (ORDER BY ts ROWS BETWEEN 99 PRECEDING AND CURRENT ROW) AS running_median
FROM orders;

В PostgreSQL 11+ это работает как window function. В старых версиях — приходится через subquery.

Через subquery (универсально)

WITH numbered AS (
    SELECT order_id, ts, amount,
           ROW_NUMBER() OVER (ORDER BY ts) AS rn
    FROM orders
)
SELECT
    n1.order_id,
    n1.ts,
    n1.amount,
    (
      SELECT PERCENTILE_CONT(0.5) WITHIN GROUP (ORDER BY n2.amount)
      FROM numbered n2
      WHERE n2.rn BETWEEN n1.rn - 99 AND n1.rn
    ) AS running_median
FROM numbered n1;

Дорого, но работает везде.

ClickHouse

Прямо поддерживает:

SELECT
    order_id, ts, amount,
    quantile(0.5)(amount) OVER (
        ORDER BY ts ROWS BETWEEN 99 PRECEDING AND CURRENT ROW
    ) AS running_median
FROM orders;

MySQL

До 8.0 нет window'ов. Решение через self-join или приложение.

В 8.0+:

WITH ranked AS (
    SELECT order_id, ts, amount,
           ROW_NUMBER() OVER (ORDER BY ts) AS rn
    FROM orders
)
SELECT
    o.order_id, o.ts, o.amount,
    (
        SELECT AVG(t.amount)   -- медиана через avg средних двух
        FROM (
            SELECT amount
            FROM ranked
            WHERE rn BETWEEN o.rn - 99 AND o.rn
            ORDER BY amount
            LIMIT 2 - (100 % 2) OFFSET (100 - 1) / 2
        ) t
    ) AS running_median
FROM ranked o;

Производительность

Running median дорогой — O(n × w log w) при наивном. Для миллионов строк:

Approximate: t-digest (PostgreSQL extension), даёт 1% точности за O(n).
Reservoir sampling для приближённой медианы.
Computing в приложении через heap (поддерживать max-heap + min-heap).

Running quantile (p90, p99)

Идентично, PERCENTILE_CONT(0.9):

PERCENTILE_CONT(0.9) WITHIN GROUP (ORDER BY amount)
    OVER (ORDER BY ts ROWS BETWEEN 999 PRECEDING AND CURRENT ROW)

Подводные камни

PERCENTILE_CONT интерполирует между двумя значениями; PERCENTILE_DISC берёт точное значение из выборки.
PostgreSQL до 11 версии PERCENTILE_CONT не работал как window function.
На полном окне без ROWS BETWEEN running median ≡ глобальная медиана — невозможна оптимизация.
NULL в amount обычно игнорируются — проверяйте, если важно.
ClickHouse quantile() приближённая, quantileExact() точная (дорогая).

Эталонный ответ

PostgreSQL 11+: PERCENTILE_CONT(0.5) WITHIN GROUP (ORDER BY amount) OVER (ORDER BY ts ROWS BETWEEN 99 PRECEDING AND CURRENT ROW). ClickHouse: quantile(0.5)(amount) OVER (...). На больших данных — t-digest для приближения.

Сценарий: running median по скользящему окну