Tough Correlated Subquery issue

[steven.fafel]

I am running 2 versions of a correlated subquery. The two version
differ slightly in design but differ tremendously in performance....if
anyone can answer this, you would be awesome.

The "bad" query attempts to build a result set using a correlated
subquery. The part causing the error is that the correlated subquery
is part of a derived table (joining 3 tables). Trying to run the query
takes a long time and the more records in the source table, the
performance is exponentially worse. When i change the derived table to
a fixed table, the query runs fast.

I look at the Execution Plan in Query Analyzer and the majority of time
is taken by the Clustered Index Seek and by the Nested Loops/Inner
Join.
************************************************** ************************************************** ******
here is the "bad" query:
************************************************** ************************************************** ******
SELECT licenseKey, (
SELECT TOP 1 mi.id FROM messages mi
INNER JOIN identities i ON i.id=mi.identityid
INNER JOIN licenses l on i.licenseid=l.id
WHERE l.licenseKey = t1.licenseKey AND category = 'usage'
ORDER BY mi.created DESC
) as messageid
FROM licenses T1
************************************************** ************************************************** ******
here is the "good" query
************************************************** ************************************************** ******
SELECT licenseKey, (
SELECT TOP 1 t2.id FROM temptable T2
WHERE t2.licenseKey = t1.licenseKey
ORDER BY t2.created DESC
) as messageid
FROM licenses T1
************************************************** ************************************************** ******

Thank you in advance

[Alexander Kuznetsov]

it might be that the optimizer underestimates the cardinality of the
subquery:

SELECT TOP 1 mi.id FROM messages mi
INNER JOIN identities i ON i.id=mi.identityid
INNER JOIN licenses l on i.licenseid=l.id
WHERE l.licenseKey = t1.licenseKey AND category = 'usage'
ORDER BY mi.created DESC

and comes up with a plan more appropriate for a small number of orws.
How many rows are there in the temporary table?
Are licenseKey AND category columns in one and the same table?
If yes, you could try to create a computed column named
licenseKey_category AS CAST(licenseKey AS VARCHAR(...)) + ' ' +
category,
create an index on it, and rewrite your subquery instead of

WHERE l.licenseKey = t1.licenseKey AND category = 'usage'

try to use

WHERE l1.licenseKey_category = CAST(licenseKey AS
VARCHAR(...)) + ' usage'

That's just one possibility.

[elite150deluxe]

Thank you for your response...here is a little more information:
1. there are about 170,000 records in the temptable/derived table
2. i accidentally included the "category" criteria...it does affect
the performance either way...sorry, i didn't want to confuse the
issue...
3. The main source table "licenses" contains about 10,000 records
4. When i look at the Execution Plan, it seems to be taking a long
time on the clustered index of the "identities" table. Which seems
weird that is it slowing down dealing with one of the indexes for the
derived table. I wasn't expecting this.

You may be right about the optimizer not assessing this query
correctly. I do not know much about how the optimizer makes
determinations about execution of the query. My hope is that is would
do the following:
1. Retrieve all the rows from the "licenses" table
2. For each row in the "licenses" table, join out to the result
of the derived table using the WHERE clause to restrict the number of
rows in each correlated query.
3. Return the TOP 1 of that correlated query.

here is the "bad" query again (simplified):
************************************************** **************************
SELECT licenseKey, (
SELECT TOP 1 mi.id FROM messages mi
INNER JOIN identities i ON i.id=mi.identityid
INNER JOIN licenses l on i.licenseid=l.id
WHERE l.licenseKey = t1.licenseKey
ORDER BY mi.created DESC
) as messageid
FROM licenses T1
************************************************** **************************

- Steve

Alexander Kuznetsov wrote:

it might be that the optimizer underestimates the cardinality of the
subquery:

SELECT TOP 1 mi.id FROM messages mi
INNER JOIN identities i ON i.id=mi.identityid
INNER JOIN licenses l on i.licenseid=l.id
WHERE l.licenseKey = t1.licenseKey AND category = 'usage'
ORDER BY mi.created DESC

and comes up with a plan more appropriate for a small number of orws.
How many rows are there in the temporary table?
Are licenseKey AND category columns in one and the same table?
If yes, you could try to create a computed column named
licenseKey_category AS CAST(licenseKey AS VARCHAR(...)) + ' ' +
category,
create an index on it, and rewrite your subquery instead of

WHERE l.licenseKey = t1.licenseKey AND category = 'usage'

try to use

WHERE l1.licenseKey_category = CAST(licenseKey AS
VARCHAR(...)) + ' usage'

That's just one possibility.

[jim_geissman]

I have also observed that breaking a query with subqueries into two or
more steps with tables for the interfaces can outperform subqueries by
a substantial amount. Apparently the query planner has much better
knowledge of the scope of the queries. Having discrete tables also
allows building indexes (effectively cross-table indexes) specially
tailored for the final query.

[Erland Sommarskog]

(st**********@gmail.com) writes:

SELECT licenseKey, (
SELECT TOP 1 mi.id FROM messages mi
INNER JOIN identities i ON i.id=mi.identityid
INNER JOIN licenses l on i.licenseid=l.id
WHERE l.licenseKey = t1.licenseKey AND category = 'usage'
ORDER BY mi.created DESC
) as messageid
FROM licenses T1

Correlated subqueries in the SELECT list is rarely good for performance.
Try:

SELECT m.licenseKey, m.id
FROM messages m
JOIN (SELECT l.licenseKey, maxcreated = (mi.created)
FROM messages mi
JOIN identities i ON i.id=mi.identityid
JOIN licenses l on i.licenseid=l.id
GROUP BY l.licenseKey) AS m1 ON m.created = m1.maxcreated

This may or may not yield the same result, depending on how unique
messages.created is. Also, I'm assuming here that every license will
have a match in identities/messages.
--
Erland Sommarskog, SQL Server MVP, es****@sommarskog.se

Books Online for SQL Server 2005 at
http://www.microsoft.com/technet/pro...ads/books.mspx
Books Online for SQL Server 2000 at
http://www.microsoft.com/sql/prodinf...ons/books.mspx

[Alexander Kuznetsov]

Regarding performance of correlated subqueries, I could not agree more.
But your query will not retrieve licenses without messages, and
Steven's query does that. Steven, what are your requirements?