Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Informix Новый топик    Ответить
 Алгоритм работы hash join  [new]
Журавлев Денис
Member

Откуда: St.John,NB,CA
Сообщений: 5532
Читая доку можно увидеть такой абзац:

Performance Guide
In the build phase, the database server reads one table and, after it applies any filters, creates a hash table. Think of a hash table conceptually as a series of buckets, each with an address that is derived from the key value by applying a hash function. The database server does not sort keys in a particular hash bucket.


И у меня праздный интерес как его перевести два последних предложения.

Думайте о хэш-таблице как о наборе корзин, имеющих адрес полученный с помощью хэш-функции примененной к ключу. Сервер не сортирует ключи в отдельных корзинах.???

Мысли вслух:
Адрес корзины - это результат хеш-функции к ключу. Непонятно в корзине лежат адреса (rowid) нескольких строк или одной? Похоже нескольких.
Набор корзин - это массив с индексным доступом (address)? Или список сортированный по возрастанию адреса (значения хэш)?
А зачем третье предложение? Чтобы написать про отличие от merge/sort-join? Их вроде совсем нет.
И что все-таки он не сортирует? Содержимое корзин? Или сами корзины?

-----------------------------------------------------------
Решительный шаг вперед -- результат хорошего пинка сзади
23 сен 05, 10:16    [1904093]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм работы hash join  [new]
Enlighten me
Member

Откуда:
Сообщений: 172
Журавлев Денис
Содержимое корзин? Или сами корзины?
С этим вопросом легче всего - внимательно читаем приведенную вами цитату и видим ответ. С остальными - IMHO, освежаем воспоминания о хэшировании и всё встанет на свои места. Мне не лень цитировать книжки, просто там всё равно написано лучше, чем я расскажу.
23 сен 05, 12:23    [1904810]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм работы hash join  [new]
Valentyn Pidburtnyi
Member

Откуда: Kyiv, Ukraine
Сообщений: 69
Журавлев Денис
Think of a hash table conceptually as a series of buckets, each with an address that is derived from the key value by applying a hash function. The database server does not sort keys in a particular hash bucket.

"Хэш-таблицу понимайте как ряд секций, при этом адресом каждой секции является значение хэш-функции, примененной к ключу. Сервер БД не сортирует значения ключей внутри отдельной хэш-секции"
Имхо, так.

Журавлев Денис
Набор корзин - это массив с индексным доступом (address)? Или список сортированный по возрастанию адреса (значения хэш)?
И что все-таки он не сортирует? Содержимое корзин? Или сами корзины?

Как я понял хэш-таблицу:

1-е поле - значение хэш-функции(Address)
2-е поле - массив ключей, т.е. тех значений, которые выступали аргументом для хэш-функции. Наверное, в частном случае это будут просто rowid, а в общем - просто какой-то key, по которому можно однозначно получить строку. Вот именно этот массив ключей - и не отсортирован. Да это и не надо, ведь получить нужно будет в любом случае все строки из данной секции и уже там сравнить: подходит эта строка нам или нет.

Хэш-таблица отсортирована по 1-му полю.
23 сен 05, 13:06    [1905091]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм работы hash join  [new]
Журавлев Денис
Member

Откуда: St.John,NB,CA
Сообщений: 5532
Enlighten me
...Мне не лень цитировать книжки, просто там всё равно написано лучше, чем я расскажу.

Спасибо за конструктивный ответ, все сразу стало ясно.
23 сен 05, 13:14    [1905129]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм работы hash join  [new]
Журавлев Денис
Member

Откуда: St.John,NB,CA
Сообщений: 5532
Valentyn Pidburtnyi

"Хэш-таблицу понимайте как ряд секций, при этом адресом каждой секции является значение хэш-функции, примененной к ключу. Сервер БД не сортирует значения ключей внутри отдельной хэш-секции"
Имхо, так.

Спасибо, похоже на правду.

Valentyn Pidburtnyi

Как я понял хэш-таблицу:

Я предполагаю тоже самое.

Valentyn Pidburtnyi

Хэш-таблица отсортирована по 1-му полю.

Это логично -- для быстрого поиска, но нигде об этом не говорится.
23 сен 05, 13:18    [1905158]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм работы hash join  [new]
vasilis
Member

Откуда: Украина, Киев
Сообщений: 2205
Вот отрывок из учебного материала на эту тему для лучшего понимания
===================
Три стратегии соединения
Каждое соединение распространяется на две таблицы. Одна таблица выбирается как первич-ная, соответственно она будет просмотрена сначала. Другая таблица, вторичная, будет ис-пользована для поиска в ней соответствующих данных, требуемых для выполнения соединения.
Кортеж создается в процессе соединения данных двух таблиц. Понимание того, каким обра-зом создаются кортежи, очень важно для того, чтобы оценить необходимость в оптимальном выполнении запроса.
Существуют три основные стратегии, которые могут использоваться при соединении двух таблиц.
....
• Соединение хешированием (hash join ) – производится последовательное сканирование первой из таблиц, во время которого строится хеш-таблица. Затем для выполнения со-единения строки из второй таблицы отбираются по хеш-таблице. Соединения хешированием доступны, начиная с версии 7 INFORMIX Dynamic Server.

Соединение хешированием
• Таблица table2 сканируется и размещается в хеш-таблице.
• Значения из таблицы table1 отыскиваются в хеш-таблице.
Соединения хешированием могут обеспечивать значительные преимущества в производительности по сравнению с другими методами соединения, особенно в тех случаях, когда размеры соединяемых таблиц весьма велики. Соединения хешированием работают быстрее соединений сортировкой слиянием, поскольку в последних приходится сортировать обе таблицы. Обычно в случае применения соединений хешированием хеш-таблица создается по меньшей из таблиц, и в этом случае исчезает необходимость в сортировке большей из них.
В приведенном выше примере для построения хеш-таблицы выбирается table2. Используя хеш-функцию, Informix прочитывает каждую строку таблицы, выполняет по отношению к ней хеш-функцию и определяет, так называемую хеш-секцию (hash bucket ), в которой будет храниться строка. Строки в пределах каждой хеш-секции не сортируются.
Как только table2 будет полностью прочитана и помещена в хеш-таблицу, прочитываются строки таблицы table1, вычисляются значения хеш-ключей и отыскиваются в хеш-таблице.
Хеш-таблица создается в виртуальной части разделяемой памяти. Если адекватный объем памяти недоступен, хеш-таблица частично записывается на диск. Место для временных файлов распределяется во временных DB-пространствах в соответствии со значением переменной среды или параметра конфигурации DBSPACETEMP. Оптимальным вариантом является создание хеш-таблицы полностью в разделяемой памяти.
Ожидаемый размер
Вы можете вычислить примерные требования к памяти для хеш-соединений с помощью следующей формулы.
(32 байта + размер_строки) * (к-во строк в меньшей таблице) = (к-во байт в хеш-таблице)
23 сен 05, 13:37    [1905241]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм работы hash join  [new]
Enlighten me
Member

Откуда:
Сообщений: 172
2Журавлев Денис

Не обижайтесь, я понимал излишнюю "общесть" своего ответа - потому в нем и содержалось скрытое еxcusez-moi. Насколько я понял, вы читали руководство для насторойки производительности в образовательных целях и такая форма подсказки (a clue) мне показалась уместной.

ЗЫ. При выборе хэш-функции как раз определить оптимальный "размер корзины" - искусство. Хорошо, когда он (размер) примерно укладывается в нормальное распределение; в большинстве случаев плохо, если одному ключу всегда соответсвует одно значение - переборщили...
23 сен 05, 13:48    [1905285]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм работы hash join  [new]
Журавлев Денис
Member

Откуда: St.John,NB,CA
Сообщений: 5532
vasilis
...
(32 байта + размер_строки) * (к-во строк в меньшей таблице) = (к-во байт в хеш-таблице)

А, вот оно как, 32 байта видимо размер хэш, и сама строка целиком, а не rowid (как я предполагал), лежат в хэш таблице.
23 сен 05, 13:48    [1905286]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм работы hash join  [new]
Журавлев Денис
Member

Откуда: St.John,NB,CA
Сообщений: 5532
Enlighten me
2Журавлев Денис

Не обижайтесь, я понимал излишнюю "общесть" своего ответа - потому в нем и содержалось скрытое еxcusez-moi. Насколько я понял, вы читали руководство для насторойки производительности в образовательных целях и такая форма подсказки (a clue) мне показалась уместной.

Я так среагировал потому что во первых прочитал ваше "внимательно читаем приведенную вами цитату и видим ответ", а я и просил помочь мне перевести эту фразу. Я не догадывался что в хэш-таблице лежит вся строка и поэтому слово keys которые сервер не сортирует внутри секции меня очень сильно смущало. Во вторых в других книжках по информиксу ни слова о хэш-таблицах нет (я не нашел). А мне был интересен именно информикс.

Enlighten me

ЗЫ. При выборе хэш-функции как раз определить оптимальный "размер корзины" - искусство.

это понятно.

Enlighten me

Хорошо, когда он (размер) примерно укладывается в нормальное распределение; в большинстве случаев плохо, если одному ключу всегда соответсвует одно значение - переборщили...

Пока мы не знаем как оно на самом деле устроено, можно об этом спорить до посинения. Можно сказать что ровно наоборот оптимум - это когда одному ключу соответствует одно значение хэш функции (в этом случае не нужно сравнивать ключи внутри секции, надо всего лишь быстро спуститься к секции сравнивая хеши).
23 сен 05, 14:13    [1905390]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм работы hash join  [new]
Valentyn Pidburtnyi
Member

Откуда: Kyiv, Ukraine
Сообщений: 69
Журавлев Денис
А, вот оно как, 32 байта видимо размер хэш, и сама строка целиком, а не rowid (как я предполагал), лежат в хэш таблице.

Я тоже не ожидал, что вся строка хранится...
23 сен 05, 15:08    [1905752]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм работы hash join  [new]
vasilis
Member

Откуда: Украина, Киев
Сообщений: 2205
А зачем же два раза на диск лазить ?
Лучше один раз все считать и в память засунуть, а уж тут разберемся...
Все равно таблица страницами читается (а не ключами или строками).
Это то же самое, что буффер использовать (проще страницу считать даже если нужна только одна строка - к тому же, есть вероятность, что еще строки понадобятся). Тем более, что тут чтение идет через Bigbuffer (если не ошибаюсь).
23 сен 05, 15:22    [1905858]     Ответить | Цитировать Сообщить модератору
Все форумы / Informix Ответить