Я работаю с базами данных в течение последних нескольких лет, и мне хотелось бы думать, что я достаточно компетентен в их использовании. Однако я недавно читал о законе «дырявых абстракций» Джоэла и понял, что, хотя я могу написать запрос, чтобы получить из базы данных практически все, что я хочу, я понятия не имею, как база данных фактически интерпретирует запрос. Кто-нибудь знает какие-нибудь хорошие статьи или книги, объясняющие, как базы данных работают внутри компании?
Вот некоторые конкретные вещи, которые меня интересуют:
- Что на самом деле делает база данных, чтобы узнать, что соответствует оператору select?
- Как база данных интерпретирует соединение иначе, чем запрос с несколькими операторами «where key1 = key2»?
- Как база данных хранит всю свою память?
- Как хранятся индексы?
Ответы:
Откровенно говоря, это вопрос грубой силы. Просто он читает каждую запись кандидата в базе данных и сопоставляет выражение с полями. Итак, если у вас есть «select * from table where name = 'fred'», он буквально проходит через каждую запись, берет поле «name» и сравнивает его с 'fred'.
Теперь, если поле «table.name» проиндексировано, то база данных будет (вероятно, но не обязательно) сначала использовать индекс, чтобы найти записи-кандидаты, к которым будет применяться фактический фильтр.
Это уменьшает количество записей-кандидатов, к которым нужно применить выражение, в противном случае оно будет просто выполнять то, что мы называем «сканированием таблицы», то есть читать каждую строку.
Но по сути, как бы то ни было, он находит записи-кандидаты отдельно от того, как он применяет фактическое выражение фильтра, и, очевидно, есть несколько умных оптимизаций, которые могут быть выполнены.
Итак, объединение используется для создания новой «псевдотаблицы», к которой применяется фильтр. Итак, у вас есть критерии фильтрации и критерии присоединения. Критерии объединения используются для построения этой «псевдотаблицы», а затем к ней применяется фильтр. Теперь при интерпретации соединения это снова та же проблема, что и с фильтром - сравнения грубой силы и чтение индекса для построения подмножества для «псевдотаблицы».
Один из ключей к хорошей базе данных - это то, как она управляет своими буферами ввода-вывода. Но в основном он сопоставляет блоки RAM с блоками диска. С современными диспетчерами виртуальной памяти более простая база данных может почти полагаться на виртуальную машину в качестве диспетчера буфера памяти. Высококачественные DB делают все это сами.
B + Деревья обычно, вы должны поискать это. Это простая техника, которая существует уже много лет. Это преимущество характерно для большинства сбалансированных деревьев: согласованный доступ к узлам, плюс все конечные узлы связаны, поэтому вы можете легко переходить от узла к узлу в ключевом порядке. Таким образом, с индексом строки можно считать «отсортированными» по определенным полям в базе данных, и база данных может использовать эту информацию для оптимизации. Это отличается, скажем, от использования хеш-таблицы для индекса, которая позволяет быстро перейти только к определенной записи. В B-дереве вы можете быстро перейти не только к конкретной записи, но и к точке в отсортированном списке.
Фактический механизм хранения и индексации строк в базе данных действительно довольно прост и понятен. Игра управляет буферами и преобразует SQL в эффективные пути запросов для использования этих основных идиом хранения.
Кроме того, к идиоме хранилища добавляется вся сложность многопользовательского режима, блокировки, ведения журнала и транзакций.
источник
Что на самом деле делает база данных, чтобы узнать, что соответствует оператору select?
БД используют индексы (см. Ниже)
Как база данных интерпретирует соединение иначе, чем запрос с несколькими операторами «where key1 = key2»? Операции соединения можно преобразовать в операции с двоичным деревом путем слияния деревьев.
Как база данных хранит всю свою память?
файлы с отображением памяти для более быстрого доступа к их данным
Как хранятся индексы?
Внутренние базы данных работают с B-деревьями для индексации.
Об этом следует подробнее рассказать в Википедии.
http://en.wikipedia.org/wiki/B-tree
http://en.wikipedia.org/wiki/Database
источник
В дополнение к чтению может быть поучительно использование инструментов БД для изучения плана выполнения, который база данных использует для ваших запросов. Помимо понимания того, как это работает, вы можете поэкспериментировать с методами оптимизации запросов с помощью лучшего цикла обратной связи.
источник
Саиф, отличная ссылка. Обзор с высоты птичьего полета, который охватывает большинство тем и предоставляет подробную информацию о реализациях конкретных поставщиков.
Я сделал три попытки написать объяснение, но это действительно слишком большая тема. Ознакомьтесь со статьей Hellerstein (той, на сервере Berkeley, на которую ссылался Саиф), а затем спросите о деталях.
Стоит отметить, что только часть «известных хороших идей» реализована в любой конкретной СУБД. Например, SQLite даже не выполняет хэш-соединения, он выполняет только вложенные циклы (ack !!). Но с другой стороны, это легко встраиваемая СУБД, и она очень хорошо выполняет свою работу, так что есть что сказать об отсутствии сложности.
Изучение того, как СУБД собирает статистику и как она использует их для построения планов запросов, а также научиться читать планы запросов в первую очередь, является бесценным навыком - если вам нужно выбрать одну "внутреннюю тему базы данных" для учись, учись этому. Это будет иметь огромное значение (и вы больше никогда случайно не напишете декартово произведение ... ;-)).
источник
Если вы хотите узнать больше, я бы рекомендовал получить исходные коды sqlite и посмотреть, как он это делает. Он полный, хотя и не в масштабе более крупных коммерческих баз данных с открытым исходным кодом. Если вы хотите узнать больше, я рекомендую The Definitive Guide to SQLite, который не только дает прекрасное объяснение sqlite, но и является одной из самых читаемых технических книг, которые я знаю. Что касается MySQL, вы можете узнать из блога о производительности MySQL, а также из книги O'Reilly High Performance MySQL (V2), одним из авторов которой является этот блог.
источник