How to interpret correlated subqueries?

Question

EDIT: Both answers are great but I think I must clarify my question.

NOTE: I must indicate that in the following, by executed, I mean logically. I understand that the actual execution made by the particular DBMS may use a completely different approach. So what I will ask is not about the actual execution but rather about the evaluation logic of a correlated subquery.

What I particularly want to know is:

"Why a correlated subquery is executed in this way?" For example, for the example query I have given, why isn't it executed in the following way:

"Return the rows of the cities_stores relation whose store_type is equal to some row's store_type in stores relation. If the resulting relation has at least 1 element, the value of EXISTS clause is TRUE. Otherwise, its value is FALSE."

but rather in this way:

"For each row processed in the outer query (let's call this row as "current row"), process the inner (correlated) subquery, using the current row's values for the attributes not present in the subquery's FROM clause."

and from where can I learn to think about correlated subqueries in the latter method, instead of the former one?

I hope this is not an unwise question to ask but exactly this is what I don't understand.

---

Correlated subqueries are highly confusing me.

Example query from here:

SELECT DISTINCT store_type FROM stores
  WHERE EXISTS (SELECT * FROM cities_stores
                WHERE cities_stores.store_type = stores.store_type);

Initially, I thought that EXISTS clause would have a value that doesn't change for each row of the outer query and that value would be calculated in the following way:

"Return the rows of the cities_stores relation whose store_type is equal to some row's store_type in stores relation. If the resulting relation has at least 1 element, the value of EXISTS clause is TRUE. Otherwise, its value is FALSE."

Had the EXISTS statement evaluated in this way, it would have a value that does not change among various rows for the outer relation and hence, the query would be equivalent to the following:

SELECT DISTINCT store_type FROM stores
  WHERE TRUE; -- Or FALSE, if the subquery did not return any rows.

And of course this made me think how is an EXISTS statement is useful at all?

But apparently, that isn't the way a correlated subquery is executed. Apparently, a correlated subquery is executed in the following way:

"For each row processed in the outer query (let's call this row as "current row"), process the inner (correlated) subquery, using the current row's values for the attributes not present in the subquery's FROM clause."

So finally, what I don't understand:

1. Why is this the way it happens? I mean, why not it doesn't happen in the way I initially thought? (That is: Why it doesn't return the rows of the cities_stores relation whose store_type is equal to some row's store_type in stores relation?) From exactly where am I supposed to interpret that it is how SQL works?

2. In various sources around the internet, I constantly see the following about the correlated subqueries:

   In a correlated subquery, the subquery is evaluated once for each row processed by the outer query.

   But most curiously, a statement similar to this does not exist in MySQL's page about correlated subqueries. So:

   Is that an incompleteness in MySQL manual, or is such a statement simply not required? If it is not required, from where am I supposed to understand that it the way how a correlated subquery is evaluated? Or, as another possibility, is the quote I have given simply a vague statement that is not completely correct? If so, how am I supposed to interpret a correlated subquery?

Answer 1

This specific case (the exists predicate) is a bit of an outlier as far as correlated subqueries go. ish...

Some correlated subqueries are certainly evaluated once for every row in the outer query, but I don't think you can apply that across the board, and I specifically think that's a statement that cannot be applied with authority to the exists predicate.

The SQL example below this paragraph is highly contrived, but nevertheless illustrates an "evaluated once for each row in the outer query" correlated subquery. It's "highly contrived" because a straight relational join would be a much better solution, and in this simple case the join is super easy to write.

select
    team_name
    , (
       select league_name
       from leagues
       where leagues.league_id = teams.league_id
    ) as league_name
from teams

In this instance, each row in the result set is going to contain the name of the league that the team belongs to, because of the correlated subquery. And the correlated subquery is probably going to be run once for each row in the outer query. Maybe.

The thing is, the database's query optimizer might rewrite this as a more efficient join, depending on the database. So even this simple example might not be executed "once per row in the outer query."

Either way, the subquery is dependent on the values returned from the table in the outer query, and that makes it a correlated subquery--because of the correlation with the outer table.

Part of the point of SQL in general is that the specific implementation is not important to you.

You should think in terms of sets of data (think set arithmetic), not in terms of iterations and comparisons per iteration.

The exists predicate doesn't make you any promises about the particular implementation. In general, exists is supposed to take advantage of table statistics and indexes in such a way that it produces a more efficient query plan than many other approaches will (and more efficient than you're likely to come up with on your own).

The actual query that ends up being run is going to be some kind of join, or multiple joins. But you don't need to get worked up about that. That's why your exists clause contains select * instead of identifying specific fields.

The query plan produced by the database engine will figure out which fields it wants to use, which key or keys and which index or indexes matter, etc.

So your exists example is still a correlated subquery, despite the underlying implementation, because the inner query refers to and is logically dependent upon the table in the outer query.

SELECT DISTINCT store_type FROM stores
WHERE EXISTS
    (
    SELECT * FROM cities_stores
    WHERE cities_stores.store_type = stores.store_type
    );

Answer 2

1. The subquery in your example becomes correlated because it refers to a table (stores) in the outer query. This is the definition of a correlated subquery - a subquery which depends on rows in an outer query. What you ask about is an independent subquery not correlated to the main query. You can do that like:

   SELECT DISTINCT store_type FROM stores
       WHERE EXISTS (SELECT * FROM cities_stores, stores
           WHERE cities_stores.store_type = stores.store_type);
   

2. The text is just a way of explaining how a correlated subquery logically works. The MySql manual just explains the same thing in a different way.

Answer 3

A correlated subquery (whether inside EXISTS or not) must be evaluated over and over because some component (usually in its WHERE clause) comes from outside the subquery. In your first example, that's stores.store_type.

An uncorrelated subquery could be evaluated only once and the output saved for repeated use. (MySQL sometimes fails to do this obvious optimization.)

Often, but not always, it is better to turn a subquery into a JOIN.

EXISTS ( SELECT * ... ) is a special case of subquery:

Logically it evaluates the subquery, which could return many rows, then EXISTS checks whether more than zero rows were returned.

However, it can be executed as a "semi join". This means that the subquery need not be completely evaluated, rather it need be evaluated only long enough to see if any row matching the WHERE exists. This is an optimization, especially if cities_stores has multiple rows with the desired store_type. In fact, if there is an INDEX starting with store_type, the subquery is trivial to evaluate.

Is that an incompleteness in MySQL manual, or is such a statement simply not required?

One could argue "How else could the subquery be evaluated? It must be reevaluated for each different value coming in from the outside". And that is how I would say that a correlated subquery is logically executed.