Основи на съвременните бази данни Предговор
Изтегляне 1.71 Mb.
|
- Навигация на страницата:
- 18.1. Общая схема обработки запроса
- 18.2. Синтактическая оптимизация заявките
- 18.2.1. Простые логические преобразования заявките
- 18.2.2 Преобразования заявките с изменением порядка релационных операций
- 18.2.3 Приведение заявките со вложенными подзапросами к запросам с соединениями
- 18.3. Семантическая оптимизация заявките
- 18.3.1. Преобразования заявките на основе семантической информации
- 18.3.2. Използование семантической информации при оптимизации заявките
- 18.4. Выбор и оценка альтернативных планов изпълнения заявките
- 18.4.1. Генерация планов
- 18.4.2. Оценка стойности плана запроса
- 18.4.3. Более точные оценки
Компилаторы езика SQLЛекция 18. Компилаторы SQL. Проблемы оптимизацииГоворя про оптимизацию заявките в релационных СУБД, обикновено имеют в виду такой способ обработки заявките, когато по начальному представлению запроса путем его преобразований вырабатывается процедурный план его изпълнения, наиболее оптимальный при съществуващих в базе от данни управляющих структурах. Соответствующие преобразования начального представления запроса выполняются специалним компонентом СУБД - оптимизатором, и оптимальность производимого им плана запроса носит условный характер: план оптимален в соответствии с критериями, заложенными в оптимизатор. 18.1. Общая схема обработки запросаМожно представить, что обработка поступившего в систему запроса състои из фаз, изображенных ниже. 
На первой фазе запрос, заданный на езике заявките, подвергается лексическому и синтактическому анализу. При этом вырабатывается его внутреннее представление, отражающее структуру запроса и съдържащее информацию, которая характеризует обекти базы от данни, упомянутые в запросе (отношения, поля и константы). Информация о хранимых в базе от данни обектах выбирается из каталогов базы от данни. Внутреннее представление запроса използуется и преобразуется на следующих стадиях обработки запроса. Форма внутреннего представления должна быть достатъчно удобной за последующих оптимизационных преобразований. На второй фазе запрос во внутреннем представлении подвергается логической оптимизации. Могут применяться различные преобразования, "улучшающие" начальное представление запроса. Среди преобразований могут быть эквивалентные, после проведения които получается внутреннее представление, семантически эквивалентное начальному (например, приведение запроса к някоиой канонической форме), Преобразования могут быть и семантическими: получаемое представление не является семантически эквивалентным начальному, но гарантируется, что резултат изпълнения преобразованного запроса совпадает с резултатом запроса в начальной форме при съблюдении ограничений целостности, съществуващих в базе от данни. После изпълнения второй фазы обработки запроса его внутреннее представление остается непроцедурным, хотя и является в някоиом смысле более эффективным, чем начальное. Третий этап обработки запроса състои в выборе на основе информации, которой располагает оптимизатор, набора альтернативных процедурных планов изпълнения данного запроса в соответствии с его внутреннем представлением, полученным на второй фазе. За каждого плана оценивается предполагаемая стойност изпълнения запроса. При оценках използуется статистическая информация о состоянии базы от данни, достъпная оптимизатору. Из полученных альтернативных планов выбирается наиболее дешевый, и его внутреннее представление теперь соответствует обрабатываемому запросу. На четвертом этапе по внутреннему представлению наиболее оптимального плана изпълнения запроса формируется выполняемое представление плана. Выполняемое представление плана може да бъде програмой в машинных кодах, ако, как в случае System R, система ориентирована на компилацию заявките в машинные коды, или быть машинно-независимым, но более удобным за интерпретации, ако, как в случае INGRES, система ориентирована на интерпретацию заявките. В нашем случае это непринципиально, поскольку четвертая фаза обработки запроса уже не свързана с оптимизацией. Наконец, на пятом этапе обработки запроса происходит его реальное изпълнение. Это либо изпълнение соответствующей подпрограмы, либо извикване интерпретатора с передачей ему за интерпретации выполняемого плана. 18.2. Синтактическая оптимизация заявкитеПри классическом подходе к организации оптимизаторов заявките на этапе логической оптимизации производятся эквивалентные преобразования внутреннего представления запроса, които "улучшают" начальное внутреннее представление в соответствии с фиксированными стратегиями оптимизатора. Характер "улучшений" свързан со спецификой общей организации оптимизатора, в частности, с особенностями процедуры поиска възможных процедурных планов заявките, выполняемой на третьей фазе обработки запроса. Поэтому трудно привести полную характеристику и классификацию методов логической оптимизации. Мы ограничимся несколькими примерами, а также рассмотрим один частный, но важный класс логических преобразований, касающихся сложных заявките, выраженных на езике SQL. 18.2.1. Простые логические преобразования заявкитеОчевидный класс логических преобразований запроса составляют преобразования предикатов, входящих в условие выборки, к каноническому представлению. Имеются в виду предикаты, съдържащие операции сравнения простых значений. Такой предикат имеет вид "аритметиченое выражение op аритметиченое выражение", где "op" - операция сравнения, а аритметичение выражения левой и правой частей в общем случае съдържат имена полей отношений и константы (в езике SQL среди констант могут встречаться и имена переменных объемлющей програмы, значения които становятся известными только при реальном изпълнении запроса). Канонические представления могут быть различными за предикатов разных типов. Ако предикат включает только одно имя поля, то его каноническое представление может, например, иметь вид "имя поля op константное аритметиченое выражение" (эта форма предиката - простой предикат селекции - очень полезна при изпълнении следующего этапа оптимизации). Ако начальное представление предиката имеет вид (a+5)(A op 36 (малыми буквами обозначены имена объемлющих переменных, а большими - имена полей отношений), то каноническим представлением такого предиката може да бъде A op 36/(a+5). Ако предикат включает в точности два имени поля разных отношений (или двух разных вхождений одного отношения), то его каноническое представление может иметь вид "имя поля op аритметиченое выражение", где аритметиченое выражение в правой части включает только константы и второе имя поля (это тоже форма, полезная за изпълнения следующего стъпкаа оптимизации, - предикат соединения; особенно важен случай эквисоединения, когато op - это равенство). Ако в начальном представлении предикат имеет вид 5(A-a(B op b, то его каноническое представление - A op (b+a(B)/5. Наконец, за рассматриваемых предикатов более общего вида имеет смысл приведение предиката к каноническому представлению вида "аритметиченое выражение op константное аритметиченое выражение", где выражения правой и левой частей также приведены к каноническому представлению; например, в выражениях напълно раскрыты скобки и произведено лексикографическое упорядочение. В дальнейшем можно произвести поиск общих аритметичених выражений в разных предикатах запроса. Это оправдано, поскольку при изпълнении запроса вычисление аритметичених выражений будет производиться при выборке каждого очередного кортежа, т.е. потенциально большое число раз. При приведении предикатов к каноническому представлению можно вычислять константные выражения и избавляться от логических отрицаний. Следующий класс логических преобразований свързан с приведением к каноническому виду логического выражения, задающего условие выборки запроса. Как правило, използуются либо дизъюнктивная, либо конъюнктивная нормалные формы. Выбор канонической формы зависит от общей организации оптимизатора. При приведении логического условия к каноническому представлению можно производить поиск общих предикатов (они могут съществува изначально, могут появиться после приведения предикатов к каноническому виду или в процесе нормализации логического условия) и упрощать логическое выражение за счет, например, выявления конъюнкции взаимно противоречащих предикатов. Фрагмент логического выражения 1/4(A>5)AND(A<5)1/4 можно заменить на 1/4FALSE1/4 Възможны и более "умные" упрощения. Например, фрагмент логического выражения 1/4(A>B)AND(B=5)1/4 можно заменить на 1/4(A>5) 1/4 Такие упрощения могут оказаться съществеными за дальнейшей обработки запроса: в запросе с логическим условием первого вида предполагалось соединение отношений; после преобразования запрос уже не требует соединения.
(A JOIN B) WHERE restriction-on-A AND restriction-on-B эквивалентно выражению A WHERE restriction-on-A) JOIN (B WHERE restriction-on-B). Здесь JOIN обозначает релационный оператор естественного соединения отношений; A WHERE restriction - оператор ограничения отношения A в соответствии с предикатом restriction. Хотя немногие релационные системы имеют езики заявките, основанные в чистом виде на релационной алгебре, правила преобразований алгебраических выражений могут быть полезны и в других случаях. Довольно часто релационная алгебра използуется в качестве основы внутреннего представления запроса. Естественно, что после этого можно выполнять и алгебраические преобразования. В частности, съществуват подходы, свързанные с преобразованием к алгебраической форме заявките на езике SQL. Можно выявить две основные побудительные причины преобразований заявките на SQL к алгебраической форме. Первой, на наш взгляд, менее важной причиной може да бъде стремление к използованию релационной алгебры в качестве унифицированного внутреннего интерфейса релационной СУБД. Такой подход разпространен при използовании специализированных машин баз от данни, на основе които реализуются различные интерфейсы достъпа к базам от данни. Интерфейс машины баз от данни должен быть унифицирован (например, быть алгебраическим), а все остальные интерфейсы, включая интерфейс на основе SQL, приводятся к алгебраическому. Второй причиной, особенно важной в контексте проблем оптимизации, является то, что релационная алгебра более проста, чем език SQL. Преобразование запроса к алгебраической форме упрощает дальнейшие действия оптимизатора по выборке оптимальных планов. Вообще говоря, развитый оптимизатор заявките системы, ориентированной на SQL, должен выявить все възможные планы изпълнения любого запроса, но "пространство поиска" этих планов в общем случае очень велико; в каждом конкретном оптимизаторе използуются свои эвристики за сокращения пространства поиска. Некоито, възможно, наиболее оптимальные планы никогато не будут рассматриваться. Разумное преобразование запроса на SQL к алгебраическому представлению сокращает пространство поиска планов изпълнения запроса с гарантией того, что оптимальные планы потеряны не будут. 18.2.3 Приведение заявките со вложенными подзапросами к запросам с соединениямиОсновным отличием езика SQL от езика релационной алгебры является възможность използовать в логическом условии выборки предикаты, съдържащие вложенные подзаявки. Глубина вложенности не ограничивается езиком, т.е., вообще говоря, може да бъде произвольной. Предикаты с вложенными подзапросами при наличии общего синтаксиса могут обладать весьма различной семантикой. Единственным общим за всех възможных семантик вложенных подзаявките алгоритмом изпълнения запроса является вычисление вложенного подзапроса всякий раз при вычислении значения предиката. Поэтому естественно стремиться к такому преобразованию запроса, съдържащего предикаты со вложенными подзапросами, которое сделает семантику подзапроса более явной, предоставив тем самым в дальнейшем оптимизатору възможность выбрать способ изпълнения запроса, наиболее точно соответствующий семантике подзапроса. Ниже Ri обозначает i-е отношение базы от данни; Ck - k-е поле (столбец) отношения. Предикаты, допустимые в запросах езика SQL, можно разбить на следующие четыре группы:
Приведенная классификация является упрощением реальной ситуации в SQL. Не рассматриваются предикаты соединения общего вида, включающие аритметичение выражения с полями более чем двух отношений. Каноническим представлением запроса на n отношениях се нарича запрос, съдържащий n-1 предикат соединения и не съдържащий предикатов со вложенными подзапросами. Фактически, каноническая форма - это алгебраическое представление запроса. Ниже приводятся два примера канонических форм заявките с предикатами разного типа. Соответствующая техника съществует и за других видов предикатов. SELECT Ri.Ck FROM Ri WHERE Ri.Ch IS IN SELECT Rj.Cm FROM Rj WHERE Ri.Cn = Rj.Cp эквивалентно SELECT Ri.Ck FROM Ri, Rj WHERE
эквивалентно SELECT Ri.Ck FROM Ri, Rt WHERE
Разумность таких преобразований обосновывается тем, что оптимизатор получает възможность выбора большего числа способов изпълнения заявките. Часто открывающиеся после преобразований способы изпълнения более эффективны, чем планы, използуемые в традиционном оптимизаторе System R. При използовании в оптимизаторе заявките подобного подхода не обязательно производить формальные преобразования заявките. Оптимизатор должен в большей степени използовать семантику обрабатываемого запроса, а каким образом она будет распознаваться - это вопрос техники. Заметим, что в кратко описанном нами подходе имеются некоито тонкие семантические некоректности. Известны исправленные методы, но они слишком сложны технически, чтобы рассматривать их на наших лекциях. 18.3. Семантическая оптимизация заявкитеРассмотренные преобразования заявките основывались на семантике езика заявките, но в них не използовалась семантика базы от данни, к которой адресуется запрос. Любое преобразование може да бъде произведено независимо от того, какая конкретная база от данни имеется в виду. На самом же деле, при каждой истинно релационной базе от данни хранится и някоиая семантическая информация, определяющая, например, целостность базы от данни. Ако говорить о базах от данни, поддерживаемых System R, то эта информация хранится в системных каталогах базы от данни в виде заот данни ограничений целостности. Поскольку СУБД гарантирует целостность базы от данни, то ограничения целостности можно рассматривать как аксиомы, в окружении които формулируются заявки к базе от данни. 18.3.1. Преобразования заявките на основе семантической информацииВ качестве начальных примеров преобразований заявките на основе семантической информации рассмотрим подходы известных СУБД System R и INGRES к обеспечению работы с базами от данни через представления. Эти преобразования не были ориентированы на оптимизацию заявките, но имеют к ней непосредственное отношение. Представление базы от данни (view) в терминах езиков SQL и QUEL - это именованный каталогизированный запрос, представляющий собой с гледна точка потребителей такой же обект базы от данни, как и отношение. Представления могут използоваться в запросах так же, как и хранимые отношения (с ограничениями на използование их в операторах модификации базы от данни). Семантика представлений требует, чтобы они были точными: в момент изпълнения запроса над представлением получаемая информация должна точно соответствовать текущему состоянию хранимой части базы от данни. Изпълнение запроса над представлением требует его материализации, т.е. вычисления отношения, определяемого запросом, который свързан с представлением. Подход System R и INGRES основан на том, что представления хранятся в каталогах базы от данни во внутренней форме, получаемой после изпълнения грамматического разбора (а также, възможно, логической оптимизации) соответствующего запроса. При обработке запроса над представлением до изпълнения фазы логической оптимизации се извършва слияние внутренних форм запроса и представления. Образуется някоиая новая преобразованная внутренняя форма, и над ней се извършва вся последующая обработка запроса, включая логическую оптимизацию и выбор оптимального плана изпълнения запроса. При этом оптимизатор получает больше информации о данном запросе и может принимать более правильные решения. Приведем простой пример. Пусть представление определено как DEFINE VIEW V (C2) AS SELECT C1 FROM R WHERE C1 > 6. Запрос формулируется следующим образом: SELECT C2 FROM V WHERE C2 < 6. Ако бы запрос компилировался в расчете на явную материализацию представления, был бы выбран способ его изпълнения, основанный на последовательном сканировании V с выбором кортежей, удовлетворяющих условию. Запрос так бы и выполнялся, чтобы в конце концов выдать пустой резултат. При слиянии же внутренних форм запроса и представления мы получили бы внутреннюю форму, эквивалентную запросу SELECT C1 FROM R WHERE C1 < 6 AND C1 >6. Уже на фазе логической оптимизации можно было бы установить, что он эквивалентен запросу SELECT C1 FROM R WHERE FALSE, из чего следовало бы, что резултат запроса пуст. Очевидно, что в ряде случаев этот способ обработки заявките над представлениями базы от данни позволяет добиться более эффективного изпълнения запроса за счет предоставления оптимизатору большей информации. Та же идея лежит и в основе семантической оптимизации заявките: използование при оптимизации запроса семантической информации, хранящейся в базе от данни независимо от данного запроса. Другим примером преобразований заявките, имеющих непосредственное отношение к оптимизации, являются преобразования заявките на модификацию базы от данни за удовлетворения съществуващих в базе от данни ограничений целостности. Этот подход впервые был применен в СУБД INGRES, но използуется и в других системах, например, в System R. Ограничением целостности се нарича сохраняемое в каталогах базы от данни логическое выражение, составленное из предикатов над обектами базы от данни. База от данни находится в целостном состоянии, ако удовлетворяются все заданные ограничения целостности. Ако задан запрос на модификацию базы от данни, включающей ограничения целостности, удовлетворение които требуется при изпълнении любой модификации, то можно добавить соответствующие ограничениям предикаты к логическому условию запроса. Пусть база от данни, характеризующая структуру организации, състои из отношений EMP и DEPT. В отношении EMP регистрируются служащие организации. Схема этого отношения EMP (EMP#, EMPNAME, DEPT#); поле EMP# съдържит уникальный номер служащего, поле EMPNANE - имя служащего, а DEPT# - номер отдела организации, в котором работи данный сътрудник. Отношении DEPT хранит информацию об отделах и имеет схему DEPT (DEPT#, EMPCOUNT), где в поле EMPCOUNT хранится общее число сътрудников данного отдела. Пусть задано ограничение целостности ASSERT B IMMEDIATE ON EMP: EMP.DEPT# = 6. Это ограничение означает запрещение занесения, удаления и модификации кортежей в отношении EMP со значением поля DEPT#, отличным от 6. Пусть обрабатывается запрос на удаление кортежа DELETE EMP WHERE EMPNAME = 'Brown'. Ако при компилации запроса не учитывать наличие ограничения целостности, то коректным способом изпълнения такого запроса будет следующий: последовательно выбирать кортежи, у които значением поля EMPNAME является 'Brown'; проверять удовлетворение очередного кортежа ограничению целостности, и ако проверка удовлетворительна, удалить кортеж. Ако же ограничения целостности учитываются при компилации, то можно слить внутренние формы запроса и соответствующих ограничений целостности, а потом произвести совместную оптимизацию. В нашем случае после слияния образуется внутренняя форма, эквивалентная запросу DELETE EMP WHERE EMPNAME = 'Brown' AND DEPT# = 6. При изпълнении такого запроса не понадобятся дополнительные извикванеы проверок ограничений целостности второго типа, поскольку они все уже включены в логическое условие изпълнения операции удаления. Кроме того, оптимизатор получает большую свободу в выборе способа изпълнения запроса. Например, ако отделы малочисленны, и за отношения EMP поддържася индекс на поле DEPT#, то, възможно, наиболее оптимальным способом изпълнения запроса будет сканирование отношения через индекс по DEPT# с условием DEPT# = 6 с удалением всякого выбираемого таким образом кортежа со значением поля EMPNAME, равным 'Brown'. Тем самым, преобразующие запрос действия, не направленные специально на оптимизацию, могут способствовать более эффективному изпълнению запроса. Эффективность изпълнения запроса удается повысить за счет използования знаний, независимо хранящихся в базе от данни. Рассмотренные примеры показывают, что идея семантической оптимизации в принципе не нова. Имеется и принципиальная разница между рассмотренными выше преобразованиями заявките и теми, които производятся при семантической оптимизации. Основное отличие състои в том, что когато производятся слияния внутренней формы запроса с внутренней формой представления или внутренними формами ограничений целостности, мы обязаны напълно и однозначно използовать внешнюю информацию, независимо от того, будут ли это способствовать оптимизации запроса: условие выборки представления должно быть целиком добавлено через AND к условию выборки запроса; то же относится и к набору логических условий ограничений целостности. Иначе семантика запроса над представлением или оператора модификации базы от данни будет нарушена.
Каждое из полученных внутренних представлений подвергается полной дальнейшей обработке, включая логическую оптимизацию и выбор оптимального плана изпълнения; из полученных планов (все они семантически эквивалентны, т.е. вырабатывают один и тот же резултат) выбирается наиболее дешевый, который и становится реальным планом изпълнения исходного запроса. За разумного применения семантической оптимизации удобно представлять ограничения целостности базы от данни в импликативной форме. Тогда можно добиться более осмысленного порядка преобразований. Пусть, например, в нашей базе от данни о структуре организации отношение EPM расширено полями STATUS и SALARY. Значения поля STATUS характеризуют должность служащего, а поле SALARY - его оклад. Може да бъде наложено ограничение целостности, выражающееся в том, что оклад, превышающий 40.000, може да бъде назначен только начальникам отделов: ASSERT A ON EMP: IF SALARY > 40.000 THEN STATUS = 'Manager'. Предположим, что обрабатывается запрос SELECT EMPNAME, STATUS FROM EMP WHERE SALARY = 20.000. Ако не учитывать импликативного характера ограничения целостности, то по общим правилам будет произведено слияние внутренних представлений запроса и ограничения целостности, которое заведомо ничего не даст. Ако же рассматривать ограничение целостности как правило преобразования, а левую часть импликации как условие применения правила, то слияние производиться и не будет, что в общем случае сэкономит время обработки запроса. Но за запроса SELECT EMPNAME, STATUS FROM EMP WHERE SALARY > 40.000 правило преобразования применимо и приводит к семантически эквивалентному запросу SELECT EMPNAME, STATUS FROM EMP WHERE STATUS = 'Manager', изпълнение которого може да бъде более эффективным. После преобразования запроса в соответствии с някоиым правилом к полученному представлению может оказаться применимым другое правило и т.н. Възможно появление циклов преобразований. Проблема построения полного набора семантически эквивалентных представлений запроса на основе заданного набора правил в общем случае является весьма сложной. Точное решение этой проблемы может потребовать затрат, соизмеримых с затратами на изпълнение запроса по наиболее оптимальному плану. Поэтому, вообще говоря, необходимо применение эвристических алгоритмов, сокращающих пространство поиска, т.е. задающих условие прекращения генерации новых представлений. Эвристики основываются на минимизации взвешенной суммы стойностей семантической оптимизации и изпълнения запроса. Примером грубой эвристики може да бъде следующий: оптимизация се извършва до тех пор, пока затраты на нее не превзойдут оценочную стойност наиболее эффективного из всех найденных планов изпълнения запроса.
Процедурным представлением или планом изпълнения запроса се нарича такое его представление, в котором детализирован порядок изпълнения операций достъпа к базе от данни физического уровня. Как правило, в релационных СУБД выделяется подсистема управления данными на физическом уровне. В System R, такая подсистема се нарича RSS (Relational Storage System) и обеспечивает простой интерфейс, позволяющий последовательно преглежда кортежи отношений, удовлетворяющие заданным условиям на значения полей, с използованием индексов или простым сканированием страниц базы от данни. Кроме того, RSS позволяет производить отсортированные временные файлы и заносить, удалять и модифицировать индивидуальные кортежи. Аналогичные подсистемы явно или неявно выделяются во всех подобных СУБД. Естественно, что до изпълнения запроса необходимо выработать его процедурное представление. Поскольку оно, вообще говоря, выбирается неоднозначно, необходимо выбрать среди альтернативных планов запроса один в соответствии с някоиыми критериями. Как правило, критерием выбора плана изпълнения запроса является минимизация стойности изпълнения. Тем самым, при обработке запроса на стадии, следующей за логической оптимизацией, решаются две задачи. Первая задача: исходя из внутреннего представления запроса и информации, характеризующей управляющие структуры базы от данни (например, индекси), выбрать набор потенциально възможных планов изпълнения данного запроса. Вторая задача: оценить стойност изпълнения запроса в соответствии с каждым альтернативным планом и выбрать план с наименьшей стойностю. 18.4.1. Генерация плановПри традиционном подходе к организации оптимизаторов обе задачи решаются на основе фиксированных встроенных в оптимизатор алгоритмов. Оптимизатор може да бъде рассчитан на то, что ограничение любого отношения в соответствии с заданным предикатом може да бъде изпълнено путем някоиого последовательного просмотра отношения. Так, запрос SELECT EMPNAME FROM EMP WHERE DEPT# = 6 AND SALARY > 15.000 может выполняться последовательным сканированием отношения EMP с выбором кортежей с DEPT# = 6 и SALARY > 15.000; сканированием отношения через индекс I1, определенный на поле DEPT#, с условием достъпа к индексу DEPT# = 6 и условием выборки кортежа SALARY > 15.000; наконец, сканированием отношения через индекс I2, определенный на поле SALARY, с условием достъпа к индексу SALARY > 15.000 и условием выборки кортежа DEPT# = 6. Аналогично, фиксированы и стратегии изпълнения более сложных операций - релационных соединений отношений, вычисления агрегатных функций на группах кортежей отношения и т.н. Например, в System R за (экви)соединения двух отношений използуются две основные стратегии: метод вложенных циклов и метод сортировок со слияниями. Компонент оптимизатора, генерирующий выполняемые планы заявките, имеет достатъчно сложную организацию; генерация плана изпълнения сложного запроса - это многоэтапный процес, в ходе которого учитываются свойства создаваемых при изпълнении запроса по данному плану временных обектов базы от данни. Например, пусть запрос задан над тремя отношениями и в нем имеются два предиката соединения: SELECT R1.C1, R2.C2, R3.C3 FROM R1, R2, R3 WHERE
Тогда, ако в плане запроса выбирается порядок изпълнения соединений сначала R1 с R2, а затем полученного временного отношения - с R3, и при этом за изпълнения первого соединения выбирается метод сортировок со слиянием, то временное отношение будет заведомо отсортировано по C5, и одна сортировка не потребуется, ако и второе соединение будет выполняться тем же методом. Компонент оптимизатора, ведающий порождением множества альтернативных планов изпълнения запроса, базируется на стратегиях декомпозиции запроса на елементарные составляющие и стратегиях изпълнения елементарных составляющих. Первая группа стратегий определяет пространство поиска оптимального плана изпълнения запроса, вторая направлена на то, чтобы в этом пространстве действительно находились эффективные планы изпълнения запроса. Ключом к обеспечению эффективного изпълнения сложного запроса является наличие эффективных стратегий изпълнения елементарных составляющих. Это очень важный вопрос, но здесь мы его не касаемся: оптимизатор заявките пользуется заданными стратегиями. Рассмотрим более актуальную за оптимизатора проблему - обоснованный выбор плана изпълнения запроса из множества альтернативных планов.
Следуя принятой терминологии, мы будем говорить о стойности плана изпълнения запроса, определяемой ресурсами процесора и устройств внешней памети, които расходуются при изпълнении запроса. В традиционных релационных СУБД выделяется подсистема управления достъпом к данным на внешней памети (RSS в System R). Данные на внешней памети традиционно хранятся в блокированном виде; база от данни занимает някоиый набор блоков одного или нескольких дисковых томов. Предполагается, что средства достъпа к блокам внешней памети порождают несравненно меньшие накладные расходы. Как правило, подсистема управления достъпом к данным на внешней памети осъществляет буферизацию блоков базы от данни в оперативной памети. Всеки блок базы от данни, прочитанный в оперативную паметь за изпълнения запроса, сохраняется в одном из буферов буферного пула СУБД, пока не будет вытеснен из него другим блоком базы от данни. Эта особенность СУБД съществена за повышения общей эффективности системы, но не учитывается (за исключением частного, но важного случая) при оценках стойностей планов изпълнения запроса. В любом случае компонент стойности изпълнения запроса, свързанный с ресурсами устройств внешней памети, монотонно зависит от числа блоков внешней памети, достъп к которым потребуется при изпълнении запроса. С другой стороны, число блоков внешней памети, достъп к которым требуется при изпълнении запроса, монотонно зависит от числа кортежей, затрагиваемых запросом. Из этого следует важность показателя предиката ограничения, характеризующего долю кортежей отношения, които удовлетворяют данному предикату, и называемого степенью селективности предиката. Степени селективности простых предикатов вида R.C op const, где R.C задает имя поля отношения базы от данни, op - операция сравнения (=, !=, >, <, >=, <=), а const - константа, являются основой за оценок стойности планов запроса. Точность оценок степеней селективности определяет точность общих оценок и правильность выбора оптимального плана запроса. Степень селективности предиката R.C op const зависит от вида операции сравнения, значения константы и распределения значений поля C отношения R в базе от данни. Первые два параметра селективности могут быть известны при проведении оценок, но истинные распределения значений полей отношений, как правило, неизвестны. Съществует ряд подходов к приближенным определениям распределений на основе статистической информации. Далее мы рассмотрим наиболее интересные из них. Ако известна степень селективности предиката ограничения отношения, то тем самым известна и мощность результирующего отношения (обикновено мощности хранимых отношений известны при обработке запроса). Но в оценочных формулах учитывается необходимое за изпълнения запроса число обменов с внешней паметью. Конечно, число кортежей является верхней оценкой требуемого числа обменов, но эта оценка може да бъде очень завышенной. Все зависит от распределения кортежей по блокам внешней памети. В ряде случаев можно получить более точную оценку числа блоков. Наконец, за сложных заявките, включающих, например, соединения более двух отношений, требуется оценивать размеры возникающих в процесе изпълнения запроса промежуточных отношений. Чтобы оценить мощность резултата соединения двух отношений, вообще говоря, необходимо знать степень селективности предиката соединения по отношению к прямому произведению отношений-операндов. В общем случае степень селективности такого предиката невъзможно определить на основе простой статистической информации. Обикновено применяются достатъчно грубые эвристические оценки, хотя предлагаются и подходы, обеспечивающие большую точность. Подход System R базируется на двух основных предположениях о распределениях значений полей отношений: предполагается, что значения полей всех отношений базы от данни распределены равномерно и что значения любых двух полей распределены независимо. Первое предположение позволяет оценивать селективность простых предикатов на основе скудной статистической информации о базе от данни. На втором предположении основываются оценки числа блоков, в които располагается известное количество кортежей. Эти два предположения являются предметом критики System R. Они сделаны исключительно в целях упрощения оптимизатора и не могут быть теоретически обоснованы. Можно привести примеры баз от данни, за които эти предположения не оправданы. В этих случаях оценки оптимизатора System R будут неверны. В каталогах базы от данни за каждого отношения R сохраняется число кортежей в данном отношении (T) и число блоков внешней памети, в които располагаются кортежи отношения (N); за каждого поля C отношения хранится число различных значений этого поля (CD), минимальное хранимое значение этого поля (CMin) и максимальное значение (CMax). При наличии такой информации с учетом первого базового предположения степени селективности простых предикатов вычисляется просто (и точно, ако распределение на самом деле равномерно). Пусть SEL (P) - степень селективности предиката P. Тогда SEL (R.C = const) = CD / (CMax - CMin) (при равномерном распределении степень селективности такого предиката не зависит от значения константы). SEL (R.C > const) = (CMax - const) / (CMax - CMin) и т.н. При оценках числа блоков, в които могут располагаться кортежи, удовлетворяющие предикату R.C op const, различаются случаи кластеризованности или некластеризованности отношения по полю C. Эти оценки имеют смысл только при рассмотрении варианта сканирования отношения с използованием индекса на поле C. При просмотре отношения без използования индекса понадобится всегда обратиться ровно к N блокам внешней памети. Предположения о равномерности распределений значений атрибутов отношений позволяват достатъчно просто оценивать и мощности отношений, являющихся резултатами двухместных релационных и теоретико-множественных операций над отношениями. Оценки селективности предикатов използуются и за оценки затрат ресурсов процесора. Предполагается, что основная часть процесорной обработки се извършва в RSS. Поэтому процесорные затраты измеряются числом обращений к RSS, которое соответствует числу кортежей, получаемых при сканировании хранимого или временного отношения, т.е. селективностью логического выражения, состоящего из простых предикатов (условие выборки уровня RSS). Предположения о равномерности и независимости значений разных полей отношения позволяват легко оценить селективность логического выражения, составленного из простых предикатов, при известных их степенях селективности. На самом деле в System R не оценивается селективность предикатов в чистом виде. Оценки оптимизатора основываются на фиксированном наборе елементарных оценочных формул, опирающихся на статистическую информацию о базе от данни. Каждая формула соответствует някоиому елементарному действию системы; изпълнение любого запроса състои в комбинации някоиых елементарных действий. Примерами елементарных действий могут быть изпълнение ограничения отношения путем его сканирования через кластеризованный индекс, сортировка отношения, соединение двух ранее отсортированных отношений и т.н. Общая оценка плана изпълнения запроса се извършва в итерационном процесе, начиная с оценок елементарных операций над хранимыми отношениями.
При отказе от предположения о равномерности распределения значений поля отношения необходимо уметь установить реальное распределение значений. Съществует два базовых подхода к оценкам распределения значений поля отношения: параметрический и основанный на методе сигнатур. Подход System R является тривиальным частным случаем метода параметрической оценки распределения - любое распределение оценивается как равномерное. В более развитом подходе было предложено използовать за оценки реального распределения значений поля отношения серию распределений Пирсона, в которую входят распределения от равномерного до нормалного. Распределение выбирается из серии путем вычисления нескольких параметров на основе выборок реально встречающихся значений. Примеры практического применения этого подхода нам неизвестны. Метод оценки распределения на основе сигнатур в целом можно описать следующим образом. Область значений поля разбивается на няколко интервалов. За каждого интервала някоиым образом устанавливается число значений поля, попадающих в этот интервал. Внутри интервала значения считаются разпределеными по някоиому фиксированному закону (как правило, принимается равномерное приближение). Рассмотрим два альтернативных подхода, свързанных с сигнатурным описанием распределений. При традиционном подходе область значений поля разбивается на N интервалов равного размера, и за каждого интервала подсчитывается число значений полей из кортежей данного отношения, попадающих в интервал. Предположим, что EMP расширено еще одним полем AGE - возраст сътрудника. Пусть всего в организации работи 60 сътрудников в возрасте от 10 до 60 лет. Тогда гистограмма, изображающая распределение значений поля AGE может иметь вид, показанный ниже на рисунке. Гистограмма построена исходя из разбиения диапазона значений поля AGE на 10 интервалов. 
Рассмотрим, как можно оценивать селективность простых предикатов, задаваемых на поле AGE, с използованием такой гистограммы. Пусть в интервал значений AGE Si попадает Ki значений. Тогда SEL (EMP.AGE = const), ако значение константы попадает в интервал значений Si, можно оценить следующим образом: 0 <= SEL (EMP.AGE) <= Ki/T (T - общее число кортежей в отношении EMP). Отсюда средняя оценка степени селективности предиката - Ki / (2 ( T). Например, SEL (AGE = 29) оценивается в 40/200 = 0.2, а SEL (AGE = 16) оценивается в 5/200 = 0.025. Это, конечно, съществено более точные оценки, чем те, които можно получить, исходя из предположений о равномерности распределений. Но не так хорошо обстоят дела с оценками селективности простых предикатов с неравенствами. Например, пусть требуется оценить степень селективности предиката EMP.AGE < const. Ако значение константы попадает в интервал Si, и SUMi - суммарное количество значений AGE, попадающих в интервалы S1, S2, ..., Si, то SUMi-1 / T <= SEL (AGE < const) <= SUMi / T. Тогда средняя оценка степени селективности (SUMi-1 + SUMi) / (2 ( T), и ошибка оценки может достигать половины веса подобласти, в которую попадает значение константы предиката. Самое неприятное, что ошибка оценки зависит от значения константы и тем больше, чем больше значений поля съдържится в соответствующем интервале гистограммы. Например, SEL (AGE < 29) оценивается как 46/100 <= SEL (AGE < 29) <= 86/100, откуда оценка степени селективности (46 + 86) / 200 = 0.66; при этом ошибка оценки может достигать 0.2. В то же время SEL (AGE < 49) оценивается съществено более точно. За устранения этого дефекта был предложен другой подход к описанию распределений значений поля отношения. Идея подхода състои в том, что множество значений поля разбивается на интервалы вообще говоря разного размера, чтобы в всеки интервал (кроме, вообще говоря, последнего) попадало одинаковое число значений поля. Количество интервалов выбирается исходя из ограничений по памети, и чем оно больше, тем точнее получаемые оценки. При разбиении области значений на десять интервалов получаемая псевдогистограммная картина распределений значений поля AGE показана на рисунке ниже. 
Область значений поля AGE отношения EMP разбита на 10 интервалов таким образом, что в всеки интервал попадает ровно по 10 значений поля AGE. Интервалы имеют разные размеры. Граничные значения интервалов показаны над вертикальными линиями. В псевдогистограмме допустимы интервалы, правая и левая граница които совпадают, например, интервал (28,28). Он образовался по причине наличия в отношении EMP большого (большего десяти) числа кортежей со значением AGE = 28. При използовании "псевдогистограммы" ошибки в оценках степеней селективности предикатов с операцией, отличной от равенства, уменьшаются. Размер ошибки не зависит от значения константы и уменьшается при увеличении числа интервалов. Недостатком метода псевдогистограмм по сравнению с методом гистограмм является необходимость сортировки отношения по значениям поля за построения псевдогистограммы распределений значений этого поля. Известен подход, позволяющий получить достоверную псевдогистограмму без необходимости сортировки всего отношения. Подход основывается на статистике Колмогорова, из которой применительно к случаю релационных баз от данни следует, что ако из отношения выбирается образец из 1064 кортежей, и b - доля кортежей в образце со значениями поля C < V, то с достоверностью 99% доля кортежей во всем отношении со значениями поля C < V находится в интервале [b-0.05, b+0.05]. При уменьшении мощности образца достоверность, естественно, уменьшается.
Каталог: tadmin -> upload -> storage storage -> Литература на факта. Аналитизъм. Интерпретативни стратегии. Въпроси и задачи storage -> Лекция №2 Същност на цифровите изображения Въпрос. Основни положения от теория на сигналите storage -> Лекция 5 система за вторична радиолокация storage -> Толерантност и етничност в медийния дискурс storage -> Ethnicity and tolerance in media discourse revisited Desislava St. Cheshmedzhieva-Stoycheva abstract storage -> Тест №1 Отбележете невярното твърдение за подчертаните думи storage -> Лекции по Въведение в статистиката storage -> Търсене на живот във вселената увод storage -> Еп. Константинови четения – 2010 г някои аспекти на концептуализация на богатството в руски и турски език Изтегляне 1.71 Mb. Сподели с приятели:
|