Почему объединения ha sh создают таблицу ha sh из таблицы меньшего размера, а не из таблицы большего размера?

Question

Я выполнил объяснение по этому запросу

SELECT
  city.name
  , country.name
FROM
  city
  JOIN country ON
    city.countrycode = country.code

QUERY PLAN
------------------------------------------------------------------
Hash Join (cost=10.38..139.25 rows=4079 width=20)
 Hash Cond: (city.countrycode = country.code)
 ->  Seq Scan on city (cost=0.00..72.79 rows=4079 width=13)
 ->  Hash  (cost=7.39..7.39 rows=239 width=15)
       ->  Seq Scan on country (cost=0.00..7.39 rows=239 width=15)

И я прочитал, что таблица меньшего размера всегда является внутренней в этом запросе. Но, поскольку мы знаем, что таблицы ha sh в среднем дают вам доступ O (1), почему лучше создать небольшую таблицу ha sh и обращаться к ней больше раз, вместо того, чтобы создавать таблицу ha sh большего размера? и доступ к нему меньше раз? Я использую Postres SQL, но это не должно иметь значения, потому что это фундаментальная концепция для РСУБД.

Answer 1

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

Зачем циклически проходить по меньшей таблице? Рассмотрим проделанную работу:

1. Создание таблицы ha sh: чтение и запись одной таблицы.
2. Обработка другой таблицы: чтение другой таблицы.
3. Заключительная работа: выписка набора результатов

Примечание: это упрощение реальной работы, предполагая, что таблица ha sh помещается в память и игнорируя коллизии ha sh.

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

Однако первые два в основном:

<read one table> + <write one table> + <read the other table>

То есть одна таблица читается и записывается, поэтому она считается дважды. Другой только для чтения. Вы оптимизируете это, обрабатывая таблицу SMALLER как ha sh.

Кроме того, меньшая таблица с большей вероятностью помещается в памяти. И менее вероятно, что у него будет sh столкновений.

В общем, лучше иметь sh меньшую таблицу.