3

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?

migrated from programmers.stackexchange.com Mar 30 '15 at 21:15

This question came from our site for professionals, academics, and students working within the systems development life cycle.

  • 3
    "Had the EXISTS statement evaluated in this way, it would have a value that does not change among various rows for the outer relation". No, your interpretation is wrong. The correlated subquery has =stores.store_type which is a value from the external query. How can it be then result to a value that does not change among various rows for the outer relation? – ypercubeᵀᴹ Mar 30 '15 at 21:20
  • Clarification regarding your update: my comment above is about logical execution. – ypercubeᵀᴹ Mar 31 '15 at 11:17
  • @ypercube Thanks, yes I know but I am asking why isn't this the way it happens? – Utku Mar 31 '15 at 11:21
  • 1
    You are interpreting wrong (in reverse). The whole query should be intrepreted as ""Return the rows of the stores relation whose store_type is equal to some row's store_type in cities_stores relation." – ypercubeᵀᴹ Mar 31 '15 at 11:29
  • 1
    "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." --You are still phrasing this in terms of implementation ("for each row processed..."). The point of SQL and therefore of set-oriented thinking is that you don't think in terms of the underlying implementation. – Craig May 6 '15 at 0:07
3

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
    );
  • Thank you very much. Actually, regarding: You should think in terms of sets of data (think set arithmetic), not in terms of iterations and comparisons per iteration. That's what I want to achieve but I can't manage to fully do so right now. For example, how can I think correlated subqueries in terms of set arithmetic? – Utku Mar 31 '15 at 16:48
  • 1
    @Utku Well, try to think more in terms of what the syntax represents instead of what it is actually doing. Because you don't really know what it's doing (it's looping and doing lookups in various types of indexes and more). So, where exists (select * from t2 where t1.key = t2.key) says that you only want the rows from t1 (the outer table) where the key also exists in the inner table. What you get back is the intersection of the two sets (t1 being one set, t2 being the other, and the result being the intersection containing only keys that exist in both tables). – Craig Mar 31 '15 at 23:41
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.

1

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.

  • Thank you Rick. Actually I am trying to understand the logic behind SQL. I mean, why it behaves in this way rather than another. Especially in the edit part of my question, I tried to clarify the question. (The part where I ask why the query I gave executes in this way, rather than the another way that I described). Would you happen to have any ideas about that part as well? By the way, if that edit seems like it should be asked as a new question, I can do that. – Utku Apr 2 '15 at 8:58
  • 1
    Your edit seems to boil down to "from where can I learn ... about correlated subqueries". Sorry, I have no manuals/textbooks to point you at. I know what I know, and I am happy to share/explain it to others. – Rick James Apr 2 '15 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.