Производительность кластеризованного индекса в SQL-запросе

Предположим, у вас есть две таблицы:

Student(id, class) // 100 rows
Course(id, course) // 100 rows

Первоначально предположим, что в обеих таблицах нет индекса. Теперь предположим, что у нас есть запрос:

select id, course 
from Student join course 
on student.id = Course.id and student.id = 20

Поскольку у вас нет индекса, вам нужно просмотреть все строки в обеих таблицах.

Time complexity - O(100 x 100)

Теперь мы обновили таблицу и Student.id — это первичный ключ. На нем будет создан кластеризованный индекс, и теперь общая сложность

Time complexity - O(log 100) // Nested loop join

Как вы думаете, мое предположение верно? Кто-нибудь может мне помочь?

Алгоритм соединения вложенного цикла находится здесь:

введите здесь описание изображения


mysql sql indexing clustered-index time-complexity
person python    schedule 12.12.2015    source источник
comment
Я думаю, что вы не должны смешивать соединение + где. select id, course from Student join Course ON student.id = Course.id WHERE student.id = 20   -  person Lukasz Szozda    schedule 12.12.2015
comment
Пожалуйста, не используйте этот устаревший синтаксис соединения. Это работает, но в SQL Standard для этого есть JOIN .. ON....   -  person Lukasz Szozda    schedule 12.12.2015

Ответы (1)


arrow_upward
1
arrow_downward 

join course 
on student.id = Course.id

правильно в O(MN) (наихудший случай), где M и N — количество строк в первой и второй таблице соответственно, поскольку это equi-join (присоединение к условию =), он сравнивает каждую строку из первой со второй.

Однако у вас также есть второе условие. Поскольку SQL имеет множество алгоритмов повышения производительности, весьма вероятно, что student.id = 20 будет оцениваться первым. Тогда у вас будет сначала M (предполагается, что линейно по количеству строк таблицы студентов) для поиска student.id = 20. Тогда, если student.id = 20 является только константой, скажем, m, у вас будет m * N.

В общем, O(M + (m * N)).

Вот это сейчас зависит от m. Если m постоянно, то в асимптотическом анализе O(M + N) = O(2M), так как M=N и вы получите O(M) = O(N) или линейное. В противном случае, если m находится в Omega(1), то это будет O(M + M * N) или, как вы предположили, O(MN).

Затем, что касается PRIMARY KEY, будет/может быть создан кластеризованный индекс. Временная сложность для будущих запросов будет, как вы сказали, O(log K), где K - строки в новой таблице (может быть! = 100).

Теперь, почему log K? Потому что реляционные базы данных структурируют индексы как B-деревья. Тогда в WC вы получите O(log K) в высоту дерева.

Точнее

так как на B-деревьях у вас макс. 2d children и количество ключей s между d - 1 < s < 2d. d называется порядком, степенью или коэффициентом ветвления дерева.

Надеюсь, поможет!

person Dimitar    schedule 23.12.2015