<\/p>\n
SQL Server converts the JOIN expressions written in TSQL to the following join types in the background.<\/p>\n
While performing this conversion, it will execute the query in the following join types, which will work better.<\/p>\n
<\/p>\n
- \n
- NESTED LOOPS JOIN<\/li>\n
- MERGE JOIN<\/li>\n
- HASH JOIN<\/li>\n<\/ul>\n
<\/p>\n
First we will explain the concepts above. We will then use the queries in the topic “Join Types in SQL Server<\/a>” to create examples.<\/p>\n
And we’ll add indexes to some columns to make the query work better.<\/p>\n
After adding an index, we will see how the join process (nested loop, merge, hash) in the background changes.<\/p>\n
<\/p>\n
NESTED LOOPS JOIN<\/h3>\n
Marks one of the tables as inner (inner) and the other as outer, and for each row of the table marked as outer, reads each row in the table marked inner.<\/p>\n
If one of the tables is small and the other is large and the large table has an index in the join column, then this join type will work very well. The following picture will be a good example for you to understand the logic of Nested Loop Join.<\/p>\n
As you can see in the picture below, for each row of the table marked as outer on the left, all rows of the table marked as inner on the right side are checked.<\/p>\n
If there is an index on the join column of the table marked as outer, it will work very well.<\/p>\n
![](\"http:\/\/dbtut.com\/wp-content\/uploads\/2018\/06\/401-1.png\")
<\/p>\n<\/h3>\n
MERGE JOIN<\/h3>\n
If the two tables to join are not small and the two tables are ordered according to the join columns (if there is an index in the join columns), merge join will be the most efficient option.<\/p>\n
<\/p>\n
Let’s go through a sample,<\/p>\n
Consider a join as follows.<\/p>\n
Select * from table1 INNER JOIN table2 ON table1.a = table2.b\r\n<\/pre>\n
<\/p>\n
In column a in the first table there is an index in ordered structure,<\/p>\n
In column b in the secondary table there is an index in ordered structure too.<\/p>\n
As a result of such a join, merge join will work very well because both of the columns to be joined are in ordered structure.<\/p>\n
Merge Join compares two columns in a join with these two columns, and if it is equal, it returns the result.<\/p>\n
![](\"http:\/\/dbtut.com\/wp-content\/uploads\/2018\/06\/589-1.png\")
<\/p>\n<\/p>\n
<\/p>\n
HASH JOIN<\/h3>\n
The type of join we do not like. We do not want to see in the execution plan.<\/p>\n
If large, unordered, and non-indexed tables enter the join process, SQL Server will have to use the HASH JOIN method to join these two tables.<\/p>\n
A hash table is created in the memory by taking the smallest of the two tables.<\/p>\n
Then the large table is scanned and the hash value of the large table is compared to the hash value of the hash table in the memory, and equal values \u200b\u200bare added to the result list.<\/p>\n
Below you can find the image showing the hash join.<\/p>\n
![](\"http:\/\/dbtut.com\/wp-content\/uploads\/2018\/06\/848.png\")
<\/p>\n<\/p>\n
<\/p>\n
Which of these join methods is more efficient?<\/h4>\n
Which join type should we try to convert to which join type?<\/h4>\n
<\/p>\n
When we told Hash join, we said we do not like this join type.<\/p>\n
Let’s illustrate how we can convert a hash join to other join types. I will proceed using queries from my previous article, “Join Types in SQL Server<\/a>“.<\/p>\n
<\/p>\n
For example, let’s open a new query page and paste the\u00a0 INNER JOIN query.<\/p>\n
select s.CityName,my.FoodName from City s\r\nINNER JOIN FamousFood my ON s.ID=my.CityID<\/pre>\n
<\/p>\n
Next, let’s look at how to create the estimated execution plan without running the query by clicking on the Display Estimated Execution plan as shown in the picture below.<\/p>\n
Since there are no indexes in both tables, Table Scan has performed on both tables, and Hash Join has performed afterwards.<\/p>\n
![](\"http:\/\/dbtut.com\/wp-content\/uploads\/2018\/06\/266.png\")
<\/p>\nLet’s run the same script again by adding an index to the join column. For example, add the index to the CityID column in the FamousFood table using the following script.<\/p>\n
USE [Test]\r\nGO\r\nCREATE NONCLUSTERED INDEX [IX_CityID] ON [dbo].[FamousFood]\r\n(\r\n[CityID] ASC\r\n)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, \r\nONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON)\r\nGO<\/pre>\n
<\/p>\n
After adding our index, let’s look at the estimated execution plan just as we did before.<\/p>\n
We always read the execution plan starting from the right side. When we look at the following execution plan;<\/p>\n
First, in the FamousFood table we have index seek from the index named IX_CityID (It goes to the index and finds records that it searched for without searching all of the index)<\/p>\n
Later, it made a table scan (It goes to the index and finds records that it searched for with scanning all of the index) from the City table and concatenated the two results with Nested Loop method,<\/p>\n
Since there is no Clustered Index in the FamousFood table,Sql server uses row id from index named IX_CityID to do RID Lookup and brings the other columns from the table.<\/p>\n
Finally, the results from the previous join and RID Lookup are combined with the Nested Loops join type to produce the result.<\/p>\n
<\/p>\n
What is RID Lookup ?,<\/span><\/h4>\n
What is <\/span>Clustered Index<\/span>?<\/span>,<\/span><\/h4>\n
What are the differences between Clustered and NonClustered Indexes? <\/span><\/h4>\n
<\/p>\n
The answers to your questions can be found in the following articles.<\/span><\/p>\n
“Index Concept and Performance Effect on SQL Server<\/a>“,<\/p>\n
“Statistics Concept and Performance Effect on SQL Server<\/a>“,(Scan, seek operations have been examined in detail in this article.)<\/p>\n
“Difference Between Clustered Index and Non Clustered Index<\/a>”<\/p>\n
![](\"http:\/\/dbtut.com\/wp-content\/uploads\/2018\/06\/311-1.png\")
<\/p>\n<\/p>\n
Let’s put a Clustered Index on the FamousFood table with the following script and then look at the execution plan again.<\/p>\n
USE [Test]\r\nGO\r\nCREATE UNIQUE CLUSTERED INDEX [IX_Clustered] ON [dbo].[FamousFood]\r\n(\r\n[ID] ASC\r\n)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, \r\nDROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON)\r\nGO<\/pre>\n
<\/p>\n
Looking back at the execution plan, Key Lookup came in instead of RID Lookup as follows.<\/p>\n
You can find the RID Lookup and Key Lookup difference in the article “Difference Between Clustered Index and Non Clustered Index<\/a>“.<\/p>\n
![](\"http:\/\/dbtut.com\/wp-content\/uploads\/2018\/06\/209.png\")
<\/p>\n<\/p>\n
Let’s keep improving our query. To remove the TableScan for the Cities table, let’s put an index into the ID column that joins the Cities table.<\/p>\n
I would prefer to place the Clustered Index in this example because the ID column is the determinative column for the Cities table.<\/p>\n
USE [Test]\r\nGO\r\nCREATE UNIQUE CLUSTERED INDEX [IX_Clustered] ON [dbo].[City]\r\n(\r\n[ID] ASC\r\n)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, \r\nDROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON)\r\nGO<\/pre>\n
<\/p>\n
let’s look at the execution plan again.<\/p>\n
As you can see below, the table scan for the Cit<\/span>y<\/span> tab<\/span>le<\/span> returned to the Clustered Index seek.<\/span><\/p>\n
SQL Server was performing Index Seek + Key Lookup in a previous execution plan. <\/span><\/p>\n
As you remember the previous execution plan, the sql server first performs index seek, then join, <\/span>then <\/span>key lookup, and then join again.<\/span><\/p>\n
Instead, it decided that the cost of the Clustered Index Scan + single join process was less.<\/p>\n
Of course, the number of columns in the table, the size of the data can change the sql server’s decision.<\/p>\n
![](\"http:\/\/dbtut.com\/wp-content\/uploads\/2018\/06\/998.png\")
<\/p>\nAs you see in our query, the CityID column of the FamousFood table is joined and the FoodName column of the FamousFood table is also selected in the select section.<\/p>\n
We can use the following script to add the FoodName column to the included field of the IX_CityID index that we created, so that we can use the IX_CityID index instead of the Clustered Index Scan.<\/p>\n
USE [Test]\r\nGO\r\nSET ANSI_PADDING ON\r\nGO\r\nCREATE NONCLUSTERED INDEX [IX_CityID] ON [dbo].[FamousFood]\r\n(\r\n[CityID] ASC\r\n)\r\nINCLUDE ([FoodName]) WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, \r\nDROP_EXISTING = ON, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]\r\nGO\r\n<\/pre>\n
<\/p>\n
After running the script, I see that the clustered index scan process is still on the execution plan.<\/p>\n
Let’s add a few columns to the FamousFood table and fill these columns with meaningless values.<\/p>\n
Use Test\r\nGO\r\nBEGIN TRANSACTION\r\nSET QUOTED_IDENTIFIER ON\r\nSET ARITHABORT ON\r\nSET NUMERIC_ROUNDABORT OFF\r\nSET CONCAT_NULL_YIELDS_NULL ON\r\nSET ANSI_NULLS ON\r\nSET ANSI_PADDING ON\r\nSET ANSI_WARNINGS ON\r\nCOMMIT\r\nBEGIN TRANSACTION\r\nGO\r\nALTER TABLE dbo.FamousFood ADD\r\ntest nchar(10) NULL,\r\ntest2 nchar(10) NULL,\r\ntest3 nchar(10) NULL,\r\ntest4 nchar(10) NULL,\r\ntest5 nchar(10) NULL\r\nGO\r\nALTER TABLE dbo.FamousFood SET (LOCK_ESCALATION = TABLE)\r\nGO\r\nCOMMIT\r\nUSE [Test]\r\nGO\r\nUPDATE [dbo].[FamousFood]\r\n\u00a0\u00a0 SET [test] = '0123456789'\r\n\u00a0\u00a0\u00a0\u00a0\u00a0 ,[test2] = '0123456789'\r\n\u00a0\u00a0\u00a0\u00a0\u00a0 ,[test3] = '0123456789'\r\n\u00a0\u00a0\u00a0\u00a0\u00a0 ,[test4] = '0123456789'\r\n\u00a0\u00a0\u00a0\u00a0\u00a0 ,[test5] = '0123456789'\r\nGO\r\n<\/pre>\n
<\/p>\n
Then we will insert the table to enlarge the table.<\/p>\n
Let’s run the following script to set the value of the ID column to auto-increment before doing the Insert operation.<\/p>\n
BEGIN TRANSACTION\r\nSET QUOTED_IDENTIFIER ON\r\nSET ARITHABORT ON\r\nSET NUMERIC_ROUNDABORT OFF\r\nSET CONCAT_NULL_YIELDS_NULL ON\r\nSET ANSI_NULLS ON\r\nSET ANSI_PADDING ON\r\nSET ANSI_WARNINGS ON\r\nCOMMIT\r\nBEGIN TRANSACTION\r\nGO\r\nCREATE TABLE dbo.Tmp_FamousFood\r\n(\r\nID int NOT NULL IDENTITY (1, 1),\r\nCityID int NULL,\r\nFoodName varchar(100) NULL,\r\ntest nchar(10) NULL,\r\ntest2 nchar(10) NULL,\r\ntest3 nchar(10) NULL,\r\ntest4 nchar(10) NULL,\r\ntest5 nchar(10) NULL\r\n)\u00a0 ON [PRIMARY]\r\nGO\r\nALTER TABLE dbo.Tmp_FamousFood SET (LOCK_ESCALATION = TABLE)\r\nGO\r\nSET IDENTITY_INSERT dbo.Tmp_FamousFood ON\r\nGO\r\nIF EXISTS(SELECT * FROM dbo.FamousFood )\r\nEXEC('INSERT INTO dbo.Tmp_FamousFood (ID, CityID, FoodName, test, test2, test3, test4, test5)\r\nSELECT ID, CityID, FoodName, test, test2, test3, test4, test5 FROM dbo.FamousFood WITH (HOLDLOCK TABLOCKX)')\r\nGO\r\nSET IDENTITY_INSERT dbo.Tmp_FamousFood OFF\r\nGO\r\nDROP TABLE dbo.FamousFood\r\nGO\r\nEXECUTE sp_rename N'dbo.Tmp_FamousFood ', N'FamousFood ', 'OBJECT'\r\nGO\r\nCREATE UNIQUE CLUSTERED INDEX IX_Clustered ON dbo.FamousFood\r\n(\r\nID\r\n) WITH( STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]\r\nGO\r\nCREATE NONCLUSTERED INDEX IX_CityID ON dbo.FamousFood\r\n(\r\nCityID\r\n) INCLUDE (FoodName)\r\n\u00a0WITH( STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]\r\nGO\r\nCOMMIT\r\n\r\n<\/pre>\n<\/p>\n
Then we will I add\u00a0 records to our table using the following script. You can run the script for 1 minute.<\/p>\n
USE [Test]\r\nGO\r\nwhile(1=1)\r\nBEGIN\r\nINSERT INTO [dbo].[FamousFood]\r\n([CityID]\r\n,[FoodName]\r\n,[test]\r\n,[test2]\r\n,[test3]\r\n,[test4]\r\n,[test5])\r\nVALUES\r\n(1\r\n,'Test'\r\n,'0123456789'\r\n,'0123456789'\r\n,'0123456789'\r\n,'0123456789'\r\n,'0123456789')\r\nEND<\/pre>\n
<\/p>\n
Once we stop the script, let’s look at the execution plan again.<\/p>\n
As you can see, I only increased the number of columns and the number of records in the FamousFood table (setting the ID to automatically increase does not affect the execution plan)<\/p>\n
SQL Server did not choose to use the nonclustered index we created in the FamousFood table when the number of rows (data density) in the table was low.<\/p>\n
Since the table is small, it has been estimated that it would be less costly to bring the data over the clustered index.<\/p>\n
But once the data in the table grows, it chose to use the index to cover our query (an index that contains the columns of the select and where expressions).<\/p>\n
Another point that attracts our attention is Merge Join.<\/p>\n
It did not use merge join before.<\/p>\n
Because it was using the clustered index instead of the nonclustered index in the FamousFoods table when doing the join process.<\/p>\n
When we look at the execution plan below;<\/p>\n
ClusteredIndexScan was made using the index named IX_Clustered of the City table. IX_Clustered index has an ID column.<\/p>\n
IndexScan has been made using the index names IX_CityID of the FamousFood Table. IX_CityID index has an CityID column.<\/p>\n
While the table was small, the ID column of the City table was joined with the ID column of the FamousFood table.<\/p>\n
When the table grows, it performs merge join on the ordered columns (with index).<\/p>\n
![](\"http:\/\/dbtut.com\/wp-content\/uploads\/2018\/06\/270.png\")
<\/p>\n<\/p>\n
As you can see, there can be hash join, nested loop or merge join on the same query, based on index and number of records in the table.<\/p>\n
Why does SQL Server perform Index Scan and Clustered Index Scan?<\/p>\n
Can we convert these operations to Clustered Index Seek and Index Seek?<\/p>\n
Because the result set of the join process is getting almost all the rows.<\/p>\n
By filtering the query as follows, the execution plan will return to index seek and clustered index seek.<\/p>\n
select s.CityName,my.FoodName from City s\r\nINNER JOIN FamousFood my ON\u00a0 s.ID=my.CityID\r\nwhere my.CityID=42<\/pre>\n
![](\"http:\/\/dbtut.com\/wp-content\/uploads\/2018\/06\/406.png\")
<\/p>\n<\/p>\n
In the article “Spool Concept in Execution Plan(Eager Spool, Lazy Spool)<\/a>” we will continue to enter the details of the execution plan.<\/p>\n
You can reach our articles by searching for words that contain the subject you are interested.<\/p>\n
<\/p>\n
What are the differences between Index Scan and Index Seek?<\/h4>\n
What are the differences between RID Lookup and KeyLookup?<\/h4>\n
<\/p>\n
The answers to these questions can be found in the article titled “Statistics Concept and Performance Effect on SQL Server<\/a>“.<\/p>\n\n
<\/div>\n