На PG BootCamp Алена Рыбакина (Яндекс) честно разобрала, работают ли вообще генетические алгоритмы и машинное обучение в оптимизаторах. Проблема. Соединить 5 таблиц — 120 вариантов. 20 таблиц — 2,4 × 10¹⁸. Полный перебор невозможен. А если в графе запроса есть цикл — задача становится NP-hard. Добавьте сюда ошибки селективности: PostgreSQL думает, что Paris + France встретятся в 0.005% строк, а в реальности — 0.1%. На пяти JOIN-ах ошибка может вырасти в 2000+ раз. Что пробовали: • Классика. Selinger DP (1979) оптимален, но только до 12 таблиц. IKKBZ быстр, но требует дерева. DPhyp (2008) понимает гиперграфы и строит bushy-планы — именно он в DuckDB и Umbra. • Рандом. GEQO в PostgreSQL при более 12 таблиц — генетика. Минусы: недетерминизм, игнорирует startup_cost, скрещивание часто бесполезно. SAIO (имитация отжига) в 2010-м был быстрее, но не взлетел из-за грязного кода и ручных настроек. • ML-эпоха. Neo предсказывает latency через нейросеть (+18% на JOB), но учится на ошибках PG и переобучается часами. Bao подсказывает hints и гарантирует, что не хуже vanilla PG (+38%). SkinnerDB учится прямо во время выполнения и единственный имеет математические гарантии. Критика. В 2024 году вышла работа, которая показала: ML-методы достигли успеха из-за утечки данных и игнорирования времени инференса. На большом бенчмарке STACK PostgreSQL оказался стабильнее. Итог. Генетика и ML — не замена классике, а дополнение. Selinger, DPhyp и эвристики работают здесь и сейчас. Обучаемые методы хороши в исследованиях, но в production пока уступают старой школе. 🌐 ССЫЛКА НА ОНЛАЙН-ТРАНСЛЯЦИЮ