Semi Joins in FROM clause (instead of using EXISTS

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

SQL Server 2000 Forums

SQL Server Development (2000)

Semi Joins in FROM clause (instead of using EXISTS

Author

Topic

GreatInca
Posting Yak Master

102 Posts

Posted - 2001-11-28 : 15:37:17

I have a query with a loop join hint on the 2nd join, where the optimizer normally chooses a many to many merge join with 550 input rows. It goes faster. Howevever, it turned the first join from a regular (not many to many) merge join to a hash join. This join is from an EXISTS subquery. I want to put a hint to make it back into a MERGE Right Anti Semi Join, which is the way it was without the loop join hint on the 2nd join to see if it will go faster. With WHERE NOT EXISTS (SubQuery) I have no place to put a join hint on it. Is there any way to define a semi join in the from clause or to put join hints on an Exists()?

izaltsman
A custom title

1139 Posts

Posted - 2001-11-28 : 16:01:04

Not sure if it would work or not (it might clash with your other join hint), but you could try to stick a join hint into the OPTION clause at the end of your query.

btrimpop
Posting Yak Master

214 Posts

Posted - 2001-11-28 : 16:12:38

You should be able to convert the exists clause into a regular join expression and apply your hints from that point.
If you post your select statement I'm sure someone here will be able to come up with a good rewrite.

"In theory there is no difference between theory and practice. But in practice there is!"

GreatInca
Posting Yak Master

102 Posts

Posted - 2001-11-28 : 16:43:24

This is the query and query plan without any hints:

SELECT
BadWords.WordID, BadWords.Word, WordListM.Length,
'"' + CASE
WHEN ASCII(LEFT(BadWords.Word,1))<91 AND ASCII(RIGHT(BadWords.Word,1))<91 THEN UPPER(WordListM.Word)
WHEN ASCII(LEFT(BadWords.Word,1))<91 THEN UPPER(LEFT(WordListM.Word,1)) + RIGHT(WordListM.Word,WordListM.Length-1)
ELSE WordListM.Word
END + '",' AS Suggestion
FROM
(
SELECT WordID, Word, CONVERT(VarChar(50), dbo.metaphone(word,50)) AS Metaphone, CONVERT(int, LEN(Word)*.65) AS LengthL, CONVERT(int,LEN(Word)*1.35) AS LengthH
FROM #Words
WHERE LEN(Word)>1 AND NOT EXISTS (SELECT * FROM WordList_SpellCheck WHERE WordList_SpellCheck.Word=#Words.Word)
) AS BadWords
LEFT OUTER JOIN WordList_Suggestion AS WordListM ON BadWords.Metaphone=WordListM.[Metaphone] AND WordListM.Length BETWEEN BadWords.LengthL AND BadWords.LengthH
ORDER BY BadWords.WordID, BadWords.Word, ABS(LEN(BadWords.Word)-WordListM.Length), LEN(BadWords.Word)-WordListM.Length, Suggestion 222 1 0 NULL NULL 1 NULL 1616.8345 NULL NULL NULL 2.0905166 NULL NULL SELECT 0 NULL
|--Sort(ORDER BY:([#Words].[WordID] ASC, [#Words].[Word] ASC, [Expr1010] ASC, [Expr1011] ASC, [Expr1009] ASC)) 222 2 1 Sort Sort ORDER BY:([#Words].[WordID] ASC, [#Words].[Word] ASC, [Expr1010] ASC, [Expr1011] ASC, [Expr1009] ASC) NULL 1616.8345 1.1261261E-2 2.6984679E-2 84 2.0905166 [#Words].[Word], [#Words].[WordID], [WordListM].[Length], [Expr1009], [Expr1010], [Expr1011] NULL PLAN_ROW 0 1.0
|--Compute Scalar(DEFINE:([Expr1009]='"'+If (ascii(substring([#Words].[Word], 1, 1))<91 AND ascii(right([#Words].[Word], 1))<91) then Convert(upper([WordListM].[Word])) else If (ascii(substring([#Words].[Word], 1, 1))<91) then Convert((upper(substring([WordListM].[Word], 1, 1))+right([WordListM].[Word], [WordListM].[Length]-1))) else Convert([WordListM].[Word])+'",', [Expr1010]=abs(len([#Words].[Word])-[WordListM].[Length]), [Expr1011]=len([#Words].[Word])-[WordListM].[Length])) 222 3 2 Compute Scalar Compute Scalar DEFINE:([Expr1009]='"'+If (ascii(substring([#Words].[Word], 1, 1))<91 AND ascii(right([#Words].[Word], 1))<91) then Convert(upper([WordListM].[Word])) else If (ascii(substring([#Words].[Word], 1, 1))<91) then Convert((upper(substring([WordListM].[Word], 1, 1))+right([WordListM].[Word], [WordListM].[Length]-1))) else Convert([WordListM].[Word])+'",', [Expr1010]=abs(len([#Words].[Word])-[WordListM].[Length]), [Expr1011]=len([#Words].[Word])-[WordListM].[Length]) [Expr1009]='"'+If (ascii(substring([#Words].[Word], 1, 1))<91 AND ascii(right([#Words].[Word], 1))<91) then Convert(upper([WordListM].[Word])) else If (ascii(substring([#Words].[Word], 1, 1))<91) then Convert((upper(substring([WordListM].[Word], 1, 1))+right([WordListM].[Word], [WordListM].[Length]-1))) else Convert([WordListM].[Word])+'",', [Expr1010]=abs(len([#Words].[Word])-[WordListM].[Length]), [Expr1011]=len([#Words].[Word])-[WordListM].[Length] 1616.8345 0.0 1.6168345E-4 84 2.0522707 [#Words].[Word], [#Words].[WordID], [WordListM].[Length], [Expr1009], [Expr1010], [Expr1011] NULL PLAN_ROW 0 1.0
|--Merge Join(Left Outer Join, MANY-TO-MANY MERGE:([Expr1005])=([WordListM].[Metaphone]), RESIDUAL:(([Expr1005]=[WordListM].[Metaphone] AND [WordListM].[Length]>=[Expr1006]) AND [WordListM].[Length]<=[Expr1007])) 222 4 3 Merge Join Left Outer Join MANY-TO-MANY MERGE:([Expr1005])=([WordListM].[Metaphone]), RESIDUAL:(([Expr1005]=[WordListM].[Metaphone] AND [WordListM].[Length]>=[Expr1006]) AND [WordListM].[Length]<=[Expr1007]) NULL 1616.8345 0.001878 0.20340389 74 2.052109 [#Words].[Word], [#Words].[WordID], [WordListM].[Word], [WordListM].[Length] NULL PLAN_ROW 0 1.0
|--Sort(ORDER BY:([Expr1005] ASC)) 222 5 4 Sort Sort ORDER BY:([Expr1005] ASC) NULL 1389.6001 1.1261261E-2 2.2732567E-2 54 1.4606813 [#Words].[Word], [#Words].[WordID], [Expr1005], [Expr1006], [Expr1007] NULL PLAN_ROW 0 1.0
| |--Compute Scalar(DEFINE:([Expr1005]=[dbo].[metaphone](Convert([#Words].[Word]), 50), [Expr1006]=Convert(Convert(len([#Words].[Word]))*0.65), [Expr1007]=Convert(Convert(len([#Words].[Word]))*1.35))) 222 6 5 Compute Scalar Compute Scalar DEFINE:([Expr1005]=[dbo].[metaphone](Convert([#Words].[Word]), 50), [Expr1006]=Convert(Convert(len([#Words].[Word]))*0.65), [Expr1007]=Convert(Convert(len([#Words].[Word]))*1.35)) [Expr1005]=[dbo].[metaphone](Convert([#Words].[Word]), 50), [Expr1006]=Convert(Convert(len([#Words].[Word]))*0.65), [Expr1007]=Convert(Convert(len([#Words].[Word]))*1.35) 1389.6001 0.0 1.3896001E-4 54 1.4266875 [#Words].[Word], [#Words].[WordID], [Expr1005], [Expr1006], [Expr1007] NULL PLAN_ROW 0 1.0
| |--Merge Join(Right Anti Semi Join, MERGE:([WordList_SpellCheck].[Word])=([#Words].[Word]), RESIDUAL:([WordList_SpellCheck].[Word]=[#Words].[Word])) 222 7 6 Merge Join Right Anti Semi Join MERGE:([WordList_SpellCheck].[Word])=([#Words].[Word]), RESIDUAL:([WordList_SpellCheck].[Word]=[#Words].[Word]) NULL 1389.6001 0.0 0.52851915 19 1.4265486 [#Words].[Word], [#Words].[WordID] NULL PLAN_ROW 0 1.0
| |--Clustered Index Scan(OBJECT:([jobing].[dbo].[WordList_SpellCheck].[PK__WordList_SpellCh__0E659BCC]), ORDERED FORWARD) 222 8 7 Clustered Index Scan Clustered Index Scan OBJECT:([jobing].[dbo].[WordList_SpellCheck].[PK__WordList_SpellCh__0E659BCC]), ORDERED FORWARD [WordList_SpellCheck].[Word] 207145.0 0.44943035 0.227938 59 0.67736834 [WordList_SpellCheck].[Word] NULL PLAN_ROW 0 1.0
| |--Sort(ORDER BY:([#Words].[Word] ASC)) 222 9 7 Sort Sort ORDER BY:([#Words].[Word] ASC) NULL 5243.4004 1.1261261E-2 0.10904346 19 0.22065809 [#Words].[Word], [#Words].[WordID] NULL PLAN_ROW 0 1.0
| |--Table Scan(OBJECT:([tempdb].[dbo].[#Words______________________________________________________________________________________________________________000000000212]), WHERE:(len([#Words].[Word])>1)) 222 10 9 Table Scan Table Scan OBJECT:([tempdb].[dbo].[#Words______________________________________________________________________________________________________________000000000212]), WHERE:(len([#Words].[Word])>1) [#Words].[Word], [#Words].[WordID] 5243.4004 3.5455916E-2 9.6521499E-3 25 0.09021613 [#Words].[Word], [#Words].[WordID] NULL PLAN_ROW 0 1.0
|--Index Scan(OBJECT:([jobing].[dbo].[WordList_Suggestion].[IX_WordList_Suggestion_Metaphone_Length] AS [WordListM]), ORDERED FORWARD) 222 34 4 Index Scan Index Scan OBJECT:([jobing].[dbo].[WordList_Suggestion].[IX_WordList_Suggestion_Metaphone_Length] AS [WordListM]), ORDERED FORWARD [WordListM].[Metaphone], [WordListM].[Word], [WordListM].[Length] 91883.0 0.2849859 0.1011498 69 0.3861357 [WordListM].[Metaphone], [WordListM].[Word], [WordListM].[Length] NULL PLAN_ROW 0 1.0

This is the query and plan for the query with the Loop join hint

SELECT
BadWords.WordID, BadWords.Word, WordListM.Length,
'"' + CASE
WHEN ASCII(LEFT(BadWords.Word,1))<91 AND ASCII(RIGHT(BadWords.Word,1))<91 THEN UPPER(WordListM.Word)
WHEN ASCII(LEFT(BadWords.Word,1))<91 THEN UPPER(LEFT(WordListM.Word,1)) + RIGHT(WordListM.Word,WordListM.Length-1)
ELSE WordListM.Word
END + '",' AS Suggestion
FROM
(
SELECT WordID, Word, CONVERT(VarChar(50), dbo.metaphone(word,50)) AS Metaphone, CONVERT(int, LEN(Word)*.65) AS LengthL, CONVERT(int,LEN(Word)*1.35) AS LengthH
FROM #Words
WHERE LEN(Word)>1 AND NOT EXISTS (SELECT * FROM WordList_SpellCheck WHERE WordList_SpellCheck.Word=#Words.Word)
) AS BadWords
LEFT OUTER LOOP JOIN WordList_Suggestion AS WordListM ON BadWords.Metaphone=WordListM.[Metaphone] AND WordListM.Length BETWEEN BadWords.LengthL AND BadWords.LengthH
ORDER BY BadWords.WordID, BadWords.Word, ABS(LEN(BadWords.Word)-WordListM.Length), LEN(BadWords.Word)-WordListM.Length, Suggestion 225 1 0 NULL NULL 1 NULL 1616.8345 NULL NULL NULL 7.7503943 NULL NULL SELECT 0 NULL
|--Sort(ORDER BY:([#Words].[WordID] ASC, [#Words].[Word] ASC, [Expr1010] ASC, [Expr1011] ASC, [Expr1009] ASC)) 225 2 1 Sort Sort ORDER BY:([#Words].[WordID] ASC, [#Words].[Word] ASC, [Expr1010] ASC, [Expr1011] ASC, [Expr1009] ASC) NULL 1616.8345 1.1261261E-2 2.6984679E-2 84 7.7503943 [#Words].[Word], [#Words].[WordID], [WordListM].[Length], [Expr1009], [Expr1010], [Expr1011] NULL PLAN_ROW 0 1.0
|--Compute Scalar(DEFINE:([Expr1009]='"'+If (ascii(substring([#Words].[Word], 1, 1))<91 AND ascii(right([#Words].[Word], 1))<91) then Convert(upper([WordListM].[Word])) else If (ascii(substring([#Words].[Word], 1, 1))<91) then Convert((upper(substring([WordListM].[Word], 1, 1))+right([WordListM].[Word], [WordListM].[Length]-1))) else Convert([WordListM].[Word])+'",', [Expr1010]=abs(len([#Words].[Word])-[WordListM].[Length]), [Expr1011]=len([#Words].[Word])-[WordListM].[Length])) 225 3 2 Compute Scalar Compute Scalar DEFINE:([Expr1009]='"'+If (ascii(substring([#Words].[Word], 1, 1))<91 AND ascii(right([#Words].[Word], 1))<91) then Convert(upper([WordListM].[Word])) else If (ascii(substring([#Words].[Word], 1, 1))<91) then Convert((upper(substring([WordListM].[Word], 1, 1))+right([WordListM].[Word], [WordListM].[Length]-1))) else Convert([WordListM].[Word])+'",', [Expr1010]=abs(len([#Words].[Word])-[WordListM].[Length]), [Expr1011]=len([#Words].[Word])-[WordListM].[Length]) [Expr1009]='"'+If (ascii(substring([#Words].[Word], 1, 1))<91 AND ascii(right([#Words].[Word], 1))<91) then Convert(upper([WordListM].[Word])) else If (ascii(substring([#Words].[Word], 1, 1))<91) then Convert((upper(substring([WordListM].[Word], 1, 1))+right([WordListM].[Word], [WordListM].[Length]-1))) else Convert([WordListM].[Word])+'",', [Expr1010]=abs(len([#Words].[Word])-[WordListM].[Length]), [Expr1011]=len([#Words].[Word])-[WordListM].[Length] 1616.8345 0.0 1.6168345E-4 84 7.7121482 [#Words].[Word], [#Words].[WordID], [WordListM].[Length], [Expr1009], [Expr1010], [Expr1011] NULL PLAN_ROW 0 1.0
|--Nested Loops(Left Outer Join, OUTER REFERENCES:([Expr1005], [Expr1006], [Expr1007]) WITH PREFETCH) 225 4 3 Nested Loops Left Outer Join OUTER REFERENCES:([Expr1005], [Expr1006], [Expr1007]) WITH PREFETCH NULL 1616.8345 0.0 6.7583681E-3 115 7.7119865 [#Words].[Word], [#Words].[WordID], [WordListM].[Word], [WordListM].[Length] NULL PLAN_ROW 0 1.0
|--Compute Scalar(DEFINE:([Expr1005]=[dbo].[metaphone](Convert([#Words].[Word]), 50), [Expr1006]=Convert(Convert(len([#Words].[Word]))*0.65), [Expr1007]=Convert(Convert(len([#Words].[Word]))*1.35))) 225 6 4 Compute Scalar Compute Scalar DEFINE:([Expr1005]=[dbo].[metaphone](Convert([#Words].[Word]), 50), [Expr1006]=Convert(Convert(len([#Words].[Word]))*0.65), [Expr1007]=Convert(Convert(len([#Words].[Word]))*1.35)) [Expr1005]=[dbo].[metaphone](Convert([#Words].[Word]), 50), [Expr1006]=Convert(Convert(len([#Words].[Word]))*0.65), [Expr1007]=Convert(Convert(len([#Words].[Word]))*1.35) 1389.6001 0.0 1.3896001E-4 54 2.3230999 [#Words].[Word], [#Words].[WordID], [Expr1005], [Expr1006], [Expr1007] NULL PLAN_ROW 0 1.0
| |--Hash Match(Left Anti Semi Join, HASH:([#Words].[Word])=([WordList_SpellCheck].[Word]), RESIDUAL:([WordList_SpellCheck].[Word]=[#Words].[Word])) 225 7 6 Hash Match Left Anti Semi Join HASH:([#Words].[Word])=([WordList_SpellCheck].[Word]), RESIDUAL:([WordList_SpellCheck].[Word]=[#Words].[Word]) NULL 1389.6001 0.0 1.5452362 19 2.3229609 [#Words].[Word], [#Words].[WordID] NULL PLAN_ROW 0 1.0
| |--Table Scan(OBJECT:([tempdb].[dbo].[#Words______________________________________________________________________________________________________________000000000212]), WHERE:(len([#Words].[Word])>1)) 225 8 7 Table Scan Table Scan OBJECT:([tempdb].[dbo].[#Words______________________________________________________________________________________________________________000000000212]), WHERE:(len([#Words].[Word])>1) [#Words].[Word], [#Words].[WordID] 5243.4004 3.5455916E-2 9.6521499E-3 25 0.09021613 [#Words].[Word], [#Words].[WordID] NULL PLAN_ROW 0 1.0
| |--Clustered Index Scan(OBJECT:([jobing].[dbo].[WordList_SpellCheck].[PK__WordList_SpellCh__0E659BCC])) 225 9 7 Clustered Index Scan Clustered Index Scan OBJECT:([jobing].[dbo].[WordList_SpellCheck].[PK__WordList_SpellCh__0E659BCC]) [WordList_SpellCheck].[Word] 207145.0 0.44943035 0.227938 59 0.67736834 [WordList_SpellCheck].[Word] NULL PLAN_ROW 0 1.0
|--Index Seek(OBJECT:([jobing].[dbo].[WordList_Suggestion].[IX_WordList_Suggestion_Metaphone_Length] AS [WordListM]), SEEK:([WordListM].[Metaphone]=[Expr1005] AND [WordListM].[Length] >= [Expr1006] AND [WordListM].[Length] <= [Expr1007]) ORDERED FORWARD) 225 31 4 Index Seek Index Seek OBJECT:([jobing].[dbo].[WordList_Suggestion].[IX_WordList_Suggestion_Metaphone_Length] AS [WordListM]), SEEK:([WordListM].[Metaphone]=[Expr1005] AND [WordListM].[Length] >= [Expr1006] AND [WordListM].[Length] <= [Expr1007]) ORDERED FORWARD [WordListM].[Word], [WordListM].[Length] 1.1635251 6.3284999E-3 7.9791513E-5 69 5.3821282 [WordListM].[Word], [WordListM].[Length] NULL PLAN_ROW 0 1389.6001

How do you make it into a regular join and duplicate a semi join without using a left outer join to a Select Distinct subquery with a xxx IS NULL where clause, which is slower?

GreatInca
Posting Yak Master

102 Posts

Posted - 2001-11-28 : 16:45:46

It runs in 5 seconds with 100KB of word data (maximum that can be read through request.form). It runs in 1-2 seconds with a more typical sample of 4-12KB.

btrimpop
Posting Yak Master

214 Posts

Posted - 2001-11-29 : 11:22:32

Something like this I think will let you eliminate the exists clause.

SELECT
BadWords.WordID,
BadWords.Word,
WordListM.Length,
'"' + CASE WHEN ASCII(LEFT(BadWords.Word,1))<91 AND ASCII(RIGHT(BadWords.Word,1))<91 THEN UPPER(WordListM.Word)
WHEN ASCII(LEFT(BadWords.Word,1))<91 THEN UPPER(LEFT(WordListM.Word,1)) + RIGHT(WordListM.Word,WordListM.Length-1)
ELSE WordListM.Word
END + '",' AS Suggestion
FROM (SELECT #Words.WordID,
#Words.Word,
CONVERT(VarChar(50),
dbo.metaphone(#Words.word,50)) AS Metaphone,
CONVERT(int, LEN(#Words.Word)*.65) AS LengthL,
CONVERT(int,LEN(#Words.Word)*1.35) AS LengthH
FROM #Words LEFT JOIN WordList_SpellCheck WLSC ON
(WLSC.Word = #Words.Word)
WHERE LEN(#Words.Word)>1 AND
WLSC.Word is null) AS BadWords LEFT OUTER JOIN WordList_Suggestion AS WordListM ON
(BadWords.Metaphone=WordListM.[Metaphone] AND
WordListM.Length BETWEEN BadWords.LengthL AND BadWords.LengthH)
ORDER BY BadWords.WordID, BadWords.Word, ABS(LEN(BadWords.Word)-WordListM.Length), LEN(BadWords.Word)-WordListM.Length, Suggestion 222 1 0 NULL NULL 1 NULL 1616.8345 NULL NULL NULL 2.0905166 NULL NULL SELECT 0 NULL

"In theory there is no difference between theory and practice. But in practice there is!"

GreatInca
Posting Yak Master

102 Posts

Posted - 2001-11-29 : 12:51:29

Cool. Using the left outer join /isNull didn't need a distinct sort so didn't drag down the query. And also the extra filter step made the optimize estimate many less rows (it overestimates the rowcount with the EXISTS version) going into the join to the suggestions and therefore gave me the plan I was hoping for without using any hints.

There should still be a way to do a semi join / anti semi join in the from clause though becuase a semi join only collects the first match and not all of them. I generally don't like subqueries in the where clause and only use them if it truely needed to be executed for every row instead of something that can be done all at once and spooled (loop join) or hash/merge joined.

Edited by - GreatInca on 11/30/2001 12:19:42

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources