NEW BOT Телеграм, страница

✨

Физические JOIN'ы

✨

Мое незнание этой темы привело к 6-месячному куллдауну в Авито😭
Чтобы у вас не было также, давайте разберем ее подробнее.

😍Физический джойн — это алгоритм, который используется для выполнения операции объединения двух таблиц. Иными словами, это то, что происходит "под капотом", когда вы вызываете join в запросе

⭐ Основных алгоритмов всего 3: nested loops, merge join, hash join/hash match.

🩷

Nested loops

Принцип работы уже понятен из названия: каждый элемент внешнего цикла сравнивается с каждым элементом внутреннего.
Алгоритмическая сложность - O(n**2)

For Each value in pile1
    For Each value in pile2
        If pile1.value = pile2.value
        Return pile1.value, pile2.value

🩷

Merge join

Для этого алгоритма элементы уже должны быть отсортированы. Тут мы проходимся двумя указателями по элементам и сравниваем их. В конце проходим по оставшимся элементам.

Если не считать сортировку, алгоритмическая сложность - O(n).

get first row R1 from   input 1
get first row R2 from   input 2

while not at the end   of either input
      begin
          if R1 joins with R2
              begin
                  get next row R2 from input 2
                  return (R1, R2)
              end
          else if R1 < R2
              get next row R1 from input 1
          else
              get next row R2 from input 2
    end

🩷

Hash join

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

// Build phase
FOR each row in BuildTable DO
    Compute hash value for the join key
    Insert row into HashTable based on hash value
END FOR

// Probe phase
FOR each row in ProbeTable DO
    Compute hash value for the join key
    IF hash value exists in HashTable THEN
        Retrieve matching rows from HashTable
        FOR each matching row DO
            Combine rows from ProbeTable and BuildTable
            Add the combined row to the result set
        END FOR
    END IF
END FOR

Рекомендую просмотреть псевдокод и реализовать все на своем языке💖
#de_обсуждение

Please open Telegram to view this post

VIEW IN TELEGRAM

❤29🏆4👍2🔥1

1.42K viewsedited 17:13