hi all
(навеяло что-то объяснениями Влада в core-4302; но там ситуация с индексной навигацией, а тут - другой метод доступа).
DDL:
Таблица (id int, s varchar), в которую затолкано 10 млн записей с 10 различающимися значениями в поле 's':
'q'; 'qw'; 'qwe'; ...; 'qwertyui o '; 'qwertyuio p '
Обратите внимание на последние два значения: их длина 9 и 10 символов и очевидно, что для "тестовой строки" 'qwertyuio
o '
1) при ascend-порядке сравнения строк будет:
'qwertyuio'<'qwertyuio o ' and 'qwertyuio o '<'qwertyuiop'
2) при descend-порядке сравнения - всё наоборот:
'qwertyuiop' < 'qwertyuio o ' and 'qwertyuio o ' < 'qwertyuio'
На поле 's' построены два индекса - возрастающий и убывающий:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
set echo off;
commit;
recreate table td(id int, s varchar(50)); commit;
set term ^;
execute block as
begin
begin
execute statement 'create sequence g';
when any do begin end
end
end^
set term ;^
commit;
alter sequence g restart with 0;
commit;
set term ^;
execute block as
declare n int = 1000000;
declare m int;
begin
m=n; while(m>0) do insert into td(id, s) values( gen_id(g,1), 'q' ) returning :m-1 into m;
m=n; while(m>0) do insert into td(id, s) values( gen_id(g,1), 'qw' ) returning :m-1 into m;
m=n; while(m>0) do insert into td(id, s) values( gen_id(g,1), 'qwe' ) returning :m-1 into m;
m=n; while(m>0) do insert into td(id, s) values( gen_id(g,1), 'qwer' ) returning :m-1 into m;
m=n; while(m>0) do insert into td(id, s) values( gen_id(g,1), 'qwert' ) returning :m-1 into m;
m=n; while(m>0) do insert into td(id, s) values( gen_id(g,1), 'qwerty' ) returning :m-1 into m;
m=n; while(m>0) do insert into td(id, s) values( gen_id(g,1), 'qwertyu' ) returning :m-1 into m;
m=n; while(m>0) do insert into td(id, s) values( gen_id(g,1), 'qwertyui' ) returning :m-1 into m;
m=n; while(m>0) do insert into td(id, s) values( gen_id(g,1), 'qwertyuio' ) returning :m-1 into m;
m=n; while(m>0) do insert into td(id, s) values( gen_id(g,1), 'qwertyuiop' ) returning :m-1 into m;
end^ set term ;^ commit;
create index td_s_asc on td(s); commit;
create descending index td_s_des on td(s); commit;
Вот наглядное представление того, что уложено в каждом из листовых уровней этих индексов (каждый лям ключей выделен цветом):
1.
1) ascend: 'q q q ... q q qw qw qw ... qw qw . . . qwertyuio qwertyuio qwertyuio ...q wertyuio qwertyuio qwertyuiop qwertyuiop qwertyuiop ... qwertyuiop qwertyuiop '
2) descend: 'qwertyuiop qwertyuiop qwertyuiop ... qwertyuiop qwertyuiop qwertyuio qwertyuio qwertyuio ...q wertyuio qwertyuio . . . qw qw qw ... qw qw q q q ... q q '
Если заставить ФБ искать в
descend -индексе несуществующий ключ со значением 'qwertyuio
o ' (
10 символов), то бинарным поиском мы должны выйти на
9 -символьный ключ "qwertyuio".
Но это означает, что мы вышли на ключ, который СТРОГО БОЛЬШЕ (при просмотре в descend-порядке!), чем искомый.
А раз так, то поиск должен быть немедленно прекращён - ведь дальше будут только ключи со значениями, еще более "далёкими" от искомого.
Во всяком случае, если аналогично искать в
ascend- индексе несуществующий ключ 'q
y ' (строго больший, чем наименьшее значение в этом индексе), то происходит именно так: вышли бинарным поиском на 'qw' - и тут же прекратили поиск.
А теперь проверяем.
1. Временно вырубаем
ascend -индекс и делаем
запросик-1 :
1.
2.
3.
4.
alter index td_s_asc inactive; commit;
set stat on;
set plan on;
set echo on;
select count(*) from rdb$database where exists(select * from td where s='qwertyuio o ');
И видим, что:
1) ФБ строит битмап...
1.
2.
PLAN (TD INDEX (TD_S_DES) )
PLAN (RDB$DATABASE NATURAL)
2) ...но статистика при этом заставляет рыдать навзрыд:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
COUNT
=====================
0
Current memory = 2456004848
Delta memory = 5203224
Max memory = 2456004848
Elapsed time= 6.57 sec
Cpu = 0.00 sec
Buffers = 524288
Reads = 140644
Writes = 2
Fetches = 18012008
Далее оживляем ascend-индекс вводим
запросик-2 , в котором where-предикат в exists() будет с таким же "неудобным" ключём, какой был у descend-индекса:
1.
2.
3.
4.
5.
set stat off;
alter index td_s_asc active; commit;
set stat on;
select count(*) from rdb$database where exists(select * from td where s='q y ');
И видим, что:
1) ФБ снова составил битмап:
1.
2.
PLAN (TD INDEX (TD_S_ASC) )
PLAN (RDB$DATABASE NATURAL)
2) но статистика - "взлёт ракеты":
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
COUNT
=====================
0
Current memory = 2452143184
Delta memory = 39080
Max memory = 2516041048
Elapsed time= 0.01 sec
Cpu = 0.00 sec
Buffers = 524288
Reads = 0
Writes = 0
Fetches = 38
Соб-сно, вопрос простой как 3 коп: на что ушли 6.5 сек и 18 млн фетчей в первом варианте, когда мы рыскали в descend-индексе ?
ЗЫ. Проверял на 2.5 и 3.0 - ситуация одинаковая.
LI-T3.0.0.30792
LI-V2.5.3.26728
