exploysТеоретически Хэширование при соединении таблиц и группировки имеет несколько приемуществ:
хэш-функция
1. получая на вход значение ключа, на выходе дает адрес строки или указателя на строку
2. вырабатывает меньшее значение
3. равномерно распределеяет данные

Вопрос в следующем, каким образом практически реализуется 1, т.е. кто-нибуть может конкретный привести пример такой функции?
Раньше я думал, что если соединение на равенство, и одна табла из соединяемых малая, то эту малую таблу скачивать в память моно один раз, и Хэширование сократит число циклов, за счет того, что значение сравнивается по значению только с одной группой записей, с которой совпал Хэш ключ.
Допустим, эта малая табла разбита на 16 таких групп. Например, там 16 000 записей. Значение из второй таблы по ключу сравнивается с 15, и по конкретному значению только с той в которой совпал ключ. Т.е. вместо 16 000 цикл соствил 1000 + 15.
А поскольку вся табла первая в памяти, то на этом все и исчерпывается.

Но если первая табла не вся в памяти, то потребовалось бы считывать повторно блоки и из второй таблы, и хэширование могло потерять свои преимущества так как повторное чтение, могло бы, убить все это премущество.
Если в условии соединения неравенства, то это преимущество не работает.

vadiminfo,
Яж писал, про то что если ведомая таблица не помещается в памяти
exploysЧто группировка по хэш значениям это второстепенная задача. Когда хэш-таблица становиться слишком большой тогда действительно она делиться на группы по хэш-функции выполняющей роль двухуровневого дерева. [/quot]
Ну я писал, что думал так ранее. Т.е. если а малая таблица ("ведомая" ли "ведущая" ли ) не помещается в памяти, то преимущества хэш при соединении становятся менее очевидными. Т.е., возможно, нужно уже смотреть и другие алгоритмы с целью повышения производительности и сравнивать.
Т.е. выразил сомнения в преимуществах хэширования для СУБД у которых данные БД на дисках.


У Вашей СУБД есть отимизатор? Ну посмотрите планы запросов для разных ситуаций.

exploysMasterZiv, vadiminfo,

MS SQL BOL
авторРекурсия хэша возникает, когда входные данные не помещаются в доступную память, что приводит к разбиению их на несколько отдельно обрабатываемых секций. Если какая-либо из этих секций все же не помещается в доступную память, она разбивается на подсекции, которые также обрабатываются отдельно. Процесс разбиения продолжается, либо пока все секции не будут помещаться в доступную память, либо пока не будет достигнут максимальный уровень рекурсии


Ну, хорошо. Я же не говорю, что хэш не возможен. Я же предполагаю, что утрачиваются преимущества, возможно, драмматично в количестве считываний блоков. Ведь теперь блоки второй - большой таблы придется считывать с дисков по новой? Ить их нельзя было сравнить с теми что были не в памяти? Либо держать их и малые многократно считывать? Могут оказаться алгоритмы, которые обеспечат меньшее кол-во считываний. А количество считываний как правило самое критичное для СУБД такого типа хранения данных. Иначе бы в планах запросов мы вседа бы видели хэш - алгоритмы. "Но этого не происходит"(C)

exploysvadiminfo Могут оказаться алгоритмы, которые обеспечат меньшее кол-во считываний.
Это например какие алгоритмы?
исключая:
MERGE - только когда обе таблицы проиндексированы
NESTED LOOP - только когда одна из таблиц крайне мала, а большая проиндексирована
К слову в MS SQL только эти 3 алгоритма. Так какие же ещё ценные алгоритмы соединений они упустили?

Ну, Ви там в MS SQL если хотите, то исключайте SORT MERGE и NESTED LOOP.
А в Оракле, думау, все алгоритмы, включая перечисленные Вами, и так чрезмерно Вами ценимый алгоритм хэшированием (ить с ним надо сравнивать по Вашему только "ценные алгоритмы"), и в дополнение Cartesian еще какое-то время послужат.
Ну, по крайней мере, до тех пока Вы не откроете, что даже приведенные Вами случаи? када такие алгоритмы имеют преимущество, более не представляют интереса для практики.

А ить в соединении где в условиях могут быть неравенства.
А есть соедиения, где надо вернуть только первую строку (Например в SQL выражениях типа EXISTS).

Кроме того, если таблы малы? и их можно отсортировать в ОП, то SORT MERGE посему не проканает?

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

Кста, хотел бы обратить внимание Ваше, что NESTED LOOP - пока еще самый общий, и потому незаменимый алгоритм. При помощи соединения вложенными циклами можно реализовать любое условие соединения.

И как и раньше, думау, что есль соединяемые таблы очень большие, то хэширование, возможно, с каког-то момента их увеличения, возможно, не буит иметь преимуществ перед не "ценным" NESTED LOOP, а если отсортировано то SORT MERGE. На крайняк все окажутся не приемлемыми, и придется как-то по другому разруливать.

Понятие "ценные алгоритмы" не совсем ясно, так как не сталкивался с делением алгоритмов, используемых при оптимизации запросов по ценностной шкале. Потому, плиз, не нуно мне ниче подобного приписыть. Я ни про какие ценные и не ценные не говорил. Говорил про другие.

exploysvadiminfo, какой-то бессвязный набор букв.

Мы рассматриваем Хэширование. Соединение хэшированием применяется когда нету индексов. Вы высказали мнение, что если обе таблицы не поместятся в памяти то хэширование не оптимально.
Т.е. в этом случае, когда нету индексов и обе таблицы не помещаются в памяти по вашему оптимальнее будет использовать SORT MERGE и NESTED LOOP?
А уж как вы решили соединение хэшированием заменить картезианом вообще непонятно.
А когда есть индексы "Соединение хэшированием" не применимо? А планы в Оракле с хэшированием для индексированных попадаются.

Я вроде высказал, что может терять преимущества. Т.е. может оказаться не оптимальным, а не оказывается обязательно не отимальным. Это даже не означет в общем случае что, кто-то луче, Это означет, что ОНО не луче. Например, все плохи. Вы и в правду, как-то не совсем удачно связываете буквы.

Уточню что хотел сказать тада есче раз:
Я хотел сказать, что признау, что хэширование саммый эффективный способ при относительно небольшом размере меньшей таблы. Особенно када она помещается в памяти. Не зависимо ни от наличия или отсутсвия индексов или чего либо еще.
Но чем больше меньшая табла, тем более эти преимущества более утрачиваются с момента как она не помещается в памяти. Эта эффективность тает.
И не исключаю, что SORT MERGE и NESTED LOOP могут быть как минимум не хуже.



Про "нету индексов" я ниче не говорил. С какой стати? Не знау зачем их не создавать, если речь об оптимизации, и они могут помочь.

Не нуно, плиз, приписывать мне ниче такого.

Если бы Вы нашли бы связи в буквах, то типа я там приводил и др случаи када хэширование не канает.

exploys

vadiminfo , SORT MERGE это вообще сортировка слиянием и никакого отношения к соединениям не имеет. А NESTED LOOP используется когда одна из таблиц исключительно мала и никак не может применяться для соединения двух больших таблиц. Учите матчасть.
С картезианом туда же.
Т.е. Вы думаете, что при соединении, када юзается алгоритм в котором есть слово "MERGE" сортитровка не имеет никакого отношения, зато есть некоея сортировка слиянием одной таблы? Которая "SORT MERGE это вообще сортировка слиянием и никакого отношения к соединениям не имеет"?
Вообще до Вас это был "Алгоритм соединения слиянием сортированных списков ". Его могут в СУБД называть и MERGE и SORT MERGE.


Так или иначе в Оракле нпазывается SORT MERGE имеет отношение именно к соединениям. Конечно, у Оракла юзается слов MERGE, паример для команды DML, в которой и INSERT и UPDATE. А также и в оптимизатрое есть трасформация представлений View Merging.
Но алгоритм доступа к данным тока SORT MERGE. Никакой сортировка слиянием, "и никакого отношения к соединениям не имеет" там нет пока есче.

Ну Вы используйте NESTED LOOP када хотите, а я уверенно када обе малы, либо условия соединения таковы, что никакие другие алогоритмы не уместны. В остальных случаях бум посматрет.


Думаете кто первый сказал "Учите мат часть", тот типа самый умный? Этого достаточно? Тада скажите это Ораку и про "картезиан туда же".

Кто знает? Мож они все бросят, восхитятся Вами и, может быть, в подарок Вам телевизор "врУчат", а может быть "вручАт".
А я тока после них начну в серьез относиться к Вашим этим типа новаторским мыстлям.

exploysNESTED LOOP на миллионных таблицах...
Мда господа, 5 баллов! :)
Ну не тока нам:

http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D0%B5%D0%B4%D0%B8%D0%BD%D0%B5%D0%BD%D0%B8%D1%8F_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_%D1%81%D0%BF%D0%B8%D1%81%D0%BA%D0%BE%D0%B2

И там есть, к примеру:

Соединение слиянием в отличие от соединения с использованием хэширования может использоваться при больших размерах соединяемых таблиц.

Вы собираетесь кувыркаться с таблицей хеширования, если меньшая табла "многомилионная", Ваше право. А я с опасением отношусь к таким идеям..

exploys Тем более, что очевидно вы так и не прочитали по приведённым ссылкам как на самом деле работает HASH JOIN.

Зато я прочитал у Вас

exploys Соединение хэшированием применяется когда нету индексов.
.....
Если есть индексы по обоим полям то применялось бы всегда MERGE или NESTED LOOP. Тогда и не было бы смысла в HASH JOIN в принципе.


Возиможно, это компенсируент пробелы в знаниях:

Это значительно поднимает ценность MERGE или NESTED LOOP. Ну тада собсно Хэш особо и не нужен получается, поскоку индексы понасоздавать может кажный.

exploysТ.е. по вашему всегда можно понасоздавать индексов и всегда они будут использоваться, а HASH JOIN в СУБД реализовали зря? :)
Нет это Вы сказали, что если есть индексы, то HASH JOIN не нужен. Я то так не считал до сих пор, что он эффективнее всех остальных алгоритмов при определенных факторах (соединение на равеннство, относительно небольшая меньшая табла) всех дуругих известных алгоритмов не зависмо от наличия индексов на соединемые поля. Т.е. создавай не создавай индексы, нельзя пока обойтись.

Но если Вы были правы, то можно было бы. Тада да, зря парились, поскоку "Если есть индексы по обоим полям то применялось бы всегда MERGE или NESTED LOOP".

exploys
Как вы обойдетесь без HASH JOIN...?

Ну Вы же сказали, что если создать индексы, то HASH JOIN не нужен. Чего же проще? Создайте индекс. Делов то. И обойдетесь.

А у меня идеи "обходиться" без какого-либо алгоритма вроде никада не было (как и вообще ,tp чего-либо имеющегося в Оракле). И, в частности, нет готовности "обоходиться" только одним хэшем, т.е. "обходиться" без вложенных циклов и слияний. Есть ситуации, для которых есть больше уверенности када какой алгоритм луче, а есть менее ясные. Соединение больших табл отношу к менее ясным ситуациям, в которых нуно смотреть конкретные ситуации.
И, возможно, "обойтись" одними только алгоритмами вообще не удастся. Можно буит тока посматреть какой хуже. Придется пытаться в основу "обхода" положить что-либо другое. Напрмер,рассматривать кластреры, таблы организованные по индексу, может мат представления как-то заюзать или как-то иначе заблаговременно вычислять результат соединений, чтобы в запросе юзера уже соединения не было.

exploysЕсли есть индексы по обоим полям то применялось бы всегда MERGE или NESTED LOOP. Тогда и не было бы смысла в HASH JOIN в принципе.

exploysиндексы созданы


Ну на скока я понял Вы обошлись без HASH JOIN "в принципе"?

А я, если прикажет партия непеременно "обойтись" без HASH JOIN, напишу хинты, наверное, на случай если оптимизатор выберет HASH JOIN.

exploysИндекс создан, но использоваться не сможет. Поэтому хоть обсоздавайся индексов, без HASH JOIN ты тот запрос будешь выполнять до морковкеного заговенья. Именно потому, что таблицы не отсортированы, слишком велики и не помещаются в памяти. ?
А при чем тут я? Это у Вас:
"Если есть индексы по обоим полям то применялось бы всегда MERGE или NESTED LOOP. Тогда и не было бы смысла в HASH JOIN в принципе."

Или это не Вы писали?

А я про отмену индексами HASH JOIN ниче не говорил.

Так что это Вы сами себя типа спросите.



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

Ну хорошо, долго рекурсия продолжается.
А там еще могут быть переполнения раздела.

exploysЕсли укажите хинт MERGE JOIN,

Ну я укажу хинт, если потребуют гарантировано "обойтись" без HASH JOIN. Каков был вопрос, таков был ответ.

exploysто пойдет сортировка - самая тяжелая операция.
Таблицы не помещаются в памяти - значит сортировка будет происходить с использованием temp сохраняемого на диск. Вы представляете что это такое?
Вы когда-нибуть видели планы и их стоимость при использовании SORT IN TEMP?

Ну хорошо. Не помещаются. Temp - это уже Ваши там какие-то МS дела.

Оценку для сортировки, думау, по книжному примерно: 27*100000000 для одной таблы, а оценку соединеиия двух как сумму.

Самой тяжелой операцией по старинке считаю соединение.

Можно, конечно, надыбать и формулы для Хэш. И там есть лучшие и худьшие предположения.

А вот если одна табла поместилась в память, то, думау, ценка: 3* на сумму болков обоих табл. Это превзойти сложно, хотя слияние отсортированных это просто сумма блоков обоих табл.

Для больших табл, возможно, отклонения оценок от реальных цифр могут быть значительными.

Так или иначе, думаю, оставться на консервтивных позициях в этих вопросах все еще уместно: т.е. надо смотреть в кажном конкретном случае.
Но если в условиях соединение не эквивалентность, то думау, Хэш, скорее всего, в проигрыше.