Есть лента новостей. Все новости разделены на 10 категорий(Политика, спорт, авто, недвижимость и тд).Однако, задача стояла - сделать это оптимально, а стандартное решение с обычным TopN через row_number никак оптимальным не назвать, особенно в случае больших таблиц, относительно небольшого количества категорий и неравномерного распределения или просто общей низкой селективности. И вот после нескольких более-менее хороших вариантов, подглядев в решение с PostgreSQL(правда я в нем не стал сильно разбираться, достаточно было увидеть рекурсию, min и предикат), получился отличный вариант.
Надо 1 запросом для каждой категории выбрать 4 новости.
Получается если перебрать результат - сразу идет 4 новости о политике, затем 4 новости о спорте и тд.
Но обо всем по порядку:
1. Получение distinct значений из индекса
Пусть есть табличка с индексом на поле а:
create table xt_test(a not null,b not null,c)
as
select
length(object_name)
,nvl(object_id,0)
,o.OBJECT_NAME
from dba_objects o;
create index ix_test_a on xt_test(a);
DB11G/XTENDER> select i.index_name
2 ,i.distinct_keys,i.num_rows
3 ,i.blevel,i.leaf_blocks
4 ,i.avg_leaf_blocks_per_key,i.avg_data_blocks_per_key
5 from user_indexes i where i.table_name='XT_TEST';
INDEX_NAME DISTINCT_KEYS NUM_ROWS BLEVEL LEAF_BLOCKS AVG_LEAF_BLOCKS_PER_KEY AVG_DATA_BLOCKS_PER_KEY
----------- ------------- --------- -------- ----------- ----------------------- -----------------------
IX_TEST_A 30 69230 1 135 4 191
1 row selected.
drop table xt_test purge;
create table xt_test(a not null,b not null,c)
as
select
length(object_name)
,nvl(object_id,0)
,o.OBJECT_NAME
from dba_objects o
;
create index ix_test_a on xt_test(a);
begin
dbms_stats.gather_table_stats( ''
,'XT_TEST'
,estimate_percent=>100
,cascade=>true
,method_opt => 'for all indexed columns size auto'
);
end;
/
select i.index_name
,i.distinct_keys,i.num_rows
,i.blevel,i.leaf_blocks
,i.avg_leaf_blocks_per_key,i.avg_data_blocks_per_key
from user_indexes i where i.table_name='XT_TEST';
Распределение значений у этого поля очень неравномерное:
| A | COUNT(*) |
|---|---|
| 1 | 11 |
| 2 | 20 |
| 3 | 59 |
| 4 | 92 |
| 5 | 178 |
| 6 | 251 |
| 7 | 521 |
| 9 | 570 |
| 10 | 636 |
| 8 | 640 |
| 11 | 962 |
| 12 | 970 |
| 13 | 1151 |
| 15 | 1363 |
| 14 | 1544 |
| 16 | 1692 |
| 18 | 2021 |
| 17 | 2023 |
| 19 | 2550 |
| 20 | 2606 |
| 21 | 3050 |
| 22 | 3171 |
| 23 | 3395 |
| 24 | 3472 |
| 29 | 3527 |
| 27 | 3596 |
| 26 | 3698 |
| 28 | 4130 |
| 25 | 4268 |
| 30 | 17063 |
| Всего | 69230 |
С IFS:
DB11G/XTENDER> select/*+ INDEX(xt_test) */ distinct a from xt_test;
30 rows selected.
Elapsed: 00:00:00.02
Execution Plan
----------------------------------------------------------
Plan hash value: 3405466263
--------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
--------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 30 | 90 | 140 (3)| 00:00:02 |
| 1 | SORT UNIQUE NOSORT| | 30 | 90 | 140 (3)| 00:00:02 |
| 2 | INDEX FULL SCAN | IX_TEST_A | 69230 | 202K| 137 (1)| 00:00:02 |
--------------------------------------------------------------------------------
Statistics
----------------------------------------------------------
1 recursive calls
0 db block gets
138 consistent gets
0 physical reads
0 redo size
751 bytes sent via SQL*Net to client
431 bytes received via SQL*Net from client
3 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
30 rows processed
C IFFS:DB11G/XTENDER> select distinct a from xt_test;
30 rows selected.
Elapsed: 00:00:00.05
Execution Plan
----------------------------------------------------------
Plan hash value: 4206828362
-----------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-----------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 30 | 90 | 42 (10)| 00:00:01 |
| 1 | HASH UNIQUE | | 30 | 90 | 42 (10)| 00:00:01 |
| 2 | INDEX FAST FULL SCAN| IX_TEST_A | 69230 | 202K| 38 (0)| 00:00:01 |
-----------------------------------------------------------------------------------
Statistics
----------------------------------------------------------
1 recursive calls
0 db block gets
143 consistent gets
0 physical reads
0 redo size
751 bytes sent via SQL*Net to client
431 bytes received via SQL*Net from client
3 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
30 rows processed
А ведь можно же было бы идти по дереву заходя только в нужные блоки, а не по всем листовым блокам! Однако, Oracle сам по себе такое не осилит и тут как раз придется его выкрутиться: у Oracle помимо IFS(min/max) есть и IRS(min/max) хорошо работающий с диапазонами и границами, и с помощью рекурсивного запроса, можно заставить его читать только нужное!DB11G/XTENDER> with t_unique( a ) as (
2 select min(t1.a)
3 from xt_test t1
4 union all
5 select (select min(t1.a) from xt_test t1 where t1.a>t.a)
6 from t_unique t
7 where a is not null
8 )
9 select * from t_unique where a is not null;
30 rows selected.
Elapsed: 00:00:00.00
Execution Plan
----------------------------------------------------------
Plan hash value: 2791305641
-------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 2 | 26 | 4 (0)| 00:00:01 |
|* 1 | VIEW | | 2 | 26 | 4 (0)| 00:00:01 |
| 2 | UNION ALL (RECURSIVE WITH) BREADTH FIRST| | | | | |
| 3 | SORT AGGREGATE | | 1 | 3 | | |
| 4 | INDEX FULL SCAN (MIN/MAX) | IX_TEST_A | 1 | 3 | 2 (0)| 00:00:01 |
| 5 | SORT AGGREGATE | | 1 | 3 | | |
| 6 | FIRST ROW | | 1 | 3 | 2 (0)| 00:00:01 |
|* 7 | INDEX RANGE SCAN (MIN/MAX) | IX_TEST_A | 1 | 3 | 2 (0)| 00:00:01 |
|* 8 | RECURSIVE WITH PUMP | | | | | |
-------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - filter("A" IS NOT NULL)
7 - access("T1"."A">:B1)
8 - filter("A" IS NOT NULL)
Statistics
----------------------------------------------------------
1 recursive calls
0 db block gets
36 consistent gets
0 physical reads
0 redo size
751 bytes sent via SQL*Net to client
431 bytes received via SQL*Net from client
3 SQL*Net roundtrips to/from client
32 sorts (memory)
0 sorts (disk)
30 rows processed
Разница очевидна: 36 consistent gets на 30 значений, вместо 135. И это очень маленькая табличка, а на миллионах и миллиардах записей разница будет еще более огромной!Поясню алгоритм:
- В первой части union all (3-4 строки плана) мы указываем с чего начать рекурсию, а конкретно выбираем минимальное(первое) значение из индекса.
- Затем с помощью IRS(min/max) (7-6-5 строки плана) выбираем первое значение большее выбранного на предыдущем этапе
- Повторяем рекурсию пока что-то находим
Переходим к следующему:
2. Топ N записей для каждого значению ключа
Теперь вооруженные легким получением каждого начального значения, мы легко можем получить Топ для каждого из них, но для этого придется воспользоваться либо недокументированным Lateral() с включением соответствующего ивента, либо более простым и стандартным table(). Проблема остается только в том, что воспользоваться инлайн вью с row_number/rownum не получится, т.к. предикат с верхнего уровня не просунется, и придется воспользоваться простым ограничением по count stop key(по rownum) c обязательным доступом по IRS descending (order by там в общем лишний, но дополнительно уменьшает стоимость чтения IRS descending который нам и нужен для неявной сортировки) c подсказкой index_desc, чтобы прибить намертво, иначе сортировка может слететь:
DB11G/XTENDER> with t_unique( a ) as (
2 select min(t1.a)
3 from xt_test t1
4 union all
5 select (select min(t1.a) from xt_test t1 where t1.a>t.a)
6 from t_unique t
7 where a is not null
8 )
9 select/*+ use_nl(rids tt) */ *
10 from t_unique v
11 ,table(
12 cast(
13 multiset(
14 select/*+ index_desc(tt ix_xt_test_ab) */ tt.rowid rid
15 from xt_test tt
16 where tt.a=v.a
17 and rownum<=5
18 order by tt.b desc
19 )
20 as sys.odcivarchar2list
21 )
22 ) rids
23 ,xt_test tt
24 where tt.rowid=rids.column_value
25 order by tt.a,tt.b desc;
150 rows selected.
Elapsed: 00:00:00.01
Execution Plan
----------------------------------------------------------
Plan hash value: 4085270117
----------------------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes |TempSpc| Cost (%CPU)| Time |
----------------------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 11M| 506M| | 149K (1)| 00:29:54 |
| 1 | SORT ORDER BY | | 11M| 506M| 649M| 149K (1)| 00:29:54 |
| 2 | NESTED LOOPS | | 11M| 506M| | 16402 (1)| 00:03:17 |
| 3 | NESTED LOOPS | | 16336 | 239K| | 60 (0)| 00:00:01 |
| 4 | VIEW | | 2 | 26 | | 4 (0)| 00:00:01 |
| 5 | UNION ALL (RECURSIVE WITH) BREADTH FIRST| | | | | | |
| 6 | SORT AGGREGATE | | 1 | 3 | | | |
| 7 | INDEX FULL SCAN (MIN/MAX) | IX_TEST_A | 1 | 3 | | 2 (0)| 00:00:01 |
| 8 | SORT AGGREGATE | | 1 | 3 | | | |
| 9 | FIRST ROW | | 1 | 3 | | 2 (0)| 00:00:01 |
|* 10 | INDEX RANGE SCAN (MIN/MAX) | IX_TEST_A | 1 | 3 | | 2 (0)| 00:00:01 |
|* 11 | RECURSIVE WITH PUMP | | | | | | |
| 12 | COLLECTION ITERATOR SUBQUERY FETCH | | 8168 | 16336 | | 28 (0)| 00:00:01 |
|* 13 | COUNT STOPKEY | | | | | | |
|* 14 | INDEX RANGE SCAN DESCENDING | IX_XT_TEST_AB | 2308 | 64624 | | 8 (0)| 00:00:01 |
|* 15 | TABLE ACCESS BY USER ROWID | XT_TEST | 692 | 22144 | | 1 (0)| 00:00:01 |
----------------------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
10 - access("T1"."A">:B1)
11 - filter("A" IS NOT NULL)
13 - filter(ROWNUM<=5)
14 - access("TT"."A"=:B1)
15 - access(CHARTOROWID(VALUE(KOKBF$)))
Statistics
----------------------------------------------------------
1 recursive calls
0 db block gets
166 consistent gets
0 physical reads
0 redo size
7523 bytes sent via SQL*Net to client
519 bytes received via SQL*Net from client
11 SQL*Net roundtrips to/from client
33 sorts (memory)
0 sorts (disk)
150 rows processed
Аналогично можно через lateral:
alter session set events '22829 trace name context forever';
with t_unique( a ) as (
select min(t1.a)
from xt_test t1
union all
select (select min(t1.a) from xt_test t1 where t1.a>t.a)
from t_unique t
where a is not null
)
select/*+ use_nl(rids tt) */ *
from t_unique v
,lateral(
select/*+ index_desc(tt ix_xt_test_ab) */ tt.*
from xt_test tt
where tt.a=v.a
and rownum<=5
order by tt.a, b desc
) r
order by r.a,r.b desc
В целом, конечно, можно было обойтись и без опасной сортировки, а взять и воспользоваться xmltable вместо table с передачей параметра сразу во внутренний подзапрос, но это чуток потяжелее чем обычный table.
Сообщения
Just another Oracle developers
Comments
Интересный метод, спасибо, Саян
Имхо, имеет один недостаток, который может быть существенным, - пока не умеет считать стоимость для рекурсивных WITH.
Длинный коммент (>4096) не удалось оставить, поэтому отписал отдельно http://iusoltsev.wordpress.com/2012/09/26/recursive-subquery-factoring-cost/
Отправить комментарий