Order of Execution of correlated Sub-queries in select and where clauses and Cross Apply

Question

I'm new to SQL Server. I recently learned that the order of execution is:

From
Where
Group By
Having 
Select 
Order By

Where do correlated subqueries and cross apply fit in the order of execution?

---

I have a query where I have correlated subquery in the select clause. The outer query without the where clause returns 10k rows and after the where clause is applied, it returns 50 rows. Is the correlated sub query executed 10k times or 50 times when the outer query has where clause?

According to the logical order of execution, it should only execute 50 times since select statement is one of the last ones to be executed. But my friend said that it executes 10k times since the optimizer executes this during the "From" logical order of execution. Any thoughts?

Answer 1

One novel feature of the relational model was the separation of the logic representation of data (tables, queries) from the physical (disk files, run-time execution). The list you gave is the logical sequence of a query's clauses. It does not represent the physical sequence in which the run-time engine executes.

There is a component of the DBMS called the query optimizer (QO). Its job is to translate the logical definition of the desired output, i.e. the SQL query, into a reasonably efficient physical implementation. It is free to re-arrange the parts of the query into any provably equivalent configuration.

For example, if the query has an ORDER BY the QO may decide to perform a sort at the end of execution. Alternatively at the outset it may read data that is already known to be in the desired order because of an index. Two very different physical implementations which give the same logical outcome.

The process of choosing the physical implementation is knows as query planning. It is a deep and fascinating topic. Nowadays most DBMS use a cost-based optimiser. Lists of alternative plans are generated, the cost of each is evaluated according to some internal, proprietary cost function, and the cheapest is chosen to be executed for the query. SQL Server's optimizer is based on the Cascades framework. There are many resources on the web that explain it.

To answer your actual question, logically sub-queries in general fit into whichever part of the SQL they are written. If they are embedded in the FROM (..from T1 inner join (select x from t2) as y..) they're considered part of the FROM. If in the SELECT (select a, (select b from c where d='e') as f, g, h..) they're part of the SELECT. Physically, however, they are evaluated wherever the optimizer considers it best to do so.

"Is the correlated sub query executed 10k times or 50 times" - it could be either or none of these. It may be executed once and cached within the run-time. It would depend on the precise SQL, the table definitions, the number of rows involved in each table, what options are set at compile time and run-time. If you want a full explanation ask a new question which includes the definitions of all tables, indexes and constraints. Copy the actual execution plan to https://www.brentozar.com/pastetheplan/. There are plenty of regulars here on DBA.SE who can explain what it means.

Subqueries do present additional optimization challenges. There's a paper "Execution Strategies for SQL Subqueries" by Mostafa Elhemali et al which I found interesting and readable.