Алгоритм Объединения слиянием

Вступление

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

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

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

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

Сущность Post имеет связанную post таблицу с 1000 записями, которые выглядят следующим образом:

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

И дочерняя ПостКоммент сущность имеет 10 000 строк, которые связаны с 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            |
|---------|---------------|-------------------|
| 1000    | Post no. 1000 | Comment no. 10000 |
| 1000    | Post no. 1000 | Comment no. 9999  |
| 1000    | Post no. 1000 | Comment no. 9998  |
| 1000    | Post no. 1000 | Comment no. 9997  |
| 1000    | Post no. 1000 | Comment no. 9996  |
| 1000    | Post no. 1000 | Comment no. 9995  |
| 1000    | Post no. 1000 | Comment no. 9994  |
| 1000    | Post no. 1000 | Comment no. 9993  |
| 1000    | Post no. 1000 | Comment no. 9992  |
| 1000    | Post no. 1000 | Comment no. 9991  |
| ..      |..             | ..                |
| 1       | Post no. 1    | Comment no. 2     |
| 1       | Post no. 1    | Comment no. 1     |

Алгоритм Объединения слиянием

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

posts.sort(Comparator.comparing(Post::getId));

postComments.sort((pc1, pc2) -> {
    int result = Comparator
        .comparing(PostComment::getPostId)
        .compare(pc1, pc2);
    
    return result != 0 ? result : Comparator
        .comparing(PostComment::getId)
        .compare(pc1, pc2);
});

На втором шаге мы повторяем две таблицы и проверяем условие соединения.

List tuples = new ArrayList<>();

int postCount = posts.size(), postCommentCount = postComments.size();
int i = 0, j = 0;

while(i < postCount && j < postCommentCount) {
    Post post = posts.get(i);
    PostComment postComment = postComments.get(j);
    
    if(post.getId().equals(postComment.getPostId())) {
        tuples.add(
            new Tuple()
                .add("post_id", postComment.getPostId())
                .add("post_title", post.getTitle())
                .add("review", postComment.getReview())
        );
        j++;
    } else {
        i++;
    }
}

В отличие от Вложенных циклов или алгоритмов Хэш-соединения , сложность алгоритма соединения слиянием является логарифмической звездой n (например, O(n log(n) + mlog(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
ORDER BY pc.post_id DESC

создает объединение слиянием, как показано в базовом плане выполнения:

Merge Join  
  (cost=0.56..793.06 rows=10000 width=1048) 
  (actual time=0.621..8.986 rows=10000 loops=1)
  Merge Cond: (p.id = pc.post_id)
  ->  Index Scan Backward using idx_post_id on post p  
        (cost=0.28..63.27 rows=1000 width=524) 
        (actual time=0.402..0.798 rows=1000 loops=1)
  ->  Index Scan Backward using idx_post_comment_post_id on post_comment pc  
        (cost=0.29..602.28 rows=10000 width=524) 
        (actual time=0.167..4.583 rows=10000 loops=1)

Вывод

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

В то время как Oracle, SQL Server и PostgreSQL поддерживают алгоритм объединения слиянием, MySQL его пока не поддерживает.