Советы по написанию СУБД

Я прошел курс выпускного курса, который является всего лишь одним большим проектом - для написания СУБД.

Цель состоит не в том, чтобы изобрести колесо и сделать СУБД предприятия соперничающим с Oracle. Необходимо поддерживать только небольшое подмножество команд SQL. Также не стоит создавать какую-нибудь причудливую гибридную модель СУБД для хранения мультимедиа или чего-то еще. Это должна быть традиционная СУБД.

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

Мне просто интересно, есть ли какие-либо ресурсы для запросов, оптимизаторов, структур данных, идеальных для СУБД, или в основном что-нибудь, что могло бы помочь мне создать отличный проект. Профессор метался, например, с помощью метапрограммирования.

Проект должен быть полностью выполнен на С++.

Спасибо за ответы! Я не могу оптимизировать существующую СУБД, такую как MySQL, поскольку проект требует от вас создания собственной СУБД с нуля. Да, я знаю, что это в значительной степени заново изобретает колесо для большей части, но есть возможности для некоторых новых алгоритмов оценки запросов и оптимизации. Если вы знаете какие-либо хорошие ресурсы или книги, посвященные этой конкретной области, то, пожалуйста, скажите мне!

Ответ 1

Поскольку ваш профессор упомянул метапрограммирование, вам может потребоваться следующее:

WAM - Абстрактная машина Уоррена. Это компилирует пролог-код в набор инструкций, которые могут быть выполнены на абстрактной машине. Идея подобна jvm и cli. Вам не нужно подробно останавливаться на этом, просто понимайте идею абстрактной машины.
JVM, CLI - так же, как указано выше.
Инструменты, такие как lex, yacc, flex, bison. Поскольку вы будете писать по существу интерпретатор/компилятор для команд SQL, вы, вероятно, захотите использовать некоторые инструменты. Это можно рассматривать как форму метапрограммирования, поскольку вы используете язык для написания инструмента - так что вы программируете на метауровне.
Опять же, идея метапрограммирования - возможно, вы можете расширить свой язык конструкциями, которые позволят вашему компилятору/интерпретатору SQL автоматически оптимизировать параллельные запросы. Они могут быть реализованы в виде подсказок и т.д. Компилятору.
Recompilers - вы можете написать интерпретатор/компилятор, который перекомпилирует исходные запросы в те, которые могут работать параллельно для вашей целевой архитектуры. Например, для архитектуры N-core он может перекомпилировать запрос в N-подзапросы, которые выполняются параллельно, а затем объединить результаты.

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

Ответ 2

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

Затем ознакомьтесь с bx-деревьями для ваших индексов. Затем сделайте фиксацию и откат, и это почти все, что нужно. Это не ракетостроение, по сравнению с другими проектами, которые вы могли бы предпринять, но определенно вам лучше начать сразу, если вы хотите получить хороший результат к концу семестра/год.

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

Ответ 3

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

Этот подход (ориентированное на столбцы хранилище + сжатие) и более традиционный механизм запросов, возможно, основанный на движке SQLite, должен быть хорошей основой для проекта.

Ответ 4

За исключением собственных проблем, как насчет оптимизации MySQL таким образом? Однако это не тривиальная задача. Оптимизация запросов, которая использует преимущества параллельной обработки, может быть целым термином.

Лучше встать на плечи гигантов, чтобы достичь вверх, чем стоять рядом с ними.