Algoritmi per le Join basati sui blocchi

Nelle versioni di MariaDB/MySQL precedenti alla 5.3 era implementato solo un algoritmo per le Join basato sui blocchi: il Block Nested Loop (BNL), loop sui blocchi annidati. Può essere utilizzato per le Inner Join. MariaDB 5.3 e successivi migliorano l'implementazione delle Join BNL e fornisce una varietà di algoritmi basati sui blocchi adatti alle Inner Join, Outer Join e Semi-Join. Questi algoritmi in MariaDB impiegano un join buffer che immagazzina i record del primo operando join prima di iniziare a cercare le corrispondenze nel secondo operando.

Questa pagina documenta i vari algoritmi di Join basati sui blocchi.

• Block Nested Loop (BNL) join
• Block Nested Loop Hash (BNLH) join
• Block Index join known as Batch Key Access (BKA) join
• Block Index Hash join known as Batch Key Access Hash (BKAH) join

Block Nested Loop Join

La differenza più importante tra l'implementazione del BNL in MariaDB 5.3 e le precedenti versioni è che il primo usa un nuovo formato per i record scritti nel buffer delle join. Questo nuovo formato ha i seguenti vantaggi:

• un uso più efficiente dello spazio nel buffer per i valori NULL e per i tipi di lunghezza variabile (come VARCHAR);
• supporto per i cosiddetti buffer incrementali delle Join, risparmiando spazio nel buffer per le Join a più vie;
• l'algoritmo viene usato anche per le outer join e le semi-join.

Come funziona il Block Nested Loop Join

L'algoritmo effettua un'operazione join fra le tabelle t1 e t2 secondo il seguente schema.
I record del primo operando sono scritti nel buffer delle join uno ad uno, finché il buffer è pieno. I record nel secondo operando sono letti dalla tabella fisica o temporanea uno ad uno. Per ogni record r2 letto dalla tabella t2, viene scensito il buffer delle join; per ogni record r1 del buffer in cui r2 corrisponde a r1, la concatenazione dei campi interessati di r1 e r2 viene aggiunta al risultato della join parziale corrispondente.
Per leggere i record di t2 viene eseguita una scansione completa della tabella, una scansione completa di un indice o una lettura di un intervallo nell'indice. Aolo i record che soddisfano la consizione relativa alla tabella t2 vengono controllati, per sapere corrispondono ai record del buffer delle join.
Quando la scansione della tabella t2 termina, un'altra porzione dei record del primo operando riempe il buffer, e corrisponde a quei record che sono stati estratti da t2.
Il buffer riempe nuovamente e scansisce il recondo operando, cercando corrispondenze nel buffer delle join, e via così fino a quando i record nel primo operando non sono esauriti.
Il numero totale delle scansioni del secondo operando equivale al numero di scritture nel buffer delle join.

Uso più efficiente dello spazio nel buffer delle join

Per i valori NULL non viene usato alcuno spazio all'interno del buffer delle join.
Tutti i valori di tipi di lunghezza variabile non vengono più riempiti con degli zeri.

Buffer delle join incrementali

Se si ha una query con una join di tre tabella (t1, t2, t3), tale che t1 venga unita a t2 e il risultato di questa join venga unito a t3, allora per eseguire la query è possibile usare due join buffer. Il primo join buffer B1 viene usato per immagazzinare i record con i campi della tabella t1, mentre il secondo join buffer B2 contiene i record con i campi della join parziale tra t1 e t2. I campi interessanti dei record r1 di B1 vengono copiati in B2 per i record r1,r2 dalla join parziale fra t1 e t2. Si potrebbe suggerire di registrare in B2 solo un puntatore alle posizioni dei campi r1 che si trovano in B2 e i campi interessanti di t2. Così per ogni record r2 che corrisponde a un record r1 il buffer B2 conterrebbe una referenza ai campi di r1 in B1 e i campi di r2. In questo caso il buffer B2 si definisce incrementale. I buffer incrementali consentono di evitare di copiare i valori dei campi da un buffer a un altro. Inoltre permettono di risparmiare un ammontare di spazio significativo nel buffer, se ci si aspetta che ad un record di t1 corrispondano diverse righe di t2.

Usare i buffer delle join per semplici outer join e semi-join

Se un join buffer viene usato per una semplice left outer join tra le tabelle t1 e t2: t1 LEFT JOIN t2 ON P(t1,t2) allora ogni record r1 registrato nel buffer ha un flag di corrispondenza. Inizialmente questo flag è falso. Appena viene trovata la prima corrispondenza di r1, il flag viene impostato a vero. Quando tutti i candidati di t2 sono stati controllati, i record del buffer vengono scansionati e per quelli che ancora hanno il flag di corrispondenza falso, vengono generate delle righe complementati NULL. Lo stesso flag viene utilizzato per qualsiasi record nel join buffer di una operazione di semi-join: t1 SEMI JOIN t2 ON P(t1,t2) che sia eseguita con un algoritmo basato sui blocchi. Quando questo flag di corrispondenza è impostato a vero per un record r1 nel buffer, non vengono più cercate corrispondenze nella tabella t2.

Usare i buffer delle join per le outer join annidate e semi-join

Block Hash Join

L'argoritmo block based hash è una nuova opzione che può essere usata per le operazioni di join in MariaDB 5.3. Può essere impiegato nei casi in cui vi sono sottocondizioni di equi-join per le tabelle unite con una join; in altre parole, quando le eguaglianze nella forma di t2.f1= e1(t1),...,t2.fn=en(t1) possono essere estratte dalla condizione della full join. Come tutti gli algoritmi basati sui blocchi, anche questo è usa un join buffer riempito con i record del primo operando e cerca attraverso i record del recondo operando per trovare corrispondenze per i record nel buffer.

How Block Hash Join works

For each refill of the join buffer and each record r1 from it the algorithm builds a hash table with the keys constructed over the values e1(r1),...en(r1). Then the records of t2 are looked through. For each record r2 from t2 that the condition pushed to the table t2 a hash key over the fields r2.f1,..., r2.fn is calculated to probe into the hash table. The probing returns those records from the buffer to which r2 matches. As for BNL join algorithm this algorithm scans the second operand as many time as many refills of the buffer occur. Yet it has to look only through the records of one bucket in the hash table when looking for the records to which a record from t2 matches, not through all records in the join buffer as BNL join algorithm does. The implementation of this algorithm in MariaDB builds the hash table with hash keys at the very end of the join buffer. That's why the number of records written into the buffer at one refill is less then for BNL join algorithms. However a much shorter list of possible matching candidates makes this the block hash join algorithm usually much faster then BNL join.

Batch Key Access Join

Batch Keys Access join algorithm performs index look-ups when looking for possible matching candidates provided by the second join operand. With this respect the algorithm behave itself as the regular join algorithm. Yet BKA performs index look-ups for a batch of the records from the join buffer. For conventional database engines like InnoDB/MyISAM it allows to fetch matching candidates in an optimal way. For the engines with remote data store such as FederateX/Spider the algorithm allows to save on transfers between the MySQL node and the data store nodes.

How Batch Keys Access Join works

The implementation of the algorithm in 5.3 heavily exploits the multi-range-read interface and its properties. The interface hides the actual mechanism of fetching possible candidates for matching records from the table to be joined. As any block based join algorithm the BKA join repeatedly fills the join buffer with records of the first operand and for each refill it finds records from the join table that could match the records in the buffer. To find such records it asks the MRR interface to perform index look-ups with the keys constructed over all records from the buffer. Together with each key the interface receives a return address - a reference to the record over which this key has been constructed. The actual implementation functions of the MRR interface organize and optimize somehow the process of fetching the records of the joined table by the received keys. Each fetched record r2 is appended with the return address associated with the key by which the record has been found and the result is passed to the BKA join procedure. The procedure takes the record r1 from the join buffer by the return address, joins it with r2 and checks the join condition. If the condition is evaluated to true the joined records is sent to the result stream of the join operation. So for each record returned by the MRR interface only one record from the join buffer is accessed. The number of records from table t2 fetched by the BKA join is exactly the same as for the regular nested loops join algorithm. Yet BKA join allows to optimize the order in which the records are fetched.

Interaction of BKA join with with the MRR functions

BKA join interacts with the MRR functions respecting the following contract. The join procedure calls the MRR function multi_range_read_init passing it the callback functions that allows to initialize reading keys for the records in the join buffer and to iterate over these keys. It also passes the parameters of the buffer for MRR needs allocated within the join buffer space. Then BKA join repeatedly calls the MRR function multi_range_read_next. The function works as an iterator function over the records fetched by index look-ups with the keys produced by a callback function set in the call of multi_range_read_init. A call of the function multi_range_read_next returns the next fetched record through the dedicated record buffer, and the associated reference to the matched record from the join buffer as the output parameter of the function.

Managing usage of block-based join algorithms

Currently 4 different types of block-based join algorithms are supported. For a particular join operation each of them can be employed with a regular (flat) join buffer or with an incremental join buffer.

Three optimizer switches - 'join_cache_incremental', 'join_cache_hashed', 'join_cache_bka' – and the system variable 'join_cache_level' control what of 8 variants of the block-based algorithms can be used for join operations.

If join_cache_bka is off then BKA and BKAH join algorithms are not allowed. If join_cache_hashed is off then BNLH and BKAH join algorithms are not allowed. If join_cache_incremental is off then no incremental variants of the block-based join algorithms are allowed.

By default the switches join_cache_incremental, join_cache_hashed, join_cache_bka are set to on. However it does not mean that by default any of block-based join algorithms is allowed to be used. All of them are allowed only if the system variable join_cache_level is set to 8. This variable can take an integer value in the interval from 0 to 8.

If the value is set to 8 no block-based algorithm can be used for a join operation. The values from 1 to 8 correspond to the following variants of block-based join algorithms:

• 1 – flat BNL
• 2 – incremental BNL
• 3 – flat BNLH
• 4 – incremental BNLH
• 5 – flat BKA
• 6 – incremental BKA
• 7 – flat BKAH
• 8 – incremental BKAH

If the value of join_cache_level is set no N any of block-based algorithms with the level greater than N is disallowed.

So if join_cache_level is set to 5 no usage of BKAH is allowed and usage of incremental BKA is not allowed either while usage of all remaining variants are controlled by the settings of the optimizer switches join_cache_incremental, join_cache_hashed, join_cache_bka.

By default join_cache_level is set to 1. In other words only usage of flat BNL is allowed.

By default block-based algorithms can be used only for regular (inner) join operations. To allow them for outer join operations (left outer joins and right outer joins) the optimizer switch 'outer_join_with_cache' has to be set to 'on'. Setting the optimizer switch 'semijoin_with_cache' to 'on' allows using these algorithms for semi-join operations.

Currently only incremental variants of the block-based join algorithms can be used for nested outer joins and nested semi-joins.

Size of join buffers

Maximum size of join buffers used by block-based algorithms is controlled by the setting of the system variable 'join_buffer_size'. This value must be big enough in order the join buffer employed for a join operation to contain all interesting fields at least of one joined record.

MariaDB 5.3 introduces the system variable 'join_cache_space_limit' that limits the total memory used for join buffers in a query.

To optimize the usage of the join buffers within the limit set by 'join_cache_space_limit' one should use the optimizer switch 'optimize_join_buffer_size' set to 'on'.

Related MRR settings

To use BKA/BKAH join algorithms for InnoDB/MyISAM one must set the optimizer switch 'mrr' to 'on'. When using these algorithms for InnoDB/MyISAM the overall performance of the join operations can be dramatically improved if the optimizer switch 'mrr_sort_keys' is set 'on'.