В 1970-х годах известный программист Эдгар Кодд разработал математически выверенную теорию организации данных в виде таблиц (реляций). С тех пор утекло немало воды — появилось большое количество различных коммерческих и open-source реляционных систем управления базами данных (РСУБД). Скоро стало понятно, что эффективное получение данных из базы — задача далеко не тривиальная. Если говорить прямо, она нелинейная и в общем случае NP-сложная.
Когда SQL-запрос становится немного сложнее: SELECT * FROM table, у нас появляется огромная вариативность его исполнения внутри системы — и не всегда понятно, какой из возможных вариантов эффективнее как по памяти, так и по скорости. Чтобы сократить огромное количество вариантов до приемлемого, обычно используются так называемые эвристики — эмпирические правила, которые придуманы человеком для сокращения пространства поиска на несколько порядков. Понятное дело, эти правила могут отсечь и сам оптимальный план выполнения запроса, но позволяют получить хоть что-то приемлемое за адекватное время.
В последние годы в связи с активным развитием ML начали развиваться и нейронные оптимизаторы запросов —особенность которых в том, что они самостоятельно, без участия человека, находят необходимые закономерности в выполнении сложных планов исходя из обучения на огромном количестве данных. Тенденция началась приблизительно в 2017 году и продолжается до сих пор. Давайте посмотрим, что уже появилось в этой области в хронологическом порядке и какие перспективы нас ждут.
