Ciao, Habr! Ti presento la traduzione di un articolo
"Come funziona un database relazionale".

Quando si parla di database relazionali, non posso fare a meno di pensare che manchi qualcosa. Sono utilizzati ovunque. Esistono molteplici database: dal piccolo e utile SQLite al potente Teradata. Eppure, ci sono solo pochi articoli che spiegano come funziona un database. Puoi cercare tu stesso con la query "howdoesarelationaldatabasework" per vedere quanto pochi siano i risultati. Inoltre, questi articoli sono brevi. Se invece cerchi le ultime tecnologie di tendenza (Big Data, NoSQL o JavaScript), troverai più articoli approfonditi che ne spiegano il funzionamento.

I database relazionali sono troppo vecchi e noiosi per essere spiegati al di fuori dei corsi universitari, delle ricerche e dei libri?

Come sviluppatore, odio utilizzare ciò che non comprendo. E se i database sono stati usati per più di 40 anni, un motivo deve esserci. Negli anni ho speso centinaia di ore per comprendere veramente queste strane scatole nere che uso ogni giorno. Basi di dati relazionali sono molto interessanti perché si basano su concetti utili e riutilizzabili. Se siete interessati a comprendere i database, ma non avete mai avuto tempo o voglia di addentrarvi in questo vasto argomento, vi piacerà questo articolo.

Anche se il titolo di questo articolo è esplicito, lo scopo di questo articolo non è capire come utilizzare un database. Di conseguenza, dovreste già sapere come scrivere una semplice query di join e le query di base CRUD; altrimenti, potrebbero esserci parti di questo articolo che non capirete. Questa è l'unica cosa che dovete sapere, spiegherò il resto.

Inizierò con alcune basi dell'informatica, come la complessità temporale degli algoritmi (BigO). So che alcuni di voi odiano questo concetto, ma senza di esso non sarete in grado di comprendere le sfumature all'interno di un database. Poiché questo è un argomento enorme, mi concentrerò su ciò che ritengo importante: come un database gestisce SQL la query. Presenterò solo i concetti fondamentali dei database, affinché alla fine dell'articolo abbiate un'idea di cosa accade dietro le quinte.

Poiché si tratta di un articolo lungo e tecnico che include molti algoritmi e strutture dati, non affrettatevi a leggerlo. Alcuni concetti possono essere complessi da comprendere; potete saltarli e avere comunque un'idea generale.

Per coloro che sono più esperti, questo articolo è suddiviso in 3 parti:

Panoramica dei componenti di database a basso e alto livello
Panoramica del processo di ottimizzazione delle query
Panoramica della gestione delle transazioni e del buffer pool

Tornando alle basi

Molti anni fa (in una galassia lontana lontana...), gli sviluppatori dovevano conoscere esattamente il numero di operazioni che codificavano. Sapevano a memoria i loro algoritmi e le loro strutture dati, perché non potevano permettersi di sprecare CPU e memoria dei loro computer lenti.

In questa parte vi ricorderò alcuni di questi concetti, poiché sono necessari per comprendere i database. Introdurrò anche il concetto di indice del database.

O(1) vs O(n2)

Al giorno d'oggi molti sviluppatori non si preoccupano della complessità temporale degli algoritmi... e hanno ragione!

Ma quando si ha a che fare con grandi quantità di dati (non parlo di migliaia) o se si stanno combattendo per millisecondi, diventa fondamentale comprendere questo concetto. E come sai, i database devono affrontare entrambe le situazioni! Non ti farò spendere più tempo del necessario per afferrare il nocciolo della questione. Questo ci aiuterà in seguito a comprendere il concetto di ottimizzazione basata sui costi (costo basata ottimizzazione).

Concetto

La complessità temporale dell'algoritmo viene utilizzata per vedere quanto tempo richiederà l'esecuzione dell'algoritmo per una data mole di dati. Per descrivere questa complessità, si utilizzano le notazioni matematiche big O. Questa notazione viene usata con una funzione che descrive quante operazioni sono necessarie all'algoritmo per un certo numero di dati in ingresso.

Ad esempio, quando dico "questo algoritmo ha una complessità O (some_function() )", significa che per elaborare una certa quantità di dati l'algoritmo necessita di some_function(a_certain_amount_of_data) operazioni.

In questo modo non è importante il numero di dati**, ma come ** aumenta il numero di operazioni all'aumentare della mole di dati. La complessità temporale non fornisce un numero esatto di operazioni, ma è un buon modo per stimare il tempo di esecuzione.

In questo grafico puoi vedere la dipendenza del numero di operazioni dal volume dei dati in ingresso per vari tipi di complessità temporali degli algoritmi. Ho usato una scala logaritmica per rappresentarli. In altre parole, la quantità di dati aumenta rapidamente da 1 a 1 miliardo. Possiamo vedere che:

O(1) o complessità costante rimangono costanti (altrimenti non sarebbe chiamata complessità costante).
O(log(n)) rimane bassa anche con miliardi di dati.
La complessità peggiore è O(n2), dove il numero di operazioni aumenta rapidamente.
Le altre due complessità aumentano altrettanto rapidamente.

Esempi

Con un numero ridotto di dati, la differenza tra O(1) e O(n2) è trascurabile. Ad esempio, supponiamo che tu abbia un algoritmo che deve elaborare 2000 elementi.

L'algoritmo O(1) ti costerà 1 operazione
L'algoritmo O(log(n)) ti costerà 7 operazioni
L'algoritmo O(n) ti costerà 2000 operazioni
L'algoritmo O(n * log(n)) ti costerà 14.000 operazioni
L'algoritmo O(n2) ti costerà 4.000.000 di operazioni

La differenza tra O(1) e O(n2) sembra grande (4 milioni di operazioni), ma perdi al massimo 2 ms, solo il tempo di battere le palpebre. Infatti, i processori moderni possono gestire centinaia di milioni di operazioni al secondo. Ecco perché le prestazioni e l'ottimizzazione non sono un problema in molti progetti IT.

Come ho già detto, è comunque importante conoscere questo concetto quando si lavora con un grande volume di dati. Se in questo caso l'algoritmo deve gestire 1 000 000 di elementi (che non è poi così tanto per un database):

L'algoritmo O(1) ti costerà 1 operazione
L'algoritmo O(log(n)) richiederà 14 operazioni
L'algoritmo O(n) richiederà 1 000 000 di operazioni
L'algoritmo O(n * log(n)) richiederà 14 000 000 di operazioni
L'algoritmo O(n2) richiederà 1 000 000 000 000 di operazioni

Non ho fatto calcoli, ma direi che con l'algoritmo O(n2) hai il tempo di prendere un caffè (anche due!). Se aggiungi un altro 0 al volume dei dati, avrai tempo per un pisolino.

Andiamo più a fondo

Per riferimento:

La ricerca in una buona tabella hash trova l'elemento in O(1).
La ricerca in un albero ben bilanciato restituisce il risultato in O(log(n)).
La ricerca in un array restituisce il risultato in O(n).
I migliori algoritmi di ordinamento hanno una complessità di O (n * log (n)).
Un algoritmo di ordinamento scadente ha una complessità di O (n²).

Nota: nelle parti successive vedremo questi algoritmi e strutture dati.

Esistono diversi tipi di complessità temporale di un algoritmo:

scenario medio
miglior caso
e peggior caso

La complessità temporale è spesso il peggior caso.

Ho parlato solo della complessità temporale di un algoritmo, ma la complessità si applica anche a:

consumo di memoria dell'algoritmo
consumo di I/O su disco dell'algoritmo

Naturalmente, ci sono complessità peggiori di n², ad esempio:

n⁴: è terribile! Alcuni degli algoritmi menzionati hanno tale complessità.
3n: è ancora peggio! Uno degli algoritmi che vedremo a metà di questo articolo ha questa complessità (ed è realmente utilizzato in molti database).
fattoriale n: non otterrai mai i tuoi risultati anche con un piccolo set di dati.
nⁿ: se ti imbatti in questa complessità, dovresti chiederti se è veramente il tuo campo...

Nota: ti ho fornito solo un'idea della notazione "grande O", non una definizione reale. Puoi leggere quest'articolo in Wikipedia per una vera definizione (asimptotica).

MergeSort (Ordinamento per fusione)

Cosa fai quando devi ordinare una collezione? Cosa? Chiami la funzione sort()... Ok, buona risposta... Ma per i database devi capire come funziona questa funzione sort().

Esistono diversi buoni algoritmi di ordinamento, quindi mi concentrerò su quello più importante: ordinamento per fusione. Forse ora non capisci perché l'ordinamento dei dati sia utile, ma dovrai farlo dopo la parte dedicata all'ottimizzazione delle query. Inoltre, comprendere l'ordinamento per fusione ci aiuterà in seguito a capire l'operazione generale di join nei database, chiamata merge join (fusione join).

Merge (fusione)

Come molti algoritmi utili, l'ordinamento per fusione si basa su un'idea: unire 2 array ordinati di dimensione N / 2 in un array ordinato di N elementi richiede solo N operazioni. Questa operazione è chiamata fusione.

Vediamo cosa significa con un semplice esempio:

In questa illustrazione, è evidente che per costruire l'array finale ordinato di 8 elementi, è sufficiente eseguire un'iterazione una sola volta su due array da 4 elementi. Poiché entrambi gli array da 4 elementi sono già ordinati:

1) si confrontano gli elementi correnti di entrambi gli array (inizialmente, l'elemento corrente = il primo)
2) quindi si prende il più piccolo, per inserirlo nell'array da 8 elementi
3) e si passa all'elemento successivo nell'array da cui si è preso l'elemento più piccolo
e si ripetono i punti 1, 2, 3, finché non si arriva all'ultimo elemento di uno dei due array.
Successivamente, si prendono gli altri elementi dall'altro array, per inserirli nell'array da 8 elementi.

Questo funziona perché entrambi gli array da 4 elementi sono ordinati, e quindi non è necessario 'tornare' in questi array.

Ora che abbiamo compreso questo trucco, ecco il mio pseudocodice per la merge:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //chiamate ricorsive
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //unione dei 2 piccoli array ordinati in uno grande
   array result := merge(new_left_array,new_right_array);
   return result;

Il merge sort suddivide il problema in compiti più piccoli e poi trova i risultati di questi compiti per arrivare al risultato finale (nota: questo tipo di algoritmi è noto come divide et impera). Se non comprendi questo algoritmo, non preoccuparti; anch'io non l'ho capito la prima volta che l'ho visto. Se può aiutarti, vedo questo algoritmo come un processo in due fasi:

Fase di divisione, dove l'array viene suddiviso in array più piccoli
Fase di ordinamento, dove i piccoli array vengono uniti (utilizzando il merge) per formare un array più grande.

Fase di divisione

Nella fase di divisione, l'array viene suddiviso in array unitarie in 3 passaggi. Il numero formale di passaggi è log(N) (dato che N=8, log(N) = 3).

Come lo so?

Sono un genio! In una parola: matematica. L'idea è che ogni passaggio divide la dimensione dell'array originale per 2. Il numero di passaggi è quante volte puoi dividere l'array originale per due. Questa è la definizione esatta del logaritmo (con base 2).

Fase di ordinamento

Nella fase di ordinamento, inizi con array unitari (unici). Durante ogni fase, esegui diverse operazioni di fusione, e il costo totale è N = 8 operazioni:

Nella prima fase hai 4 fusioni, ciascuna costa 2 operazioni
Nella seconda fase hai 2 fusioni, ciascuna costa 4 operazioni
Nella terza fase hai 1 fusione, che costa 8 operazioni

Poiché ci sono log(N) fasi, il costo totale è N * log(N) operazioni.

Vantaggi del merge sort

Perché questo algoritmo è così potente?

Perché:

Puoi modificarlo per ridurre l'uso di memoria, in modo da non creare nuovi array, ma modificare direttamente l'array di input.

Nota: questo tipo di algoritmo è chiamato in—place (ordinamento senza memoria aggiuntiva).

Puoi modificarlo per utilizzare simultaneamente spazio su disco e una piccola quantità di memoria senza costi significativi per l'I/O del disco. L'idea è di caricare in memoria solo le parti attualmente elaborate. Questo è importante quando devi ordinare una tabella di diversi gigabyte usando solo un buffer di memoria di 100 megabyte.

Nota: questo tipo di algoritmo è chiamato ordinamento esterno.

Puoi modificarlo per funzionare su più processi / thread / server.

Ad esempio, l'ordinamento distribuito per fusione è uno dei componenti chiave Hadoop (che è una struttura nei big data).

Questo algoritmo può trasformare il piombo in oro (è vero!).

Questo algoritmo di ordinamento è utilizzato nella maggior parte (se non in tutte) le basi di dati, ma non è l'unico. Se vuoi saperne di più, puoi leggere questo lavoro di ricerca, che discute i pro e i contro dei principali algoritmi di ordinamento nelle basi di dati.

Array, Albero e Tabella Hash

Ora che comprendiamo l'idea della complessità temporale e dell'ordinamento, devo parlarvi di 3 strutture dati. È importante perché esse sono alla base dei moderni database. Introdurrò anche il concetto di indice del database.

Array

Array bidimensionale — la struttura dati più semplice. Una tabella può essere vista come un array. Ad esempio:

Questo array 2D rappresenta una tabella con righe e colonne:

Ogni riga rappresenta un'entità
Le colonne memorizzano le proprietà che descrivono l'entità.
Ogni colonna memorizza dati di un certo tipo (integer, string, date …).

È così conveniente memorizzare e visualizzare i dati, tuttavia, quando avete bisogno di trovare un certo valore, questo non è adatto.

Ad esempio, se desiderate trovare tutte le persone che lavorano nel Regno Unito, dovrete controllare ogni riga per determinare se appartiene al Regno Unito. Questo vi costerà N operazioni, dove N — il numero di righe, il che non è male, ma c'è un modo più veloce? Ora è tempo di familiarizzare con gli alberi.

Nota: la maggior parte dei database moderni fornisce array avanzati per una gestione efficiente delle tabelle: heap-organized tables e index-organized tables. Tuttavia, ciò non risolve il problema della ricerca rapida di una condizione specifica in un gruppo di colonne.

Albero e indice del database

Un albero binario di ricerca è un albero binario con una proprietà speciale, la chiave in ogni nodo deve essere:

maggiore di tutte le chiavi contenute nel sottoalbero sinistro
minore di tutte le chiavi contenute nel sottoalbero destro

Vediamo visivamente cosa significa questo

Idea

Questo albero ha N = 15 elementi. Supponiamo che stia cercando 208:

Inizio dalla radice, il cui valore chiave è 136. Poiché 136<208, guardo il sottoalbero destro del nodo 136.
398>208, quindi guardo il sottoalbero sinistro del nodo 398
250>208, quindi guardo il sottoalbero sinistro del nodo 250
200<208, quindi guardo il sottoalbero destro del nodo 200. Ma 200 non ha un sottoalbero destro, il valore non esiste (perché, se esistesse, sarebbe nel sottoalbero destro di 200).

Ora, supponiamo di cercare 40

Inizio dalla radice, il cui valore chiave è 136. Poiché 136 > 40, guardo il sottoalbero sinistro del nodo 136.
80 > 40, quindi guardo il sottoalbero sinistro del nodo 80
40= 40, il nodo esiste. Estraggo l'identificativo della riga all'interno del nodo (questo non è mostrato nella figura) e controllo nella tabella per questo identificativo di riga.
Conoscere l'identificativo della riga mi consente di sapere esattamente dove si trovano i dati nella tabella, e quindi posso recuperarli istantaneamente.

Di conseguenza, entrambe le ricerche mi costeranno il numero di livelli all'interno dell'albero. Se leggi attentamente la parte sulla sort merge, dovresti notare che qui ci sono log(N) livelli. Quindi, il costo della ricerca è log(N), non male!

Torniamo al nostro problema

Ma questo è molto astratto, quindi torniamo al nostro problema. Invece di un semplice intero, immagina una stringa che rappresenta il paese di qualcuno nella tabella precedente. Supponiamo di avere un albero che contiene il campo "country" (colonna 3) della tabella:

Se vuoi sapere chi lavora nel Regno Unito
guardi nell'albero per ottenere il nodo che rappresenta il Regno Unito
all'interno di "UKnode" troverai la posizione delle registrazioni dei lavoratori nel Regno Unito.

Questa ricerca costerà log(N) operazioni invece di N operazioni se utilizzi direttamente un array. Ciò che hai appena presentato era l'indice del database.

Puoi costruire un albero indice per qualsiasi gruppo di campi (stringa, numero, 2 stringhe, numero e stringa, data...) purché tu abbia una funzione per confrontare le chiavi (cioè i gruppi di campi) in modo da poter stabilire l'ordine tra le chiavi (il che è valido per qualsiasi tipo primitivo nel database).

B+TreeIndex

Sebbene questo albero funzioni bene per ottenere un valore specifico, esiste un GRANDE problema quando hai bisogno di ottenere più elementi tra due valori.Questo costerà O(N) perché dovrai esaminare ogni nodo nell'albero e verificare se si trova tra questi due valori (ad esempio, con un ordinamento dell'albero). Inoltre, questa operazione non è comoda per l'I/O su disco, poiché dovrai leggere l'intero albero. Dobbiamo trovare un modo per eseguire efficacemente la query di intervallo. Per affrontare questo problema, i moderni sistemi di database utilizzano una versione modificata dell'albero precedente chiamata B+Tree. Nell'albero B+Tree:

solo i nodi più bassi (fogli) conservano le informazioni (posizione delle righe nella tabella collegata)
gli altri nodi sono qui per la gestione del routing al nodo corretto durante la ricerca..

Come puoi vedere, qui ci sono più nodi (due volte). Infatti, hai nodi aggiuntivi, 'nodi decisionali', che ti aiutano a trovare il nodo corretto (che conserva la posizione delle righe nella tabella collegata). Ma la complessità della ricerca è ancora O(log(N)) (c'è solo un altro livello). La grande differenza è che i nodi al livello inferiore sono collegati ai loro successori..

Con questo B+Tree, se stai cercando valori tra 40 e 100:

Devi semplicemente cercare 40 (o il valore più vicino dopo 40, se 40 non esiste), come facevi con l'albero precedente.
Poi raccogli i successori di 40, utilizzando riferimenti diretti ai successori, fino a raggiungere 100.

Supponiamo che tu abbia trovato M successori e che l'albero abbia N nodi. La ricerca di un nodo specifico costa log(N), proprio come l'albero precedente. Tuttavia, una volta ottenuto questo nodo, avrai M successori in M operazioni con riferimenti ai loro successori. Questa ricerca costa solo M+log(N) operazioni rispetto a N operazioni con l'albero precedente. Inoltre, non è necessario esaminare l'intero albero (solo M + log(N) nodi), il che significa un minore utilizzo di disco. Se M è basso (ad esempio, 200 righe) e N è grande (1.000.000 righe), questa sarà una GRANDE differenza.

Ma ci sono nuovi problemi qui (di nuovo!). Se aggiungi o rimuovi una riga dal database (e, di conseguenza, dall'indice associato B+Tree):

devi mantenere l'ordine tra i nodi all'interno dell'albero B+Tree, altrimenti non sarai in grado di trovare i nodi all'interno di un albero non ordinato.
devi mantenere il numero minimo possibile di livelli nel B+Tree, altrimenti la complessità temporale in O(log(N)) diventa O(N).

In altre parole, il B+Tree deve essere autoordinato e bilanciato. Fortunatamente, ciò è possibile grazie a operazioni di inserimento e cancellazione intelligenti. Tuttavia, questo ha un costo: l'inserimento e la cancellazione in un B+Tree richiedono O(log(N)). Ecco perché alcuni di voi hanno sentito che l'uso eccessivo di indici non è una buona idea. Infatti, riducete la rapida inserzione/aggiornamento/cancellazione di righe nella tabella, poiché il database deve aggiornare gli indici della tabella con un'operazione costosa O(log(N)) per ciascun indice. Inoltre, l'aggiunta di indici aumenta il carico per il gestore delle transazioni (sarà descritto alla fine dell'articolo).

Per ulteriori informazioni, puoi consultare l'articolo di Wikipedia su B+Tree. Se desideri un esempio di implementazione di un B+Tree in un database, guarda questo articolo e questo articolo da un importante sviluppatore di MySQL. Entrambi si concentrano su come InnoDB (il motore di MySQL) gestisce gli indici.

Nota: un lettore mi ha detto che, a causa delle ottimizzazioni low-level, l'albero B+ deve essere completamente bilanciato.

Hashtable (Tabella hash)

La nostra ultima importante struttura dati è la tabella hash. È molto utile quando si desidera cercare valori rapidamente. Inoltre, comprendere la tabella hash ci aiuterà in seguito a capire l'operazione principale di join con il database, chiamata hash join ( hash join). Questa struttura dati è anche utilizzata dal database per memorizzare alcune cose interne (ad esempio, tabella di blocco o buffer pool, vedremo entrambe queste concetti più avanti).

La tabella hash è una struttura dati che trova rapidamente un elemento in base alla sua chiave. Per costruire una tabella hash è necessario definire:

la chiave per i vostri elementi
la funzione di hash per le chiavi. Gli hash calcolati delle chiavi forniscono la posizione degli elementi (chiamati segmenti ).
funzione per confrontare le chiavi. Una volta trovato il segmento corretto, bisogna trovare l'elemento che si cerca all'interno del segmento, utilizzando questo confronto.

Un esempio semplice

Prendiamo un esempio visivo:

Questa tabella hash ha 10 segmenti. Poiché sono pigro, ho rappresentato solo 5 segmenti, ma so che siete intelligenti, quindi vi lascio immaginare gli altri 5 da soli. Ho utilizzato una funzione hash che opera modulo 10 sulla chiave. In altre parole, conservo solo l'ultima cifra della chiave dell'elemento per trovare il suo segmento:

se l'ultima cifra è 0, l'elemento va nel segmento 0,
se l'ultima cifra è 1, l'elemento va nel segmento 1,
se l'ultima cifra è 2, l'elemento va nel segmento 2,
…

La funzione di confronto che ho usato è semplicemente l'uguaglianza tra due numeri interi.

Supponiamo che tu voglia ottenere l'elemento 78:

La tabella hash calcola il codice hash per 78, che è 8.
La tabella hash guarda nel segmento 8 e il primo elemento che trova è 78.
Ti restituisce l'elemento 78
La ricerca richiede solo 2 operazioni (una per calcolare il valore della funzione hash e l'altra per cercare l'elemento all'interno del segmento).

Ora, supponiamo che tu voglia ottenere l'elemento 59:

La tabella hash calcola il codice hash per 59, che è 9.
La tabella hash cerca nel segmento 9, il primo elemento trovato è 99. Poiché 99!=59, l'elemento 99 non è corretto.
Usando la stessa logica, si prende il secondo elemento (9), il terzo (79), …, fino all'ultimo (29).
Elemento non trovato.
La ricerca ha richiesto 7 operazioni..

Una buona funzione hash.

Come potete vedere, a seconda del valore che cercate, il costo non è lo stesso!

Se ora modifico la funzione hash al modulo 1.000.000 della chiave (cioè, prendendo le ultime 6 cifre), la seconda ricerca costerà solo 1 operazione, poiché nel segmento 000059 non ci sono elementi. La vera sfida è trovare una buona funzione hash che crei segmenti contenenti un numero molto ridotto di elementi..

Nel mio esempio, trovare una buona funzione hash è semplice. Ma si tratta di un esempio semplice; trovare una buona funzione hash è più difficile quando la chiave è:

una stringa (ad esempio, un cognome)
2 stringhe (ad esempio, un cognome e un nome)
2 stringhe e una data (ad esempio, un cognome, un nome e una data di nascita)
…

Con una buona funzione hash, la ricerca nella tabella hash avviene in O(1)..

Array vs tabella hash.

Perché non usare un array?

Hm, buona domanda.

La tabella hash può essere parzialmente caricata in memoria., e gli altri segmenti possono rimanere sul disco.
Con un array, devi utilizzare uno spazio contiguo in memoria. Se carichi una grande tabella è molto difficile trovare spazio contiguo sufficiente..
Per una tabella hash, puoi scegliere la chiave desiderata (ad esempio, il paese e il cognome di una persona).

Per ulteriori informazioni, puoi leggere l'articolo su JavaHashMap, che è un'implementazione efficace di una tabella hash; non è necessario comprendere Java per afferrare i concetti esposti in questo articolo.

Fonte: habr.com