Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Firebird, InterBase Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 40 41 42 43 44 [45] 46 47 48 49 50   вперед  Ctrl
 Re: Конкурс идей про Firebird  [new]
Симонов Денис
Member

Откуда: Рязань
Сообщений: 10142
rdb_dev
А я тебе о чем уже который комментарий толкую? :) Ты всё никак не можешь врубиться в суть моего вопроса. Просто перечитай его, сделав акцент на одном из ключевых слов - "занафига" (зачем, почему, с какой целью) и соотнеси его с обеими частями вопроса.


я тебе вроде всё расписал. Читай медленно, можешь по слогам если не доходит. Если ты будешь для индекса применять ту же стратегию, что и для NATRAL, то он будет на фиг не нужен. Тебе же писали потому что при соединении по индексу ты можешь одни и те же страницы читать многократно. Кстати для обычных случаем FIELD = 1 этого не будет (в Firebird).

rdb_dev
А хэш-таблица не будет удалена до конца выполнения транзакции или будет удалена сразу после выполнения запроса, в котором используется HASH JOIN, а затем заново построена с повторным вычислением хэшей, если по тем же самым данным будет встречен другой запрос с HASH JOIN?


Время жизни хеш-таблицы привязано к запросу. А может быть она помрёт и раньше, как только больше не нужна запросу.
Не тупи, запросы выполненные в разных снимках дадут разные данные, а следовательно и хеш-таблицы
1 окт 19, 11:22    [21983587]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Симонов Денис
Member

Откуда: Рязань
Сообщений: 10142
Дегтярев Евгений,

да он бредит. Про какое-то удаление пишет.

rdb_dev,

какое на фиг удаление? Хеш-таблица строится динамически по текущему снимку. Не будет там ссылок на удалённые записи.
Стоимость O(1) если нет коллизий. Для случая когда в таблице 2 записи и ключ целый, коллизий не будет точно.
1 окт 19, 11:29    [21983599]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Симонов Денис
Member

Откуда: Рязань
Сообщений: 10142
rdb_dev,

держи, сам тестируй

+ скрипт создания БД
recreate table sex (
  id int not null,
  name char(1) not null,
  constraint pk_sex primary key(id)
);

recreate table peoples(
  id bigint generated by default as identity,
  sex_id int not null,
  constraint pk_people primary key(id),
  constraint fk_people_sex foreign key(sex_id) references sex(id)
);

insert into sex(id, name)
values(1, 'м');

insert into sex(id, name)
values(2, 'ж');

commit;

set term !;

execute block
as
  declare variable n int = 50000000;
begin
  while (n > 0) do
  begin
    insert into peoples(sex_id)
    values (iif(mod(:n, 2) = 0, 1, 2));

    n = n - 1;
  end
end!

set term ;!

commit;

SET STATISTICS INDEX FK_PEOPLE_SEX;

SET STATISTICS INDEX PK_PEOPLE;

SET STATISTICS INDEX PK_SEX;


+ мои результаты

select count(*)
from peoples
join sex on sex.id = peoples.sex_id


Select Expression
-> Aggregate
-> Nested Loop Join (inner)
-> Table "SEX" Full Scan
-> Filter
-> Table "PEOPLES" Access By ID
-> Bitmap
-> Index "FK_PEOPLE_SEX" Range Scan (full match)

План
PLAN JOIN (SEX NATURAL, PEOPLES INDEX (FK_PEOPLE_SEX))

------ Информация о производительности ------
Время подготовки запроса = 16ms
Время выполнения запроса = 5m 3s 516ms
Среднее время на получение одной записи = 303 516,00 ms
Current memory = 170 220 496
Max memory = 170 425 920
Memory buffers = 16 384
Reads from disk to cache = 710 145
Writes from cache to disk = 1
Чтений из кэша = 50 709 755


select count(*)
from peoples
join sex on sex.id+0 = peoples.sex_id+0


Select Expression
-> Aggregate
-> Filter
-> Hash Join (inner)
-> Table "PEOPLES" Full Scan
-> Record Buffer (record length: 25)
-> Table "SEX" Full Scan

План
PLAN HASH (PEOPLES NATURAL, SEX NATURAL)

------ Информация о производительности ------
Время подготовки запроса = 0ms
Время выполнения запроса = 4m 22s 971ms
Среднее время на получение одной записи = 262 971,00 ms
Current memory = 151 429 936
Max memory = 170 425 920
Memory buffers = 16 384
Reads from disk to cache = 331 327
Writes from cache to disk = 1
Чтений из кэша = 51 324 719
1 окт 19, 11:42    [21983630]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3061
Дегтярев Евгений, если мы говорим о связывании по HASH JOIN производных таблиц в запросе, то в случае лишь упорядоченного списка пар ключ-строка, говорить о монотонности ключа в "ассоциативном массиве" - хэш-таблице не приходится, следовательно, "O(1)" это из области фантастики, потому что СУБД не в состоянии с высокой долей вероятности предсказать точное местоположение ключа в таком упорядоченном списке. Если же хэш-таблица использует для пар ключ-строка не упорядоченный список по ключу, а именно древо индексов по ключу, то в этом случае, монотонность ключа не будет иметь значение.

Возникает ещё один вопрос - зачем для подобного связывания использовать именно динамически созданную в памяти хэш-таблицу с результатами хэш-функции по значениям связываемого поля, а не реальные значения полей, если они, к примеру, целочисленные? Почему нельзя просто создать динамически в памяти для таких производных таблиц ассоциативный массив с парами ключ-строка, где в качестве ключей использовались бы реальные значение полей, а не результаты хэш-функций по ним?
1 окт 19, 11:47    [21983642]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3061
Симонов Денис
rdb_dev, какое на фиг удаление? Хеш-таблица строится динамически по текущему снимку. Не будет там ссылок на удалённые записи.
Стоимость O(1) если нет коллизий. Для случая когда в таблице 2 записи и ключ целый, коллизий не будет точно.
Перечитай ещё раз про монотонность индекса.
1 окт 19, 11:49    [21983647]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Дегтярев Евгений
Member

Откуда: Барнаул
Сообщений: 1711
rdb_dev что за каша...
- хештаблицы не упорядочены по ключу
- если говорить о целочисленных ключах, то монотонность данных никак не влияет на стоимость поиска, которая в среднем для хештаблицы таки O(1), для красночерного дерева O(log n)

зы
что за панический страх вычисления хешфункции? это какая-то детская травма?
1 окт 19, 12:05    [21983679]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Симонов Денис
Member

Откуда: Рязань
Сообщений: 10142
rdb_dev,

достал ты про свою монотонность вещать если честно.

Читай как устроена хеш-таблица и не морщ нам мозг. Хеш-таблице абсолютно по фигу монотонность значений ключа.

Смотри. Ты создаёшь хеш-таблицу размером N. Все слоты в ней созданы заранее, их адресация известна. Теперь тебе приходит M значений. Берётся хеш-функция, которая должна распределить M значений в N слотов. Коллизии помещаются в один слот и сортируются для быстрого поиска (это одна из реализаций). Приходит значение X. Мы берём hash(X) и она даёт адрес слота, туда мы пихаем данные. Всё. Поиск так же идёт по hash(Y). На монотонность X и Y нам плевать.

Если N>>M, то вероятность коллизий кране мала. Если N~M, то коллизии есть, но их количество не велико и мы всё ещё выигрываем. Если M>>N, то коллизий много и уже не факт, что хеш таблица полезна. В этом случае есть вариант пересоздать хеш-таблицу с большим N (насколько я знаю такой вариант в ФБ не используется, но возможно будет в будущем)
1 окт 19, 12:13    [21983700]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48652

Симонов Денис
Если M>>N, то коллизий много и уже не факт, что хеш таблица полезна.

Она остаётся полезна вплоть до момента когда M/N остаётся меньше, чем log2(M) и даже
некоторое время после него, поскольку проход по списку коллизий гораздо дешевле, чем
проход по дереву индекса, поскольку не сопровождается взятием лока на каждый шаг.

Posted via ActualForum NNTP Server 1.5

1 окт 19, 12:38    [21983732]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3061
Дегтярев Евгений
- хештаблицы не упорядочены по ключу
Если хэш-таблицы неупорядочены по ключу, то каким образом результат хэш-функции "адресует" слот, в соответствии с утверждением Симонова Дениса?:
Симонов Денис
Смотри. Ты создаёшь хеш-таблицу размером N. Все слоты в ней созданы заранее, их адресация известна. Теперь тебе приходит M значений. Берётся хеш-функция, которая должна распределить M значений в N слотов. Коллизии помещаются в один слот и сортируются для быстрого поиска (это одна из реализаций). Приходит значение X. Мы берём hash(X) и она даёт адрес слота, туда мы пихаем данные. Всё. Поиск так же идёт по hash(Y). На монотонность X и Y нам плевать.
1 окт 19, 13:04    [21983775]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3061
Симонов Денис, то есть, СУБД, всё таки, резервирует 2^64 слотов, чтобы иметь возможность адресовать каждый слот с помощью полученного результата хэш-функции без какой-либо дополнительной информации? Ведь заранее не известно - каким будет результат вычисления хэш-функции от конкретного значения поля, а результат этот может быть любым во всём диапазоне целых чисел от 0 до 2^64 - 1. Я правильно понял?
1 окт 19, 13:08    [21983784]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Симонов Денис
Member

Откуда: Рязань
Сообщений: 10142
Dimitry Sibiryakov,

индекс не бинарное дерево. Там стоимость равна высоте дерева (глубине индекса).
Ну и насчёт локов я не верен. Что-то не увидел по количеству фетчей, что индекс на каждый скан от корня лочится.

+ статистика

PEOPLES (133)
Primary pointer page: 206, Index root page: 207
Total formats: 1, used formats: 1
Average record length: 14.66, total records: 50000000
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: 20.00, compression ratio: 1.36
Pointer pages: 203, data page slots: 331128
Data pages: 331128, average fill: 59%
Primary pages: 331128, secondary pages: 0, swept pages: 0
Empty pages: 2, full pages: 331125
Fill distribution:
0 - 19% = 2
20 - 39% = 0
40 - 59% = 331126
60 - 79% = 0
80 - 99% = 0

Index FK_PEOPLE_SEX (1)
Root page: 12838, depth: 3, leaf buckets: 47480, nodes: 50000000
Average node length: 5.58, total dup: 49999998, max dup: 24999999
Average key length: 2.00, compression ratio: 0.75
Average prefix length: 1.50, average data length: 0.00
Clustering factor: 662252, ratio: 0.01
Fill distribution:
0 - 19% = 0
20 - 39% = 0
40 - 59% = 30239
60 - 79% = 0
80 - 99% = 17241

Index PK_PEOPLE (0)
Root page: 3580, depth: 3, leaf buckets: 73209, nodes: 50000000
Average node length: 11.72, total dup: 0, max dup: 0
Average key length: 8.14, compression ratio: 1.11
Average prefix length: 3.86, average data length: 5.14
Clustering factor: 331126, ratio: 0.01
Fill distribution:
0 - 19% = 1
20 - 39% = 0
40 - 59% = 1148
60 - 79% = 0
80 - 99% = 72060

1 окт 19, 13:14    [21983793]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Симонов Денис
Member

Откуда: Рязань
Сообщений: 10142
rdb_dev,

я не говорил сколько слотов резервируется, но точно не 2^64, намного меньше.
Так никакой памяти не напасёшься.
1 окт 19, 13:16    [21983794]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Дегтярев Евгений
Member

Откуда: Барнаул
Сообщений: 1711
rdb_dev
Если хэш-таблицы неупорядочены по ключу, то каким образом результат хэш-функции "адресует" слот

результат хеш функции ничего не адресует, адрес слота ты получишь разделив это значение на размер хештаблицы

зы
сходи уже в интернеты, прочитай как оно устроено, а лучше, чтоб понятно стало, сделай свою реализацию.
1 окт 19, 13:19    [21983798]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9498
rdb_dev
Массив данных всегда остаётся массивом
Вот только не надо переобуваться прямо в прыжке - строка, в общем случае, не является массивом символов.
Простейший пример: UTF8-строка это массив байт, но индексация доступа по байтам слабо помогает индексировать символы.
Даже если используются "широкие" символы - всегда надо помнить, что юникод явно и недвусмысленно определяет составные символы и попытка индексировать коды (кодовые точки) всё равно слабо решает проблему индексации символов.
1 окт 19, 13:36    [21983818]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9498
rdb_dev
Перечитай ещё раз про монотонность индекса.
Проблема в том, что монотонность предполагает упорядоченность (сильное условие). Для хэшей упорядоченность отсутствует - только сравнимость (слабое условие).
В типичном случае для соединения требуется только сравнимость. Поэтому достаточно хэшей и это позволяет реализовать "всякое разное".
1 окт 19, 13:42    [21983823]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3061
Дегтярев Евгений
rdb_dev
Если хэш-таблицы неупорядочены по ключу, то каким образом результат хэш-функции "адресует" слот

результат хеш функции ничего не адресует, адрес слота ты получишь разделив это значение на размер хештаблицы

зы
сходи уже в интернеты, прочитай как оно устроено, а лучше, чтоб понятно стало, сделай свою реализацию.
Дегтярев Евгений, Ok...
Допустим, имеем хэш-таблицу из трёх слотов и три результата хэш-функции, далее, делим каждый хэш на 3:
0x1EDCBA9876543210 / 3 = 0x0A49938827716605
0x7EDDBA00765AA219 / 3 = 0x2A49E8AAD21E3608
0x7FFFFFFFFFFFFFFA / 3 = 0x2AAAAAAAAAAAAAA8
и каким же образом ты предлагаешь адресовать слоты?

Может тогда надо сделать не так, а представить весь диапазон возможных значений хэш-функций в трёх слотах - (немного урежу диапазон для упрощения вычислений) 0x7FFFFFFFFFFFFFFF / 3 = 0x2AAAAAAAAAAAAAAA и использовать именно это значение для целочисленного деления результата хэш-функции, чтобы получить номер слота?
0x1EDCBA9876543210 / 0x2AAAAAAAAAAAAAAA = 0
0x7EDDBA00765AA219 / 0x2AAAAAAAAAAAAAAA = 2
0x7FFFFFFFFFFFFFFA / 0x2AAAAAAAAAAAAAAA = 2
Похоже?
1 окт 19, 14:00    [21983853]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48652

rdb_dev
далее, делим каждый хэш на 3

Ты бы всё же почитал теорию... Делить надо по модулю, чудак.

Posted via ActualForum NNTP Server 1.5

1 окт 19, 14:02    [21983857]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3061
Basil A. Sidorov
rdb_dev
Массив данных всегда остаётся массивом
Вот только не надо переобуваться прямо в прыжке - строка, в общем случае, не является массивом символов.
Простейший пример: UTF8-строка это массив байт, но индексация доступа по байтам слабо помогает индексировать символы.
Даже если используются "широкие" символы - всегда надо помнить, что юникод явно и недвусмысленно определяет составные символы и попытка индексировать коды (кодовые точки) всё равно слабо решает проблему индексации символов.
Это уже вопрос реализации, а не способа хранения. В оперативной памяти, с точки зрения языка Си, тоже хранятся, как бы, не только UINT8.
1 окт 19, 14:02    [21983858]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3061
Dimitry Sibiryakov
Ты бы всё же почитал теорию... Делить надо по модулю, чудак.
Чудак, это не я предложил. Глаза разуй!
1 окт 19, 14:03    [21983859]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3061
Basil A. Sidorov
Проблема в том, что монотонность предполагает упорядоченность (сильное условие). Для хэшей упорядоченность отсутствует - только сравнимость (слабое условие).
В типичном случае для соединения требуется только сравнимость. Поэтому достаточно хэшей и это позволяет реализовать "всякое разное".
Не совсем корректное объяснение, но наводящее на мысль о том, что именно отсутствие упорядоченности для результатов хэш-функции от обычного целочисленного и пусть даже монотонно возрастающего индекса позволяет равномерно распределить результаты хэш-функций по слотам.

Вот, теперь всё встало на свои места...
1 окт 19, 14:16    [21983874]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3061
*более-менее равномерно
1 окт 19, 14:18    [21983878]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48652

rdb_dev
это не я предложил.

Все, кто в теме, делят исключительно по модулю. Кто ж знал, что тебе, магистру гугля, надо
разжовывать и такую самоочевидность...

Posted via ActualForum NNTP Server 1.5

1 окт 19, 14:18    [21983881]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Симонов Денис
Member

Откуда: Рязань
Сообщений: 10142
rdb_dev
Вот, теперь всё встало на свои места...


ну наконец-то. Я уж думал это никогда не кончится
1 окт 19, 14:25    [21983890]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3061
Dimitry Sibiryakov, зачем вообще делить по модулю результат хэш-функции, когда достаточно просто экранировать старшие биты оставив только необходимые для адресации слотов, несколько модифицировав значение? При условии, что хэш-таблица имеет 10 слотов, можно сделать что-то типа ((hash(x) & 0x0F) - 10) & 0x0F, что наверняка быстрее чем деление по модулю.
1 окт 19, 14:39    [21983915]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3061
Симонов Денис
rdb_dev
Вот, теперь всё встало на свои места...

ну наконец-то. Я уж думал это никогда не кончится
Удивляет другое - ни от кого из вас я не услышал внятного объяснения - зачем возиться с хэшами. Оказалось, что дело не столько в скорости выполнения HASH JOIN по сравнению с обычным JOIN на обычных индексах, сколько в возможности более-менее равномерно распределить значения ключей по количеству слотов в ограниченном пространстве ключей. Видимо, вы тоже были не в курсе.
1 окт 19, 14:43    [21983921]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 40 41 42 43 44 [45] 46 47 48 49 50   вперед  Ctrl
Все форумы / Firebird, InterBase Ответить