ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Firebird, InterBase [игнор отключен] [закрыт для гостей] / FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
25 сообщений из 32, страница 1 из 2
  1  все
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512507
Таблоид
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Таблоид
Участник
hi all

DDL (на новой базе): две таблицы, по одному int-полю в каждой, плюс индексы по этому полю:
 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
set explain off;
set stat off;
set autoddl on;
commit;
recreate table tm(x int); create index tm_x on tm(x);
insert into tm select row_number()over() from rdb$types,(select row_number()over() r from rdb$types rows 5);
commit;

set statistics index tm_x;
commit;

recreate table td(x int); create index td_x on td(x);
insert into td select rand()*255 from rdb$types,rdb$types,(select row_number()over() r from rdb$types rows 20);
commit;

set statistics index td_x;
commit;

select count(*) from tm;
select count(*) from td;

set explain on;
set stat on;
В результате число строк: в таблице `tm` = 1'255, в таблице `td` = 1'260'020.

Статистика по индексам:
Код: sql
1.
2.
3.
select cast(ri.rdb$index_name as varchar(30)) idx_name, ri.rdb$segment_count seg_cnt, ri.rdb$statistics idx_stat
from rdb$indices ri
where ri.rdb$relation_name in('TM', 'TD');


Код: plaintext
1.
2.
3.
4.
IDX_NAME                       SEG_CNT                IDX_STAT
============================== ======= =======================
TM_X                                 1   0.0007968127611093223
TD_X                                 1    0.003906250000000000
Это значит, что средняя кардинальность на одно уник. значение ключей:
* в таблице `tm` = 1 запись - это следует из скрипта, см. выше
* в таблице `td` = 1260020*0.00390625 = 4922 записей

Далее делаю:

var. 1 .
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
SQL> select count(*) from tm m join td d  on m.x=d.x ;

Select Expression
    -> Aggregate
        ->  Nested Loop Join (inner)
            -> Table "D" Full Scan
            -> Filter
                -> Table "M" Access By ID
                    -> Bitmap
                        -> Index "TM_X" Scan

                COUNT
=====================
              1257601

Current memory = 2472978264
Delta memory = 10992
Max memory = 2481027240
 Elapsed time= 4.37 sec 
Cpu = 0.00 sec
Buffers = 524288
Reads = 0
Writes = 0
 Fetches = 8846440
(или план по-старому: PLAN JOIN (D NATURAL, M INDEX (TM_X)))

Сразу вопрос-0 : почему ведущей таблицей была взята 'TD' ?

var-2.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
SQL> select count(*) from tm m join td d on  m.x+0=d.x+0 ;

Select Expression
    -> Aggregate
        -> Filter
            -> Hash Join (inner)
                -> Table "D" Full Scan
                -> Record Buffer
                    -> Table "M" Full Scan

                COUNT
=====================
              1257601

Current memory = 2473040088
Delta memory = 5624
Max memory = 2481027240
 Elapsed time= 2.26 sec 
Cpu = 0.00 sec
Buffers = 524288
Reads = 0
Writes = 0
 Fetches = 2553717

Теперь вопрос-1 . Что удерживало оптизизатор от применения HJ в первом случае, когда условие соединения было без "плюс-нулей" ?

И еще.
var-3 . Заставляем его в варианте с NL взять ведущей таблицу `tm`:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
SQL> select count(*) from tm m join td d on  m.x+0=d.x ;

Select Expression
    -> Aggregate
        ->  Nested Loop Join (inner)
            -> Table "M" Full Scan
            -> Filter
                -> Table "D" Access By ID
                    -> Bitmap
                        -> Index "TD_X" Scan

                COUNT
=====================
              1257601

Current memory = 2473036656
Delta memory = -3432
Max memory = 2481027240
 Elapsed time= 1.44 sec 
Cpu = 0.00 sec
Buffers = 524288
Reads = 0
Writes = 0
 Fetches = 2525320

Как видим, время выполнения на треть лучше, чем с hash join. Однако, по числу фетчей они почти равны, отличие на 1%.

Поэтому вопрос-2 . Что там в hash join'e "заклинило", почему он проигрывает ? Построение hash-таблицы - его как-то можно будет отразить в статистике (особливо в трейсе, конечно :)) ?

PS. LI-T3.0.0.30792, PAGE_SIZE 4096
...
Рейтинг: 0 / 0
25.12.2013, 20:17:26
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512515
Таблоид
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Таблоид
Участник
Для сравнения - варианты 1 и 3 из предыдущего поста на LI-V2.5.3.26728

DDL:
 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
set plan off;
set stat off;
set autoddl on;
create sequence g;
commit;
recreate table tm(x int); create index tm_x on tm(x);
insert into tm select gen_id(g,1) from rdb$types,(select 1 r from rdb$types rows 10) rows 1255;
commit;

set statistics index tm_x;
commit;

recreate table td(x int); create index td_x on td(x);
alter sequence g restart with 0;
commit;
insert into td select rand()*255 from rdb$types,rdb$types,(select 1 r from rdb$types rows 30) rows 1260020;
commit;

set statistics index td_x;
commit;

select count(*) from tm;
select count(*) from td;
SQL> set stat on;
SQL> set plan on;


var-1.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
SQL> select count(*) from tm m join td d on m.x=d.x;

PLAN JOIN (D NATURAL, M INDEX (TM_X))  -- ведущей снова взята здоровенная таблица! 

       COUNT
============
     1257529

Current memory = 2222016680
Delta memory = 10144
Max memory = 2222632368
 Elapsed time= 3.95 sec 
Cpu = 0.00 sec
Buffers = 512000
Reads = 0
Writes = 0
 Fetches = 8846300

var-3.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
SQL> select count(*) from tm m join td d on m.x+0=d.x;

PLAN JOIN (M NATURAL, D INDEX (TD_X))

       COUNT
============
     1257529

Current memory = 2222017600
Delta memory = 920
Max memory = 2222632368
 Elapsed time= 1.38 sec 
Cpu = 0.00 sec
Buffers = 512000
Reads = 0
Writes = 0
 Fetches = 2525209
...
Рейтинг: 0 / 0
25.12.2013, 20:30:57
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512522
dimitr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dimitr
Участник
ТаблоидСразу вопрос-0: почему ведущей таблицей была взята 'TD' ?
потому что с учетом существующей статистики это должно быть дешевле. Откуда оптимизатору знать, что в TM две трети записей напрочь отсутствуют в TD (насколько я понял из скрипта)?

ТаблоидТеперь вопрос-1. Что удерживало оптизизатор от применения HJ в первом случае, когда условие соединения было без "плюс-нулей" ?HJ/MJ используются только при отсутствии индексов для полей связи. Со времен 2.х тут ничего пока не менялось.

ТаблоидПоэтому вопрос-2. Что там в hash join'e "заклинило", почему он проигрывает ?
понятия не имею, тем более я уже говорил что до беты он остается неоптимизированным и предназначенным для ловли багов. Но вообще-то он и не обязан выигрывать у NL во всех случаях.

ТаблоидПостроение hash-таблицы - его как-то можно будет отразить в статистике (особливо в трейсе, конечно :)) ?
нет, тем более не оно тормозит
...
Рейтинг: 0 / 0
25.12.2013, 20:52:07
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512532
Таблоид
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Таблоид
Участник
dimitrТаблоидСразу вопрос-0: почему ведущей таблицей была взята 'TD' ?
потому что с учетом существующей статистики это должно быть дешевле. Откуда оптимизатору знать, что в TM две трети записей напрочь отсутствуют в TD (насколько я понял из скрипта)?я не могу понять, как эта дешевизна следует из статистики.
Если в исходном скрипте заменить
Код: plaintext
insert into tm select  row_number()over()  from rdb$types,(select 1 r from rdb$types rows 5);
на:
Код: plaintext
insert into tm select  rand()*255  from rdb$types,(select 1 r from rdb$types rows 5);
 
исправленный скрипт, полностью
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
set explain off;
set stat off;
set autoddl on;
commit;
recreate table tm(x int); create index tm_x on tm(x);
insert into tm select rand()*255 from rdb$types,(select 1 r from rdb$types rows 5);
commit;

set statistics index tm_x;
commit;

recreate table td(x int); create index td_x on td(x);
insert into td select rand()*255 from rdb$types,rdb$types,(select 1 r from rdb$types rows 20);
commit;

set statistics index td_x;
commit;

select count(*) from tm;
select count(*) from td;

set explain on;
set stat on;
- то статистика индексов будет:
Код: plaintext
1.
2.
3.
4.
IDX_NAME                       SEG_CNT                IDX_STAT
============================== ======= =======================
TM_X                                 1     0.003937007859349251 
TD_X                                 1    0.003906250000000000

И это означает, что на 1 уник. значение ключа в таблице `t m ` будет 4.94 записи.
И хотя это значение ХУЖЕ, чем в первом варианте (там на 1 ключ была 1 запись), ФБ теперь соединяет так, как и должен был - делает ведущей таблицу `t m `:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
SQL> select count(*) from tm m join td d on m.x=d.x;

Select Expression
    -> Aggregate
        ->  Nested Loop Join (inner)
            ->  Table "M" Full Scan 
            -> Filter
                -> Table "D" Access By ID
                    -> Bitmap
                        -> Index "TD_X" Scan

                COUNT
=====================
              6174534

Current memory = 2473039464
Delta memory = 114536
Max memory = 2481027240
 Elapsed time= 6.36 sec 
Cpu = 0.00 sec
Buffers = 524288
Reads = 0
Writes = 0
 Fetches = 12369273 
SQL>

Только HJ всё равно лучше и при этом раскладе данных:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
SQL> select count(*) from tm m join td d on m.x+0=d.x+0;

Select Expression
    -> Aggregate
        -> Filter
            -> Hash Join (inner)
                -> Table "D" Full Scan
                -> Record Buffer
                    -> Table "M" Full Scan

                COUNT
=====================
              6174534

Current memory = 2472958120
Delta memory = -81344
Max memory = 2481027240
 Elapsed time= 4.83 sec 
Cpu = 0.00 sec
Buffers = 524288
Reads = 0
Writes = 0
 Fetches = 2553717 
SQL>
(2.5 млн фетчей при HJ против 12.3 млн при NL!)

А это значит, что эвристику:dimitrHJ/MJ используются только при отсутствии индексов для полей связи. Со времен 2.х тут ничего пока не менялось. - хотелось бы видеть уже более изворотливой. Это реально сделать в альфе или лучше не мечтать ?

dimitrдо беты он остается неоптимизированным и предназначенным для ловли багов. Но вообще-то он и не обязан выигрывать у NL во всех случаях.
<. . .>
нет, тем более не оно тормозитВроде бы HJ должен выигрывать при соединении источников с сильно различающейся кардинальностью - а тут как раз такой случай.
И еще: ты говоришь, что "не оно тормозит" - а что тогда ?
...
Рейтинг: 0 / 0
25.12.2013, 21:16:42
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512542
dimitr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dimitr
Участник
Таблоидя не могу понять, как эта дешевизна следует из статистики
учитывай оба потока. В первом приближении: cost(NL) = cardinality(A) + cardinality(A) * cardinality(B) * selectivity(I) .

ТаблоидА это значит, что эвристику хотелось бы видеть уже более изворотливой. Это реально сделать в альфе или лучше не мечтать ?
и не мечтай

ТаблоидИ еще: ты говоришь, что "не оно тормозит" - а что тогда ?
пробирование хеш-таблицы может обходиться дороже, чем ее построение
...
Рейтинг: 0 / 0
25.12.2013, 21:24:51
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512550
Таблоид
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Таблоид
Участник
dimitrВ первом приближении: cost(NL) = cardinality(A) + cardinality(A) * cardinality(B) * selectivity(I) .Вот я снова читаю Писание и вижу там:
авторИспользуются следующие формулы для оценки стоимости определенного порядка соединения:
Код: plaintext
1.
  cost = cardinality(outer) + (cardinality(outer) * (indexScanCost + cardinality(inner) * selectivity(link)))
  cardinality = cardinality(outer) * (cardinality(inner) * selectivity(link))
Что здесь есть indexScanCost - ?
И правильно ли я понимаю, что selectivity(link) - это на самом деле selectivity(соответствующего_индекса_в_inner) - ?

dimitrТаблоидА это значит, что эвристику хотелось бы видеть уже более изворотливой. Это реально сделать в альфе или лучше не мечтать ?
и не мечтай

dimitrпробирование хеш-таблицы может обходиться дороже, чем ее построениекак увидеть затраты на это ? можно ли будет патчик какой-то поиметь (хотя бы в isql set stat on чтобы отражалось) - ?
...
Рейтинг: 0 / 0
25.12.2013, 21:32:58
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512552
Таблоид
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Таблоид
Участник
ЗЫ. Да, и еще хочу уточнить. Вот это вот:dimitrВ текущих версиях сервера стоимость определяется количеством логических чтений (страничных фетчей, page fetches) , необходимых для возврата всех записей методом доступа.- оно и в ТРЁШКЕ тоже так ?
...
Рейтинг: 0 / 0
25.12.2013, 21:35:03
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512555
dimitr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dimitr
Участник
ТаблоидЧто здесь есть indexScanCost - ?
а перевести не судьба? :-) Стоимость скана индекса = высота дерева + число листовых страниц для данной выборки.

ТаблоидИ правильно ли я понимаю, что selectivity(link) - это на самом деле selectivity(соответствующего_индекса_в_inner) - ?
разумеется

Таблоидкак увидеть затраты на это ? можно ли будет патчик какой-то поиметь (хотя бы в isql set stat on чтобы отражалось) - ?
никак, нельзя. Потом возможно в плане это будет выводиться.

Таблоидоно и в ТРЁШКЕ тоже так ?
принципы оптимизации не менялись
...
Рейтинг: 0 / 0
25.12.2013, 21:39:06
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512600
Таблоид
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Таблоид
Участник
Так. Я тут подсчитал кое-чё. По раскладу данных первого поста, для селективности индексов:
Код: plaintext
1.
2.
3.
IDX_NAME                       SEG_CNT                IDX_STAT
============================== ======= =======================
TM_X                                 1   0.0007968127611093223
TD_X                                 1    0.003906250000000000

Насколько я смог врубиться, формулы для расчета стоимости при NL следующие.

1. Когда ведущая таблица = 'T D ':
Код: plaintext
1.
2.
cost = cardinality(td) + (cardinality(td) * (indexScanCost_t D _x + cardinality(tm) * selectivity( tm_x )))
cardinality = cardinality(td) * (cardinality(tm) * selectivity(t m _x))

2. Когда ведущая таблица = 'T M ':
Код: plaintext
1.
cost = cardinality(tm) + (cardinality(tm) * (indexScanCost_t M _x + cardinality(td) * selectivity(td_x)))
cardinality = cardinality(tm) * (cardinality(td) * selectivity(t d _x))

По данным gstat -r:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
cardinality(t m ) = 16
cardinality(t d ) = 15560

indexScanCost_t m _x = 1 (depth) + 1 (leaf buckets) = 2
indexScanCost_t d _x = 3 (depth) + 2562 (leaf buckets) = 2565

selectivity(t m _x) = 0.0007968127611093223
selectivity(t d _x) = 0.003906250000000000

gstat -r:
 
Код: plaintext
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.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
TD (129)
    Primary pointer page: 235, Index root page: 236
    Total formats: 1, used formats: 1
    Average record length: 9.00, total records: 1260020
    Average version length: 0.00, total versions: 0, max versions: 0
    Average fragment length: 0.00, total fragments: 0, max fragments: 0
    Average unpacked length: 8.00, compression ratio: 0.89
    Pointer pages: 20,  data page slots: 15560 
    Data pages: 15560, average fill: 52%
    Primary pages: 15560, secondary pages: 0, swept pages: 0
    Empty pages: 4, full pages: 15555
    Fill distribution:
         0 - 19% = 4
        20 - 39% = 0
        40 - 59% = 15556
        60 - 79% = 0
        80 - 99% = 0

    Index TD_X (0)
        Root page: 5081,  depth: 3, leaf buckets: 2562 , nodes: 1260020
        Average node length: 4.87, total dup: 1259764, max dup: 5130
        Average key length: 2.01, compression ratio: 1.34
        Average prefix length: 2.68, average data length: 0.01
        Clustering factor: 1081610, ratio: 0.86
        Fill distribution:
             0 - 19% = 0
            20 - 39% = 0
            40 - 59% = 2337
            60 - 79% = 103
            80 - 99% = 122

TM (128)
    Primary pointer page: 185, Index root page: 189
    Total formats: 1, used formats: 1
    Average record length: 9.00, total records: 1255
    Average version length: 0.00, total versions: 0, max versions: 0
    Average fragment length: 0.00, total fragments: 0, max fragments: 0
    Average unpacked length: 8.00, compression ratio: 0.89
    Pointer pages: 1,  data page slots: 16 
    Data pages: 16, average fill: 50%
    Primary pages: 16, secondary pages: 0, swept pages: 0
    Empty pages: 0, full pages: 15
    Fill distribution:
         0 - 19% = 0
        20 - 39% = 1
        40 - 59% = 15
        60 - 79% = 0
        80 - 99% = 0

    Index TM_X (0)
        Root page: 226,  depth: 1 ,  leaf buckets: 1 , nodes: 1255
        Average node length: 3.20, total dup: 1002, max dup: 11
        Average key length: 2.20, compression ratio: 1.21
        Average prefix length: 2.47, average data length: 0.20
        Clustering factor: 1071, ratio: 0.85
        Fill distribution:
             0 - 19% = 0
            20 - 39% = 0
            40 - 59% = 0
            60 - 79% = 0
            80 - 99% = 1


I. Если я не перепутал ` * ` в indexScanCost_t * _x, то подставляя числа, получаем:

1. Когда ведущая таблица = 'T D ':
Код: plaintext
1.
2.
cost = cardinality(td) + (cardinality(td) * (indexScanCost_t d _x + cardinality(tm) * selectivity( tm_x ))) 
     = 15560 + (15560 * (2565 + 16 * 0,0007968127611093223 )) =  39'927'158  fetches
2. Когда ведущая таблица = 'T M ':
Код: plaintext
1.
2.
cost = cardinality(tm) + (cardinality(tm) * (indexScanCost_tm_x + cardinality(td) * selectivity(td_x)))
     = 16 + 16 * (2 + 1260020 * 0,003906250000000000)) =  78'799  fetches.

II. Если же я перепутал с ` * ` в indexScanCost_t * _x и формулы для расчета фетчей должны быть такими:
1_upd.
Код: plaintext
cost = cardinality(td) + (cardinality(td) * (indexScanCost_t M _x + cardinality(tm) * selectivity( tm_x )))
2_upd.
Код: plaintext
cost = cardinality(tm) + (cardinality(tm) * (indexScanCost_t D _x + cardinality(td) * selectivity(td_x)))

- то получаем вот это:
1. Когда ведущая таблица = 'T D ':
Код: plaintext
cost = 15560 + (15560 * (2 + 16 * 0,0007968127611093223 )) =  46'878  fetches

2. Когда ведущая таблица = 'T M ':
Код: plaintext
cost = 16 + 16 * (2565 + 1260020 * 0,003906250000000000)) =  119'807  fetches

А теперь смотрим на результат, который был показан в isql: Fetches = 8'846'440
Не сходится. Ни с чем, вообще.

2 dimitr: если я перепутал в обоих случаях и формула для расчета стоимости совсем не такая, то как её правильно записать ?
...
Рейтинг: 0 / 0
25.12.2013, 22:50:15
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512602
Таблоид
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Таблоид
Участник
dimitrСтоимость скана индекса = высота дерева + число листовых страниц для данной выборки.А кстати: как он может быстро оценить число листовых страниц ? Да еще если доп. условие какое-нибудь наверчено на индексное поле! Это же только примитивный случай сейчас рассмотрен.
...
Рейтинг: 0 / 0
25.12.2013, 22:52:12
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512606
dimitr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dimitr
Участник
1) cardinality меряется в записях, а не в страницах
2) оценка никогда не будет равна реальному числу фетчей, ибо не учитываются фетчи для pointer pages
...
Рейтинг: 0 / 0
25.12.2013, 22:55:55
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512607
Таблоид
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Таблоид
Участник
И таки снова цитата из Писания:
dimitrГлавные критерии выбора: кардинальности обоих потоков и селективность условия связи. Используется следующие формул ы для оценки стоимости определенного порядка соединения:

Код: plaintext
1.
  cost = cardinality(outer) + (cardinality(outer) * (indexScanCost + cardinality(inner) * selectivity(link)))
   cardinality  = cardinality(outer) * (cardinality(inner) * selectivity(link))

Последняя часть формулы определяет стоимость выборки из внутреннего потока на каждой итерации. Умножив ее на количество итераций, получаем общую стоимость выборки из внутреннего потока. Общая стоимость получается путем добавления стоимости выборки из внешнего потока. Из всех возможных перестановок выбирается вариант с наименьшей стоимостью. В процессе перебора вариантов отбрасываются заведомо худшие (на основании уже имеющейся стоимостной информации).Не понимаю фразу "Последняя часть формулы" - это ЧТО ИМЕННО, выдели цветом, плз!
И еще. Вторая формула (в которой в левой части cardinality = ...) - она дальше как влияет на выбор ?
Вот получили мы cost, затем получили эту самую 'cardinality' - и что, в куда её ?
...
Рейтинг: 0 / 0
25.12.2013, 22:59:51
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512608
dimitr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dimitr
Участник
Таблоидкак он может быстро оценить число листовых страниц ? Да еще если доп. условие какое-нибудь наверчено на индексное поле!
все условия на индексное поле дают итоговую (умноженную) селективность. Общий размер индекса оценивается исходя из числа записей, длины индексного ключа и средней компрессии. Из этих двух цифр получается число листовых страниц нашего скана. Прикидка нифига не точная, но она влияет на итоговую оценку лишь во втором порядке.
...
Рейтинг: 0 / 0
25.12.2013, 22:59:58
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512610
Таблоид
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Таблоид
Участник
dimitrcardinality меряется в записях, а не в страницахТогда и про число записей вопрос - такой же, как про число листовых страниц в индексе:
1) как он может так быстро определить их ? gstat -r трудится ведь минутами над этим вопросом...
2) учитывает ли он при этом версии записей (ведь их дохрена может случиться!) ?
...
Рейтинг: 0 / 0
25.12.2013, 23:01:43
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512614
dimitr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dimitr
Участник
ТаблоидНе понимаю фразу "Последняя часть формулы" - это ЧТО ИМЕННО, выдели цветом, плз!
(indexScanCost + cardinality(inner) * selectivity(link))

ТаблоидИ еще. Вторая формула (в которой в левой части cardinality = ...) - она дальше как влияет на выбор ?
Вот получили мы cost, затем получили эту самую 'cardinality' - и что, в куда её ?
для джойна двух потоков - в никуда, для большего числа - вместо кардинальности внутреннего потока на предыдущем уровне рекурсии
...
Рейтинг: 0 / 0
25.12.2013, 23:03:59
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512616
dimitr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dimitr
Участник
Таблоид1) как он может так быстро определить их ? gstat -r трудится ведь минутами над этим вопросом...
2) учитывает ли он при этом версии записей (ведь их дохрена может случиться!) ?
1) ты понимаешь разницу между посчитать и прикинуть? Есть число страниц данных таблицы, есть длина распакованной записи, есть средняя степень сжатия.
2) нет конечно же, ибо не знает о них

ты тут какой-то детский сад развел, ей-богу...
...
Рейтинг: 0 / 0
25.12.2013, 23:06:17
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512621
Таблоид
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Таблоид
Участник
dimitrОбщий размер индекса оценивается исходя из числа записей, длины индексного ключа и средней компрессии. Из этих двух цифр получается число листовых страниц нашего скана.Хорошо, вот фрагмент из gstat -r для индекса TD_X:
Таблоид
Код: plaintext
1.
2.
        Root page: 5081,  depth: 3, leaf buckets: 2562 , nodes: 1260020
        Average node length: 4.87, total dup: 1259764, max dup: 5130
        Average key length: 2.01,  compression ratio: 1.34

У мну длина ключа = 4 байта. Число записей в таблице = 1'260'020, компрессия = 1.34 (ЕМНИП, это значит, что ключ жмётся в среднем до 4/1.34 "байта" - так ?).
Получаем (4 / 1.34) * 1260020 / page_size = (4 / 1.34) * 1260020 / 4096 = ~ 918 - это и есть число листовых страниц при сканировании индекса TD_X ?
...
Рейтинг: 0 / 0
25.12.2013, 23:09:51
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512629
Таблоид
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Таблоид
Участник
dimitrты тут какой-то детский сад развел, ей-богу...не, погодь!.. я в статью твою, как оказалось, не въехал.

dimitrпонимаешь разницу между посчитать и прикинуть? Есть число страниц данных таблицы, есть длина распакованной записи, есть средняя степень сжатия.да, понимаю я эту разницу.
Просто хочу теперь пройти тем же путём, что оптимизатор.

Откудова он так быстро берёт вот эти сведения:
1) для таблиц:
Код: plaintext
1.
    Average record length: 9.00, total records: 1260020
    Average unpacked length: 8.00, compression ratio: 0.89
2) для индексов:
Код: plaintext
1.
2.
        Root page: 5081, depth: 3, leaf buckets: 2562, nodes: 1260020
        Average node length: 4.87, total dup: 1259764, max dup: 5130
        Average key length: 2.01, compression ratio: 1.34
- ?
Он вообще на ЭТО опирается в своём расчете или нет ?
...
Рейтинг: 0 / 0
25.12.2013, 23:17:42
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512638
dimitr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dimitr
Участник
ТаблоидУ мну длина ключа = 4 байта
это ты фантазируешь

ТаблоидПросто хочу теперь пройти тем же путём, что оптимизатор
тогда читай код, я не буду здесь все до байта разжевывать

ТаблоидОткудова он так быстро берёт вот эти сведения
часть из них прикидывает, часть считает предопределенными (константы в коде)
...
Рейтинг: 0 / 0
25.12.2013, 23:26:23
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512640
dimitr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dimitr
Участник
известно изначально: длина несжатой записи, длина несжатого ключа индекса
определяется в рантайме: размер таблицы в страницах (для мелких таблиц - сразу в записях), средняя степень сжатия записей
берется из статистики: селективность индекса
берется из констант: глубина индекса, степень сжатия ключей индекса
все остальное вычисляется
...
Рейтинг: 0 / 0
25.12.2013, 23:31:14
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512643
Таблоид
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Таблоид
Участник
dimitrтогда читай код, я не буду здесь все до байта разжевыватья пока не готов к нанесению себе тяжелейшей мозговой травмы...

ты лучше скажи прямо, по-пролетарски, как ПРАВИЛЬНО:
так:
Код: plaintext
 cost = cardinality(outer) + (cardinality(outer) * (indexScanCost_ OUTER _idx + cardinality(inner) * selectivity(link)))

или вот так:
Код: plaintext
 cost = cardinality(outer) + (cardinality(outer) * (indexScanCost_ INNER _idx + cardinality(inner) * selectivity(link)))

Мне надоело башку ломать, просто втупую подставлять буду, да и всё.
...
Рейтинг: 0 / 0
25.12.2013, 23:38:21
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512646
dimitr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dimitr
Участник
Таблоид,

бесполезно, утром прочитаешь и сам поймешь
...
Рейтинг: 0 / 0
25.12.2013, 23:43:08
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512648
Таблоид
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Таблоид
Участник
dimitrопределяется в рантайме: размер таблицы в страницах (для мелких таблиц - сразу в записях), средняя степень сжатия записейэмпирически было установлено, что для здоровенных таблиц, типа широко известной в узких кругах "миллиардерши", ФБ достаточно долго делает первую вычитку.
Но при втором и последующем обращениях к ней он строит план мгновенно.
Если он запоминает "где-то в памяти" это число страниц, то как часто он обновляет эти сведения ?
...
Рейтинг: 0 / 0
25.12.2013, 23:43:45
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512649
Таблоид
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Таблоид
Участник
dimitrбесполезно, утром прочитаешь и сам поймешьвряд ли... ладно - нет, значит нет.
...
Рейтинг: 0 / 0
25.12.2013, 23:44:20
| Ответить | Цитировать | Написать  
FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
    #38512652
dimitr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dimitr
Участник
Таблоидэмпирически было установлено, что для здоровенных таблиц, типа широко известной в узких кругах "миллиардерши", ФБ достаточно долго делает первую вычитку.
Но при втором и последующем обращениях к ней он строит план мгновенно.
Если он запоминает "где-то в памяти" это число страниц, то как часто он обновляет эти сведения ?
ничего не запоминается и не обновляется, первая вычитка тормозит из-за дискового I/O, а потом помогает кеш
...
Рейтинг: 0 / 0
25.12.2013, 23:47:18
| Ответить | Цитировать | Написать  
25 сообщений из 32, страница 1 из 2
  1  все
Форумы / Firebird, InterBase [игнор отключен] [закрыт для гостей] / FB-3 hash join: какая эвристика заставляет его (не) применять при соединении таблиц ?
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=40&fpage=106&tid=1564028]:
 0ms
get settings:
 9ms
get forum list:
 14ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 276ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 58ms
get tp. blocked users:
 1ms
others: 233ms
total:  608ms
созд. / загр.: 608ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]