Oracle — приблизительное разбиение на диапазоны

Недавно у меня возникла задача по разбиению мульти-терабайтной таблицы на равные диапазоны по числовому полю id. Причём данные распределены по id крайне неравномерно, где-то есть большие "лакуны", где-то непоследовательная генерация и т.д., и т.п. Конечно, можно применить честное решение в лоб — использовать функцию NTILE, но я довольно быстро осознал, что это приведёт к многочасовому запросу с большой вероятностью упасть из-за недостатка TEMP. Но, к счастью, зачастую в таких задачах, как и в моём случае, идеальное разделение на диапазоны не требуется, достаточно более-менее приличного.

Я решил провернуть небольшой трюк для получения приблизительного разделения. Давайте посмотрим, что у меня получилось на модельном примере.

DROP table t_ids;

CREATE TABLE t_ids (id primary key , payload) as 
select id, payload FROM (
SELECT rownum as id, RPAD('*', DBMS_RANDOM.VALUE(100,200), '*') as payload from dual connect by level <=1e6
union all
SELECT rownum+2e6 as id, RPAD('*', DBMS_RANDOM.VALUE(100,200), '*') as payload from dual connect by level <=1e6
union all
SELECT rownum+6e6 as id, RPAD('*', DBMS_RANDOM.VALUE(100,200), '*') as payload from dual connect by level <=1e6
)
order by DBMS_RANDOM.value;

Создаём табличку из двух полей: id NUMBER, payload VARCHAR2(4000)
Значение id идёт по миллиону записей: начиная с 1, с большими дырками в 1 млн и в 3 млн значений.

Идеальное разделение по диапазонам можно сделать следующим образом:

select min(id), max(id), count(1), bkt
FROM (
select id, ntile(8) OVER (ORDER BY id) as bkt from t_ids 
) group by bkt
order by 1;

Что даёт в моём случае следующее разделение:

MIN(ID)	MAX(ID)	COUNT(1)	BKT
1	    375000	375000	1
375001	750000	375000	2
750001	2125000	375000	3
2125001	2500000	375000	4
2500001	2875000	375000	5
2875001	6250000	375000	6
6250001	6625000	375000	7
6625001	7000000	375000	8

Видно, что разделение действительно идеально, по 375000 записей в каждом бакете, но все же есть одна беда: сделать тоже самое на громадной таблице практически невозможно.

Я решил попробовать использовать sample_clause. Итак, первый подход к снаряду:

select min(id), max(id),  bkt
FROM (
select id, ntile(8) OVER (ORDER BY id) as bkt from t_ids SAMPLE(0.1)
) group by bkt
order by 1;

Выполняется очень быстро, так как мы сканируем приблизительно 1/1000 всех строк таблицы.

MIN(ID)	MAX(ID)	BKT
185	    393674	1
394199	751639	2
752054	2144825	3
2145030	2540133	4
2541396	2927727	5
2928411	6296609	6
6299314	6656857	7
6658031	6998888	8

Но есть проблема: верить одновременно обоим диапазонам нельзя, иначе потеряете данные! Задача состоит в том, чтобы обработать все данные, но, возможно, с неравномерным распределением на "бакеты", ведь терять данные недопустимо!

Первое тонкое место: можно выбрать либо maх, либо min значения и работать далее уже с ними. См. картинку ниже

SELECT lag(max(id)) OVER (order by bkt) prev_max_id, max(id) max_id, lead(max(id)) OVER (order by bkt) next_max_id,   bkt
FROM (
SELECT id, ntile(8) OVER (ORDER BY id) as bkt from t_ids SAMPLE(0.1)
) GROUP BY bkt
ORDER BY bkt;

PREV_MAX_ID	MAX_ID	NEXT_MAX_ID	BKT
        365798	740650	1
365798	740650	2088573	2
740650	2088573	2479586	3
2088573	2479586	2846737	4
2479586	2846737	6238003	5
2846737	6238003	6614359	6
6238003	6614359	6999794	7
6614359	6999794		    8

Здесь мы выбираем одну из точек диапазона, в качестве реперной и используем.

Второе тонкое место: верить границам диапазонов нельзя, т.е. нельзя верить min(id) для самого левого значения и max(id) для самого правого.

В итоге полный генератор клаузы WHERE выглядит так:

SELECT CASE
         WHEN prev_max_id is null then
          ' id<' || max_id
         WHEN next_max_id is null THEN
          'id>=' || prev_max_id
         ELSE
          'id>=' || prev_max_id || ' AND id<' || max_id
       END clause_where
  FROM (SELECT lag(max(id)) OVER(order by bkt) prev_max_id,
               max(id) max_id,
               lead(max(id)) OVER(order by bkt) next_max_id,
               bkt
          FROM (SELECT id, ntile(8) OVER(ORDER BY id) as bkt
                  FROM t_ids SAMPLE(0.1))
         GROUP BY bkt)
 ORDER BY bkt;

И выдаёт следующий результат:

 id<355683
id>=355683 AND id<711557
id>=711557 AND id<2094958
id>=2094958 AND id<2481798
id>=2481798 AND id<2865697
id>=2865697 AND id<6226020
id>=6226020 AND id<6606343
id>=6606343

Выполнив серию SELECT'ов с данным условием, мы получаем ошибку не более 12% для модельного примера (мы знаем количество записей в идеальном бакете), что вполне допустимо. Для реальной много-терабайтной таблицы ошибка была ещё меньше (2-3%).