Oracle всегда использует HASH JOIN, даже если обе таблицы огромны?

Question

Насколько я понимаю, HASH JOIN имеет смысл только тогда, когда одна из двух таблиц достаточно мала, чтобы поместиться в память в качестве хэш-таблицы.

, но когда я передал запрос в Oracle, обе таблицы имеют несколькосто миллионов строк, оракул все еще придумал план хэш-соединения.даже когда я обманул его подсказками OPT_ESTIMATE (rows = ....), он всегда решает использовать HASH JOIN вместо объединения с сортировкой слиянием.

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

спасибо Ян

Answer 1

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

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

Но есть некоторые исключения. Из Руководства по настройке производительности Oracle® Database, Оптимизатор запросов :

Хеш-объединения обычно работают лучше, чем сортировка слиянием. Тем не мение, Объединение сортировки слиянием может работать лучше, чем объединение хешей, если оба существуют следующие условия:

  The row sources are sorted already.
  A sort operation does not have to be done.

---

Тест

Вместо создания сотен миллионов строк проще заставить Oracle использовать только очень маленький объем памяти.

Эта диаграмма показывает, что хеш-объединения превосходят объединения слиянием, даже если таблицы слишком велики, чтобы поместиться в (искусственно ограниченную) память:

---

Примечания

Для настройки производительности обычно лучше использовать байты, чем количество строк. Но «реальный» размер таблицы сложно измерить, поэтому на графике отображаются строки. Размеры составляют примерно от 0,375 МБ до 14 МБ. Чтобы дважды проверить, что эти запросы действительно записывают на диск, вы можете запустить их с помощью / * + collect_plan_statistics * /, а затем выполнить запрос v $ sql_plan_statistics_all.

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

Я также проверил с разными _area_sizes, упорядоченными и неупорядоченными данными, а также с разной отчетливостью столбца соединения (чем больше совпадений, тем больше привязка к процессору, чем меньше совпадений, тем больше привязка к вводу-выводу), и получил относительно похожие результаты.

Однако результаты были другими, когда объем памяти был смехотворно мал. Только с 32K сортировкой | hash_area_size, объединение сортировки слиянием было значительно быстрее. Но если у вас так мало памяти, у вас, вероятно, есть более серьезные проблемы, о которых нужно беспокоиться.

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

---

Код

Ниже приведены сценарии, которые я использовал:

--Drop objects if they already exist
drop table test_10k_rows purge;
drop table test1 purge;
drop table test2 purge;

--Create a small table to hold rows to be added.
--("connect by" would run out of memory later when _area_sizes are small.)
--VARIABLE: More or less distinct values can change results.  Changing
--"level" to something like "mod(level,100)" will result in more joins, which
--seems to favor hash joins even more.
create table test_10k_rows(a number, b number, c number, d number, e number);
insert /*+ append */ into test_10k_rows
    select level a, 12345 b, 12345 c, 12345 d, 12345 e
    from dual connect by level <= 10000;
commit;

--Restrict memory size to simulate running out of memory.
alter session set workarea_size_policy=manual;

--1 MB for hashing and sorting
--VARIABLE: Changing this may change the results.  Setting it very low,
--such as 32K, will make merge sort joins faster.
alter session set hash_area_size = 1048576;
alter session set sort_area_size = 1048576;

--Tables to be joined
create table test1(a number, b number, c number, d number, e number);
create table test2(a number, b number, c number, d number, e number);

--Type to hold results
create or replace type number_table is table of number;

set serveroutput on;

--
--Compare hash and merge joins for different data sizes.
--
declare
    v_hash_seconds number_table := number_table();
    v_average_hash_seconds number;
    v_merge_seconds number_table := number_table();
    v_average_merge_seconds number;

    v_size_in_mb number;
    v_rows number;
    v_begin_time number;
    v_throwaway number;

    --Increase the size of the table this many times
    c_number_of_steps number := 40;
    --Join the tables this many times
    c_number_of_tests number := 5;

begin
    --Clear existing data
    execute immediate 'truncate table test1';
    execute immediate 'truncate table test2';

    --Print headings.  Use tabs for easy import into spreadsheet.
    dbms_output.put_line('Rows'||chr(9)||'Size in MB'
        ||chr(9)||'Hash'||chr(9)||'Merge');

    --Run the test for many different steps
    for i in 1 .. c_number_of_steps loop
        v_hash_seconds.delete;
        v_merge_seconds.delete;
        --Add about 0.375 MB of data (roughly - depends on lots of factors)
        --The order by will store the data randomly.
        insert /*+ append */ into test1
        select * from test_10k_rows order by dbms_random.value;

        insert /*+ append */ into test2
        select * from test_10k_rows order by dbms_random.value;

        commit;

        --Get the new size
        --(Sizes may not increment uniformly)
        select bytes/1024/1024 into v_size_in_mb
        from user_segments where segment_name = 'TEST1';

        --Get the rows.  (select from both tables so they are equally cached)
        select count(*) into v_rows from test1;
        select count(*) into v_rows from test2; 

        --Perform the joins several times
        for i in 1 .. c_number_of_tests loop
            --Hash join
            v_begin_time := dbms_utility.get_time;
            select /*+ use_hash(test1 test2) */ count(*) into v_throwaway
            from test1 join test2 on test1.a = test2.a;
            v_hash_seconds.extend;
            v_hash_seconds(i) := (dbms_utility.get_time - v_begin_time) / 100;

            --Merge join
            v_begin_time := dbms_utility.get_time;
            select /*+ use_merge(test1 test2) */ count(*) into v_throwaway
            from test1 join test2 on test1.a = test2.a;
            v_merge_seconds.extend;
            v_merge_seconds(i) := (dbms_utility.get_time - v_begin_time) / 100;
        end loop;

        --Get average times.  Throw out first and last result.
        select ( sum(column_value) - max(column_value) - min(column_value) ) 
            / (count(*) - 2)
        into v_average_hash_seconds
        from table(v_hash_seconds);

        select ( sum(column_value) - max(column_value) - min(column_value) ) 
            / (count(*) - 2)
        into v_average_merge_seconds
        from table(v_merge_seconds);

        --Display size and times
        dbms_output.put_line(v_rows||chr(9)||v_size_in_mb||chr(9)
            ||v_average_hash_seconds||chr(9)||v_average_merge_seconds);

    end loop;
end;
/

Answer 2

Поэтому мне интересно, как возможно HASH JOIN, если обе таблицы очень большие?

Это будет сделано за несколько проходов: ведомая таблица читается и хэшируется кусками, ведущая таблица сканируется несколько раз.

Это означает, что при ограниченном количестве хеш-памяти памяти масштабируется на O(N^2), тогда как объединение слиянием масштабируется на O(N) (конечно, сортировка не требуется), а на действительно больших таблицах слияние превосходит хеш-соединения. Однако таблицы должны быть действительно большими, чтобы преимущества одиночного чтения перевесили недостатки непоследовательного доступа, и вам потребуются все данные из них (обычно агрегированные).

Учитывая размер RAM на современных серверах, мы говорим о действительно больших отчетах по действительно большим базам данных, создание которых занимает часы, а не то, что вы бы действительно видели в повседневной жизни.

MERGE JOIN также может быть полезно, когда выходной набор записей ограничен rownum < N. Но это означает, что объединенные входы должны быть уже отсортированы, что означает, что они оба должны быть проиндексированы, что означает, что NESTED LOOPS также доступен, и это то, что обычно выбирается оптимизатором, поскольку это более эффективно, когда условие соединения является выборочным.

С их текущими реализациями MERGE JOIN всегда сканирует и NESTED LOOPS всегда ищет, в то время как более разумная комбинация обоих методов (подкрепленная статистикой) будет предпочтительнее.

Вы можете прочитать эту статью в моем блоге:

• Вещи, которые нужны SQL: MERGE JOIN для поиска

Answer 3

Соединение хеша не должно помещать всю таблицу в память, а только те строки, которые соответствуют условиям этой таблицы (или даже только хеш + идентификатор строки - я не уверен в этом).

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