Говоря про оптимизацию запросов в реляционных СУБД, обычно имеют в виду такой способ обработки, когда по начальному представлению запроса путем преобразований вырабатывается процедурный план его выполнения. Как правило, невозможно добиться точной оптимизации запроса. Речь идет скорее о рационализации, улучшении запроса. Разные способы реализации запроса могут отличаться в десятки раз по времени выполнения. Соответствующие преобразования начального представления запроса выполняются специальным компонентом СУБД – оптимизатором. Обработка поступившего в систему запроса состоит из пяти этапов.
На первом этапе запрос, заданный на языке запросов, подвергается лексическому и синтаксическому анализу. При этом вырабатывается его внутреннее представление, отражающее структуру запроса и содержащее информацию, которая характеризует объекты БД, упомянутые в запросе (отношения, поля и константы). Информация о хранимых объектах выбирается из каталога БД. Внутреннее представление запроса используется и преобразуется на следующих стадиях обработки запроса.
На втором этапе запрос во внутреннем представлении подвергается логической оптимизации. Могут применяться различные преобразования, улучшающие начальное представление запроса. Гарантируется, что результат выполнения преобразованного запроса совпадает с результатом запроса в начальной форме при соблюдении ограничений целостности, существующих в БД.
Третий этап обработки запроса состоит в выборе на основе информации, которой располагает оптимизатор, альтернативных планов выполнения данного запроса. Для каждого плана оценивается предполагаемая стоимость выполнения запроса. При оценках используется статистическая информация о состоянии БД, доступная оптимизатору. Из полученных альтернативных планов выбирается наиболее дешевый.
На четвертом этапе по внутреннему представлению выбранного плана выполнения запроса формируется выполняемое представление плана.
Наконец, на пятом этапе обработки запроса происходит его реальное выполнение. Это либо выполнение соответствующей подпрограммы, либо вызов интерпретатора с передачей ему для интерпретации выполняемого плана.