powered by simpleCommunicator - 2.0.51     © 2025 Programmizd 02
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Объясните, плиз, на пальцах в чём отличие nested loops от hash join?
13 сообщений из 13, страница 1 из 1
Объясните, плиз, на пальцах в чём отличие nested loops от hash join?
    #40038894
Yuri Kazakoff
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Объясните, плиз, на пальцах в чём отличие nested loops от hash join? Если можно, пожалуйста попроще, ибо тупой))
...
Рейтинг: 0 / 0
Объясните, плиз, на пальцах в чём отличие nested loops от hash join?
    #40038897
Фотография Corner
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
Объясните, плиз, на пальцах в чём отличие nested loops от hash join?
    #40038918
PuM256
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Не надо неокрепшие умы к Бурлесону приучать.

https://docs.oracle.com/en/database/oracle/oracle-database/21/tgsql/joins.html#GUID-BD96F1B4-76D4-43DF-98B6-D07F46838C4A
...
Рейтинг: 0 / 0
Объясните, плиз, на пальцах в чём отличие nested loops от hash join?
    #40039250
Фотография кит северных морей
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Yuri Kazakoff
на пальцах

ну если совсем на пальцах, то примерно так (псевдокод на питоне):

Код: plsql
1.
select * from outer_table join inner_table on outer_table.id = inner_table.id



Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
def nl_join(outer_table, inner_table):
    for o in outer_table: 
        for i in inner_table:
            if o.id = i.id: 
                yield o, i
                
def hash_join(outer_table, inner_table):
    outer_hash_table = {o.id : o for o in outer_table}    
    for i in inner_table: 
        if i.id in outer_hash_table:
            yield outer_hash_table[i.id], i
...
Рейтинг: 0 / 0
Объясните, плиз, на пальцах в чём отличие nested loops от hash join?
    #40039400
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Модератор форума
кит северных морей,

неверная аналогия даже в случае крайнего упрощения:

1. Основное отличие NL в том, что он передает параметр из ведущей таблицы в функцию получения из ведомой; в Cost Based Oracle Fundamentals Льюис более удачный пример привел:
Код: plsql
1.
2.
3.
4.
5.
for r1 in (select rows from table_1 where colx = {value}) loop
    for r2 in (select rows from table_2 that match current row from table_1) loop
        output values from current row of table_1 and current row of table_2
    end loop
end loop



2. В варианте HJ, не показано, почему он собственно называется Hash join.

Поэтому я бы чуток переделал примеры:
Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
def nl_join(outer_table, inner_table):
    for o in get_from(outer_table, ...): 
        for i in get_from(inner_table, 'id = $1', i.id): # 1й аргумент - источник, 2й - условие, 3й - аргумент условия
             yield o, i
                
def hash_join(build_table, prob_table):
    # создаем hash таблицу:
    hash_build_table = {o.id : (hash(o.id) as hash_key,o.*) for o in build_table}    
    for i in get_from(prob_table, ...): 
        for j in get_from(hash_build_table, 'hash_key=$1', hash(i.id)):
            if i.id = j.id:
                yield j, i



Названия inner/outer тоже не очень удачно выбраны:
“OUTER” AND “INNER” TABLES “OUTER” AND “INNER” TABLES
The terms outer and inner are really only appropriate to nested loop joins. When talking about hash joins, you
ought to refer to the build table and probe table; and for merge joins, the terms first table and second table are
sufficient. However, you will find that the 10053 trace file always uses the terms outer and inner to identify
the first and second tables respectively in a join operation. I will revisit this point in the relevant chapters.
...
Рейтинг: 0 / 0
Объясните, плиз, на пальцах в чём отличие nested loops от hash join?
    #40039420
Фотография кит северных морей
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
xtender,

я думаю что фундаментальное отличие заключается в том, что в случае с NL вы получаете m * n итераций циклов за счет их вложенности, а в случае с HJ вы получаете m + n, но с дополнительными расходами по памяти на хэш-таблицу. я намеренно максимально упростил пример, чтобы продемонстрировать этот tradeoff.

вы говорите всё правильно, конечно, но мне кажется, что это уже больше про основы реализации.
...
Рейтинг: 0 / 0
Объясните, плиз, на пальцах в чём отличие nested loops от hash join?
    #40039428
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
при NL поиск идет по индексу
при HJ по full table scan перелопачивается вся таблица

я намеренно максимально упростил пример, чтобы продемонстрировать этот tradeoff. ( C )

p.s. Вообще тема похожа на попытку вбросить что-то на вентилятор ибо
Имя Yuri Kazakoff
Статус Зарегистрированный участник
Зарегистрирован: 13 ноября 2004 , 14:13
...
Рейтинг: 0 / 0
Объясните, плиз, на пальцах в чём отличие nested loops от hash join?
    #40039430
Фотография кит северных морей
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev
p.s. Вообще тема похожа на попытку вбросить что-то на вентилятор ибо
Имя Yuri Kazakoff
Статус Зарегистрированный участник
Зарегистрирован: 13 ноября 2004 , 14:13

он же написал, что тупой. всё нормально.
...
Рейтинг: 0 / 0
Объясните, плиз, на пальцах в чём отличие nested loops от hash join?
    #40039437
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev
при NL поиск идет по индексу


максимально упростил пример

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
SQL> l
  1  with
  2    n as (select 1 a from dual union all select 2 from dual )
  3   ,l as (select 2 b from dual)
  4* select * from n,l where a=b
SQL> /

         A          B
---------- ----------
         2          2


Execution Plan
----------------------------------------------------------
Plan hash value: 2443366440

-------------------------------------------------------------------------
| Id  | Operation        | Name | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------
|   0 | SELECT STATEMENT |      |     2 |     6 |     4   (0)| 00:00:01 |
|   1 |  NESTED LOOPS    |      |     2 |     6 |     4   (0)| 00:00:01 |



.....
stax
...
Рейтинг: 0 / 0
Объясните, плиз, на пальцах в чём отличие nested loops от hash join?
    #40039442
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Модератор форума
кит северных морей
в случае с NL вы получаете m * n итераций циклов за счет их вложенности, а в случае с HJ вы получаете m + n
это как это? А лукап в хэш-таблицу? Вообще это не про циклы, а про количество и характер операций чтения, т.е именно доступ к данным
...
Рейтинг: 0 / 0
Объясните, плиз, на пальцах в чём отличие nested loops от hash join?
    #40039450
Alexander Anokhin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Yuri Kazakoff
Объясните, плиз, на пальцах в чём отличие nested loops от hash join? Если можно, пожалуйста попроще, ибо тупой))


Тут Оракл попытался объяснить на иховом.
YouTube Video
...
Рейтинг: 0 / 0
Объясните, плиз, на пальцах в чём отличие nested loops от hash join?
    #40039482
Фотография кит северных морей
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
xtender
это как это? А лукап в хэш-таблицу?

согласен. на каждом шаге n будет один лукап. ну, пусть будет m + 2n операций.

xtender
Вообще это не про циклы, а про количество и характер операций чтения, т.е именно доступ к данным

каждый шаг цикла - это какая-то операция доступа к данным с определенной стоимостью. я не вижу здесь противоречия.
...
Рейтинг: 0 / 0
Объясните, плиз, на пальцах в чём отличие nested loops от hash join?
    #40039517
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Модератор форума
кит северных морей
один лукап
лукап в хэш-таблицу - это тоже цикл перебирающий ее строки, соответствующие ключу.

Код: plsql
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.
SQL> get tests/1
  1  explain plan for
  2  with t as (select/*+ materialize */ 1 a, rpad('x',111,'x') b from dual connect by level<=100)
  3* select * from t t1, t t2 where t1.a=t2.a

Plan hash value: 1434490737

----------------------------------------------------------------------------------------------------------------------
| Id  | Operation                                | Name                      | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                         |                           |     1 |   120 |     6   (0)| 00:00:01 |
|   1 |  TEMP TABLE TRANSFORMATION               |                           |       |       |            |          |
|   2 |   LOAD AS SELECT (CURSOR DURATION MEMORY)| SYS_TEMP_0FD9D68B5_257369 |       |       |            |          |
|*  3 |    CONNECT BY WITHOUT FILTERING          |                           |       |       |            |          |
|   4 |     FAST DUAL                            |                           |     1 |       |     2   (0)| 00:00:01 |
|*  5 |   HASH JOIN                              |                           |     1 |   120 |     4   (0)| 00:00:01 |
|   6 |    VIEW                                  |                           |     1 |    60 |     2   (0)| 00:00:01 |
|   7 |     TABLE ACCESS FULL                    | SYS_TEMP_0FD9D68B5_257369 |     1 |    70 |     2   (0)| 00:00:01 |
|   8 |    VIEW                                  |                           |     1 |    60 |     2   (0)| 00:00:01 |
|   9 |     TABLE ACCESS FULL                    | SYS_TEMP_0FD9D68B5_257369 |     1 |    70 |     2   (0)| 00:00:01 |
----------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   3 - filter(LEVEL<=100)
   5 - access("T1"."A"="T2"."A")

например, тут по #6 будет построена хэш-таблица из 100 строк с одним и тем же ключом, и для каждой строки из #8 будет цикл-перебор по 100 строкам в хэш-таблице, т.к. ключ у них одинаковый. Однако, происходить это будет внутри самой функции HJ.
...
Рейтинг: 0 / 0
13 сообщений из 13, страница 1 из 1
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Объясните, плиз, на пальцах в чём отличие nested loops от hash join?
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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