Ciao, Habr! Vi presento la traduzione dell'articolo
"Come funziona un database relazionale".

Quando si parla di database relazionali, non posso fare a meno di pensare che ci sia qualcosa che manca. Sono utilizzati ovunque. Ci sono molti tipi diversi di database: da SQLite, utile e piccolo, a Teradata, potente. Eppure ci sono solo pochi articoli che spiegano come funziona un database. Puoi cercare tu stesso con "howdoesarelationaldatabasework" per vedere quanti pochi risultati ci siano. Inoltre, questi articoli sono brevi. Se cerchi invece le ultime tecnologie in voga (BigData, NoSQL o JavaScript), troverai articoli più approfonditi che spiegano come funzionano.

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

Come sviluppatore, odio utilizzare ciò che non comprendo. E se i database sono in uso da più di 40 anni, ci deve essere un motivo. In questi anni ho speso centinaia di ore per comprendere davvero queste strane scatole nere che utilizzo ogni giorno. Database relazionali sono molto interessanti perché si basano su concetti utili e riutilizzabili. Se sei interessato a capire i database, ma non hai mai avuto il tempo o la voglia di approfondire questo vasto argomento, ti piacerà leggere questo articolo.

Anche se il titolo di questo articolo è chiaro, l'obiettivo di questo articolo non è farti capire come utilizzare un database. Di conseguenza, dovresti già sapere come scrivere una semplice query di join e query di base CRUD; altrimenti potresti non capire questo articolo. Questo è tutto ciò che devi 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 potrete capire le complessità interne di un database. Poiché questo è un argomento enorme, mi concentrerò su ciò che ritengo importante: come un database gestisce SQL una richiesta. Presenterò solo i concetti fondamentali di un database, in modo che alla fine dell'articolo tu abbia un'idea di ciò che avviene sotto il cofano.

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

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

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

Ritorniamo 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 si potevano permettere di sprecare CPU e memoria sui loro computer lenti.

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

O(1) vs O(n2)

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 sto parlando di migliaia) o se si combatte per millisecondi, diventa critico comprendere questo concetto. E come sai, i database devono affrontare entrambe le situazioni! Non ti farò spendere più tempo del necessario per cogliere l'essenza. Questo ci aiuterà più tardi a capire il concetto di ottimizzazione basata sui costi (cost based optimization).

Concetto

La complessità temporale di un algoritmo è utilizzata per vedere quanto tempo impiega per eseguire l'algoritmo su una certa quantità di dati. Per descrivere questa complessità si utilizzano le notazioni matematiche del grande O. Questa notazione viene usata con una funzione che descrive quante operazioni servono all'algoritmo per un dato quantitativo di dati in ingresso.

Ad esempio, quando dico "questo algoritmo ha una complessità O (some_function() )", significa che per elaborare un certo volume di dati, l'algoritmo richiede some_function(a_certain_amount_of_data) operazioni.

In questo è importante non il numero di dati**, ma come ** aumenta il numero di operazioni all'aumentare del volume 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 diversi tipi di complessità temporali degli algoritmi. Ho utilizzato 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 rimane costante (altrimenti non sarebbe chiamata complessità costante).
• P(registro(n)) rimane bassa anche con miliardi di dati.
• La complessità peggiore è - O(n2), dove il numero di operazioni cresce rapidamente.
• Le altre due complessità aumentano altrettanto rapidamente.

Esempi

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

• L'algoritmo O(1) ti costerebbe 1 operazione
• L'algoritmo O(log(n)) ti costerebbe 7 operazioni
• L'algoritmo O(n) ti costerebbe 2000 operazioni
• L'algoritmo O(n * log(n)) ti costerebbe 14.000 operazioni
• L'algoritmo O(n2) ti costerebbe 4.000.000 operazioni

La differenza tra O(1) e O(n2) sembra grande (4 milioni di operazioni), ma perderesti al massimo 2 ms, solo il tempo per battere le palpebre. Infatti, i moderni processori possono elaborare 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 enormi quantità di dati. Se stavolta l'algoritmo deve elaborare 1.000.000 di elementi (non tanto per un database):

• L'algoritmo O(1) ti costerebbe 1 operazione
• L'algoritmo O(log(n)) ti costerebbe 14 operazioni
• L'algoritmo O(n) ti costerebbe 1.000.000 di operazioni
• L'algoritmo O(n * log(n)) ti costerebbe 14.000.000 di operazioni
• L'algoritmo O(n2) ti costerebbe 1.000.000.000.000 di operazioni

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

Andiamo più a fondo

Per riferimento:

• La ricerca in una buona tabella hash trova un elemento in O(1).
• La ricerca in un albero ben bilanciato dà un risultato in O(log(n)).
• La ricerca in un array dà un risultato in O(n).
• I migliori algoritmi di ordinamento hanno complessità O(n * log(n)).
• Un cattivo algoritmo di ordinamento ha complessità O(n2).

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

Ci sono diversi tipi di complessità temporale per un algoritmo:

• caso medio
• migliore scenario possibile
• e peggiore scenario

La complessità temporale è spesso il peggiore scenario.

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

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

• n⁴: è terribile! Alcuni degli algoritmi menzionati hanno questa complessità.
• 3n: è ancora peggio! Uno degli algoritmi che vedremo più avanti in questo articolo ha questa complessità (e viene davvero utilizzato in molti database).
• fattoriale n: non otterrai mai i tuoi risultati anche con un numero ridotto di dati.
• n^n: se ti imbatti in questa complessità, dovresti chiederti se sia davvero il tuo campo …

Nota: ti ho fornito una definizione non reale della notazione ‘grande O’, ma solo un'idea. Puoi leggere questo articolo per Wikipedie una definizione reale (asintotica).

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().

Ci sono alcuni buoni algoritmi di ordinamento, quindi mi concentrerò su quello più importante: ordinamento per fusione.Forse in questo momento non capisci perché sia utile ordinare i dati, ma dovrai capirlo dopo la parte dedicata all'ottimizzazione delle query. Inoltre, comprendere l'ordinamento per fusione ci aiuterà più tardi a capire l'operazione join generale nei database, chiamata merge upgrade (fusione join).

Fusion (fusione)

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

Diamo un'occhiata a cosa significa in un semplice esempio:

In questa figura, puoi vedere che per costruire l'array ordinato finale di 8 elementi hai bisogno di iterare solo una volta su 2 array di 4 elementi. Poiché entrambi gli array da 4 elementi sono già ordinati:

• 1) confronti entrambi gli elementi attuali nei due array (all'inizio il corrente = il primo)
• 2) quindi prendi il più piccolo per inserirlo in un array di 8 elementi
• 3) e passa al successivo elemento nell'array, dove hai preso l'elemento più piccolo
• e ripeti 1,2,3 fino a raggiungere l'ultimo elemento di uno degli array.
• Poi prendi gli altri elementi dell'altro array per inserirli nell'array di 8 elementi.

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

Ora che abbiamo capito questo trucco, ecco il mio pseudocodice per il 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);

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

Il merge sort divide il problema in problemi più piccoli e poi trova i risultati dei problemi più piccoli per ottenere il risultato del problema originale (nota: questo tipo di algoritmo è chiamato divisione e conquista). Se non capisci questo algoritmo, non preoccuparti; non l'ho capito la prima volta che l'ho visto. Se questo può aiutarti, vedo questo algoritmo come un algoritmo in due fasi:

• Fase di divisione, in cui l'array viene suddiviso in array più piccoli
• Fase di ordinamento, in cui 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 unitari in 3 passaggi. Il numero formale di passaggi è log(N) (poiché N=8, log(N) = 3).

Come lo so?

Sono un genio! In una parola — matematica. L'idea è che ogni passo divide la dimensione dell'array originale per 2. Il numero di passaggi è quante volte puoi dividere l'array originale a metà. Questa è la definizione esatta di logaritmo (in base 2).

Fase di ordinamento

Nella fase di ordinamento, inizi con array unitari (di un solo elemento). Durante ogni fase applichi diverse operazioni di merge e il costo totale è N = 8 operazioni:

• Nella prima fase hai 4 merge che costano 2 operazioni ciascuno
• Nella seconda fase hai 2 merge che costano 4 operazioni ciascuno
• Nella terza fase hai 1 merge che costa 8 operazioni

Poiché ci sono log(N) passaggi, costo totale N * operazioni log(N).

Vantaggi del merge sort

Perché questo algoritmo è così potente?

Perché:

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

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

• Puoi modificarlo per utilizzare contemporaneamente spazio su disco e poca memoria senza costi significativi per l'I/O su disco. L'idea è di caricare in memoria solo le parti che vengono elaborate in quel momento. Questo è importante quando devi ordinare una tabella di diverse gigabyte con solo un buffer di memoria di 100 megabyte.

Nota: questo tipo di algoritmo si chiama ordinamento esterno.

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

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

• Questo algoritmo può trasformare il piombo in oro (davvero!).

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

Array, Albero e Tabella Hash

Ora che comprendiamo l'idea di complessità temporale e ordinamento, devo parlarti di 3 strutture dati. È importante perché esse sono alla base delle moderne basi di dati. Introduco anche il concetto di indice di database.

Array

Un 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 (intero, stringa, data ...).

È così comodo memorizzare e visualizzare i dati; tuttavia, quando hai bisogno di trovare un certo valore, non è adatto.

Ad esempio, se vuoi trovare tutti i ragazzi che lavorano nel Regno Unito, dovrai esaminare ogni riga per determinare se quella riga appartiene al Regno Unito. Questo ti costerà N operazioni, dove N — il numero di righe è abbastanza buono, ma c'è un modo più veloce? È ora di familiarizzare con gli alberi.

Nota: la maggior parte dei moderni database fornisce array avanzati per una memorizzazione efficace delle tabelle: heap-organized tables e index-organized tables. Ma questo non cambia il problema di una rapida ricerca 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 memorizzate nel sottoalbero sinistro
• minore di tutte le chiavi memorizzate nel sottoalbero destro

Vediamo cosa significa visivamente

Idea

Questo albero ha N = 15 elementi. Supponiamo di cercare 208:

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

Ora, supponiamo di cercare 40

• Inizio dalla radice, la cui chiave è 136. Poiché 136 > 40, guardo al sottoalbero sinistro del nodo 136.
• 80 > 40, quindi guardo al sottoalbero sinistro del nodo 80
• 40= 40, il nodo esiste. Estraggo l'identificatore della riga all'interno del nodo (questo non è presente nell'immagine) e guardo nella tabella per il dato identificatore della riga.
• Conoscere l'identificatore della riga mi permette di sapere dove si trovano esattamente i dati nella tabella, e quindi posso ottenerli immediatamente.

Di conseguenza, entrambe le ricerche mi costeranno in base ai livelli all'interno dell'albero. Se leggi attentamente la parte sulla fusione, dovresti notare che qui ci sono log (N) livelli. Quindi, il costo di 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 la nazionalità di qualcuno nella tabella precedente. Supponiamo che tu abbia un albero che contiene il campo "country" (colonna 3) della tabella:

• Se vuoi sapere chi lavora nel Regno Unito
• guardi l'albero per ottenere il nodo che rappresenta il Regno Unito
• all'interno del "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 è stato 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è gruppi di campi) in modo da poter stabilire l'ordine tra le chiavi (cosa che vale 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'attraversamento ordinato dell'albero). Inoltre, quest'operazione non è comoda per l'input/output su disco, poiché dovrai leggere l'intero albero. Dobbiamo trovare un modo per eseguire efficacemente una query di intervallo. Per affrontare questo problema, i moderni database utilizzano una versione modificata dell'albero precedente chiamata B+Tree. Nel B+Tree:

• solo i nodi più bassi (foglie) memorizzano le informazioni (posizione delle righe nella tabella correlata)
• gli altri nodi sono qui per il routing al nodo corretto durante la ricerca.

Come puoi vedere, ci sono più nodi qui (il doppio). In effetti, hai nodi aggiuntivi, i "nodi decisionali", che ti aiutano a trovare il nodo corretto (che memorizza la posizione delle righe nella tabella correlata). Ma la complessità della ricerca rimane 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 da 40 a 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 l'albero ha N nodi. La ricerca di un nodo specifico costa log(N) come nell'albero precedente. Ma, ottenendo questo nodo, riceverai M successori in M operazioni con i riferimenti ai loro successori. Questa ricerca costa solo M+log(N) operazioni rispetto a N operazioni con l'albero precedente. Inoltre, non è necessario leggere l'intero albero (solo M + log (N) nodi), il che significa un minore utilizzo del disco. Se M è basso (ad esempio, 200 righe) e N è grande (1.000.000 righe), questa sarà una GRANDE differenza.

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

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

In altre parole, il B+Tree deve essere auto-organizzato e bilanciato. Fortunatamente, questo è possibile con operazioni intelligenti di cancellazione e inserimento. Ma questo ha un costo elevato: l'inserimento e la cancellazione in un albero B+ costano O(log(N)). Ecco perché alcuni di voi hanno sentito dire che utilizzare troppi indici non è una buona idea. Infatti, rallenti l'inserimento rapido / aggiornamento / eliminazione di una riga nella tabella, poiché il database deve aggiornare gli indici della tabella con un'operazione costosa O(log(N)) per ogni indice. Inoltre, l'aggiunta di indici significa un maggior carico per il gestore delle transazioni (sarà descritto alla fine dell'articolo).

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

Nota: il lettore mi ha detto che, a causa delle ottimizzazioni a basso livello, l'albero B+ deve essere completamente bilanciato.

Hashtable (Tabella Hash)

La nostra ultima struttura dati importante è la tabella hash. È molto utile quando desideri cercare valori rapidamente. Inoltre, comprendere la tabella hash ci aiuterà in seguito a comprendere l'operazione di join generale con il database, chiamata hash join ( hash join). Questa struttura dati è utilizzata anche dal database per memorizzare alcune cose interne (ad esempio, tabella di blocco o pool di buffer, vedremo entrambi questi 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:

• chiave per i vostri elementi
• funzione 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, dovete trovare l'elemento che cercate all'interno del segmento, utilizzando questo confronto.

Un esempio semplice

Prendiamo un esempio pratico:

Questa tabella hash ha 10 segmenti. Poiché sono pigro, ho illustrato solo 5 segmenti, ma so che siete intelligenti, quindi vi lascio immaginare gli altri 5 da soli. Ho usato la funzione hash modulo 10 della 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 nell'area 2,
• …

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

Supponiamo che vogliate 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.
• Vi restituisce l'elemento 78
• La ricerca è costata 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 vogliate 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 è quello corretto.
• Utilizzando questa stessa logica, si prende il secondo elemento (9), il terzo (79), …, l'ultimo (29).
• Elemento non trovato.
• La ricerca è costata 7 operazioni.

Una buona funzione hash

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

Se ora cambio la funzione hash a modulo 1 000 000 dalla chiave (cioè prendendo le ultime 6 cifre), la seconda ricerca costerà solo 1 operazione, poiché nel segmento 000059 non ci sono elementi. Il compito reale è trovare una buona funzione hash che crei segmenti contenenti un numero molto ridotto di elementi..

Nel mio esempio, trovare una buona funzione hash è facile. Ma questo è un esempio semplice; trovare una buona funzione hash è più complesso quando la chiave:

• è una stringa (ad esempio, il cognome)
• è composta da 2 stringhe (ad esempio, il cognome e il nome)
• è composta da 2 stringhe e una data (ad esempio, cognome, nome e data di nascita)
• …

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

Array vs tabella hash

Perché non usare un array?

Hmm, bella domanda.

• Una tabella hash può essere parzialmente caricata in memoria, mentre gli altri segmenti possono rimanere su disco.
• Con un array, devi utilizzare uno spazio contiguo in memoria. Se stai caricando una grande tabella, è molto difficile trovare uno 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