Organizzazione fisica dei dati e accesso programmatico alle basi di dati

In questa pagina 7

Questa nota chiude la parte di interrogazioni e copre tre argomenti del programma ufficiale: l'architettura di un DBMS, la gestione delle interrogazioni e la progettazione fisica, l'accesso programmatico con un'introduzione alle applicazioni web. Le slide del corso trattano in dettaglio solo indici, transazioni e trigger (SQL avanzato - indici, transazioni e trigger); il resto di questa nota è scritto a partire dal programma, in forma concisa, con esempi provati in SQLite e Python. Prerequisiti: Basi di dati e DBMS - architettura ANSI-SPARC e indipendenza dei dati (livelli e indipendenza dei dati), Algebra relazionale - operatori di base e join e SQL - interrogazioni, join e aggregazioni.

Architettura interna di un DBMS

I livelli ANSI/SPARC descrivono che cosa vede l'utente (schema esterno, logico, interno). Dentro il DBMS, ciò che accade tra una query SQL e i dati sul disco si divide in componenti:

applicazione / client SQL
        |  connessione (autenticazione, sessione)
        v
  parser            analisi sintattica e semantica (usa il catalogo) -> albero della query
        v
  ottimizzatore     riscrittura algebrica + scelta del piano (usa le statistiche) -> piano
        v
  esecutore         esegue gli operatori del piano
        v
  metodi di accesso  scansione di heap/file ordinato, indici B-tree e hash
        v
  buffer manager    tiene in memoria i blocchi usati di recente
        v
  gestore dei file  blocchi (pagine) su disco

Accanto stanno il gestore delle transazioni (lock per l'isolamento, log con scrittura anticipata per atomicità e durabilità, ripristino dopo un guasto: SQL avanzato - indici, transazioni e trigger) e il catalogo, un insieme di tabelle che descrive tabelle, colonne, indici e statistiche (numero di righe, numero di valori distinti, istogrammi).

Memoria e costo

I dati sono su disco, organizzati in blocchi (pagine) da alcuni KB; il disco si legge un blocco alla volta (Memoria di massa e scheduling del disco). Un accesso al disco costa ordini di grandezza più di un'operazione in memoria, quindi il costo di un piano si misura in numero di accessi a blocchi (I/O). Il buffer manager tiene in memoria centrale un insieme di blocchi: se un blocco richiesto c'è già (hit) non si accede al disco, altrimenti se ne sceglie uno da sostituire con una politica come LRU (concetto analogo alla sostituzione delle pagine in Memoria virtuale - paginazione su richiesta e sostituzione delle pagine).

Un record sta in un blocco; un blocco contiene più record. Con $n_R$ record e un fattore di blocco $f$ (record per blocco) la tabella occupa $b_R=\lceil n_R/f\rceil$ blocchi. L'organizzazione dei file (heap, ordinato, hash, B-tree) e degli indici è descritta in SQL avanzato - indici, transazioni e trigger; riassunto dei costi di una ricerca per uguaglianza: heap $b_R/2$ (in media) o $b_R$ (se non è unica), ordinato $\log_2 b_R$ , hash circa 1, B-tree $\log_F b_R$ , indice primario $\log_2 m+1$ .

Gestione delle interrogazioni

SQL è dichiarativo: il DBMS deve scegliere come eseguire la query. Il processo:

Parsing: controlla la sintassi e che tabelle e colonne esistano, e produce una rappresentazione algebrica;
Riscrittura (ottimizzazione logica): applica equivalenze algebriche per ottenere un'espressione più efficiente;
Scelta del piano (ottimizzazione fisica): per ogni operatore sceglie un algoritmo e un metodo di accesso, stimando il costo con le statistiche, e tiene il piano di costo minimo;
Esecuzione.

Equivalenze e riscrittura

Sono le stesse equivalenze dell'algebra (Algebra relazionale - operatori di base e join), usate come euristiche:

selezioni il prima possibile: $\sigma_{\varphi_1\wedge\varphi_2}(R)=\sigma_{\varphi_1}(\sigma_{\varphi_2}(R))$ , e se $\varphi$ riguarda solo gli attributi di $R$ , $\sigma_\varphi(R\bowtie S)=\sigma_\varphi(R)\bowtie S$ (si riducono le dimensioni prima del join);
proiezioni il prima possibile, conservando gli attributi che servono dopo (per i join e per il risultato);
prodotto + selezione = join: $\sigma_{R.A=S.B}(R\times S)=R\bowtie_{A=B}S$ , che si può calcolare senza generare il prodotto;
join commutativo e associativo: l'ordine dei join conta molto: conviene cominciare dai join più selettivi (risultato più piccolo).

Esempio. "Titoli dei riferimenti di McGraw-Hill": $\pi_{\text{title}}\big(\text{Reference}\bowtie_{\text{publisher}=\text{id}}\sigma_{\text{name}='\text{McGraw-Hill}'}(\text{Publisher})\big)$ filtra prima i 4 editori a uno e poi fa il join; l'espressione equivalente $\pi_{\text{title}}\big(\sigma_{\text{name}='\text{McGraw-Hill}'}(\text{Reference}\bowtie\text{Publisher})\big)$ fa prima il join su tutta la tabella. Il risultato è lo stesso, il costo no: un ottimizzatore ben fatto li riconduce alla stessa forma.

Algoritmi

Selezione $\sigma_{A=v}(R)$ :

scansione completa (sequential scan): legge tutti i $b_R$ blocchi; l'unica scelta senza indici o quando molte righe soddisfano la condizione;
uso di un indice sull'attributo: pochi accessi se la condizione è selettiva (frazione piccola delle righe).

Join $R\bowtie_{A=B}S$ (con $R$ operando esterno; $b_R,b_S$ blocchi, $n_R$ record, $M$ pagine di buffer):

Algoritmo	Idea	Costo (accessi a blocchi)
Nested loop (per tupla)	per ogni tupla di $R$ scandisce $S$	$b_R+n_R\cdot b_S$
Block nested loop	per ogni gruppo di $M-2$ blocchi di $R$ scandisce $S$	$b_R+\lceil b_R/(M-2)\rceil\cdot b_S$
Index nested loop	per ogni tupla di $R$ cerca in $S$ con un indice su $B$	$b_R+n_R\cdot c$ ( $c$ = costo di una ricerca per indice)
Sort-merge	ordina entrambe su $A$ / $B$ e le fonde	ordinamento + $b_R+b_S$ (se già ordinate, solo $b_R+b_S$ )
Hash join	partiziona entrambe con la stessa funzione hash, poi unisce partizione per partizione	circa $3(b_R+b_S)$

Esempio numerico. $b_R=1000$ , $b_S=100$ , $n_R=10\,000$ , $M=12$ .

nested loop per tupla: $1000+10\,000\cdot100=1\,001\,000$ ;

block nested loop con $R$ esterna: $1000+\lceil1000/10\rceil\cdot100=1000+10\,000=11\,000$ ;

block nested loop con $S$ esterna (la più piccola all'esterno): $100+\lceil100/10\rceil\cdot1000=10\,100$ ;

hash join: $3\cdot(1000+100)=3300$ .

Si vede quanto pesa la scelta: dal primo all'ultimo ci sono tre ordini di grandezza. Per questo l'ottimizzatore ha bisogno delle statistiche del catalogo.

Vedere il piano. EXPLAIN (PostgreSQL: EXPLAIN [ANALYZE]; SQLite: EXPLAIN QUERY PLAN) mostra la scelta. Su una query a tre tabelle del database bibliografico SQLite dà ad esempio SCAN w USING COVERING INDEX sqlite_autoindex_Write_1, poi SEARCH a USING INDEX sqlite_autoindex_Author_1 (id=?) e SEARCH r USING INDEX sqlite_autoindex_Reference_1 (id=?): un index nested loop (una scansione e due ricerche per chiave primaria, create implicitamente da PRIMARY KEY). È lo strumento per controllare che un indice sia davvero usato.

Progettazione fisica

Ultima fase del progetto di una base di dati, dopo la progettazione concettuale e logica (Ristrutturazione dello schema ER e traduzione nel modello relazionale). Partendo dallo schema logico e dal carico di lavoro (le operazioni, la loro frequenza e la priorità, già stimate nella ristrutturazione dello schema ER) si decide:

organizzazione di ogni tabella (heap, ordinata, hash, B-tree);
indici: candidati naturali sono le colonne usate in WHERE con uguaglianza o intervallo, nei join (chiavi esterne), in GROUP BY e ORDER BY; per ogni indice si confronta il guadagno sulle letture con il costo sulle scritture e lo spazio;
eventuale denormalizzazione (attributi derivati, tabelle unite, ridondanza controllata): velocizza le letture ma riporta le anomalie e il lavoro di mantenere coerente la ridondanza (Dipendenze funzionali e normalizzazione - BCNF e terza forma normale);
altre scelte del DBMS: partizionamento delle tabelle grandi, viste materializzate per aggregazioni costose, parametri della memoria.

Si verifica con EXPLAIN sulle query vere. Un indice inutilizzato è solo un costo; il carico cambia nel tempo, quindi la progettazione fisica si rivede.

Accesso programmatico

Le applicazioni (un sito, un'app, un programma di calcolo) non lavorano dalla console SQL: devono interrogare e modificare i dati dal codice. SQL da solo non basta: non ha interfaccia utente, né cicli e strutture generali di un linguaggio ospite. Il problema di fondo è l'impedance mismatch (disallineamento): SQL lavora su insiemi di righe di tipi propri (NUMERIC, DATE, NULL), il linguaggio ospite su variabili e oggetti, riga per riga.

Approcci

Approccio	Come funziona	Esempi
SQL incorporato (embedded)	le istruzioni SQL sono scritte nel codice ospite (`EXEC SQL ...`) e un precompilatore le traduce in chiamate; si usano variabili ospiti e cursori	SQL embedded in C, SQLJ
Interfaccia a livello di chiamata (call-level interface)	l'applicazione chiama funzioni di una libreria passando l'SQL come stringa, e legge i risultati	ODBC, JDBC, `libpq` di PostgreSQL, DB-API di Python (`sqlite3`, `psycopg`)
ORM (object-relational mapping)	tabelle mappate su classi, righe su oggetti; la libreria genera l'SQL	SQLAlchemy, Hibernate
Routine memorizzate	la logica sta nel DBMS (SQL avanzato - indici, transazioni e trigger) e l'applicazione la chiama (`CALL`)	PL/pgSQL

Lo schema è sempre lo stesso: connessione $\to$ cursore $\to$ execute (con parametri) $\to$ fetch delle righe $\to$ commit o rollback $\to$ chiusura.

python

import sqlite3                                   # DB-API: con PostgreSQL sarebbe psycopg
conn = sqlite3.connect("riferimenti.db")         # 1. connessione
cur = conn.cursor()                              # 2. cursore
cur.execute("SELECT id, title, year FROM Reference WHERE publisher = ? ORDER BY year",
            ("PrenticeHall",))                   # 3. execute con parametro (? = segnaposto)
for ref_id, title, year in cur.fetchall():       # 4. fetch (fetchone / fetchmany / fetchall)
    print(ref_id, title, year)
conn.close()

cursor.description dà i nomi delle colonne; fetchone() restituisce una riga alla volta (utile per risultati grandi), fetchall() tutte. NULL diventa None, NUMERIC diventa Decimal, DATE diventa datetime.date.
Il segnaposto cambia con il driver: ? per sqlite3 e JDBC, %s per psycopg, :nome per i parametri con nome.
Si chiudono cursore e connessione; in un server si usa un pool di connessioni, perché aprirne una per richiesta è costoso.

SQL injection e query parametrizzate

L'errore più grave è costruire l'SQL concatenando l'input dell'utente:

python

q = f"SELECT username FROM Utente WHERE username = '{u}' AND password = '{p}'"   # VIETATO

Con u = "alice" e p = "x' OR '1'='1" la stringa diventa ... WHERE username = 'alice' AND password = 'x' OR '1'='1', e per la precedenza di AND su OR la condizione è sempre vera: la query restituisce tutti gli utenti (provato: alice e bob). Con u = "' OR 1=1 --" il commento -- taglia il resto. Il danno può arrivare alla cancellazione di tabelle, se il driver accetta più istruzioni in una stringa.

La difesa è la query parametrizzata (prepared statement): SQL e dati viaggiano separati; il driver non interpreta mai i valori come SQL.

python

cur.execute("SELECT username FROM Utente WHERE username = ? AND password = ?", (u, p))

Con lo stesso input x' OR '1'='1 la query parametrizzata restituisce zero righe (provato); con le credenziali giuste restituisce alice. Vantaggi: sicurezza, e il piano di esecuzione si può riusare. I nomi di tabelle e colonne non si possono parametrizzare: se dipendono dall'utente si controllano contro un elenco fisso. Le password non si salvano in chiaro (come nel database del laboratorio, che è solo didattico) ma con un hash lento e salato.

Transazioni dal codice

Per default il driver apre una transazione alla prima istruzione di modifica e non la conferma: serve commit(); in caso di errore, rollback(). In Python:

python

try:
    with conn:                                   # commit alla fine, rollback se c'è un'eccezione
        conn.execute("UPDATE Conto SET saldo = saldo + 150 WHERE id = 2")
        conn.execute("UPDATE Conto SET saldo = saldo - 150 WHERE id = 1")   # viola CHECK (saldo >= 0)
except sqlite3.IntegrityError as e:
    print("annullata:", e)                       # i saldi tornano (100, 50): atomicità

(Provato: dopo l'errore i saldi sono invariati; con importi leciti il commit li porta a $(70,80)$ dopo uno spostamento di 30.) Le transazioni di una richiesta web devono essere brevi e non aspettare l'utente.

Altri problemi

N+1 query: leggere una lista (1 query) e poi, per ogni riga, una query di dettaglio ( $N$ query): meglio un join o una query unica con IN.
Portare al client solo le righe e le colonne che servono: filtrare e aggregare nel DBMS, non nell'applicazione.
Gestione degli errori (vincoli violati, connessione persa) e chiusura delle risorse.
Il codice SQL va tenuto in un punto solo (livello di accesso ai dati), non sparso nella logica.

Applicazioni web

Un'applicazione web a dati è tipicamente a tre livelli (three-tier):

presentazione: il browser (HTML, CSS, JavaScript);
logica applicativa: il server web e l'applicazione (Python, Java, PHP, JavaScript...);
dati: il DBMS.

Il browser parla con il server in HTTP, un protocollo senza stato: ogni richiesta è indipendente (HTTP 1.1 - connessioni persistenti, Content-Length e chunked transfer encoding, Caching, autenticazione, tipi MIME e URI in HTTP). Il server genera la risposta in modo dinamico: legge i parametri della richiesta (query string o corpo di un modulo), esegue query parametrizzate sul DBMS e costruisce HTML oppure JSON (CGI e applicazioni web dinamiche, Web service, XML, JSON, SOAP e REST). Lo stato dell'utente (chi è, il carrello) si ricostruisce con sessioni e cookie.

Esempio minimo (WSGI, libreria standard di Python): un servizio che restituisce in JSON i riferimenti di un editore, GET /?publisher=PrenticeHall.

python

import json
from urllib.parse import parse_qs

def app(environ, start_response):
    params = parse_qs(environ.get("QUERY_STRING", ""))
    publisher = params.get("publisher", [None])[0]
    if publisher is None:
        start_response("400 Bad Request", [("Content-Type", "application/json")])
        return [json.dumps({"errore": "manca publisher"}).encode()]
    rows = conn.execute("SELECT id, title, year FROM Reference WHERE publisher = ? ORDER BY year",
                        (publisher,)).fetchall()                    # query parametrizzata
    body = json.dumps([{"id": i, "title": t, "year": y} for i, t, y in rows], ensure_ascii=False)
    start_response("200 OK", [("Content-Type", "application/json; charset=utf-8")])
    return [body.encode()]

Provato chiamando app direttamente: con publisher=PrenticeHall risponde 200 OK e tre riferimenti (anni 1996, 1999, 2001); senza parametro 400; con un input d'attacco (x' OR '1'='1) 200 con la lista vuota, perché il valore è trattato come testo.

Punti di attenzione per un'applicazione vera: SQL injection (query parametrizzate), XSS (si fa l'escape dell'input prima di scriverlo in HTML), autenticazione e autorizzazione (utenti del DBMS con privilegi minimi: la web app non deve connettersi come amministratore), pool di connessioni, transazioni brevi, indici sulle colonne dei filtri più frequenti.

Errori tipici

Concatenare input nelle stringhe SQL invece di usare parametri.
Dimenticare commit() (le modifiche non sono salvate) o lasciare transazioni aperte.
Fare nell'applicazione ciò che farebbe meglio il DBMS (filtrare e aggregare lato client), o il contrario (logica pesante nelle routine).
Una query per riga ( $N+1$ ).
Scegliere gli indici "a caso", senza EXPLAIN e senza guardare il costo sulle scritture.
Dimenticare che l'ordine dei join o la stima delle statistiche (non aggiornate) cambiano di molto il costo.
Confondere i livelli ANSI/SPARC (che cosa vede l'utente) con i componenti del DBMS (come lavora dentro).

Domande d'esame

1. Elencare le fasi di elaborazione di una query SQL in un DBMS e dire che cosa decide l'ottimizzatore. Traccia. Parsing, riscrittura algebrica (selezioni e proiezioni in basso, join al posto di prodotto + selezione), scelta del piano (algoritmo e metodo di accesso per ogni operatore, con le statistiche del catalogo), esecuzione. L'ottimizzatore sceglie ordine dei join, uso degli indici, algoritmo di join minimizzando gli accessi a blocchi.

2. Con $b_R=1000$ , $b_S=100$ e 12 pagine di buffer, confrontare il costo di un block nested loop e di un hash join. Traccia. Block nested loop con $S$ esterna: $100+\lceil100/10\rceil\cdot1000=10\,100$ ; hash join: $3(1000+100)=3300$ .

3. Che cos'è una SQL injection e come ci si difende? Traccia. Costruendo l'SQL con l'input dell'utente si permette di cambiare la struttura della query (x' OR '1'='1 rende vera la condizione). Si usano query parametrizzate, che separano SQL e dati; si limitano i privilegi dell'utente del DBMS.

Versione ripasso

Architettura del DBMS: client, poi parser (usa il catalogo), ottimizzatore (usa le statistiche), esecutore, metodi di accesso (heap, ordinato, hash, B-tree, indici), buffer manager, blocchi su disco. Accanto: gestore delle transazioni (lock, log) e catalogo. Non confondere con i livelli ANSI/SPARC (Basi di dati e DBMS - architettura ANSI-SPARC e indipendenza dei dati).

Costo: si misura in accessi a blocchi (Memoria di massa e scheduling del disco). Con $n_R$ record e $f$ record per blocco, $b_R=\lceil n_R/f\rceil$ . Ricerca per uguaglianza: heap $b_R/2$ in media, ordinato $\log_2 b_R$ , hash circa 1, B-tree $\log_F b_R$ .

Gestione delle interrogazioni: parsing, riscrittura algebrica, scelta del piano (algoritmo e metodo di accesso per ogni operatore, costo stimato con le statistiche), esecuzione.

Selezioni e proiezioni il più in basso possibile; $\sigma_{R.A=S.B}(R\times S)=R\bowtie_{A=B}S$ .
Join commutativo e associativo: conta l'ordine. Si parte dai join più selettivi.
Esempio: $\pi_{\text{title}}\big(\text{Reference}\bowtie_{\text{publisher}=\text{id}}\sigma_{\text{name}='\text{McGraw-Hill}'}(\text{Publisher})\big)$ filtra prima e dà lo stesso risultato dell'espressione con il join fatto per primo, ma costa molto meno.

Selezione: scansione completa ( $b_R$ accessi) oppure indice, conveniente solo se la condizione è selettiva.

Join $R\bowtie_{A=B}S$ , con $R$ esterna, $M$ pagine di buffer:

Algoritmo	Costo (accessi)
Nested loop	$b_R+n_R\cdot b_S$
Block nested loop	$b_R+\lceil b_R/(M-2)\rceil\cdot b_S$
Index nested loop	$b_R+n_R\cdot c$ ( $c$ = costo di una ricerca per indice)
Sort-merge	ordinamento $+\ b_R+b_S$
Hash join	circa $3(b_R+b_S)$

Esempio con $b_R=1000$ , $b_S=100$ , $n_R=10\,000$ , $M=12$ : nested loop $1\,001\,000$ ; block nested loop con $R$ esterna $11\,000$ ; con $S$ esterna (la più piccola) $10\,100$ ; hash join $3300$ . Tre ordini di grandezza di differenza: per scegliere serve il catalogo.

EXPLAIN: PostgreSQL EXPLAIN [ANALYZE], SQLite EXPLAIN QUERY PLAN. Su tre tabelle del database bibliografico mostra SCAN seguita da due SEARCH ... USING INDEX su chiave primaria: un index nested loop.

Progettazione fisica: da schema logico e carico di lavoro (frequenza e priorità delle operazioni) si decide:

organizzazione di ogni tabella (heap, ordinata, hash, B-tree);
indici su colonne di WHERE (uguaglianza o intervallo), chiavi esterne nei join, GROUP BY, ORDER BY; si confronta il guadagno in lettura con il costo in scrittura e lo spazio;
eventuale denormalizzazione: veloce in lettura, ma riporta le anomalie (Dipendenze funzionali e normalizzazione - BCNF e terza forma normale);
partizioni, viste materializzate, parametri di memoria.

Si verifica con EXPLAIN. Un indice inutilizzato è solo un costo.

Accesso programmatico: impedance mismatch tra insiemi di righe SQL e variabili del linguaggio ospite. Approcci: SQL incorporato (precompilatore, cursori), call-level interface (ODBC, JDBC, DB-API di Python), ORM, routine memorizzate (CALL).

Flusso: connessione, cursore, execute con parametri, fetch, commit o rollback, chiusura. Segnaposto: ? in sqlite3 e JDBC, %s in psycopg.

python

cur.execute("SELECT id, title, year FROM Reference WHERE publisher = ? ORDER BY year", ("PrenticeHall",))
for ref_id, title, year in cur.fetchall():
    print(ref_id, title, year)

SQL injection: costruendo la stringa con f"... WHERE username = '{u}' AND password = '{p}'" e p = "x' OR '1'='1" la condizione diventa sempre vera e torna tutti gli utenti. Difesa: query parametrizzate (SQL e dati separati), con execute(..., (u, p)) la stessa password dà zero righe. Tabelle e colonne non si parametrizzano: si controllano contro un elenco fisso. Password salvate con hash lento e salato, privilegi minimi per l'utente del DBMS.

Transazioni dal codice: il driver non conferma da solo; serve commit(), in caso di errore rollback(). Con with conn: si ha commit alla fine e rollback se c'è un'eccezione. Esempio: il trasferimento che viola CHECK (saldo >= 0) lascia i saldi invariati (atomicità). Transazioni brevi, che non aspettano l'utente.

Altri problemi: $N+1$ query (meglio un join o una query con IN); filtrare e aggregare nel DBMS e non nel client; gestione degli errori; pool di connessioni; SQL in un solo livello di accesso ai dati.

Applicazioni web: tre livelli (browser, server applicativo, DBMS). HTTP è senza stato: sessioni e cookie ricostruiscono lo stato. Il server legge i parametri, esegue query parametrizzate e risponde con HTML o JSON (CGI e applicazioni web dinamiche, Web service, XML, JSON, SOAP e REST). Attenzione a injection, XSS (escape dell'input in HTML) e autenticazione.

Errori tipici

Concatenare l'input nelle stringhe SQL invece di usare parametri.
Dimenticare commit() o lasciare transazioni aperte.
Una query per riga ( $N+1$ ).
Indici scelti a caso, senza EXPLAIN e senza costo in scrittura.
Confondere i livelli ANSI/SPARC con i componenti del DBMS.

Domande d'esame (tracce)

Fasi di una query: parsing, riscrittura, scelta del piano, esecuzione. L'ottimizzatore decide ordine dei join, indici e algoritmo di join, minimizzando gli accessi a blocchi.
$b_R=1000$ , $b_S=100$ , 12 buffer: block nested loop con $S$ esterna $=10\,100$ ; hash join $=3300$ .

Prerequisiti: Algebra relazionale - operatori di base e join, SQL - interrogazioni, join e aggregazioni. Seguito: SQL avanzato - indici, transazioni e trigger.

Organizzazione fisica dei dati e accesso programmatico alle basi di dati

Architettura interna di un DBMS

Memoria e costo

Gestione delle interrogazioni

Equivalenze e riscrittura

Algoritmi

Progettazione fisica

Accesso programmatico

Approcci

SQL injection e query parametrizzate

Transazioni dal codice

Altri problemi

Applicazioni web

Errori tipici

Domande d'esame

Teoria collegata