Изпълнение на клъстерен индекс на 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
Мисля, че не трябва да смесвате join + where. 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