В какой последовательности запросы и подзапросы выполняются механизмом SQL?

Вариант 4 близок.

SQL является декларативным: вы говорите оптимизатору запросов, что вы хотите, и он работает наилучшим образом (с учетом время/"стоимость" и т.д.) способ сделать это. Это может варьироваться для внешне идентичных запросов и таблиц в зависимости от статистики, распределения данных, количества строк, параллелизма и бог знает чего еще.

Это означает, что нет фиксированного порядка. Но это не совсем "на лету"

Я видел, что даже с идентичными серверами, схемой, запросами и данными планы выполнения различаются.

Я думаю, что ответ 4 правильный. Есть несколько соображений:

тип подзапроса - коррелирован или нет. Рассмотреть возможность:

SELECT *
FROM   t1
WHERE  id IN (
             SELECT id
             FROM   t2
            )

Здесь подзапрос не связан с внешним запросом. Если количество значений в t2.id невелико по сравнению с t1.id, вероятно, наиболее эффективно сначала выполнить подзапрос и сохранить результат в памяти, а затем просмотреть t1 или индекс в t1.id, сопоставив их с кэшированные значения.

Но если запрос:

SELECT *
FROM   t1
WHERE  id IN (
             SELECT id
             FROM   t2
             WHERE  t2.type = t1.type
            )

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

С другой стороны, РСУБД может быть очень умной и понимать, что существует всего несколько возможных значений для t2.type. В этом случае он все еще может использовать подход, используемый для некоррелированного подзапроса, если он может предположить, что стоимость выполнения подзапроса один раз будет дешевле, чем выполнение его для каждой строки.

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

Если вы хотите что-то прочитать по этим темам, получите копию Inside SQL Server 2008: T-SQL Querying. В нем есть две отдельные главы, посвященные логической и физической обработке запросов в SQL Server.

Обычно это зависит от вашей СУБД, но... Я думаю, что второй ответ более правдоподобен. Основной запрос обычно не может быть рассчитан без результатов подзапроса.