1632
правки
Изменения
м
От выбора плана '''сильно''' зависит производительность
Чуть ли не на уровне парсера у нас реляционное Реляционное исчисление преобразуется в реляционную алгебру. Если была запись в реляционном исчислении, то у нее вынесли кванторы и преобразовали в реляционную алгебру на основе подхода . Для любого запроса в терминах реляционного исчисления можно построить запрос в терминах реляционной алгебры.
Первое что происходит - Сначала избавляемся от внешних соединений. Внешние соединения - — это надстройка над обычными соединениями и более простыми операциями.
Давайте сразу объединим фильтр связанный с естественным соединением и фильтр по номеру группы в общий фильтр с конъюнкцией.
Сразу все спроецируем на имя студента.
Сначала спроецировалиОбратим внимание, потом отфильтровали и опять спроецировали. Давайте перенесем что в обратном порядке мы делать не можем, не можем вытаскивать фильтр во внутрь из-под проекции, так как фильтр может зависеть от тех столбцов, которые проекция удалит. Две внешние операции оказываются проекциями. Можем склеить их в одну проекцию с конъюнкцией.
Обратим внимание, что в обратном порядке мы делать не можем, не можем вытаскивать фильтр из-под проекции, так как фильтр может зависеть от тех столбцов, которые проекция удалит.
1) Мы можем пользовать стандартными алгебраическими трюками. Предположим хотим отфильтровать объединение. Можем отфильтровать первый аргумент, потом второй, а потом объединить.
2) Аналогично для пересечения'''Фильтрация'''
3Мы можем пользовать стандартными алгебраическими трюками. Предположим хотим отфильтровать объединение. Можем отфильтровать первый аргумент, потом второй, а потом объединить.{{Утверждение|statement=$σ_{cond}(R_1 ∪ R_2) Аналогично для разности⇒ σ_{cond}(R_1) ∪ σ_{cond}(R_2)$}}
4) Естественное соединение. Если можем разделить условие на две части, одна из которых относится проверяет атрибуты только из левого атрибута, а вторая только из правого, то мы можем протолкнуть этот фильтр отдельно в левый и правый аргумент, а потом соединить только Аналогично для строк, удовлетворяющим своим половинкам фильтра. пересечения*Фильтрация** $σ_{cond}(R_1 ∪ R_2) ⇒ σ_{cond}(R_1) ∪ σ_{cond}(R_2)$Утверждение** $σ_{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)$** $σ_{cond_1 ∧ cond_2}(R_1 ⋈ R_2) ⇒ σ_{cond_1}(R_1) ⋈ σ_{cond_2}(R_2)$
1Аналогично для разности{{Утверждение|statement=$σ_{cond}(R_1 - R_2) Можем безопасно проекцировать результат объединения⇒ σ_{cond}(R_1) - σ_{cond}(R_2)$}}
2) Не Естественное соединение. Если можем безопасно проецировать результат пересеченияразделить условие на две части, потому что слева могли быть кортежиодна из которых относится проверяет атрибуты только из левого атрибута, а вторая только из правого, которые кроме атрибута $A$ содержат еще какой-то дополнительный атрибут $X$. Они различались, вошли мы можем протолкнуть этот фильтр отдельно в пересечение левый и уже правый аргумент, а потом мы их спроецируемсоединить только для строк, удовлетворяющим своим половинкам фильтра. Если же сначала сделать проекцию, то этот атрибут Аналогично для разности{{Утверждение|statement=$X$ теряется и два кортежа с одинаковым атрибутом $A$ но разным атрибутом $Xσ_{cond_1 ∧ cond_2}(R_1 ⋈ R_2) ⇒ σ_{cond_1}(R_1) ⋈ σ_{cond_2}(R_2)$ для нас станут неразличимы.}} '''Проекция'''
3Можем безопасно проекцировать результат объединения{{Утверждение|statement=$π_A(R_1 ∪ R_2) Аналогично для разности⇒ π_A(R_1) ∪ π_A(R_2)$}}
4) С естественным соединением все чуть сложнее. Протолкнем в проекцию только те атрибутыНе можем безопасно проецировать результат пересечения, которые были из левого аргумента, вправо только тепотому что слева могли быть кортежи, которые были из правого. Но зачем мы делаем кроме атрибута $A ∪ R_2$содержат еще какой-то дополнительный атрибут $X$. Они различались, зачем вошли в пересечение и уже потом мы их спроецируем. Если же сначала сделать проекцию, то этот атрибут $R_2X$? Именно по теряется и два кортежа с одинаковым атрибутом $R_2A$ мы будем соединять, по ним проводилось естественное соединение. Аналогично но разным атрибутом $A ∪ R_1X$. Внешняя проекция нужна для того, чтобы избавиться от тех атрибутов, которые мы потенциально могли добавить в левой и правой частинас станут неразличимы. . {{Утверждение*Проекция|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(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))$
За счет коммутативности можем выбирать какая сторона считается левой, а какая правой. Это полезно, потому что можем не делать дублирующиеся методы, когда они не симметричны.
Для ассоциативных операция можем выбирать порядок в котором будет эти ассоциативные операции применять. Мы можем рассматривать не конкретное дерево, которое получилось в результате разбора, а плоский набор отношений и ассоциативные операции между ними, а дальше в каком порядке будет выполнять операции и расставлять скобки зависит уже от нас.
Оценки, которые пренадлежат отдному и тому же студенту, причем оценка по первому предмету лучше, чем оценка по второму предмету и по второму предмету есть хотя бы 60 баллов. Замкнув предикат получим, что оценка по первому предмету строго больше 60 баллов ( > 60). Теперь есть условие, которое зависит только от первого экземпляра таблицы оценок и условие, зависящее только от второго экземпляра таблицы оценок. Протолкнем их во внутрь соединения. За счет замыкания предикатов получили новое условие, которое можно протолкнуть в один из операндов.
rollbackEdits.php mass rollback
== Обработка запроса ==
От выбора плана '''сильно''' зависит производительность
=== Мотивирующий пример ===
==== Пример базы данных: ====
Пусть у нас есть база данных Университет.
** $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))$
Закончили $45$ операций — наиболее '''быстрый''' план
Разница на много порядков. Сократили время чуть ли не в миллион раз. Выбор плана исполнения запроса очень-'''очень сильно ''' влияет на скорость работы.
----
[[Файл:Structure_Query.png|430px|thumb|right|Обработка запроса]]
=== Обработка запроса ===
По большому счету sql базы данных отличаются двумя вещами - тотем, как они поддерживают транзакции и тотем, насколько хорошо у них умеет работать планировщик запросов. '''Общий план:'''
* На вход приходит sql.
* Отправляем его в разборщик запросов(парсер). Он на выходе выдаст реляционную алгебру.
* Реляционная алгебра передается в исполнитель запроса, который ее исполняет. Исполнитель запроса взаимодействует с источником данных в тот момент, когда ему понадобились данные для исполнения запросов.
'''Планировщики делятся на две части:'''
==== Перезапись и планировщик ====
Перезапись запроса. Составляет некоторый набор фиксированных правил, которые не зависят от конкретного запроса
==== Преобразование подзапросов ====
Начиная с этого момента оперируем '''только реляционной алгеброй'''
==== Преобразование соединений ====
*Внешние соединения
**$R_1 ⟗_θ R_2 ⇒ (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разу объединим фильтр связанный с естественным соединением и фильтр по номеру группы в общий фильтр с конъюнкцией.
==== Повторная проекция ====
Если есть несколько проекций, то можно заменить на одну внешнюю проекцию.
**$π_{A}(π_{B}(R)) ⇒ π_{A}(R)$
*Пример
**$π_{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))$
}}
==== Коммутативность операций ====
За счет коммутативности можем выбирать какая сторона считается левой, а какая правой. Это полезно, потому что можем не делать дублирующиеся методы, когда они не симметричны.
*Коммутативные операции
**$\div$, $⋇$
*Применение коммутативности
** Выбор левой и правой стороны для несимметричных методов исполнения
==== Ассоциативность операций ====
Для ассоциативных операция можем выбирать порядок в котором будет эти ассоциативные операции применять. Мы можем рассматривать не конкретное дерево, которое получилось в результате разбора, а плоский набор отношений и ассоциативные операции между ними, а дальше в каком порядке будет выполнять операции и расставлять скобки зависит уже от нас.
*Ассоциативные операции
**$\div$, $⋇$
*Применение ассоциативности
**Выбор порядка выполнения операций
**$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$
