1632
правки
Изменения
м
От выбора плана '''сильно''' зависит производительность
*'''Фильтрация''' Мы можем пользовать стандартными алгебраическими трюками. Предположим хотим отфильтровать объединение. Можем отфильтровать первый аргумент, потом второй, а потом объединить.{{Утверждение|statement=** $σ_{cond}(R_1 ∪ R_2) ⇒ σ_{cond}(R_1) ∪ σ_{cond}(R_2)$** }} Аналогично для пересечения{{Утверждение|statement=$σ_{cond}(R_1 \cap ∩ R_2) ⇒ σ_{cond}(R_1) \cap ∩ σ_{cond}(R_2)$** }} Аналогично для разности{{Утверждение|statement=$σ_{cond}(R_1 - R_2) ⇒ σ_{cond}(R_1) - σ_{cond}(R_2)$** }} Естественное соединение. Если можем разделить условие на две части, одна из которых относится проверяет атрибуты только из левого атрибута, а вторая только из правого, то мы можем протолкнуть этот фильтр отдельно в левый и правый аргумент, а потом соединить только для строк, удовлетворяющим своим половинкам фильтра. Аналогично для разности{{Утверждение|statement=$σ_{cond_1 ∧ cond_2}(R_1 ⋈ R_2) ⇒ σ_{cond_1}(R_1) ⋈ σ_{cond_2}(R_2)$}} '''Проекция''' Можем безопасно проекцировать результат объединения{{Утверждение|statement=$π_A(R_1 ∪ R_2) ⇒ π_A(R_1) ∪ π_A(R_2)$}}
*Проекция** Не можем безопасно проецировать результат пересечения, потому что слева могли быть кортежи, которые кроме атрибута $A$ содержат еще какой-то дополнительный атрибут $X$. Они различались, вошли в пересечение и уже потом мы их спроецируем. Если же сначала сделать проекцию, то этот атрибут $X$ теряется и два кортежа с одинаковым атрибутом $A$ но разным атрибутом $π_A(R_1 ∪ R_2) ⇒ π_A(R_1) ∪ π_A(R_2)X$для нас станут неразличимы.{{Утверждение|statement=** $π_A(R_1 ∩ R_2) ⇏ π_A(R_1) ∩ π_A(R_2)$** $π_A(R_1 - R_2) ⇏ π_A(R_1) - π_A(R_2)$** $π_{A}(R_1 ⋈ R_2) ⇒ π_A(π_{(A ∪ R_2) ∩ R_1}(R_1) ⋈ π_{(A ∪ R_1) ∩ R_2}(R_2))$
rollbackEdits.php mass rollback
== Обработка запроса ==
От выбора плана '''сильно''' зависит производительность
=== Мотивирующий пример ===
==== Пример базы данных: ====
Пусть у нас есть база данных Университет.Есть следующая таблица Students:
*<var>Students(SId, FirstName, LastName, GId, Year)</var>
** $10^4$ записей
** Индексы: <var>(SId)</var> (кластеризованный), <var>(GId)</var>
И следующая таблица Groups:
*<var>Groups(GId, Name)</var>
** $10^3$ записей
** Индексы: <var>(GId)</var> (кластеризованный), <var>(Name)</var>
==== Запрос: ====
Будем выбирать студентов группы M3439
Фамилии студентов группы M3439
==== Планы запросов без индексов ====
Делаем декартово произведение, на него навешено условие естественного соединения, потом делаем фильтр и потом проецируем.
* План 1
** $π_{FirstName}(σ_{Name=M34391}(σ_{S.GId=G.GId}(S × G)))$
** Получаем $10^4·10^3 + 10^4·10^3 + 10^4 + 20 ≈ 2·10^7$ операций
Сразу делаем естественное соединение без отдельной стадии фильтрации и декартового произведения. Тем не менее в середине все равно строим $10^4·10^3$, но только один раз. Потом опять отфильтруем и спроецируем. Снизили трудозатраты примерно в два раза.
*План 2
** $π_{Name}(σ_{Name=M34391}(S ⋈ G))$
** $10^4·10^3 + 10^4 + 20 ≈ 10^7$ операция
Сначала отфильтруем группы. Это обработать $1000$ групп. Выберем из них 1 группу. Потом переберем $10^4$ студентов. И финальная проекция на $20$ элементов.
Снизили время на $3$ порядка!
* План 3
** $π_{Name}(S ⋈ σ_{Name=M34391}(G))$
==== Планы запросов с индексами ====
Аналогично плану 3, только теперь не перебираем всех студентов, а достаем их из индекса. Если был индекс на основе B дерева глубины $3$. Мы дошли до его листа и достали примерно $20$ студентов из группы. Осталось сделать проекцию, а это еще $20$ операций. В итоге снизили время еще на порядок.
* План 4. <var>Students(GId)</var>
** $π_{Name}(S ⋈ σ_{Name=M34391}(G))$
** $10^3 + (3 + 20) + 20 ≈ 10^3$ операций
Поиск группы тоже можем ускорить, так как есть индекс по имени группы. Он скорее всего поместится в памяти, оценим его глупину как $2$. К этому нам нужно достать инфомрацию об одной из групп. Итого нашли конкретнуб группу, потом сделаем соединение с помощью индекса по GroupId в студентах и финальная проекция.
* План 5. <var>Groups(Name)</var>, <var>Students(GId)</var>
** $π_{Name}(S ⋈ σ_{Name=M34391}(G))$
==== Результат ====
Начали с $2·10^7$ операций — наиболее '''медленный''' план
Закончили $45$ операций — наиболее '''быстрый''' план
Разница на много порядков. Сократили время чуть ли не в миллион раз. Выбор плана исполнения запроса '''очень сильно''' влияет на скорость работы.
----
[[Файл:Structure_Query.png|430px|thumb|right|Обработка запроса]]
=== Обработка запроса ===
По большому счету sql базы данных отличаются двумя вещами - тотем, как они поддерживают транзакции и тотем, насколько хорошо у них умеет работать планировщик запросов. '''Общий план:'''
* На вход приходит sql.
* Отправляем его в разборщик запросов(парсер). Он на выходе выдаст реляционную алгебру.
* Реляционная алгебра передается в исполнитель запроса, который ее исполняет. Исполнитель запроса взаимодействует с источником данных в тот момент, когда ему понадобились данные для исполнения запросов.
'''Планировщики делятся на две части:'''
==== Перезапись и планировщик ====
Перезапись запроса. Составляет некоторый набор фиксированных правил, которые не зависят от конкретного запроса
==== Преобразование подзапросов ====
Реляционное исчисление преобразуется в реляционную алгебру. Если была запись в реляционном исчислении, то у нее вынесли кванторы и преобразовали в реляционную алгебру на основе подхода. Для любого запроса в терминах реляционного исчисления можно построить запрос в терминах реляционной алгебры.
Начиная с этого момента оперируем '''только реляционной алгеброй'''
* Преобразуются в реляционную алгебру
==== Преобразование соединений ====
Сначала избавляемся от внешних соединений. Внешние соединения — это надстройка над обычными соединениями и более простыми операциями.
*Внешние соединения
**$R_1 ⟗_θ R_2 ⇒ (R_1 ⟕_θ R_2) ∪ (R_1 ⟖_θ R_2)$
**$R_1 ⟕_θ R_2 ⇒ σ_θ(R_1 × R_2) ∪ (R_1 - π_{R_1}(σ_θ(R_1 × R_2)))$
**$R_1 ⟖_θ R_2 ⇒ σ_θ(R_1 × R_2) ∪ (R_2 - π_{R_2}(σ_θ(R_1 × R_2)))$
Избавляемся от декартового произведения сказав, что это просто естественное соединения. При необходимости переименуем совпадающие атрибуты, чтобы они случайно не совпали. В будущем будет считать, что совпадающие атрибуты мы переименовываем автоматически. Можем безболезненно делать, така как переименование атрибутов "бесплатно", т.e. O(1). В рантайме никто не оперирует названиями, есть просто номера колонок. Названия просто преобразуются в индексы. На этом уровне нам переименование ровно ничего не стоит.
*Декартово соединение
**$R_1 × R_2 ⇒ R_1 ⋈ R_2$
=== Унарные операции ===
Мы минимизировали набор операций. У нас остались унарные операции — фильтр и проекция.
==== Повторная фильтрация ====
Если есть два повторных применения фильтрации, то давайте отфильтруем по конъюнкции. Если внутреннее условие очень слабо фильтрует, то в лучшем случае мы ускоримся в два раза.
*Правило
**Повторное применение фильтрации заменяется одинарным
**$σ_{cond_1}(σ_{cond_2}(R)) ⇒ σ_{cond_1 ∧ cond_2}(R)$
*Пример
**$π_{FirstName}(σ_{Name=M34391}(σ_{S.GId=G.GId}(S × G))) ⇒ π_{FirstName}(σ_{Name=M34391 ∧ S.GId=G.GId}(S × G))$
Cразу объединим фильтр связанный с естественным соединением и фильтр по номеру группы в общий фильтр с конъюнкцией.
==== Повторная проекция ====
Если есть несколько проекций, то можно заменить на одну внешнюю проекцию.
*Правило
**Повторное применение проекции заменяется внешней
*Пример
**$π_{FirstName}(π_{FirstName, Name}(S × G)) ⇒ π_{FirstName}(S × G)$
Сразу все спроецируем на имя студента.
==== Проекция и фильтрация ====
Как работать со смесью проекций и фильтраций?
{{Утверждение
|statement=
Фильтрацию всегда можно осуществлять до проекции.
}}
*Правило
**Фильтрация осуществляется до проекции
**$σ_{cond}(π_{A}(R)) ⇒ π_{A}(σ_{cond}(R))$
Обратим внимание, что в обратном порядке мы делать не можем, не можем вытаскивать фильтр из-под проекции, так как фильтр может зависеть от тех столбцов, которые проекция удалит.
*Пример
** $π_{FirstName}(σ_{Name=M34391}(π_{FirstName, Name}(S × G))) ⇒ π_{FirstName}(π_{FirstName, Name}(σ_{Name=M34391}(S × G))) ⇒ π_{FirstName}(σ_{Name=M34391}(S × G))$
Сначала спроецировали, потом отфильтровали и опять спроецировали. Давайте перенесем фильтр во внутрь проекции. Две внешние операции оказываются проекциями. Можем склеить их в одну проекцию с конъюнкцией.
=== Алгебраические свойства операций ===
==== Дистрибутивность операций ====
Аналогично для разности
{{Утверждение
|statement=
$π_A(R_1 - R_2) ⇏ π_A(R_1) - π_A(R_2)$
}}
С естественным соединением все чуть сложнее. Протолкнем в проекцию только те атрибуты, которые были из левого аргумента, вправо только те, которые были из правого. Но зачем мы делаем $A ∪ R_2$, зачем $R_2$? Именно по $R_2$ мы будем соединять, по ним проводилось естественное соединение. Аналогично $A ∪ R_1$. Внешняя проекция нужна для того, чтобы избавиться от тех атрибутов, которые мы потенциально могли добавить в левой и правой части.
{{Утверждение
|statement=
$π_{A}(R_1 ⋈ R_2) ⇒ π_A(π_{(A ∪ R_2) ∩ R_1}(R_1) ⋈ π_{(A ∪ R_1) ∩ R_2}(R_2))$
}}
==== Коммутативность операций ====
За счет коммутативности можем выбирать какая сторона считается левой, а какая правой. Это полезно, потому что можем не делать дублирующиеся методы, когда они не симметричны.
*Коммутативные операции
*Применение коммутативности
**Выбор левой и правой стороны для несимметричных методов исполнения
==== Ассоциативность операций ====
Для ассоциативных операция можем выбирать порядок в котором будет эти ассоциативные операции применять. Мы можем рассматривать не конкретное дерево, которое получилось в результате разбора, а плоский набор отношений и ассоциативные операции между ними, а дальше в каком порядке будет выполнять операции и расставлять скобки зависит уже от нас.
*Ассоциативные операции
==== Замыкание предикатов ====
Можем извлекать дополнительную информацию, используя замыкание предикатов
*Примеры правил
**$a = b ∧ b = c ⇒ a = b ∧ b = c ∧ a = c$
**$a > b ∧ b = c ⇒ a > b ∧ b = c ∧ a > c$
**$a > b ∧ b > c ⇒ a > b ∧ b > c ∧ a > c$
Переразбить условие и запихнуть часть из них под соединение.
*Пример
**$σ_{P_1.p > P_2.p ∧ P_2.p ≥ 60}(P_1 ⋈_{P_1.SId = P_2.SId} P_2) ⇒ σ_{P_1.p > P_2.p ∧ P_2.p ≥ 60 ∧ P_1.p > 60}(P_1 ⋈_{P_1.SId = P_2.SId} P_2) ⇒ σ_{P_1.p > P_2.p}(σ_{p > 60}(P_1) ⋈_{P_1.SId = P_2.SId} σ_{p ≥ 60}(P_2))$
Оценки, которые принадлежат одному и тому же студенту, причем оценка по первому предмету лучше, чем оценка по второму предмету и по второму предмету есть хотя бы 60 баллов. Замкнув предикат получим, что оценка по первому предмету строго больше 60 баллов ( > 60). Теперь есть условие, которое зависит только от первого экземпляра таблицы оценок и условие, зависящее только от второго экземпляра таблицы оценок. Протолкнем их во внутрь соединения. За счет замыкания предикатов получили новое условие, которое можно протолкнуть в один из операндов.
==== КНФ и ДНФ ====
Некоторые базы данных преобразуют условия в дизъюнктивную или конъюнктивную нормальную форму исходя из соображения, что и ту и другую можно исполнять слева направо, пока не найдем первую лож для КНФ или первую истину для ДНФ. При этом можем пересортировать условия в нужном и удобном нам порядке. К примеру более быстрые условия поместить вперед. С другой стороны оптимизатор может более строгие условия, то есть те, которые отсеивают большее количество строк, перемещать вперед.
Превратили все в ассоциативный и коммутативный вид, что позволяет нам произвольным образом переупорядочивать конъюнкты, в случаю КНФ, или дизъюнкты, в случае ДНФ.
К тому же за счет правил более эффективно вычислять.
*Преобразование предикатов
**Конъюнктивная нормальная форма
=== Семантические оптимизации ===
Можем применять знания об ограничениях
Есть схема, в ней есть
Ограничения ключей
Ограничения внешних ключей
Формально можем построить не эквивалентный запрос, который всегда будет давать ровно тот же результат. То есть он будет эквивалентен с учетом тех ограничений, которые у нас есть для базы данных.
==== Семантическая оптимизация ====
**Неэквивалентные запросы
**Тот же результат
В частности, если если нас просят спроецировать на имя студентов естественное соединение студентов и групп и мы знаем, что в $Students$ $GroupId$ является внешним ключом, то мы можем сделать вывод, что это просто проецирование на имя таблички студентов.
*Пример
**$π_{FirstName}(Students ⋈ Groups) ⇒ π_{FirstName}(Students)$, если $Students.GId ⊂ Groups.GId$
Обратим внимание, что без ограничения на ключи данное преобразование корректным не является
==== Пример оптимизации ====
