Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Отличие от методов NLJ и SMJ⇐ ПредыдущаяСтр 11 из 11
Метод хешированного соединения имеет важную особенность. В методах NLJ или SMJ соединяемые таблицы должны уже храниться на сервере перед выполнением соединения. А в этом методе соединение таблиц может выполняться асинхронно, по мере поступления записей с других серверов. На серверах 1 и 2 выполняются подзапросы, а на сервере 0 выполняется соединение. Предположим, с сервера 2 на сервер 0 поступила очередная запись из таблицы S. При этом СУБД на сервере 0 выполняет следующие действия:
Лекция №14 - Оценки (продолжение) Оптимизация SQL-запросов Физический план Методы соединения таблиц Число кортежей, блоков и мощности атрибутов в соединениях Справедливы для NLJ, SMJ и HJ. 1) количество кортежей в соединении: T (Q 1⋈ Q 2)= T (Q 1)⋅ T (Q 2) max (I (Q 1, a), I (Q 2, a)) 2) числов блоков: B (Q 1⋈ Q 2)=⌈ T (Q 1⋈ Q 2) JOIN ⌉ - верхние неполные квадратные скобки означают округление с избытком; 3) мощности атрибутов: · атрибутов (a) в результирующей таблице: I (Q 1⋈ Q 2, a)= min (I (Q 1, a), I (Q 2, a)) · остальных атрибутов (b): два варианта: · I (Q 1⋈ Q 2, b)= min (T (Q 1⋈ Q 2, I (Q 1, b)), если b - атрибут таблицы Q 1; · I (Q 1⋈ Q 2, b)= min (T (Q 1⋈ Q 2, I (Q 2, b)), если b - атрибут таблицы Q 2. Алгоритмы для поиска физического плана Алгоритмы описываются на псевдоязыке с заимствованиями из C++:
// камент
структура.поле Алгоритм поиска физического плана с минимальной стоимостью (для левостороннего дерева) Вход: логический план выполнения запроса с таблицами R 1.. R n (декартово соединение таблиц). Выход: квазиоптимальный (потому что рассматриваем левосторонние деревья) план выполнения запроса. @НАЧАЛО АЛГОРИТМА ДЛЯ i =1, n AccessPlan (R i); // определение параметров подзапроса Q i =Π A i (Σ f i (R i)). КОНЕЦ ДЛЯ // поиск оптимального плана ДЛЯ i =2, n ДЛЯ всех подмножеств P ⊂ Q 1.. Q n, // для i =2 // P =(Q 1, Q 2), P =(Q 2, Q 3), P =(Q 1, Q 3) // для i =3 // P =(Q 1, Q 2, Q 3) и так же все варианты комбинаций ДЛЯ всех таблиц Q j ∈ P
JoinPlan (P − Q j, Q j) // (P − Q j)⋈ Q j КОНЕЦ ДЛЯ КОНЕЦ ДЛЯ КОНЕЦ ДЛЯ // вывод оптимального плана OptPlanReturn (Q 1.. Q n) @КОНЕЦ АЛГОРИТМА Массив структур Процедуры из алгоритма выше:
Процедуры алгоритма работают с массивом структур. Формат экземпляра структуры:
W: если мощность W >1, то W ⊂ Q i, W = X ⋃ Y; если мощность W =1, то W - это имя таблицы {Q_i}}}. X: X ⊂ Q i, которые были использованы в качестве левого аргумента соединения. Y: имя таблицы Q i, которая была использована в качестве правого аргумента соединения. Если мощность W =1, то X и Y пустые. Z: если W >1, Z - текущая стоимость выполнения плана, включающая стоимость выполнения подзапросов и промежуточных соединений; если W =1, Z - оценка времени выполнения(?) Q i. ZIO: составляющая Z, касающаяся ввода/вывода. V: опции. Включает в себя: 1) число записей: · если мощность W >1, то T (W) - число прогнозируемых записей; · если мощность W =1, то T (Q i) - оценка числа записей в подзапросе; 2) B (W) - прогнозируемое число блоков; 3) I (W, A i) - мощности атрибутов, по которым было выполнено или выполняется соединение; 4) идентификатор: · если мощность W >1, то k - идентификатор метода соединения таблиц; · если мощность W =1, то k - идентификатор метода выбора записей из исходных таблиц. AccessPlan() Вход: R i - имя исходной таблицы. Выход: str [ i ] - заполненный экземпляр структуры (описанной выше). @НАЧАЛО АЛГОРИТМА // оценка стоимости выбора записей из R i для различных методов // j =1 - TableScan // j =2 - IndexScan ДЛЯ i =1,2 C j = C CPU + C I / O // для разных j разные формулы из прошлых лекций КОНЕЦ ДЛЯ // определение оптимального метода выбора записей из R i С= min (C 1, C 2) // здесь C = C k // заполнение экземпляра str [ i ] str [ i ]= { Q i, ∅, ∅ // W, X, Y C, C I / O k // Z, ZIO T (Q i), B (Q i), min (T (Q i), I (R i, A i)), k // V } @ КОНЕЦ АЛГОРИТМА JoinPlan() Вход: R =(P − Q j), S = Q. Выход: str [ n ]. @НАЧАЛО АЛГОРИТМА 1) // поиск в массиве структур str [] номеров экземпляров m 1 и m 2, для которых str [ m 1]. W = R и str [ m 2]. W = S // оценка стоимости соединения для различных методов // если i =1, то NLJ // если i =2, то SMJ // если i =3, то HJ // k - выбор оптимального из этих трёх 2) ДЛЯ i =1,3 C i = C CPU i + C I / O i // для разных i разные формулы из предыдущих лекций
КОНЕЦ ДЛЯ C = min (C 1, C 2) // стоимость соединения R и S C = str [ m 1]. Z + str [ m 2]. Z + C 3) // поиск str [ n ]. W = P // а) если такого экземпляра не существует, то заполнить очередной пустой экземпляр n. // б) если такой экземпляр найден, то сравнить стоимость выполнения плана. И если str [ n ]. Z > C, то перезаписать экземпляр n. str [ n ]= { P, R, S // W, X, Y C, C I / O k // Z, ZIO T (P), B (P), I (P, A i) i, k // V } @ КОНЕЦ АЛГОРИТМА OptPlanReturn() Вход: список таблиц Q i = Q 1.. Q n Выход: вывод оптимального плана. @НАЧАЛО АЛГОРИТМА 1) // поиск в массиме структур str [] экземпляра, который str [ i ]. W = Q печать(Q, " = ", str [ i ]. X, " ⋈ ", str [ y ]. Y, " метод ", str [ i ]. V. k) 2) // если поле str [ i ]. X пусто, то выйти из алгоритма // иначе рекурсивно вызываем сами себя, OptPlanReturn (str [ i ]. X) // вывод оптимального плана для левого аргумента соединения 3) OptPlanReturn (str [ i ]. Y) // вывод метода выбора записей из правого аргумента соединения @КОНЕЦ АЛГОРИТМА
Лекция №15 - Пример оценки Оптимизация SQL-запросов Методы соединения таблиц Алгоритмы для поиска физического плана Пример оценки физического плана Исходные данные: 1) количество записей в таблице T (R 1) = 10000, количество записей в таблице T (R 2) = 100000; 2) количество записей в одном блоке таблицы L (R 1)= L (R 2) = 100, количество записей в соединении L JOIN = 1000; 3) количество записей в блоке индекса код_пользователя {{Формула|f=L} = 200, количество записей в блоке индекса номер_счёта {{Формула|f=L} = 200; Примечание: записи исходных таблиц могут читаться в сортированном виде по своим индексированным атрибутам. Записи в таблице R 1 сгруппированы по атрибуту код_пользователя (кластеризованный индекс), а в таблице R 2 не сгруппированы. 4) мощность атрибутов:
5) тут почему-то пусто 6) b = 10, C COMP = C MOVE = C filter =0.01 мс, C B =10 мс. Для построение оптимального физического плана используется алгоритм динамического программирования (из предыдущей лекции). Алгоритм: 1) AccessPlan а) R 1 - таблица пользователи; j =1, чтение всей таблицы C 1= C CPU 1+ C I / O 1= T (R 1)⋅ C filter + B (R 1)⋅ C B =10000⋅0.01+10000100⋅10=1100 мс j =2 - индекс по атрибуту код_пользователя C 2= C CPU 2+ C I / O 2= T (R 1)⋅ KI (R 1, a)⋅ C filter + B (Index (a))⋅ kI (R 1, a)⋅ C b + B (R 2)⋅ kI (R 1, a)= =10000⋅15000⋅0.01+(10000/200)⋅15000⋅10+10000/100⋅15000⋅10=0.02+0.3=0.32 мс С= min (С1,С2)=0.32 мс С I / O = C I / O 2=0.3 мс T (Q 1)= T (R 2)⋅ P код_пользователя=3= T (R 2)⋅ kI (R 1, a)=10000⋅1/5000=2 B (Q 1)=⌈ T (Q 1) L (R 1)⋅10⌉=⌈2100⋅10⌉=1 str [1]={{ Q 1},∅,∅,0.32,0.3,{2,1,{2},2}} б) R 2 - таблица счёт. j =1 C 1=100000⋅0.01+100000100⋅10=11000 мс j =2 C = C 1=11000 мс C I / O = C I / O 1=10000 мс T (Q 2)= T (R 2)⋅ P R 2.остаток>1500=100000⋅1/3=33000, вероятность принята равной 1/3, так как по условию эта мощность неизвестна B (Q 2)=⌈ T (Q 2) L (R 2)⋅10⌉=⌈33000100⋅10⌉=33 str [2]={{ Q 2},∅,∅,11000,10000,{33000,33,{33000},1}} 2) JoinPlan m 1=1, m 2=2 - номера экземпляров структур, таких, что str [ m 1]. W = Q 1 и str [ m 2]. W = Q 2 а) i =1, NLJ C 1= C CPU 1+ C I / O 1= T (Q 1)⋅ T (Q 2)⋅ C COMP +⌊ B (Q 1) b ⌋⋅ C I / O (Q 2)=2⋅33000⋅0.01+⌊110⌋⋅10000=660 мс i =2, SMJ таблица Q 2 уже отсортирована по номер_счёта, так как имеется индекс по номеру счёта С2=С CPU 2+ C I / O 2= C SORTCPU (Q 1)+С JOINCPU (Q 1, Q 2)+ C SORTI / O (Q 1)+ C JOINI / O (Q 1, Q 2)= =2⋅log22⌊1/10⌋⋅(0.01+0.01)+(log101−1)⋅2⋅(10⋅0.01+0.01)+((3300033000+2⋅2+ +33000⋅(1−233000))⋅0.01+(2⋅1⋅log10⋅1)⋅10+(1+0)⋅10=340 мс
C = min (C 1, C 2)=340 C = str [1]. Z + str [2]. Z + C =0.32+11000+340=11340.32 мс C I / O = str [1]. ZIO + str [2]. ZIO + C I / O 2=0.3+10000+10=10010.3 мс T (Q 1⋈ Q 2)= T (Q 1)⋅ T (Q 2) max (I (Q 1, a), I (Q 2, a))=2⋅33000 max (2,33000)=2 B (Q 1⋈ Q 2)=⌈21000⌉=1 I (Q 1⋈ Q 2, a)= min (I (Q 1, a), I (Q 2, a))= min (2,33000)=2 str [3]={{ Q 1, Q 2},{ Q 1},{ Q 2},11340,10010,{2,1,{2},2}} б) структура остаётся такая же 3) OptPlanReturn - вывод оптимального плана и представление этого плана в графическом виде. 1) (Q 1, Q 2)= Q 1⋈ Q 2 2) Q 1=(IndexScan ()+ Filter ()) 3) Q 2=(TableScan ()+ Filter ())
|
|||||||||||||
Последнее изменение этой страницы: 2021-04-12; просмотров: 65; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.222.148.124 (0.033 с.) |