Алгоритм Соединения Хэшей

Автор оригинала: Vlad Mihalcea.

Вступление

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

Наборы данных

Давайте рассмотрим, что у нас есть два отношения , родитель Сообщение и ребенок Комментарий к сообщению , которые выглядят следующим образом:

Поскольку положительный атрибут в Комментарии к сообщению отношение ссылается на идентификатор атрибут в родительском Сообщении отношении, две сущности образуют отношение “один ко многим” .

Отношение родитель Сообщение содержит 1000 записей, которые выглядят следующим образом:

| id   | title         |
|------|---------------|
| 1    | Post no. 1    |
| 2    | Post no. 2    |
| ..   | ..            |
| 999  | Post no. 999  |
| 1000 | Post no. 1000 |

И, дочернее Сообщение Комментарий отношение имеет 10000 строк, которые связаны с 1000 Сообщение записей:

| id    | review            | postId  |
|-------|-------------------|---------|
| 1     | Comment no. 1     | 1       |
| 2     | Comment no. 2     | 1       |
| ..    | ..                | ..      |
| 9999  | Comment no. 9999  | 1000    |
| 10000 | Comment no. 10000 | 1000    |

Мы заинтересованы в объединении записей Сообщение и Комментарий к сообщению путем сопоставления атрибута id связи Сообщения с атрибутом postID связи PostComment , чтобы мы могли построить проекцию, содержащую следующие атрибуты:

• идентификатор поста
• Должность название
• Комментарий к сообщению обзор

В нашем случае именно так должен выглядеть вышеупомянутый отчет:

| post_id | post_title    | review            |
|---------|---------------|-------------------|
| 1       | Post no. 1    | Comment no. 1     |
| 1       | Post no. 1    | Comment no. 2     |
| 1       | Post no. 1    | Comment no. 3     |
| 1       | Post no. 1    | Comment no. 4     |
| 1       | Post no. 1    | Comment no. 5     |
| 1       | Post no. 1    | Comment no. 6     |
| 1       | Post no. 1    | Comment no. 7     |
| 1       | Post no. 1    | Comment no. 8     |
| 1       | Post no. 1    | Comment no. 9     |
| ..      |..             | ..                |
| 1000    | Post no. 1000 | Comment no. 9999  |
| 1000    | Post no. 1000 | Comment no. 10000 |

Алгоритм Соединения Хэшей

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

Map postMap = new HashMap<>();

for (Post post : posts) {
    postMap.put(post.getId(), post);
}

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

На втором шаге выполняется итерация отношения большего размера, а запись таблицы меньшего размера находится с использованием ранее построенной хэш-карты:

List tuples = new ArrayList<>();

for (PostComment postComment : postComments) {
    Long postId = postComment.getPostId();
    Post post = postMap.get(postId);

    if (post != null) {
        tuples.add(
            new Tuple()
                .add("post_id", postComment.getPostId())
                .add("post_title", post.getTitle())
                .add("review", postComment.getReview())
        );
    }
}

В отличие от алгоритма Вложенных циклов , сложность алгоритма хэш-соединения линейна (например, O(N + M) ), и чем больше размер отношений, тем больше потребуется обработки для поиска всех совпадающих записей, как показано на следующем графике:

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

Например, выполнение этого SQL-запроса на PostgreSQL при соединении таблицы post с 1000 записями и таблицы post_comment с 10000 строками:

SELECT
   p.id AS post_id,
   p.title AS post_title,
   pc.review  AS review
FROM post p
INNER JOIN post_comment pc ON pc.post_id = p.id

создает хэш-соединение, как показано в базовом плане выполнения:

Hash Join  
  (cost=29.50..238.86 rows=10000 width=1040) 
  (actual time=0.821..10.278 rows=10000 loops=1)
  Hash Cond: (pc.post_id = p.id)
  ->  Seq Scan on post_comment pc  
        (cost=0.00..183.00 rows=10000 width=524) 
        (actual time=0.155..2.833 rows=10000 loops=1)
  ->  Hash  
          (cost=17.00..17.00 rows=1000 width=524) 
          (actual time=0.534..0.535 rows=1000 loops=1)
        Buckets: 1024  Batches: 1  Memory Usage: 60kB
        ->  Seq Scan on post p  
              (cost=0.00..17.00 rows=1000 width=524) 
              (actual time=0.036..0.272 rows=1000 loops=1)

Вывод

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

Традиционно MySQL предлагал только алгоритм вложенных циклов, который был бы намного выше, но начиная с версии 8.0.18 он также поддерживает алгоритм хэш-соединения.

С другой стороны, Oracle, PostgreSQL и SQL Server уже очень давно поддерживают алгоритм хэш-соединения.