SQL Server and the JOIN operators part 1

Hi Guys!

Today we start to talk about the JOIN operators!
But don’t worry This will be first part because i don’t want bite off more than you can chew

Are you ready to learn all about JOIN?
Let’s go!


Ciao Ragazzi!

Oggi iniziamo a parlare degli operatori di JOIN. 
Non preoccupatevi: l’argomento è vasto ma lo divideremo in più parti per non mettere troppa carne al fuoco.

Siete pronti per imparare tutto ma proprio tutto sugli operatori di JOIN? 
Allora si parte! 

Introduction

First concept: we should know that we have three types of physical join algorithms in SQL Server. They are called hash, nested loops and merge.

The Hash Match algorithm is one of the three available algorithms for joining two tables together. However, it is not only about joining. You may observe below a complete list of the logical operations that Hash Match supports in Hash Join Execution Internals. In this article we will focus onto the Hash Match Algorithm.

Primo concetto: dovete sapere che in SQL Server sono presenti tre tipi diversi di algoritmi fisici di JOIN. Questi tre tipi sono chiamati hash, nested loop e merge.

L'algoritmo di Hash Match è uno dei tre algoritmi utilizzati per effettuare l'operazione di JOIN tra due tabelle. Questo algoritmo viene utilizzato in realtà anche per eseguire altre operazioni logiche che possiamo vedere in questa lista sotto.
In questo articolo ci focalizzeremo sull'algoritmo di Hash Match. 

The Hash functions and the Hash table.

The concept behind this type of JOIN is a mathematical function called of of Hash.
 Hash functions are non-invertible functions that map a string of arbitrary length to a string of predefined length. There are various algorithms that implement hash functions that could have particular useful properties depending on the application.

In general, in a database, a hash function is used to construct a data structure called Hash table. Furthermore, the only property required is that there are no more likely hash values ​​than others.

Il concetto che sta alla base di questo di tipo di JOIN è una funzione matematica detta di di Hash.
Le funzioni di hash sono funzioni non invertibili che mappano una stringa di lunghezza arbitraria in una stringa di lunghezza predefinita. Esistono vari algoritmi che implementano funzioni hash le quali sono avere particolari proprietà utili a seconda della applicazione.

In generale in una base di dati una funzione hash è utilizzata per costruire una struttura dati chiamata Hash table. Inoltre l'unica proprietà richiesta è che non ci siamo valori di hash più probabili di altri.

The Hash Match Algorithm

  The Hash algorithm implemented in SQL Server uses a hash function to construct a hash table.

The JOIN operation has two inputs that are the two tables that you want to put in JOIN.
The algorithm is therefore composed of two phases:
In the first phase called Build Phase the Build table is read and a hash table is constructed in memory.
In the second phase called Probe Phase each row of the probe table is read.
For each row, the hash value is calculated using the same hash function and then it is checked whether it is present in the hash table (ie if a bucket is found).
If it is present, the value will be returned to ouput.

Since the hash table is a structure built in memory, the query optimizer will determine which is the build table by choosing between the two tables the one that has a lower number of records.


 
Let's say now that SQL Server allocates the memory destined to contain our hash table before executing our JOIN. Also (before SQL Server 2017) this amount of memory cannot change during execution.

This limitation becomes a problem if the (estimated) memory is not sufficient. It can happen for example due to not updated statistics associated with our table.

In this case, in fact the hash match algorithm will partition the data to be put in JOIN. The part of the data that is in memory will be processed in the way just said.

The remaining part of the data will be spilled from the disk waiting to be processed.
But in this case the situation becomes complicated...

So many things remain to be said so if you liked this article, remaint anxiously awaiting the second part ...




 L'algoritmo di Hash implementato in SQL Server utilizza una funzione hash per costruire una hash table.

L'operazione di JOIN prevede due inputs che sono le due tabelle che si vogliono mettere in JOIN.  L'algoritmo è quindi composto da due fasi:
Nella prima fase detta Build Phase viene letta la tabella di Build e viene costruita in memoria una hash table.
Nella seconda fase detta Probe Phase viene letta ogni riga della tabella di probe. Per ogni sua riga viene calcolato, tramite la stessa funzione di hash, il valore di hash e poi viene verificato se è presente o meno nella hash table (cioè se viene trovato un bucket). Se è presente verrà ritornato in ouput il valore.

Essendo la hash table una struttura costruita in memoria, il query optimizer determinerà qual'è la tabella di build scegliendo tra le due tabelle quella che ha un numero di record inferiore.

Bene! Adesso abbiamo capito la logica che sta alla base dell'algoritmo di Hash Match!
Diciamo però che SQL Server alloca la memoria destinata a contenere la nostra Hash table prima dell'esecuzione della nostra JOIN. Inoltre (prima di SQL Server 2017) questa quantità di memoria non può variare durante l'esecuzione.

Questa limitazione diventa un problema nel caso in cui la memoria (stimata) non dovesse essere sufficiente. Può capitare ad esempio se le statistiche associate alla nostra tabella non sono aggiornate.

In questo caso infatti l'algoritmo di hash match effettuerà una partizione dei dati da mettere in JOIN. La parte dei dati che stanno in memoria saranno processati nel modo appena detto.

La rimanente parte dei dati verrà recuperata dal disco (in inglese spilled) in attesa di essere processata.
Ma in questo caso la situazione si complica...

Tante cose rimangono da dire per cui se vi è piaciuto questo articolo rimanete in trepidante attesa della seconda parte ...



That's all for today.
If you found this article interesting, then keep following me and subscribe!

See you soon!

Luca Biondi @ SQLServerPerformance blog!

Next Post:https://server.hoit.asia/2019/12/sql-server-trigger-optimization-part-1.html
Previous post: Sargable Queries part 2. Examples