Кратко

  • Оптимизатор System R выбирал наименьшую оценочную стоимость среди действительно рассмотренных вариантов. Он складывал ожидаемые чтения страниц и взвешенные обращения к интерфейсу хранения, а не измерял будущую длительность.
  • Селективность определяла оценку кардинальности, а та меняла привлекательность пути доступа, порядка соединений и физического оператора. «Интересный порядок» сохранял локально дорогой путь, если он мог убрать последующую сортировку.
  • Selinger организовала коллективную работу с Morton Astrahan, Donald Chamberlin, Raymond Lorie и Thomas Price. Её долговечность — в проверяемом разделении предпосылки, физического решения и факта исполнения.

Правильный ответ не гарантирует правильной цены

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

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

Решение приходится принять, когда этот запуск ещё не состоялся. Оптимизатор не знает точно, какие страницы окажутся в памяти, сколько строк встретит конкретный параметр, как конкуренция повлияет на I/O и выйдет ли оператор за лимит памяти. В его распоряжении не наблюдение будущего, а модель.

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

Декларативный язык передал власть движку

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

Статья 1979 года Access Path Selection in a Relational Database Management System описывает четыре стадии. Разбор создаёт внутреннее представление. Оптимизация выбирает спецификацию доступа. Генерация кода превращает её в исполнимую форму. Затем начинается исполнение.

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

Семантическая правильность и физическая эффективность живут на разных уровнях. Неправильные строки — дефект корректности. Правильные строки, полученные слишком поздно, указывают на оценку, план или исполнение. Успешный единичный прогон также не доказывает универсальное превосходство при других параметрах и состоянии кэша.

Каталог был сжатой картиной

System R использовала статистики NCARD для числа кортежей, TCARD для страниц отношения, P для их заполнения, ICARD для различных ключей индекса и NINDX для индексных страниц. Такое описание позволяло сравнивать пути, не читая заранее всю базу.

Значения создавались и периодически обновлялись командой UPDATE STATISTICS. Авторы объяснили отказ от синхронизации после каждого изменения: записи каталога и блокировки стоили бы слишком дорого.

Неполнота была не случайной поломкой, а экономическим выбором. Наблюдение потребляет ресурсы. Идеально свежая и подробная копия реальности могла бы стоить больше, чем решение, которому она служит. Дешёвое резюме рискует устареть.

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

От селективности к кардинальности

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

В тексте подчёркнуто: эти числа не имеют смысла кроме грубого упорядочения. Они не являются законами распределений. Это правила продолжения решения при недостатке данных.

Для условий с AND коэффициенты перемножались. Операция предполагает независимость. Город связан с индексом, категория товара — с ценой, тип договора — со сроком. Произведение независимых вероятностей способно представить обычное сочетание почти невозможным.

Кардинальность переводит долю в количество строк. Логика QCARD сочетает размеры отношений и селективности; результат входит в стоимость последующих операторов. Если внешнюю часть вложенного цикла оценили слишком низко, повторяемая работа кажется дешёвой. В действительности она выполняется множество раз. Завышенный фильтр, наоборот, лишает преимущества узкий индекс.

Селективность — отношение, кардинальность — число. Ошибка переходит от первой ко второй, затем определяет промежуточные объёмы, порядок соединений, оператор, память и сортировку.

В 2015 году Leis и соавторы показали, что ошибки кардинальности обычно вредили плану сильнее, чем небольшие неточности формулы стоимости. Ретроспектива 2025 года всё ещё называет кардинальность, устойчивость и адаптацию открытыми задачами. Уязвимое звено прежней архитектуры осталось современным.

Расчётная валюта, а не часы

Формула System R выглядела так:

COST = PAGE FETCHES + W × (RSI CALLS)

Чтения страниц обозначали ввод-вывод, обращения к Research Storage Interface приближали процессорную работу, а W задавал их относительную цену. Учёт CPU был важным шагом, но сумма разнородных величин не превращалась в секунды.

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

Низший балл действительно означает меньшую стоимость внутри модели. Более короткое время — гипотеза. Для слова «оптимальный» нужно назвать и цель, и пространство кандидатов. План, которого перечислитель не создал, не может выиграть формулу.

Документация PostgreSQL сохраняет эту границу. Стоимостные единицы условны и зависят от платформы, это не миллисекунды. EXPLAIN не запускает запрос и показывает оценки. EXPLAIN ANALYZE запускает и добавляет реальные строки и время. Первая команда объясняет прогноз, вторая возвращает факты исполнения.

Три разных решения внутри плана

Путь доступа определяет, как достичь базового отношения: сканированием или индексом. Физический оператор определяет, как соединять, сортировать или агрегировать. Порядок соединений определяет, какие отношения объединить раньше и какого размера будут промежуточные результаты.

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

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

Реляционная эквивалентность охраняет смысл с учётом правил о пустых значениях, дубликатах и агрегации. Она не обещает равных ресурсов.

Зачем сохранять «интересный порядок»

Индексный путь может быть дороже сканирования для текущего отношения, но уже выдать строки в порядке следующего соединения, GROUP BY или финального ORDER BY. Тогда он избавит от будущей сортировки.

System R сохраняла самый дешёвый неупорядоченный частичный план и лучшего представителя каждого интересного порядка. Одинаковый набор строк не делал два результата физически взаимозаменяемыми: их свойства меняли цену продолжения.

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

При этом хранить все варианты не требовалось. Достаточно было лучших представителей классов, чьи свойства способны изменить дальнейшее решение.

Поиск тоже должен закончиться

Число порядков соединений растёт комбинаторно, а полный перебор перестановок — почти факториально. Оптимизация могла бы занять больше времени, чем сэкономит исполнение.

System R применила динамическое программирование. Для подмножеств отношений сохранялись лучшие планы по интересным порядкам, а затем использовались при построении больших подмножеств. Декартовы произведения откладывались, поскольку без условия соединения обычно раздувают промежуточный результат.

Статья описывает поиск через подмножества и физические свойства и сообщает об оптимизации соединений восьми таблиц за секунды на IBM 370/158. Управляемое пространство сделало подход практичным.

Но отсечение не доказывает просмотр всех мыслимых форм. Динамическое программирование находит лучшего кандидата внутри пространства, которое задали перечислитель, операторы, формы дерева и правила хранения. Глобальная оптимальность без этих оговорок не доказана.

Время оптимизации и исполнения — отдельные статьи. Глубокий поиск окупается для дорогой аналитики и может быть расточительным для короткой частой операции. Общий план подготовленного запроса экономит перепланирование, но проигрывает, когда идеальный путь сильно зависит от параметра.

Авторы оставили модель проверяемой

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

В 1986 году Mackert и Lohman сравнили оценки R* с фактическими ресурсами. Значительная часть модели I/O работала; описание CPU нуждалось в деталях, буферные предпосылки влияли на результат, а вложенные циклы зависели сразу от кардинальности соединения, внешнего входа и доступных страниц.

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

Позднейшая работа IBM о just-in-time statistics использовала тот же принцип. Когда отдельно собранной статистики нет или она устарела, оптимизатор может запросить целевое наблюдение в момент обнаружения потребности. Он покупает полезную информацию, а не обещает всеведение.

Руководство не отменяет соавторство

Patricia G. Selinger пришла в IBM Research в 1975 году. История IBM связывает её с руководством оптимизатором System R, затем R* и организациями разработки баз данных. В 1994 году она стала IBM Fellow, в 1999-м была избрана в Национальную инженерную академию США, а в 2018-м завершила работу в IBM.

У статьи 1979 года пять авторов. P. Griffiths Selinger работала вместе с Morton M. Astrahan; к ним присоединился Donald D. Chamberlin, а также Raymond A. Lorie и, наконец, Thomas G. Price. В устной истории Chamberlin говорит, что Selinger организовала работу и ключевую статью, но отдельно называет вклад Lorie, Price и Astrahan. Более широкий рассказ IBM включает реляционную модель Edgar Codd, SQL Chamberlin и Raymond Boyce, компилятор Lorie и всю программу System R.

Коллективный контекст уточняет роль лидера. Selinger соединила статистику, селективность, кардинальность, стоимость, полезные физические свойства и ограниченный поиск в реализуемый контракт. Называть это работой одиночки или задним числом «искусственным интеллектом» не нужно.

Сильной оказалась возможность исправления

Наследие System R — не вечный маршрут. Это слой, где смысл запроса стабилен, а физический метод может меняться. Статистика становится богаче, корреляции моделируются, веса приспосабливаются, операторы добавляются, исполнение возвращает обратную связь — без превращения каждого SQL-запроса в ручную процедуру.

Выбранный план — санкционированный прогноз. Он победил в сравнении, которое система смогла провести с доступными свидетельствами. Реальность ещё не вынесла решение.

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

Источники