Рубрики
Без рубрики

Алгоритм Соединения Вложенных Циклов

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

Автор оригинала: 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    |

Теперь мы заинтересованы в присоединении к записям Сообщение и Комментарий к сообщению путем сопоставления атрибутов идентификатор и положительный и построения проекции, содержащей следующие атрибуты:

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

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

| 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  |
| ..      |..          | ..             |
| 2       | Post no. 2 | Comment no. 14 |
| 2       | Post no. 2 | Comment no. 15 |

Алгоритм Соединения Вложенных Циклов

Алгоритм соединения вложенных циклов основан на двух циклах for, которые повторяют оба отношения в поисках записей, соответствующих условию соединения:

List tuples = new ArrayList<>();

for (Post post : posts) {
    for (PostComment postComment : postComments) {
        if(post.getId().equals(postComment.getPostId())) {
            tuples.add(
                new Tuple()
                    .add("post_id", postComment.getPostId())
                    .add("post_title", post.getTitle())
                    .add("review", postComment.getReview())
            );
        }
    }
}

Хотя алгоритм прост в реализации, его сложность квадратична (например, O(n2) ), и чем больше размер отношений, тем больше потребуется обработки для поиска всех совпадающих записей, как показано на следующем графике:

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

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

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.id
LIMIT 15

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

Limit  
  (cost=0.56..5.92 rows=15 width=1048) 
  (actual time=0.229..0.272 rows=15 loops=1)
  ->  Nested Loop  
        (cost=0.56..3575.06 rows=10000 width=1048) 
        (actual time=0.227..0.269 rows=15 loops=1)
        ->  Index Scan using idx_post_comment_id on post_comment pc  
              (cost=0.29..602.28 rows=10000 width=532) 
              (actual time=0.112..0.120 rows=15 loops=1)
        ->  Index Scan using idx_post_id on post p  
              (cost=0.28..0.30 rows=1 width=524) 
              (actual time=0.009..0.009 rows=1 loops=15)
              Index Cond: (id = pc.post_id)

Вывод

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

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

Читайте ещё по теме: