Decoding the Physical Join Operators: How the Right Index Helps!

In the Part1 of decoding the physical join operators, we learned about the different types of physical operators: Nested loops, Merge joins and Hash joins. We have seen when they are useful and how to take advantage of each for the performance of our queries. We have also seen when they are useful and when they needs to be avoided.

In this part, we will know more about these operators and how the indexes really help these operator to perform better so the queries can execute faster.

In order to use the Merge join, the join must include equalities. Meaning the join should have columns of one table equal to column of another table. If the join criteria is range comparisons like inequalities or with greater than, less than and not equal to, then the optimizer will not use a Merge join.

In the part1 of physical join operators, we have joined every single value from the first table to find all the matching values from the second table. What if we just want to only work with few values (For example, lets say we are looking for 6 values) from table 1 instead of all values? For the hash join, SQL Server has to still goes through every single value from the first table before reading any values from the second table. With the nested loops, as soon as we read one row from table 1, SQL Server can look for the matching rows in the second table. We may have a question here, for each of the 6 values we are looking for from table 1, we still have to read all values from the second table for the nested loop join. That can be pretty slow until we create an Index. Index created on the value created on the second table, all the lookups will become very fast. After reading the first row from the outer table, SQL Server can use the index to find the location of the matching row in the inner table. That helps, right? Instead of reading all the values from the second table for 5 times, SQL Server has to just do 5 index lookups to find the matching values. So, it reads 5 values from the table 1 and 5 index lookups from the table 2.

For Hash join, it starts reading all the rows from the first table building the hash table. Then it starts reading the rows in the inner table. It does that until the SQL Server finds the 6 matching rows which means it may have to read all the rows from the second table as well if there is no index. Here, the hash join is so much slower than the nested loop joins.

Merge join has to sort the data first so using the index on the first table that can avoid a sort created by SQL Server own sorting process. If we have the index on the join columns then instead of sorting all the rows in the outer table, we can simply use the index getting the matching rows from the table. If we have the index on the second table for that value column, SQL Server will use that index to get the rows for the merge join.

If we are returning a small fraction of the rows from each table, then nested loops will be efficient. For the hash match, if we are looking for a couple of values in the first table which we can find them easily using the index on the first table, after building the hash table in the build phase and probe the second table using the index on the second table value column as well. With the nested loops, for every value on the first table, the values on the second table can be found by using the index quickly. Nested loops are very good when we are working on couple of rows from each table. If we want to compare the large amounts of data in the first table, we have to do as many index lookups on the second table. In that situations, it is really better to switch to the hash join to full scan the second table.

The switching point difference for the optimizer to choose from the nested loops or hash joins being the fastest can be really small. If you statistics are out of date, in that case, the row estimate can lead the optimizer choose the non-optimal join type causing performance issues.

Examples:

Nested Loop:

use Adventureworks2016
go
select soh.*, sod.*
from 
sales.SalesOrderHeader soh
inner join sales.salesorderdetail sod on soh.SalesOrderID=sod.SalesOrderID
where soh.salesorderid=71832

In the above example, SQL server used Nested loop operator. It used clustered index seek on the outer table and the estimate based on the predicate is 1 and when you observe it did the clustered index seek on the inner table and the estimated number of rows were 15. Here we have an index on the inner table. We need to have index on inner table to avoid the expensive scan operation. Here the clustered index seek operator is executed once because we are only returning one qualified row from the outer table. Here we have two times the compute scalar operator being used because we have two computed columns that we are getting from the two tables.

Merge Join:

Lets create two new tables with columns ID and Rollnumber and insert values into the tables. Since we do not have any unique constraint, no unique index defined on the Rollnumber column of the table, SQL optimizer doesn’t know about the uniqueness of the column. Since the SQL optimizer doesn’t know about the uniqueness, it doesn’t choose the merge join. We can force the merge join in option and check the execution plan.

select * from [dbo].[Table1]
select * from [dbo].[Table2]
select a.*, b.*
from
table1 a
inner join
table2 b
on a.Rollnumber=b.Rollnumber
option (merge join)
go

SQL server has to sort the data first coming from the table 1 and table 2 and used Merge join as we forced the optimizer using the hint in the query. If you look at the memory grant it used 1MB.

When you hover over your mouse to the merge join operator, you will see many to many operation as True. That means SQL server thought there may be duplicate values in the outer table join column because there is no supportive index or check constraint defined.

As it estimated the duplicate values, sql server also created the work table. You can see this information by setting the set statistics IO ON and see the messages tab.

Now, lets go ahead and create a unique nonclustered index on the second table ‘table2’. This is the inner table SQL server chosen in the execution plan. Now SQL server chooses the table 2 as the outer join because now SQL Server knows we have unique values in the table 2. As the rows are directly read from the index we created, explicit sort operator is no more needed.

create unique nonclustered index IDX_rollnumber on table2(Rollnumber)

When you observe the many to many operator, its false now.

As we created the index and as SQL server now know there are unique values in table 2, it did not use the explicit sort and it no longer need to create the work table and so the many to many operator is false this time. Now, lets go ahead and create the nonclustered index on the first table ‘table1’. This time there are no more explicit sort operators as the table column Rollnumber is in the sorted order by the newly created indexe on table 1.

create unique nonclustered index IDX_rollnumber on table1(Rollnumber)

The prerequisite for the Merge join is to have the data sorted by a supportive index or by explicitly having the SQL server use its sort operator in the execution plan.

Hash Match:

Lets run a very simple query to generate the hash match operator by running the below query in Adventureworks2016 database.

select 
p.firstname,
p.lastname,
pp.phonenumber
from person.person p
inner join person.personphone pp
on
p.BusinessEntityID=pp.BusinessEntityID
go

If you see the number of estimated rows, they are matching to the actuals. If the estimates are off when compared to the actuals, then the hash join will actually spill the rows to disk to do the operation which is really expensive.

When you observe the execution plan, personphone table was used as the outer table to create the hash table and the created hash table is probed to the inner table person to get the matching records. You can also see on which columns the probing was done by hovering your mouse over to the hash match operator under the hash keys probe.

Summary:

There are three types of physical join operators. Nested loops, Merge join and Hash join. Nested loops are suitable when joining small tables or small fractions of big tables. Hash joins are better when we are joining all the rows in a table or large tables. Merge join can be efficient if the rows are sorted but sorting is slow but can be faster if indexes are present on the joining columns.

How knowing all this information will help you? You can easily tune your queries by checking the table statistics are up to date and the indexes. One of the important things that will help optimizer to choose the join type and the join order is based on statistics estimate of how many rows it thinks going to come out of each table. While tuning the queries, check for the indexes on the join columns. If they are missing, creating the index help optimizer to choose the nested loop join. If there is no index, it will force the optimizer to use the hash join. By making sure the statistics are up to date and by checking the necessary indexes exists or not will help the optimizer to choose the good enough plan for your queries.

One thought on “Decoding the Physical Join Operators: How the Right Index Helps!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s