SQL Server - expense of a JOIN?

[generelz]

I am currently involved in a friendly debate with a coworker over whether or not using a query that contains multiple LEFT JOIN statements will have any significant performance impact.

Here is some background:

There are certain parts of our code that simply need to check if something exists. This could be done using a query such as the following:

SELECT id FROM table1 WHERE field = 'value' UNION SELECT id FROM table2 WHERE field = 'value' UNION SELECT id FROM table3 WHERE field = 'value'

and then seeing if there are any rows returned.

Now I think we can all agree that if there is an index on field for all these three tables, this query will be very inexpensive.

There is another part of the code where we need to fetch additional information, which involves following foreign key relationships using LEFT JOIN clauses, something along these lines:

select p.field1, p.field2, f.field1, pc.id, pc.name, 
ppc.id, ppc.name, cspc.id, cspc.name
from table1 p
left join table2 f on p.field2 = f.id
left join table3 cs on p.field3 = cs.id
left join table4 pc on pc.field1 = p.id
left join table4 ppc on pc.field2 = ppc.id
left join table4 cspc on cspc.field1= cs.id
where p.field4 = 'value'

My coworker is of the belief that these LEFT JOINs add a negligable amount of performance hit as long as the indexes are set up correctly, and suggests that we just reuse this query with all the JOINs to satisfy the above case (which is possible even though it is probably tough to see because of how I have obfuscated the queries)

My argument is that first of all this information is extraneous - if the JOINs can be avoided in some cases why don't we just get rid of them, especially since these queries will be run a fair number of times (maybe 10-100 times).

I understand that to accomplish a LEFT JOIN, the database must compute the cartesian product which involves two nested loops - a fairly expensive operation when compared with a simple SELECT from three tables (which would involve just looking at the indexes for those columns in each table, which as I understand it is a constant-time operation).

Could anyone provide some real-world performance numbers and optimization strategies for queries that use lots of JOINs? Should they be avoided like the plague? Are they OK if your indexes can handle them (i.e. you are mostly JOINing on the primary key)?

Thanks for any insight anyone can provide - and I will be happy to provide more information if this is not sufficient.

 

[texuspete00]

Well, what does SQL have to say?

I'm somewhat newish but the server will lay out a blue print of expenses. Like a query plan.

 

[generelz]

Indeed, the query plan for the query with the joins is quite complex. The final query my coworkers just came up with involves 5 LEFT JOIN clauses, which have relative costs of 3% - 6%. It also looks like each JOIN clause is causing a FULL table scan, which is pretty shocking.

Looking at the execution plan for the union/select query, each is resulting in Index Seeks and RID Lookup (anyone care to enlighten me as to what this is?) - and then a sort. It looks like there are some inner joins here but their cost is all 0% (my guess is those are the UNIONs)

 

[generelz]

It also looks like each JOIN clause is causing a FULL table scan, which is pretty shocking.

I verified our indexes on these fields - is it true a JOIN will always result in a full table scan? Why can't it use the index?

 

[generelz]

I verified our indexes on these fields - is it true a JOIN will always result in a full table scan? Why can't it use the index?

Update - it appears our "id" fields (which are the primary key) do not actually have the primary key constraint set on them - so sql server does not know to index these as unique. Yikes! That is why the full scans were coming up.

That is what the PK constraint does, among other things, correct?

 

[Cardboard Hammer]

If you're only checking to see if any rows are returned by this:

SELECT id FROM table1 WHERE field = 'value' UNION SELECT id FROM table2 WHERE field = 'value' UNION SELECT id FROM table3 WHERE field = 'value'

Then you'd get better performance with:

IF 0 < (SELECT count(*) FROM table1 WHERE field = 'value') + (SELECT count(*) FROM table2 WHERE field = 'value') + (SELECT count(*) FROM table3 WHERE field = 'value')
BEGIN
--do whatever needs to be done when the other query returns rows
END

 

[mikeblas]

The query you show in Post #1 seems very odd because it joins against the same table multiple times. This isn't unheard of, but you want a good reason for it. Guessing at it from the query without any context about your database it seems okay, but that's not a high-percentage guess.

I understand that to accomplish a LEFT JOIN, the database must compute the cartesian product which involves two nested loops - a fairly expensive operation when compared with a simple SELECT from three tables (which would involve just looking at the indexes for those columns in each table, which as I understand it is a constant-time operation).

Not exactly. The database could compute the Cartesian product, then go sift out the set of rows that actually match whatever predicates are on the query, sure. But that's not the way it works in practice because the size (and expense) of developing the Cartesian product explodes. Say I have 100,000 customers, and each had 15 orders. Joining customers to orders by making a cartesian product would cause 150 billion rows... and 100,000 scans of the 1.5-million row orders table. Yikes!

Any database that isn't a toy must have an optimizer to figure out how a query might be executed efficiently. The first thing to do is to find a reaosnable way to execute joins so that they only involve the absolutely necessary rows. Of course, users can still write dumb queries:

SELECT * FROM Orders JOIN Customers

gets all 150 billion rows no matter what.Doing

SELECT * FROM Orders JOIN Customers ON Customers.ID = Orders.ID

mean that we should be able to do some nested loops, since you know both access paths can be ordered on the same key, that cut us down from 150 million rows to 1.5 million rows. (And, more importantly, down to one full scan of each table.) Realistically, the user will specify something that limits the query even futher. Maybe not by much:

SELECT * FROM Orders JOIN Customers ON Customers.ID = Orders.ID WHERE Orders.OrderDate BETWEEN '01/01/2005' AND '06/01/2005'

or maybe by a lot:

SELECT * FROM Orders JOIN Customers ON Customers.ID = Orders.ID WHERE Customers.Name = 'Acme Manufacturing'

That last query could be executed in a few different ways, depending on what indexes ware available, what the estimated outputs of the filters are, and so on.

Indeed, the query plan for the query with the joins is quite complex.

The plan shouldn't be that complicated. If you can run it with SET SHOWPLAN_TEXT on, and post the text here, I'll be happy to explain what the operators are doing. Given that, we can execute a couple of other comands and I can ask some questions that should lead you to an optimal query.

is it true a JOIN will always result in a full table scan?

It depends on the query and what limiters you have. You might have a bogus query; you might have a query that's not limied enough. Our, you might have some missing indexes.

That is what the PK constraint does, among other things, correct?

The PRIMARY KEY constraint does indeed create a unique index, yes.

But I guess the big answer to your overriding question is that you probably want to write the query with the joins. The UNION query will always select all rows from each table, then sort them and merge them to prepare the result set. It should try to use an index to resolve the WHERE= predicate, but the sort and merge part is pretty expensive, too.

The JOIN on the other hand, has the opportunity to use indexes to find only the rows that hit the predicate, and any other rows matching your join critera, using indexes. With good indexes, you shouldn't sort in that plan.

That said, I can't see how you'd imagine those two semantiaclly equivalent. You must be leaving out some important details.

Update - it appears our "id" fields (which are the primary key) do not actually have the primary key constraint set on them - so sql server does not know to index these as unique. Yikes! That is why the full scans were coming up.

Well, unique or not, you need an index. You can create indexes independently of the PRIMARY KEY constraint. Do you have any index at all on those ID columns?

 

[generelz]

The query you show in Post #1 seems very odd because it joins against the same table multiple times. This isn't unheard of, but you want a good reason for it. Guessing at it from the query without any context about your database it seems okay, but that's not a high-percentage guess.

Yeah unfortunately it seems in my manual obfuscation I may have changed the meaning of the query. Would you mind if I PM'd you the two queries...I would rather not post the exact contents for everyone to see.

*snip*

The plan shouldn't be that complicated. If you can run it with SET SHOWPLAN_TEXT on, and post the text here, I'll be happy to explain what the operators are doing. Given that, we can execute a couple of other comands and I can ask some questions that should lead you to an optimal query.

Sure, I would be happy to get this to you as well (via PM?). I would love to hear what you have to say - then we can distill something down and I will post the results here in this thread. I would prefer to keep the exact details obfuscated as much as possible...but still keep this thread informative for others.

It depends on the query and what limiters you have. You might have a bogus query; you might have a query that's not limied enough. Our, you might have some missing indexes.

Yep it seems like that is exactly the case - no indexes. This is bad, for obvious reasons!

The PRIMARY KEY constraint does indeed create a unique index, yes.

Is there anything else I need to be aware of with this constraint? Besides creating an implicit unique clustered index, would it improve performance in any other ways when compared to explicitly creating an index on this column?

But I guess the big answer to your overriding question is that you probably want to write the query with the joins. The UNION query will always select all rows from each table, then sort them and merge them to prepare the result set. It should try to use an index to resolve the WHERE= predicate, but the sort and merge part is pretty expensive, too.

I think really the problem is there are two different parts of our code that do two different things - and we are trying to use the same query to accomplish both.

The first problem is finding a row with a given property that could exist in multiple tables (yielding the query with the UNIONs). No foreign key relationships need to be followed here. Is there a better way of querying multiple tables than using a UNION?

The second problem is following foreign key relationships to build a result set that contains the precise information needed. This seems to be the bread and butter of a JOIN, which is why we are using it. Due to the indexes not being present, there is tons of room for optimization both in terms of table structure and probably in the query structure as well.

That said, I can't see how you'd imagine those two semantiaclly equivalent. You must be leaving out some important details.

Yes it appears that my obfuscation of the query has confused the issue a little. Let me know if you'd be open to me PM'ing you the exact queries (and text plans) so we can discuss and distill for the thread.

Well, unique or not, you need an index. You can create indexes independently of the PRIMARY KEY constraint. Do you have any index at all on those ID columns?

Agreed and no there is no index :-(. In this case since that is for sure our primary key and will be from here to eternity, we would probably be better served specifying the PRIMARY KEY constraint and getting the index along with it, no?

Thanks for all your help, Mike!

 

[Cardboard Hammer]

On another note, take the "cost" info provided by Query Analyzer with a grain of salt. I recently had a case of the version of a query alleged to be less costly being in excess of an order of magnitude slower than the more costly version of the query.

 

[Cardboard Hammer]

...

The first problem is finding a row with a given property that could exist in multiple tables (yielding the query with the UNIONs). No foreign key relationships need to be followed here. Is there a better way of querying multiple tables than using a UNION?

...

See post #6

 

[generelz]

See post #6

Ah, I didn't even see that! Thanks!

I guess I should have specified that this query is being issued from a Java program - so the logic to be performed if the row with the given value exists is to be performed in the Java program - not via the database itself, so the SQL IF statement is of little help here. That being said, is this query:

(SELECT count(*) FROM table1 WHERE field = 'value') + (SELECT count(*) FROM table2 WHERE field = 'value') + (SELECT count(*) FROM table3 WHERE field = 'value')

any different performance-wise from this query:

SELECT id FROM table1 WHERE field = 'value' UNION SELECT id FROM table2 WHERE field = 'value' UNION SELECT id FROM table3

Note that in this case I don't really need to get the "id" - I just need the Java logic to check if any rows are returned (or look at a count).

I know the first query will return a count and the second will return 0 or more rows. However the second one may be costlier because the UNIONS will cause a sort to be performed, correct? Is there any way to turn that off?

 

[mikeblas]

Sure, I would be happy to get this to you as well (via PM?). I would love to hear what you have to say - then we can distill something down and I will post the results here in this thread. I would prefer to keep the exact details obfuscated as much as possible...but still keep this thread informative for others.

Sure, particularly if you promise to summarize your findings for the thread. If I'm going to hand out free consulting, I'd rather do it 1:M than 1:1.

You might also email the queries and show plan output to me. (In fact, given the liklihood of followup questions, email is probably best.)

Due to the indexes not being present, there is tons of room for optimization both in terms of table structure and probably in the query structure as well.

Well, you might need to make sure your database model makes sense first. Indeed, you can optimize things by adding indexes and jiggling queries around and so on, but if the underlying model sucks, that means you're just polishing a turd.

Is there a better way of querying multiple tables than using a UNION?

"Better" is dependent on the application, so I want to answer this for what you appear to be doing. That doesn't mean you need to be doing what you're doing, though; maybe you have model problems.

UNION takes two recordsets as operators. It has to remove duplicates from the operators, which is usually done by sorting both sides then merging them, throwing out the duplicates. That is expensive for big recordsets. But if you need that result set, that's the result set you need and what can you do?

I don't think you need that result set. As Cardboard suggested, you can just SELECT COUNT(*) from the tables. That can be better, particularly if the column in the predicate has an index. If that index isn't unique, we have to scan the index starting at the start point to count all the possible rows. (If there's no index, you'll scan the whole table.) You'll do that for each table, even if the first one has a match.

You can use EXISTS and the FASTFIRSTROW hint to try and get better performance. Those will indicate you're just probing for existance, which means the server doesn't have to scan anything.

Thanks for all your help, Mike!

Thanks for remembering to be kind in return. That happens about one-in-ten around here, I'm afraid.

 

[mikeblas]

On another note, take the "cost" info provided by Query Analyzer with a grain of salt. I recently had a case of the version of a query alleged to be less costly being in excess of an order of magnitude slower than the more costly version of the query.

Users often get confused between estimated cost and actual cost.

 

[mikeblas]

any different performance-wise from this query:

It depends on if you have an index on "field", if that index is unique or not, and how many rows are returned for each one.

 

[Cardboard Hammer]

Users often get confused between estimated cost and actual cost.

It doesn't help that Query Analyzer provides "Estimated Execution Plan" and "Execution Plan" and both use estimated cost. But I digress...

 

[generelz]

Sure, particularly if you promise to summarize your findings for the thread. If I'm going to hand out free consulting, I'd rather do it 1:M than 1:1.

You might also email the queries and show plan output to me. (In fact, given the liklihood of followup questions, email is probably best.)

Yes I have a meeting with my coworker in a little while to discuss the missing PRIMARY KEY constraint. After that I hope to persue optimizing the query with the JOINs. I will be happy to summarize my findings of both the table performance tweak and the query performance tweak so that others can benefit from this thread...and the process followed...as well as the information about the JOIN keyword - which I would venture to guess is used very frequently without second thought - but may deserve reconsideration/optimization in some cases!

Well, you might need to make sure your database model makes sense first. Indeed, you can optimize things by adding indexes and jiggling queries around and so on, but if the underlying model sucks, that means you're just polishing a turd.

Unfortunately at this juncture there is no chance of changing the database model. IMHO it is (for the most part) well laid out. Since we have plenty of (paying!) customers using and relying on this data model, changing it is a liability at this point because of migration/backwards compatibility issues. I may be polishing a turd, but I want it to be the shiniest damn turd I can get...

"Better" is dependent on the application, so I want to answer this for what you appear to be doing. That doesn't mean you need to be doing what you're doing, though; maybe you have model problems.

Agreed completely. I think the model is sufficient for now...

*snip*
I don't think you need that result set. As Cardboard suggested, you can just SELECT COUNT(*) from the tables. That can be better, particularly if the column in the predicate has an index. If that index isn't unique, we have to scan the index starting at the start point to count all the possible rows. (If there's no index, you'll scan the whole table.) You'll do that for each table, even if the first one has a match.

You're exactly right, I am not interested in any result set - just if there exists a record in these three tables with the given criterion: field = 'value'.

You can use EXISTS and the FASTFIRSTROW hint to try and get better performance. Those will indicate you're just probing for existance, which means the server doesn't have to scan anything

EXISTS seems promising - I forgot about that - I think I need to shy away from FASTFIRSTROW as that seems to be a SQL Server specific hint - and this query could potentially be run against MySQL and Oracle as well. I believe EXISTS is supported on all three of these databases as it is an ANSI SQL keyword IIRC.

This begs the question - how does EXISTS compare to COUNT. It seems to me that EXISTS is a logical operator - however I am not really performing any logic in the database - I just need a result set that my Java program can handle. Perhaps I could write a query along the lines of (pseudo code)

if exists record in table1 where field = 'value' or exists record in table2 where field = 'value' or exists record in table3 where field = 'value' return 1 else return 0

Then I could just check if the returned row is 1 or 0. How would this compare to a count(*)?

Thanks for remembering to be kind in return. That happens about one-in-ten around here, I'm afraid.

Unfortunately these days most people are not interested in the science or knowledge for the sake of the science or knowledge...but just getting the answer they need quick. At least that is my perjorative statement for the day...

I am of course interested in this for the answer but it is really the process and knowledge gained by going through the process that intrigues me the most.

Once again I am very thankful to you, Mike for taking time out of your assuredly busy day to answer some questions for free.

I also appreciate all the other input others have given - Cardboard Hammer I think you have led me down the right path with the other query I am working on and I very much appreciate that.

Cheers all...

 

[Cardboard Hammer]

Ah, I didn't even see that! Thanks!

You're welcome.

I guess I should have specified that this query is being issued from a Java program - so the logic to be performed if the row with the given value exists is to be performed in the Java program - not via the database itself, so the SQL IF statement is of little help here.

I'd (incorrectly) assumed it was part of a stored procedure. No big deal.

That being said, is this query:

(SELECT count(*) FROM table1 WHERE field = 'value') + (SELECT count(*) FROM table2 WHERE field = 'value') + (SELECT count(*) FROM table3 WHERE field = 'value')

any different performance-wise from this query:

SELECT id FROM table1 WHERE field = 'value' UNION SELECT id FROM table2 WHERE field = 'value' UNION SELECT id FROM table3

Note that in this case I don't really need to get the "id" - I just need the Java logic to check if any rows are returned (or look at a count).

The overall performance of the UNION query can't really be higher (as written), as it'd need to find every matching row and also filter duplicate id. Rewritten as

SELECT field FROM table1 WHERE field = 'value' UNION SELECT field FROM table2 WHERE field = 'value' UNION SELECT field FROM table3

it'd at least have a theoretical chance at being better performing, but I highly doubt it'd compile to yield higher performance.

I know the first query will return a count and the second will return 0 or more rows. However the second one may be costlier because the UNIONS will cause a sort to be performed, correct? Is there any way to turn that off?

You can get rid of the overhead of duplicate filtration by using UNION ALL. Note that UNION doesn't necessarily sort to get rid of duplicates, so don't depend on sorting as a side effect of UNION.

 

[mikeblas]

It doesn't help that Query Analyzer provides "Estimated Execution Plan" and "Execution Plan" and both use estimated cost. But I digress...

The estimated cost is the cost used to develop the plan. It helps the optimizer decide what operations to use. If we estimate something will return five rows, we'll use a different operator (or whole query shape) than if we had estimated it to return five million rows. Both versions of the plan show the estimated cost because it's one of the first steps in investigating why the QO did what it did.

FASTFIRSTROW as that seems to be a SQL Server specific hint - and this query could potentially be run against MySQL and Oracle as well.

Sooner or later, I think you're going to find that you'd rather write back-end specific SQL. Either not bveing able to easily do what you want, or leaving too much perf on the table will make you wish you could use something. You can switch statements around depending on what back end you've connected today (or your customers have configured, or ...)

How would this compare to a count(*)?

Try it and see! The answer depends on a bunch of things that you haven't told us. (Row count, table size, index on Field or not (and what kind), which version of SQL Server you're using, and probably a couple more.)

as well as the information about the JOIN keyword - which I would venture to guess is used very frequently without second thought

I wouldn't worry about using JOIN so much. It's right to try and figure out if there's a better way to skin the cat, but if you have to use JOIN, you have to you JOIN. The server does everything it can to make sure you execute in a reasonable time.

Once again I am very thankful to you, Mike for

No worries, happy to help.

 

[Cardboard Hammer]

...

EXISTS seems promising - I forgot about that - I think I need to shy away from FASTFIRSTROW as that seems to be a SQL Server specific hint - and this query could potentially be run against MySQL and Oracle as well. I believe EXISTS is supported on all three of these databases as it is an ANSI SQL keyword IIRC.

This begs the question - how does EXISTS compare to COUNT. It seems to me that EXISTS is a logical operator - however I am not really performing any logic in the database - I just need a result set that my Java program can handle. Perhaps I could write a query along the lines of (pseudo code)

if exists record in table1 where field = 'value' or exists record in table2 where field = 'value' or exists record in table3 where field = 'value' return 1 else return 0

Then I could just check if the returned row is 1 or 0. How would this compare to a count(*)?

...

This would work for using EXISTS:

SELECT 1
WHERE EXISTS(SELECT * FROM table1 WHERE field = 'value') OR EXISTS(SELECT * FROM table2 WHERE field = 'value') OR EXISTS(SELECT * FROM table3 WHERE field = 'value')

It'd return either 1 row if any match were found or no row if no match was found.

In theory, the EXISTS query should perform as well as the count(*) query in any circumstance, and better in certain circumstances. The reality probably matches theory, but YMMV.

I had forgot about EXISTS, too... oops.

 

[Cardboard Hammer]

The estimated cost is the cost used to develop the plan. It helps the optimizer decide what operations to use. If we estimate something will return five rows, we'll use a different operator (or whole query shape) than if we had estimated it to return five million rows. Both versions of the plan show the estimated cost because it's one of the first steps in investigating why the QO did what it did.

...

I guess that makes sense when looking at it that way, but it's highly misleading when the word "Estimated" appears before all the costs of a node when viewing an "Estimated Execution Plan" but isn't present for the costs of a node when viewing an "Execution Plan."

 

[generelz]

With indexes set appropriately (nonclustered nonunique index on "field" for each table), the following query:

SELECT 1
WHERE EXISTS(SELECT field FROM table1 WHERE field = 'value') OR EXISTS(SELECT field FROM table2 WHERE field = 'value') OR EXISTS(SELECT field FROM table3 WHERE field = 'value')

produces 3 index seeks, a concatenation in parallel with a constant scan aggregated through a left semi join, then computes the scalar (count).

While the following query:

SELECT field FROM table1 WHERE field = 'value' UNION
SELECT field FROM table2 WHERE field = 'value' UNION
SELECT field FROM table3 WHERE field = 'value'

produces 3 index seeks, a concatenation, and a stream aggregate.

For both, each Index Seek takes 1/3rd of the cost of the entire query and is the bulk of the estimated I/O and CPU cost.

Am I right in thinking for all practical purposes these queries would be interchangeable, performance-wise? it seems that the index seek will always be the "loss leader" in terms of CPU/IO cost. Since they are both such simple queries I am not aware of any other room for optimization.

I would like to cook up a query that uses COUNT as well but I am still working on that...I will report back when I come up with one...or if someone wants to suggest one...

Later:

Here is a COUNT query I cooked up. Thoughts?

SELECT SUM(x) 
FROM(SELECT COUNT(1) as x FROM table1 WHERE field = 'value' UNION ALL 
SELECT COUNT(1) as x FROM table2 WHERE field = 'value' UNION ALL 
SELECT COUNT(1) as x FROM table3 WHERE field = 'value') as z

it is producing once again three index seeks, but also a compute scalar/stream aggregate for each COUNT, then another stream aggregate and compute scalar for the SUM (not to mention the query is a little more complex).

Maybe I should try my earlier UNION query using UNION ALL instead?

Even later:

Changing the UNION to a UNION ALL in the second query removes the need for the stream aggregate it appears...

 

[mikeblas]

I guess that makes sense when looking at it that way, but it's highly misleading when the word "Estimated" appears before all the costs of a node when viewing an "Estimated Execution Plan" but isn't present for the costs of a node when viewing an "Execution Plan."

I see them. Is it because you're using Query Analyzer from 2000, and not SSMS from 2005? Either way, I see how "estimated" with two meanings in the same area can be confusing -- though I'm not sure I could suggest a better word, perhaps because I've been around it for too long.

 

[Cardboard Hammer]

I see them. Is it because you're using Query Analyzer from 2000, and not SSMS from 2005? Either way, I see how "estimated" with two meanings in the same area can be confusing -- though I'm not sure I could suggest a better word, perhaps because I've been around it for too long.

Yes, using Query Analyzer, because we're still using 2000. At least now I know for certain that which I had been suspecting. Thanks.