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

Откуда: Рязань
Сообщений: 10794
rdb_dev
Ты лучше объясни - в чём для алгоритма оптимизации поиска отличие использования в качестве ключа ассоциативного массива BIGINT результата хэш-функции по полю BIGINT или реального значения этого поля?


потому что хеш-таблица имеет ограниченный размер. Никто не будет резервировать 2^64 слотов
30 сен 19, 21:41    [21983287]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3604
Dimitry Sibiryakov
Повторяю медленно: равномерность распределения значений в диапазоне [0..размер
хэш-таблицы]. Это второе по значению требование к хэш-функциям, используемым для хэш-таблиц.
Ну, для поиска с применением предсказания на основании статистики распределения это, конечно, очень важно, если не использовать какой-нибудь алгоритм древа индексов, а использовать лишь упорядочивание. Получиться чуть меньше итераций для алгоритма "поймай льва в пустыне" (или как у вас там принято называть алгоритм? :)), когда "пустыня" делиться пополам на два сектора с проверкой на попадание "льва" в один из секторов, затем ещё раз пополам и т.д.
30 сен 19, 21:44    [21983293]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 52445
Хэш-таблицы не используют итераций.

Posted via ActualForum NNTP Server 1.5
30 сен 19, 21:46    [21983296]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3604
Симонов Денис
потому что хеш-таблица имеет ограниченный размер. Никто не будет резервировать 2^64 слотов
Зачем их резервировать? Достаточно использовать самосбалансированное красно-чёрное древо индексов последовательности бит от старшего к младшему.
30 сен 19, 21:46    [21983297]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3604
Dimitry Sibiryakov
Хэш-таблицы не используют итераций.
А алгоритмы поиска по этим таблицам используют итерации? :)
30 сен 19, 21:47    [21983299]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Симонов Денис
Member

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

стоимость поиска в хеш-таблице O(1), если нет коллизий. Так что по большому счёту нужен поиск среди коллизий. ЕМНИП ДЕ говорил что коллизии отсортированы и по ним идёт бинарный поиск.
30 сен 19, 21:53    [21983304]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 52445
Симонов Денис
ЕМНИП ДЕ говорил что коллизии отсортированы и по ним идёт бинарный поиск.

Может, для хэш-джоина это и так, но остальные - даже не отсортированы.

Posted via ActualForum NNTP Server 1.5
30 сен 19, 22:07    [21983314]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 10898
rdb_dev
Или я не могу переменную i использовать как позицию символа в строке?
От строки зависит, но, в общем случае - да, не можешь.
1 окт 19, 04:09    [21983407]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Дегтярев Евгений
Member

Откуда: Барнаул
Сообщений: 1985
Симонов Денис
стоимость поиска в хеш-таблице O(1)

зачем ты про стоимость, не стоит, для чувака что лукап в хештаблице, что поиск по дереву, что получение записи по ключу в БД это операции одного поряка.
1 окт 19, 08:11    [21983433]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Дегтярев Евгений
Member

Откуда: Барнаул
Сообщений: 1985
kdv
я пишу - "когда нет подходящих индексов", он пишет - "справочная таблица джойнится по первичному ключу"...
моя твоя не понимай? что в приведенных мной примерах непонятного?
Сколько надо дней или часов, чтобы взять две таблицы, с индексами по полям связи, и
тремя запросами по +0 перепробовать отрубание индекса с одной стороны, с другой стороны и с обоих сторон,
и посмотреть на планы запросов в 3.0?
Кажись, не больше пары минут...


Воу по легче
Во первых мой вопрос был не к тебе
Во вторых вопрос был не о том, как оно работает в текущей реализации фб, а о применимости хешджойна в конкретной ситуации, чиста теоритичеки, для подискутировать. Вот rdb_dev считает что занафига, идекс же есть.
1 окт 19, 08:22    [21983435]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Симонов Денис
Member

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

а я считаю что для маленьких таблиц можно и HASH JOIN вместо NESTED LOOP по индексу юзать. Будет ли это быстрее хз, эксперименты показывают когда как.
1 окт 19, 09:08    [21983445]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3604
Basil A. Sidorov
rdb_dev
Или я не могу переменную i использовать как позицию символа в строке?
От строки зависит, но, в общем случае - да, не можешь.
Неужели?21982926
1 окт 19, 09:50    [21983466]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 10898
rdb_dev
Неужели?
"Нельзя недооценивать предсказуемость тупизны" (ц) "Большой куш".
В общем случае строка представляет собой (двусвязный) список символов и переходы вперёд-назад есть, а переход по индексу - отсутствуют.
1 окт 19, 10:00    [21983474]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3604
Симонов Денис
теперь ставим нормальный кеш

PLAN JOIN (COLOR NATURAL, HORSE INDEX (FK_HORSE_COLOR))
Время выполнения запроса = 265ms
Среднее время на получение одной записи = 265,00 ms

PLAN HASH (HORSE NATURAL, COLOR NATURAL)
Время выполнения запроса = 359ms
Среднее время на получение одной записи = 359,00 ms

видишь?
Вижу! С обычным индексом быстрее. Интересно посмотреть результат каждого замера из примера выше цитируемого после рестарта СУБД.

БД, которую ты использовал для этих примеров, где-то в публичном доступе?
1 окт 19, 10:06    [21983479]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3604
Basil A. Sidorov
"Нельзя недооценивать предсказуемость тупизны" (ц) "Большой куш".
Exactly!

Basil A. Sidorov
В общем случае строка представляет собой (двусвязный) список символов и переходы вперёд-назад есть, а переход по индексу - отсутствуют.
Ты удивишься, в Си или в GNU asm у массива нет никаких "переходов". :) Чтобы использовать "переходы", тебе придётся перейти к использованию указателей. Массив данных всегда остаётся массивом и даже сама оперативная память, это массив, а с точки зрения железа, этот массив ещё и двумерный. Меняется только метод доступа к элементам массива. Следовательно, если я могу использовать штатные средства СУБД для получения символа из строки по его позиции, значит это массив, а позиция символа - индекс массива.
1 окт 19, 10:17    [21983498]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Симонов Денис
Member

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

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

rdb_dev
БД, которую ты использовал для этих примеров, где-то в публичном доступе?


нет конечно. Это копия для целей разработки и тестирования одной из моих промышленных БД.
1 окт 19, 10:25    [21983507]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Дегтярев Евгений
Member

Откуда: Барнаул
Сообщений: 1985
Симонов Денис
а я считаю что для маленьких таблиц можно и HASH JOIN вместо NESTED LOOP по индексу юзать.

я тоже считаю можно
Симонов Денис
Будет ли это быстрее хз, эксперименты показывают когда как.

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

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

когда и таблица и индексы целиком в кеше, то результаты практически равны
1 окт 19, 10:28    [21983517]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3604
Симонов Денис
rdb_dev, что ты видишь? Ты на результаты выше глянул, когда кеш намеренно уменьшен, чтобы быть меньше таблицы?
Денис, конечно глянул! Я и имел в виду результаты того примера, когда говорил, что хотел бы глянуть каждый результат после рестарта СУБД.

Симонов Денис
Вот тебе пытаются объяснить что разные случаи могут быть, разные! Предсказать заранее что эффективнее сложно. Вроде и разжевали уже всё в каких случаях точно эффективней и почему, но нет ты тут упираешься.
Всё понятно! Мы уже выяснили в каких случаях лучше использовать HASH JOIN, но мой вопрос к тебе про то - занафига вытеснять из кэша страницы подходящего для связывания обычного индекса, а потом заменять его хэш-таблицей которая не вытесняется, остался. Понятно, что СУБД это делает "несознательно" и мы на это никак повлиять не можем... Или можем?

Симонов Денис
rdb_dev
БД, которую ты использовал для этих примеров, где-то в публичном доступе?
нет конечно. Это копия для целей разработки и тестирования одной из моих промышленных БД.
Жаль... Я думал, что этот "ипподром" используется как база примера. Хотел её "помучить".
1 окт 19, 10:45    [21983542]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Дегтярев Евгений
Member

Откуда: Барнаул
Сообщений: 1985
 		Симонов Денис,

вот меня и удивило, что получение записи по ключу на фоне других операций не так затратно

зы
как это происходит? посните?
поиск по ключу на страницах индекса + получение записи со страницы данных? или как то иначе?
1 окт 19, 10:51    [21983549]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3604
Симонов Денис
Дегтярев Евгений, когда и таблица и индексы целиком в кеше, то результаты практически равны
Не скажи... В твоём примере, где:
PLAN JOIN (COLOR NATURAL, HORSE INDEX (FK_HORSE_COLOR))
и
PLAN HASH (HORSE NATURAL, COLOR NATURAL)
разница существенна, а не в пределах статистической погрешности - производительность соединение по обычному индексу на 26.18% выше.
1 окт 19, 10:52    [21983554]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Симонов Денис
Member

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


ну ты бы хоть иногда подумать попытался. Когда идёт чтение по индексу мы можем читать одни и те же страницы многократно, поэтому важно чтобы они оставались в кеше.

Смотри медленно идёт скан по индексу кеш работает по принципу LRU. Поскольку страница может быть прочитана повторно, то важно чтобы она сохранялась в кеше как можно дольше. Но если кеша недостаточно, то она будет вытеснена рано или поздно.

В случае NATURAL каждая DP страница при чтении таблицы будет прочитана лишь один раз! Кеш переключается на другую стратегию. Прочитанная страница вытесняется сразу после того как из неё кончилось извлечение записей.
1 окт 19, 10:55    [21983558]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3604
Симонов Денис
ну ты бы хоть иногда подумать попытался. Когда идёт чтение по индексу мы можем читать одни и те же страницы многократно, поэтому важно чтобы они оставались в кеше.

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

Симонов Денис
Но если кеша недостаточно, то она будет вытеснена рано или поздно.
А хэш-таблица не будет удалена до конца выполнения транзакции или будет удалена сразу после выполнения запроса, в котором используется HASH JOIN, а затем заново построена с повторным вычислением хэшей, если по тем же самым данным будет встречен другой запрос с HASH JOIN?
1 окт 19, 11:05    [21983568]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
rdb_dev
Member

Откуда: с болот
Сообщений: 3604
Дегтярев Евгений
Симонов Денис
стоимость поиска в хеш-таблице O(1)

зачем ты про стоимость, не стоит, для чувака что лукап в хештаблице, что поиск по дереву, что получение записи по ключу в БД это операции одного поряка.
Нет там никакой "стоимости"! Потому что "O(1)" работает только для идеально монотонного индекса, а "идеально монотонный индекс", это абсолютно точно не про хэши, а скорее наоборот - про обычные синтетические индексы, принимающие значения от генератора и в таблицах, из которых редко происходит удаление данных. Мозг включи!
1 окт 19, 11:14    [21983580]     Ответить | Цитировать Сообщить модератору
 Re: Конкурс идей про Firebird  [new]
Дегтярев Евгений
Member

Откуда: Барнаул
Сообщений: 1985
 		rdb_dev
> Потому что "O(1)"
уточни для какой структуры ты оцениваешь поиск? хештаблица, красночерное дерево, что то еще?
1 окт 19, 11:18    [21983583]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: ←Ctrl  назад   1 .. 39 40 41 42 43 [44] 45 46 47 48 .. 55   вперед  Ctrl→
Все форумы / Firebird, InterBase Ответить