Может кто-нибудь знает/слышал о том, какие методы оптимизации запросов используют современные СУБД.
Меня интересуют алгоритмические методы, уловки с архитектурой БД и т.д. и т.п. Конечно, такие данные являются коммерческой тайной, но ведь есть разработки программистского сообщества. Если кто-то может кинуть ссылочку или лучше доку — буду премного благодарен. Если кто-то имеет интересы в данной области, можно законнектиться по e-почте.
Здравствуйте, ShuricVZ, Вы писали:
SVZ>Может кто-нибудь знает/слышал о том, какие методы оптимизации запросов используют современные СУБД. SVZ>Меня интересуют алгоритмические методы, уловки с архитектурой БД и т.д. и т.п. Конечно, такие данные являются коммерческой тайной, но ведь есть разработки программистского сообщества. Если кто-то может кинуть ссылочку или лучше доку — буду премного благодарен. Если кто-то имеет интересы в данной области, можно законнектиться по e-почте.
К сожалению, ссылочку дать не могу. Из того что помню:
— Если в запросе идет выборка по проиндексированным полям (например, select count(*) where primkey between 1 and 100), к самой таблице можно вообще не обращаться.
— При обработке inner join (например, A.a = B.b) определяется таблица будет сканироваться во внешнем цикле:
-- Если одно из полей проиндексировано (например, A.a) а другое — нет, внешний цикл будет сканировать таблицу B.
-- Если оба поля проиндексированы, сравнивается размер таблиц и сбалансированность индексов. Вот каким образом сервер рассчитывает степерь сбалансированности индекса, я не знаю. Знаю только, что это значение хранится в атрибуте индекса. Для непроиндексированных полей сравниваются размеры таблиц.
SVZ>Может кто-нибудь знает/слышал о том, какие методы оптимизации запросов используют современные СУБД. SVZ>Меня интересуют алгоритмические методы, уловки с архитектурой БД и т.д. и т.п. Конечно, такие данные являются коммерческой тайной, но ведь есть разработки программистского сообщества. Если кто-то может кинуть ссылочку или лучше доку — буду премного благодарен. Если кто-то имеет интересы в данной области, можно законнектиться по e-почте.
Что-то пробегало с полгода назад мимо меня...
Что-то не вижу тех статей в фаворитах, ну да ладно.
Там были интервью с разработчиками DB2 и всяким таким народом.
В общем, имхо начинать надо с Кнута III. Как бы то ни было, вопросы поиска по одному ключу там рассмотрены достаточно подробно (вот только нет алгоритма слияния страниц для B-tree)
Также весьма полезно почитать SQL Books Online от MS SQL 2000, ибо там раскрыты многие подробности того, как устроен сторадж для шустрости действия. Ну и некоторые другие вещи, из которых можно сделать определенные выводы, хотя явно там написано только "наш оптимайзер крут, крут, и очень крут." Например, между 7 и 2000 они сменили статистику. Но об этом далее.
Конечно, хорошей ссылкой является поиск в Гугле, хотя по нему довольно долго искать.
Вкратце дело сводится к следующему:
Математически, каждый запрос можно представить несколькими способами. Так же, как в обычной алгебре, где a*(b+c) = a*b+a*c, можно выбирать различные способы вычисления. От выбора способа зависит стоимость (в примере мы выбираем между одним сложением и одним умножением и двумя умножениями и одним сложением).
В однотабличных запросах ключевым является выбор индекса, по которому делается первичный поиск. Т.е. предикат разбивается на две части — одна из них выражается в терминах ключа индекса, вторая, так называемый остаток (residual) применяется к результату сканирования индекса. Первая операция выполняется логарифмически, вторая — линейно. Цена имеет порядок O(log(N)+Ki), где Ki — количество записей, отобранных при сканировании индекса i, а N — полное количество записей. В данном случае оптимизация сводится к выбору правильного индекса среди имеющихся и правильному разворачиванию предиката с целью максимизации селективности, т.е. минимизации Ki. Задача эта уже нетривиальна хотя бы потому, что селективность запроса — вещь трудно предсказуемая. Скажем, если есть табличка народа, из которой надо выбрать женщин-программистов, то на первый взгляд из индексов по полу и профессии надо выбирать второй. Полов всего 2, и потому можно ожидать всего лишь 50% селективности, и половину записей придется прогнать через линейный поиск. Доля же программеров невелика, и среди этих нескольких процентов отобрать всех женщин гораздо проще. Примерно так действует MS SQL 7.0. Однако такой алгоритм встрянет, если в таблице случайно оказалась всего одна женщина. Выбор индекса по полу привел бы к единственной проверке на профессию. Поэтому MS SQL 2000 хранит, помимо количества различных ключей в индексе также и гистограмму по диапазонам. Если в 7ке план запроса не зависел от того, подставим ли мы в него 'М' или 'Ж', то в 2000 зависимость будет.
В случаях сложных предикатов типа (a>b) все сразу становится хуже. Потому, что альтернативой линейному поиску по такому предикату (очевидно, невыразимомому в терминах индексов по a либо b) становится только переход к псевдо-join, т.е. (t1.id=t2.id and t1.a>t2.b), который в некоторых случаях дешевле. Отсюда видно, как расширяется пространство планов, соответствующих исходному запросу.
В случаях многотабличных запросов ситуация намного сложнее, т.к. вариантов исполнения становится больше. При этом появляются и новые возможности по оптимизации, связанные с порядком чтения из таблиц. Примерно тут мои познания теряются в густом тумане невежества.
В прошлом движки RDBMS в основном обучали не терять измерения пространства планов из боязни упустить оптимальный. Но довольно быстро оказалось, что экспоненциальный взрыв количества вариантов выполнения запроса приводит к обратному эффекту: динамическое программирование начинает причмокивать, и выгоднее выполнить неоптимальный запрос, чем оптимизировать его.
Насколько я знаю, современные движки используют эвристические методы выбора оптимальной стратегии. Кроме того, стоимость самого выбора плана ограничивается, чтобы не ухудшить общее время работы. Эти алгоритмы (в отличие от форматов файлов, стратегий блокировки, и прочей технической информации), как правило являются закрытыми. Потому, что именно они определяют, кто окажется в Top10 www.tpc.org. В доке от MS вскользь упомянуто, что из оптимизатор "не гарантирует выбор оптимального плана, но гарантирует квазиоптимальность", то есть план не более чем на известную величину хуже, чем оптимальный.
... << RSDN@Home 1.0 beta 6 >>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, ShuricVZ, Вы писали:
SVZ>Может кто-нибудь знает/слышал о том, какие методы оптимизации запросов используют современные СУБД.
Эта тема настолько хорошо разработана, что никакой коммерческой тайны тут нет..
Очень хорошо всё это освещено и в соотв. литературе
(классика — Майерс, "Теория Реляционных Бах данных" кажется)..
Кроме того, в доке для каждой СУБД есть как правило отдельный пункт, поясняющий как именно идёт оптимизация..
Например: http://www.mysql.com/doc/ru/MySQL_Optimisation.html
Аналогичные разъяснения я видел и для FireBird и для Oracle..
План вычисления MSSQL лнгко посмотреть в Query Analizer..
У OpenSource-СУБД (mySQL, PosgreeSQL, FireBird) можно посмотреть исходники..
Здравствуйте, vvaizh, Вы писали:
V>Эта тема настолько хорошо разработана, что никакой коммерческой тайны тут нет.. V>Очень хорошо всё это освещено и в соотв. литературе V>(классика — Майерс, "Теория Реляционных Бах данных" кажется)..
Жаль, не читал. Стоящая вещь? В том интервью (1993 то ли 94 год) один из архитекторов DB2 как-то снисходительно отзывался об уровне развития академических знаний на эту тему. Типа того, что в жизни начинают играть такие малозначительные факторы, как
— требования к стабильности оптимизатора, т.е. неухудшению времени запроса (многие теоретически красивиые вещи улучшают среднюю производительность, ухудшая ее в плохих случаях)
— проблемы при работе с большими данными, когда малые члены выражения для ценв начинают играть роль. Наример, в большинстве случаев глубина B-tree не превышает 3-4, и можно считать время обращения к каждому ключу константой. Однако в таблицах с глубиной дерева 10-15 начинаются потери производительности при сканировании индекса классическим способом, и спасает толко использование прошитых деревьев.
Возможно, с тех пор ситуация поменялась (а похоже на то, поскольку появилось несколько серьезных заявок от бесплатных движков), и доступны открытые публикации на эту тему. Увы, в сети валяется огрмное количество мусора, и отделить его от крупиц истины прямым просеиванием у меня не хватает времени и терпения. Так что рекомендации к прочтению — велком.
V>http://www.mysql.com/doc/ru/MySQL_Optimisation.html
Рульно. Большая часть, конечно же, посвящена тому, как программист должен оптимизировать запросы, но некторая (неполная) информация об алгоритмах query optimizer тоже есть. V>Аналогичные разъяснения я видел и для FireBird и для Oracle..
Интересно. Для FireBird еще могу поверить (ибо во-первых они бесплатные, а во-вторых они и рядом с www.tpc.org не ночевали, т.е. хвастаться особыми оптимизациями не приходится), а вот про оракл верится с трудом... Очень буду рад оказаться неправым! Дюже интересно, как они там разруливают все эти тонкости. V>План вычисления MSSQL лнгко посмотреть в Query Analizer..
Ну-у, это фигня. План вычисления — суть результат работы оптимизатора, а не его алгоритм... Конечно, иожно потратить несколько лет на прогонку тестовыых запросов и среверсировать логику (хотя я б не взялся и с неограниченными ресурсами), но имхо быстрее все же в литературе порыть. V>У OpenSource-СУБД (mySQL, PosgreeSQL, FireBird) можно посмотреть исходники..
... << RSDN@Home 1.0 beta 6 >>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, vvaizh, Вы писали:
V>>Эта тема настолько хорошо разработана, что никакой коммерческой тайны тут нет.. V>>Очень хорошо всё это освещено и в соотв. литературе V>>(классика — Майерс, "Теория Реляционных Бах данных" кажется).. S>Жаль, не читал. Стоящая вещь?
По сложности и строгости приближается к функ-ану и всяким тяжёлым разделам мат логики
Я например одолел только первые 2 главы (из по моему 6..)
В которых объяснялись простейшие нормальные формы и методы работы с ними (кажется штук 8..)
Дальше — больше (нормальных форм тоже..)
С этим можно только "познакомиться".. так сказать заглянуть в глубь колодца..
Прыгать — не прыгать каждый решает сам
Для общего уровня полезно в общем..
S>В том интервью (1993 то ли 94 год) один из архитекторов DB2 как-то снисходительно отзывался об уровне развития академических знаний на эту тему.
Так что рекомендации к прочтению — велком.
Со всеми замечаниями согласен.. Но их можно отнести к абсолютно всем академическим знаниям о программировании (читай теории вычислимости).. Т.к. что ещё объективно брать в качестве критерия как не "максимальное значение". Средний запрос каждый понимает по своему и в каждой системе он свой..
Оттого результаты бенчмарков разные у разных производителей..
Тут все подходят примерно одинаково: оптимизируют "средние запросы", а если у тебя что то сложное то как правило везде можно ручками прописать план вычисления
V>>http://www.mysql.com/doc/ru/MySQL_Optimisation.html S>Рульно. Большая часть, конечно же, посвящена тому, как программист должен оптимизировать запросы, но некторая (неполная) информация об алгоритмах query optimizer тоже есть.
Ты хочешь логическое описание что ли? Его просто в природе нет.. ни у кого как правило..
т.е. State Art.. Правильные чуваки в таких конторах (с мат образованием, которые этого майерся знают поглубже) занимаются оптимизацией.. а описания я уверен нет ни у кого.. всё на людях держится.. Потому что если начнёшь описывать, посложнее майерса получится..
V>>Аналогичные разъяснения я видел и для FireBird и для Oracle.. S>Интересно. Для FireBird еще могу поверить (ибо во-первых они бесплатные, а во-вторых они и рядом с www.tpc.org не ночевали, т.е. хвастаться особыми оптимизациями не приходится), а вот про оракл верится с
трудом... Очень буду рад оказаться неправым! Дюже интересно, как они там разруливают все эти тонкости.
Ну аналогичную вешь можно найти здесь: http://www.citforum.ru/database/articles/oracle8_opt.shtml
Там в конце ссылки, и кстати рекомендации, что Oracle — не панацея, оптимизатор далеко не супер, и хочешь скорости, вручную прописывай чего как и с чем должно работать и сливаться..
V>>План вычисления MSSQL лнгко посмотреть в Query Analizer.. S>Ну-у, это фигня. План вычисления — суть результат работы оптимизатора, а не его алгоритм... Конечно, иожно потратить несколько лет на прогонку тестовыых запросов и среверсировать логику (хотя я б не взялся и с неограниченными ресурсами), но имхо быстрее все же в литературе порыть.
Ну а чего ты хочешь? Литературы дофига.. а как конкретно тебе всё равно мало кто объяснит, так как каждый по своему делает, и ни у кого __бесспорно__ лучшего нет..
Общая рекомендация — пишите планы вычислений сами..
S>Здравствуйте, ShuricVZ, Вы писали: S>Потому, что именно они определяют, кто окажется в Top10 www.tpc.org.
А мне вот интересно, можно ли посмотреть исходники этого теста, т.е. что конкретно он проверяет..
Есть ли к нему исходники, запросы?
Здравствуйте, vvaizh, Вы писали: V>А мне вот интересно, можно ли посмотреть исходники этого теста, т.е. что конкретно он проверяет.. V>Есть ли к нему исходники, запросы?
Конечно есть! Все открыто — бери, тестируй.
На странице каждого из тестов есть ссылки на спецификацию (в правом верхнем углу)Ж TPC-C TPC-H TPC-R TPC-W
... << RSDN@Home 1.0 beta 6 >>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
S>>Здравствуйте, ShuricVZ, Вы писали: S>>Потому, что именно они определяют, кто окажется в Top10 www.tpc.org. V>А мне вот интересно, можно ли посмотреть исходники этого теста, т.е. что конкретно он проверяет.. V>Есть ли к нему исходники, запросы?
Есть.. Запросы по крайней мере, где-то была ссылка в нужное место этого сайта, но найти сейча не могу...
Запросы к tpс-H там точно были. (tpc-H это как раз тест оптимизатора. )
Спасибо за ответы. Не ожидал, что кто-то отзовется.
Вы упоминаете книжечку Майерса, и ее описание меня очень заинтересовало.
Можно-ли ее где-нибудь достать в электронном виде? А то толковой теории никак не найду.
Если кто-нибудь поможет, буду премного благодарен.
P.S. За ссылки спасибо, только у меня что-тот ссылка на MySQL не заработала
Здравствуйте, Sinclair, Вы писали:
S>В прошлом движки RDBMS в основном обучали не терять измерения пространства планов из боязни упустить оптимальный. Но довольно быстро оказалось, что экспоненциальный взрыв количества вариантов выполнения запроса приводит к обратному эффекту: динамическое программирование начинает причмокивать, и выгоднее выполнить неоптимальный запрос, чем оптимизировать его.
Когда мне приходилось заниматься оптимизацией логического вывода для нужд ИИ,
то там получался такой же результат. Впрочем это не удивительно.
Природа реляционных БД и языков логического программирования едина.
Здравствуйте, Sinclair, Вы писали:
S>Что-то пробегало с полгода назад мимо меня... S>Что-то не вижу тех статей в фаворитах, ну да ладно. S>Там были интервью с разработчиками DB2 и всяким таким народом. S>В общем, имхо начинать надо с Кнута III. Как бы то ни было, вопросы поиска по одному ключу там рассмотрены достаточно подробно (вот только нет алгоритма слияния страниц для B-tree) S>Также весьма полезно почитать SQL Books Online от MS SQL 2000, ибо там раскрыты многие подробности того, как устроен сторадж для шустрости действия.
[skip]
S>Вкратце дело сводится к следующему: S>Математически, каждый запрос можно представить несколькими способами. Так же, как в обычной алгебре, где a*(b+c) = a*b+a*c, можно выбирать различные способы вычисления. От выбора способа зависит стоимость (в примере мы выбираем между одним сложением и одним умножением и двумя умножениями и одним сложением).
[skip]
S>В случаях сложных предикатов типа (a>b) все сразу становится хуже. Потому, что альтернативой линейному поиску по такому предикату (очевидно, невыразимомому в терминах индексов по a либо b) становится только переход к псевдо-join, т.е. (t1.id=t2.id and t1.a>t2.b), который в некоторых случаях дешевле. Отсюда видно, как расширяется пространство планов, соответствующих исходному запросу.
[skip]
S>В прошлом движки RDBMS в основном обучали не терять измерения пространства планов из боязни упустить оптимальный. Но довольно быстро оказалось, что экспоненциальный взрыв количества вариантов выполнения запроса приводит к обратному эффекту: динамическое программирование начинает причмокивать, и выгоднее выполнить неоптимальный запрос, чем оптимизировать его. S>Насколько я знаю, современные движки используют эвристические методы выбора оптимальной стратегии.
[skip]
У К. Дэйта во Введении в Системы Баз Данных данному вопросу посвящена отдельная глава. Там достаточно подробно рассмотрены теоретические основы оптимизации и, насколько я помню, вскользь упомянуты кое-какие тонкости реализации этого дела на DB2.
Процесс оптимизации там разбит на 4 этапа:
На первом запрос переводится во внутреннее представление сервера, причем основная задача здесь представить запрос в как можно более нейтральном виде, чтобы никак не повлиять на дальнейшую оптимизацию. Как правило запрос представляется ввиде некоего графа, абстрактного синтаксического дерева.
На втором этапе запрос приводится к каноническому виду. Не взирая на статистику, размер данных и т.д. и т.п., над запросом совершается ряд преобразований, которые являютя "гарантированно хорошими".
Как раз здесь используются те самые правила преобразования о которых ты упоминал, в частности семантические, когда например A JOIN B WHERE A.C, заменяется на (A WHERE A.C) JOIN B.
А, например, все выражения с использованием AND, OR... преобразуются в нормальную форму (КНФ), в этой форме условие имеет вид S1 AND S2 AND S3...
Фишка в том, что в этой форме выражение истинно только в том случае если истинны все его части, а значит оптимизатор вычисляя их поочереди, начиная с самой простой, может прекратить этим заниматься как только результатом хотя бы одного условия будет ложь.
На третьем этапе уже оглядываясь на индексы, статистику, физическую кластеризацию и прочую низкоуровневую головную боль, выбираются "пути доступа". Здесь запрос рассматривается как серия низкоуровневых операций, которые могут зависеть друг от друга. С каждой операцией связана своя стоимость вычисляемая на основе стоимости обращений к диску, время использования процессора, и т.д. Это похоже и есть самая большая загадка, ибо как оценивать стоимость операции учитывая все зависимости, тот еще вопрос...
Ну и наконец на четвертом этапе, строятся потенциальные планы запросов, и генерится собственно окончательный план с помощю некоего эвристического алгоритма. Как ты совершенно справедливо заметил он вовсе не обязан быть самым оптимальным планом на свете..
Тут есть еще одна тонкость, для оценки стоимости плана, оптимизатор должен знать, что во время выполнения запроса могут возникнуть промежуточные результаты, стоимость которых так же необходимо учитывать.
У Дэйта так же разобрана статистика, какая она бывает и для чего собирается, способы реализации некоторых реляционных операторов, объединение слиянием, хешированием (в MSSQL'е MERGE и HASH join'ы)
Еще там упоминается о "замедлителях оптимизации" типа трехзначной логики и дублирующих записей.
Вообщем много чего хорошего.. Но там понятное дело только глубокая теория и краткие упоминания о DB2, тоесть несмотря то что теория этого дела исследуется достаточно давно и глубоко, тонкости конкретной реализации никто не открывает..
Вот, так сказать, для начала...
И это все без учета возможной параллельной обработки запросов... Тут тоже есть свои пути для оптимизации, например в MSSQL'е если запрос видит, что кто-то другой уже выполняет table scan, то он просто присоединяется к первому скану, чтобы не читать второй раз, а после завершения дочитывает начало.
Мы уже победили, просто это еще не так заметно...
