Как базы данных работают внутри? [закрыто]

80

Я работаю с базами данных в течение последних нескольких лет, и мне хотелось бы думать, что я достаточно компетентен в их использовании. Однако я недавно читал о законе «дырявых абстракций» Джоэла и понял, что, хотя я могу написать запрос, чтобы получить из базы данных практически все, что я хочу, я понятия не имею, как база данных фактически интерпретирует запрос. Кто-нибудь знает какие-нибудь хорошие статьи или книги, объясняющие, как базы данных работают внутри компании?

Вот некоторые конкретные вещи, которые меня интересуют:

  • Что на самом деле делает база данных, чтобы узнать, что соответствует оператору select?
  • Как база данных интерпретирует соединение иначе, чем запрос с несколькими операторами «where key1 = key2»?
  • Как база данных хранит всю свою память?
  • Как хранятся индексы?
Бонничи
источник
Если это SQL-сервер, я настоятельно рекомендую серию статей «Внутри Microsoft SQL Server 2005» (пресса Microsoft), особенно о Storage Engine и о запросах… Она отвечает на все ваши вопросы и многое другое. Возможно, вас заинтересуют некоторые из этих блогов: Крейг Фридман Кален Делейни Также стоит подписаться на SQLServerCentral ..
Гулзар Назим
Попробуйте этот db.cs.berkeley.edu/papers/fntdb07-architecture.pdf и WikiPedia. Это довольно обширная тема и такие модели, как RDBMS, FLATFILE и т. Д. Парсер действительно является одним из наиболее важных компонентов. Спасибо
Саиф Хан
2
По состоянию на 2015 год есть эта статья, которая кажется довольно хорошей.
Piovezan 07
внутренняя архитектура баз данных усложняется В ЭТОЙ СТАТЬЕ подробно объясняется работа сервера mysql и механизмов хранения.
шашват шривастава

Ответы:

83

Что на самом деле делает база данных, чтобы узнать, что соответствует оператору select?

Откровенно говоря, это вопрос грубой силы. Просто он читает каждую запись кандидата в базе данных и сопоставляет выражение с полями. Итак, если у вас есть «select * from table where name = 'fred'», он буквально проходит через каждую запись, берет поле «name» и сравнивает его с 'fred'.

Теперь, если поле «table.name» проиндексировано, то база данных будет (вероятно, но не обязательно) сначала использовать индекс, чтобы найти записи-кандидаты, к которым будет применяться фактический фильтр.

Это уменьшает количество записей-кандидатов, к которым нужно применить выражение, в противном случае оно будет просто выполнять то, что мы называем «сканированием таблицы», то есть читать каждую строку.

Но по сути, как бы то ни было, он находит записи-кандидаты отдельно от того, как он применяет фактическое выражение фильтра, и, очевидно, есть несколько умных оптимизаций, которые могут быть выполнены.

Как база данных интерпретирует соединение иначе, чем запрос с несколькими операторами «where key1 = key2»?

Итак, объединение используется для создания новой «псевдотаблицы», к которой применяется фильтр. Итак, у вас есть критерии фильтрации и критерии присоединения. Критерии объединения используются для построения этой «псевдотаблицы», а затем к ней применяется фильтр. Теперь при интерпретации соединения это снова та же проблема, что и с фильтром - сравнения грубой силы и чтение индекса для построения подмножества для «псевдотаблицы».

Как база данных хранит всю свою память?

Один из ключей к хорошей базе данных - это то, как она управляет своими буферами ввода-вывода. Но в основном он сопоставляет блоки RAM с блоками диска. С современными диспетчерами виртуальной памяти более простая база данных может почти полагаться на виртуальную машину в качестве диспетчера буфера памяти. Высококачественные DB делают все это сами.

Как хранятся индексы?

B + Деревья обычно, вы должны поискать это. Это простая техника, которая существует уже много лет. Это преимущество характерно для большинства сбалансированных деревьев: согласованный доступ к узлам, плюс все конечные узлы связаны, поэтому вы можете легко переходить от узла к узлу в ключевом порядке. Таким образом, с индексом строки можно считать «отсортированными» по определенным полям в базе данных, и база данных может использовать эту информацию для оптимизации. Это отличается, скажем, от использования хеш-таблицы для индекса, которая позволяет быстро перейти только к определенной записи. В B-дереве вы можете быстро перейти не только к конкретной записи, но и к точке в отсортированном списке.

Фактический механизм хранения и индексации строк в базе данных действительно довольно прост и понятен. Игра управляет буферами и преобразует SQL в эффективные пути запросов для использования этих основных идиом хранения.

Кроме того, к идиоме хранилища добавляется вся сложность многопользовательского режима, блокировки, ведения журнала и транзакций.

Уилл Хартунг
источник
8
Я просто хотел сказать, что это действительно интересный и полезный ответ. Вы писали где-нибудь на эту тему более подробно?
Натан Лонг,
это поможет мне понять, как на самом деле работает база данных
Адзимзф 01
«тогда база данных будет (вероятно, но не обязательно) сначала использовать индекс, чтобы найти записи-кандидаты для применения фактического фильтра» в каких случаях индекс не используется, если он доступен и почему?
Сатьендра Кумар
1
@SatyendraKumar, это зависит от множества вещей, но, в конце концов, если оптимизатор (на основе статистики и т. Д.) Решит, что результатом запроса из индекса будет большая часть строк таблицы, дешевле игнорировать вместо этого выполняется сканирование индекса и таблицы. Индекс включает в себя множество случайных операций ввода-вывода, что требует затрат. В конце концов, эта стоимость выше, чем просто сканирование таблицы. Управление такими вещами - лишь один из аспектов процесса настройки базы данных и оптимизации запросов.
Уилл Хартунг
4
  • Что на самом деле делает база данных, чтобы узнать, что соответствует оператору select?

    БД используют индексы (см. Ниже)

  • Как база данных интерпретирует соединение иначе, чем запрос с несколькими операторами «where key1 = key2»? Операции соединения можно преобразовать в операции с двоичным деревом путем слияния деревьев.

  • Как база данных хранит всю свою память?

    файлы с отображением памяти для более быстрого доступа к их данным

  • Как хранятся индексы?

    Внутренние базы данных работают с B-деревьями для индексации.

Об этом следует подробнее рассказать в Википедии.

http://en.wikipedia.org/wiki/B-tree

http://en.wikipedia.org/wiki/Database

Питер Паркер
источник
1

В дополнение к чтению может быть поучительно использование инструментов БД для изучения плана выполнения, который база данных использует для ваших запросов. Помимо понимания того, как это работает, вы можете поэкспериментировать с методами оптимизации запросов с помощью лучшего цикла обратной связи.

Под ключ
источник
0

Саиф, отличная ссылка. Обзор с высоты птичьего полета, который охватывает большинство тем и предоставляет подробную информацию о реализациях конкретных поставщиков.

Я сделал три попытки написать объяснение, но это действительно слишком большая тема. Ознакомьтесь со статьей Hellerstein (той, на сервере Berkeley, на которую ссылался Саиф), а затем спросите о деталях.

Стоит отметить, что только часть «известных хороших идей» реализована в любой конкретной СУБД. Например, SQLite даже не выполняет хэш-соединения, он выполняет только вложенные циклы (ack !!). Но с другой стороны, это легко встраиваемая СУБД, и она очень хорошо выполняет свою работу, так что есть что сказать об отсутствии сложности.

Изучение того, как СУБД собирает статистику и как она использует их для построения планов запросов, а также научиться читать планы запросов в первую очередь, является бесценным навыком - если вам нужно выбрать одну "внутреннюю тему базы данных" для учись, учись этому. Это будет иметь огромное значение (и вы больше никогда случайно не напишете декартово произведение ... ;-)).

SquareCog
источник
0

Если вы хотите узнать больше, я бы рекомендовал получить исходные коды sqlite и посмотреть, как он это делает. Он полный, хотя и не в масштабе более крупных коммерческих баз данных с открытым исходным кодом. Если вы хотите узнать больше, я рекомендую The Definitive Guide to SQLite, который не только дает прекрасное объяснение sqlite, но и является одной из самых читаемых технических книг, которые я знаю. Что касается MySQL, вы можете узнать из блога о производительности MySQL, а также из книги O'Reilly High Performance MySQL (V2), одним из авторов которой является этот блог.

Dajobe
источник