Last chance! 50% off DataCamp Premium
Sale ends in
Come data scientist, ti capiterà spesso di dover gestire grandi quantità di dati. Gestire dati (presenti in quantità massicce) non è affatto semplice. Per farlo nel modo più efficiente possibile, devi capire chiaramente come i dati sono organizzati fisicamente, così da poterli elaborare con tecniche pratiche.
SQL è una competenza imprescindibile per qualsiasi software engineer moderno perché la maggior parte dei software dipende da qualche tipo di dato e si integra bene con un RDBMS (Relational Database Management System). Che si tratti di un’applicazione web, di un’API o di un’applicazione interna, l’RDBMS è sempre presente. E SQL è il linguaggio per interrogare un RDBMS.
Per un data scientist è fondamentale conoscere SQL e le tecniche correlate. Per poter interrogare un RDBMS e ottenere risposte alle domande specifiche che avrai sui dati con cui lavori, SQL è il requisito minimo.
Nel suo ultimo video con DataCamp, David Robinson (Chief Data Scientist @ DataCamp) ci ha mostrato come utilizza SQL in un problema di Data Science. Dagli un’occhiata: il suo workflow è molto interessante.
Oggi imparerai una tecnica chiamata indicizzazione che riguarda principalmente l’organizzazione dei dati all’interno di un database, e ne implementerai alcune con SQL. Questo ti darà una panoramica di come l’indicizzazione può essere usata per memorizzare informazioni in un database e di come può portare a tempi di esecuzione più rapidi.
N.B.: Prima di iniziare a leggere questo tutorial, è altamente consigliato imparare le basi di SQL se non le conosci già. Il corso Intro to SQL for Data Science di DataCamp è un’ottima risorsa se vuoi ripassare le fondamenta di SQL.
Una breve nota sull’organizzazione dei record in un file
Prima di studiare l’indicizzazione, è fondamentale capire come i dati sono organizzati fisicamente all’interno dei file. Ovviamente non entrerai in tutti i dettagli, ma avere una buona panoramica dell’organizzazione ti aiuterà a comprendere molto chiaramente l’indicizzazione. Iniziamo.
L’organizzazione dei record/dati in generale riguarda il modo in cui i record sono memorizzati e, in senso ampio, le organizzazioni possono essere divise in due tipi:
-
Organizzazione ordinata: Tutti i record in un file sono ordinati secondo un certo valore chiave di ricerca. In genere si usa la ricerca binaria per cercare qualsiasi valore presente nel file ordinato. Questo rende la ricerca molto efficiente, poiché la complessità temporale resta entro il tempo logaritmico. Tuttavia, l’inserimento nel file diventa un’operazione costosa perché potresti dover riorganizzare l’intero file per inserire il nuovo elemento.
-
Organizzazione non ordinata: In questo tipo, i record vengono inseriti nel file dove c’è spazio disponibile, di solito alla fine del file. Poiché si usa la ricerca lineare, la ricerca non è efficiente come nella variante precedente, ma l’inserimento non è un’operazione così costosa.
Anche se hai un’organizzazione ordinata dei file, cosa succede se le dimensioni dei blocchi dei file e la dimensione di ciascun record all’interno dei file sono molto grandi? Esploriamolo nella prossima sezione.
Perché serve l’indicizzazione
Inizierai questa sezione comprendendo la motivazione che sta dietro l’uso dell’indicizzazione per archiviare file/informazioni in modo efficiente e come questa migliori le altre operazioni relative a tali file/informazioni.
Immagina di avere una tabella (relazione) che contiene diversi record in un database. I record sono ulteriormente divisi in 1000 blocchi. Graficamente, l’organizzazione è la seguente:
Dall’organizzazione sopra, è chiaro che:
- L’ordinamento è applicato alla prima colonna dei record (considera che si tratta di un sistema di database relazionale in cui i dati sono organizzati in modo tabellare)
- Il numero di blocchi in cui è suddiviso il totale dei dati è 1000 blocchi.
Ricorda che ogni record contiene anche altre colonne, ma per questa organizzazione l’ordine è applicato alla prima colonna e i blocchi sono suddivisi di conseguenza. Ora, se esegui una ricerca binaria per cercare qualcosa all’interno di questa organizzazione di record, il tempo totale impiegato è - $\log_{2}1000$, pari a 10 unità di tempo. È possibile migliorare questo tempo di ricerca?
Certo che sì.
Pensa a questo in relazione al leggere un libro senza avere l’indice. Apri una pagina a caso (o, nel caso della ricerca binaria, apri la pagina centrale del libro) e poi giri le pagine a sinistra e a destra per arrivare a quella che ti interessa. Questo richiede tempo, no?
Ma se il libro avesse una pagina di indice, la ricerca sarebbe ancora più efficiente. Potresti andare alla pagina desiderata semplicemente guardando l’indice. Puoi applicare l’indicizzazione allo stesso modo nella situazione sopra.
Ecco un riepilogo di come puoi applicare qui l’indicizzazione:
- Mantieni un puntatore di blocco per ciascun blocco insieme ai valori ordinati usati nella precedente organizzazione.
Questo comporterà un minor numero di blocchi usati per memorizzare i file di dati. Ora, per cercare un record particolare, dovrai semplicemente cercare in questa nuova organizzazione composta da un numero minore di blocchi e alla fine otterrai il tuo record (se presente) in molto meno tempo. Visualizziamo la cosa. Supponendo che il numero di record indicizzati di nuovo risulti in 8 blocchi, otterrai un’organizzazione come la seguente:
Il tempo di ricerca si ridurrà drasticamente grazie al numero inferiore di blocchi. Supponi di voler cercare il record 90. In questo nuovo schema indicizzato, dovrai prima individuare il relativo puntatore di blocco, che in questo caso è 3, e poi usando questa informazione troverai i record di dati originali in un solo passaggio.
Quindi, il tempo di ricerca in questo caso sarà $\log_{2}8 + 1$ = 4 unità di tempo, che è significativamente inferiore rispetto a prima.
L’esempio precedente introduce l’esigenza di eseguire l’indicizzazione. Ecco alcuni punti sull’indicizzazione da tenere presenti:
- L’ordinamento sui record di dati originali può essere fatto utilizzando un solo campo. Quindi le voci di quel campo possono essere indicizzate di conseguenza. Solo se cerchi usando quel campo otterrai un tempo di ricerca migliorato. (Estremamente importante)
- Gli indici sono anch’essi ordinati.
- Il record di indice contiene due campi (struttura del file di indice)-
- La chiave del file originale
- Puntatore al blocco in cui la chiave è disponibile nei record di dati originali
- Per cercare tra gli indici si usa la ricerca binaria.
- Per accedere a un record tramite le voci indicizzate, il numero medio di accessi ai blocchi richiesto è-
$\log_{2}B_i + 1$, dove $B_i$ è il numero di blocchi nei record indicizzati - L’indice può essere creato su qualsiasi campo della relazione (chiave primaria, chiavi candidate, non chiavi).
Ora, in base all’ordinamento dei record di dati originali e a quanti record manterrai nel file indicizzato, possono esistere molti schemi di indicizzazione. Nella sezione successiva studierai i più diffusi.
Diverse strategie di indicizzazione:
- Indicizzazione densa: Se si crea una voce di indice per ogni valore della chiave di ricerca, si parla di indicizzazione densa. Considera il seguente diagramma per capirlo visivamente.
- Indicizzazione sparsa: Se si crea una voce di indice solo per alcuni record, si parla di indicizzazione sparsa. Ecco un diagramma che lo descrive visivamente.
I diagrammi sopra rendono entrambe le tipologie di indicizzazione piuttosto semplici da capire. Un punto cruciale da sottolineare è che l’esempio di indicizzazione sparsa sopra è una combinazione di indicizzazione densa e sparsa. Questo perché per ogni valore di chiave di ricerca univoco (1, 2 e 3) esiste un indice, ma non c’è un indice per ogni record di dato.
Ora studierai gli altri tipi di schemi di indicizzazione in base al livello dei record. Nell’indicizzazione a livello singolo, il numero di file di indice è uno solo. Ma a volte la dimensione del file di indice diventa così grande che anche il file di indice viene indicizzato. In quel caso si parla di indicizzazione multilivello. Approfondiamo.
Ecco una panoramica delle ulteriori strategie di indicizzazione in base ai livelli.
Indicizzazione a livello singolo:
- Indicizzazione primaria
- Indicizzazione cluster
- Indicizzazione secondaria
Indicizzazione multilivello:
- Albero B
- Albero B+
Studierai tutte le strategie di indicizzazione appartenenti all’indicizzazione a livello singolo. Alla fine di questo tutorial, avrai un link per esplorare gli schemi di indicizzazione multilivello nel caso ti interessino. Esaminiamo ora l’Indicizzazione primaria.
Indicizzazione primaria:
Un indice primario è un file ordinato i cui record sono di lunghezza fissa con due campi:
- Il primo campo coincide con la chiave primaria del file di dati.
- Il secondo campo è un puntatore al blocco di dati in cui è disponibile la chiave primaria. - Fonte
L’indice creato per il primo record di ciascun blocco è detto ancora del blocco (block anchor). Nell’indicizzazione primaria, il numero di voci di indice = il numero di blocchi di dati originali. Il numero medio di accessi ai blocchi utilizzando l’indice primario è:
Fai riferimento al seguente diagramma per capire più chiaramente: 
La figura a destra si riferisce ai record di dati originali suddivisi in diversi blocchi. Nota che la colonna contenente i numeri 1,2,3,...,9 sono le chiavi primarie. La figura a sinistra si riferisce alle voci indicizzate in cui ciascuna voce consiste di:
- La prima voce di ogni blocco di dati (ancora del blocco)
- La seconda voce indica il puntatore al blocco.
Prenditi un momento per pensare che tipo di indicizzazione sia (sparsa o densa). Usa la sezione dei commenti per pubblicare le tue risposte.
Ora passerai a studiare l’Indicizzazione cluster.
Indicizzazione cluster:
Un indice cluster viene creato su un file di dati i cui record sono fisicamente ordinati in base a un attributo non chiave che non ha un valore distinto per ogni record. Questo campo è detto campo di clustering in base al quale viene effettuata l’indicizzazione. Da qui il nome: indice cluster.
I diagrammi rendono sempre più facile capire. Come puoi vedere, i record di dati originali sono ordinati su un attributo non chiave e per ogni valore distinto dell’attributo non chiave viene creata una voce di indice. Il numero medio di accessi ai blocchi necessari per individuare un record particolare usando questo schema è $\geq$ $\log_{2}B_i + 1$, dove $B_i$ è il numero di blocchi nei record indicizzati. Nota il segno $\geq$.
Nell’indice cluster, dopo aver individuato il blocco in cui è presente una certa chiave, potresti dover attraversare anche altri blocchi (come è piuttosto evidente dalla figura sopra).
Potresti voler riflettere su che tipo di indicizzazione sia (sparsa o densa). Usa la sezione commenti per pubblicare le tue risposte. Ora studiamo l’Indicizzazione secondaria.
Indicizzazione secondaria:
Supponi di avere una tabella chiamata Employee nel tuo database. La tabella ha i seguenti attributi:
- employee_id
- employee_name
- employee_department
- employee_salary
employee_id è la sua chiave primaria. Ora, hai già creato l’indicizzazione primaria su questa tabella basata su employee_id. Ma durante lo sviluppo di un’applicazione, hai scoperto che la maggior parte delle query al database usa l’attributo employee_name. In tal caso, l’indicizzazione primaria non aiuterà molto, e sarà una buona pratica mantenere un’indicizzazione separata per tutti i valori appartenenti a employee_name. In ogni caso, i nomi dei dipendenti non saranno presenti in modo ordinato all’interno del database. Quindi indicizzarli velocizzerà senza dubbio le query che coinvolgono i nomi dei dipendenti.
Questo è un classico esempio di indicizzazione secondaria. Proviamo a costruire anche un’immagine adatta per l’indicizzazione secondaria:
Se hai una rappresentazione migliore, sentiti libero di pubblicarla nella sezione dei commenti.
Ora vedrai come creare indici in PostgreSQL. Segui il corso di DataCamp Joining Data in PostgreSQL se vuoi consolidarne le basi.
Creare indici in PostgreSQL
Prima di iniziare a creare indici in un database PostgreSQL, ti serviranno dei dati presenti in una tabella. Creiamo una semplice tabella chiamata Student composta dai seguenti record:
- student_id
- student_name
- student_year
Imposterai student_id come chiave primaria e non consentirai che i nomi degli studenti e gli anni di corso siano null.
La query sarà la seguente:
CREATE TABLE STUDENT(
student_id TEXT PRIMARY KEY,
student_name TEXT NOT NULL,
student_year TEXT NOT NULL
);
Dopo aver creato correttamente la tabella, dovrai inserire alcuni dati adatti nella tabella. Per comodità, puoi usare questo .csv e importarlo in Student. Puoi importare un file .csv compatibile in una tabella PostgreSQL usando la seguente query:
COPY STUDENT FROM '/path/to/csv/Student.csv' WITH (FORMAT csv);
La query sopra presuppone che il nome del file .csv da cui si copiano i dati sia Student.
Diamo un’occhiata ai dati ora. L’esecuzione di select * from STUDENT; restituisce i seguenti record: 
La query select dovrebbe restituire un totale di 86 record. Ora sei pronto per creare indici. Puoi creare indici a colonna singola usando la seguente sintassi:
CREATE INDEX index_name
ON table_name (column_name);
Creiamo un indice sul campo student_id (indicizzazione primaria).
CREATE INDEX id_index
ON STUDENT (student_id);
È possibile creare anche indici su più colonne:
CREATE INDEX id_index
ON STUDENT (student_id,student_name);
Puoi eliminare un indice usando la seguente sintassi:
DROP INDEX index_name;
È difficile percepire l’effetto dell’indicizzazione in una tabella piccola come STUDENT. Ma se la tabella fosse grande (pensa a una tabella di database con record simili di una grande università), l’indicizzazione svolgerebbe senza dubbio un ruolo fondamentale.
Ce l’hai fatta!
Congratulazioni per essere arrivato fino in fondo. In questo tutorial hai imparato cos’è l’indicizzazione, perché serve e i diversi schemi di indicizzazione. Hai anche visto come eseguire una semplice indicizzazione in PostgreSQL.
Non hai però studiato l’indicizzazione multilivello in questo tutorial. Di seguito trovi alcune ottime risorse se sei interessato a esplorarla:
Ma l’indicizzazione aiuta sempre? In realtà, ci sono casi in cui non è consigliabile usarla.
Spero che il tutorial ti abbia aiutato a chiarire le basi dell’indicizzazione. Fammi sapere le tue scoperte interessanti nella sezione dei commenti.
Dai un’occhiata al Learn SQL Hub di DataCamp.
Argomenti
