SQL avanzato - indici, transazioni e trigger

In questa pagina 5

Prerequisiti: SQL - definizione dei dati e vincoli e SQL - interrogazioni, join e aggregazioni. Gli indici sono uno strumento di progettazione fisica: la loro struttura interna (blocchi, B-tree, costo in accessi al disco) è ripresa in Organizzazione fisica dei dati e accesso programmatico alle basi di dati. L'esempio dei trigger usa il database dei riferimenti bibliografici (Esercizio - Interrogazioni SQL sul database dei riferimenti bibliografici (slide di SQL)).

Indici

File di record

Una tabella è memorizzata in un file di record, diviso in blocchi (o pagine) sul disco. Le principali organizzazioni:

Organizzazione	Come sono disposti i record	Accessi medi (ricerca per uguaglianza, $n$ blocchi)
Heap file (non ordinato)	in ordine di inserimento	$n/2$
File ordinato	fisicamente ordinati su un campo (campo di ordinamento)	$\log_2 n$ ; utile anche per intervalli
Hash file	un blocco scelto dall'hash di un campo	costante; solo uguaglianza
B-tree file	blocchi organizzati in un albero di ricerca bilanciato	$\log_F n$ , con $F$ = numero medio di figli; anche intervalli

Sul B-tree, vedi anche Multi-way search tree e alberi (2,4) e Alberi binari di ricerca; sull'hash, Tabelle hash; per la ricerca binaria, Ricerca lineare e binaria.

Che cos'è un indice

Definizione. Un indice è una struttura dati ausiliaria che offre un metodo alternativo di accesso ai dati senza cambiare il loro layout fisico. È un file di record, ciascuno una coppia $(K,P)$ : $K$ è la chiave dell'indice (il valore del campo indicizzato) e $P$ un puntatore al blocco o al record del file dei dati.

I valori dell'indice sono ordinati, quindi si cerca con una ricerca binaria. L'indice è molto più piccolo della tabella (può stare in memoria centrale), e la ricerca è efficiente. È denso se ha un record per ogni record del file dati, non denso altrimenti.

Indice primario. Il file dati è ordinato e l'indice è definito sul campo di ordinamento. Contiene una chiave per ogni blocco (il valore del primo record del blocco): con $n$ blocchi di dati ha $n$ record e occupa $m<n$ blocchi (tipicamente $m\ll n$ ). Non è denso. La ricerca binaria sull'indice richiede $\log_2 m+1$ accessi, molto meno di $\log_2 n$ .
Indice secondario. Definito su un campo qualsiasi (non di ordinamento); il file dati può essere heap o ordinato. Di solito è denso. Permette una ricerca binaria al posto di una scansione sequenziale: $\log_2 n$ invece di $n/2$ .

Gli indici sono uno strumento di progettazione fisica: velocizzano le letture ma hanno un costo: spazio e tempo per mantenerli aggiornati a ogni inserimento, modifica o cancellazione. Si scelgono sulla base di un'analisi accurata del carico (quali query sono frequenti e importanti) e della struttura dati adatta al tipo di operazione.

Indici in SQL

Lo standard SQL non comprende un'istruzione per creare indici; quasi tutti i DBMS offrono questa:

sql

CREATE [UNIQUE] INDEX <nome> ON <tabella> (<colonna o espressione>, ...);
DROP INDEX <nome> [CASCADE | RESTRICT];

CREATE INDEX RefTitle ON Reference (title);
CREATE INDEX RefTitleLower ON Reference (lower(title));            -- su un'espressione
CREATE UNIQUE INDEX RefTitleYear ON Reference (lower(title), year);   -- anche vincolo di unicità

UNIQUE vieta valori duplicati: l'indice è anche un vincolo. L'indice su lower(title) serve per le ricerche indipendenti dalle maiuscole: usa l'indice solo la query che contiene la stessa espressione (WHERE lower(title) = '...').

In PostgreSQL le tabelle sono file heap, quindi si hanno solo indici secondari. I tipi principali:

B-tree (predefinito): adatto a confronti (<, >, <=, >=, =) e a intervalli;
hash: solo uguaglianza = (molto migliorato dalla versione 10): CREATE INDEX ... USING hash (title).

Si possono creare quanti indici si vuole su una tabella. I vincoli PRIMARY KEY e UNIQUE creano un indice implicito.

Prova su dati inventati (SQLite, 300 mila righe). EXPLAIN QUERY PLAN mostra il piano scelto. Senza indice, SELECT * FROM Reference WHERE title = 'Titolo 5' dà SCAN Reference (legge tutta la tabella: circa 8 ms); dopo CREATE INDEX RefTitle ON Reference(title) dà SEARCH Reference USING INDEX RefTitle (title=?) (circa 0,002 ms), e anche la ricerca per intervallo usa l'indice. WHERE lower(title) = ... continua a fare SCAN finché non si crea l'indice sull'espressione lower(title); WHERE title LIKE '%5' (con % iniziale) fa sempre SCAN, perché un indice ordinato non aiuta a cercare in mezzo alla stringa. Inserire 100 mila righe con due indici richiede circa il doppio del tempo che senza indici: è il costo in scrittura.

Quando creare un indice: sulle colonne usate spesso in WHERE e nei join (soprattutto le chiavi esterne, che PostgreSQL non indicizza da solo), selettive (poche righe per valore), e su tabelle lette molto più di quanto scritte. Non conviene su colonne con pochi valori distinti (un booleano) né su tabelle piccole.

Transazioni

Definizione. Una transazione è una sequenza di operazioni da considerare atomica, corretta anche in presenza di concorrenza, e con effetti permanenti.

Esempio: un bonifico sottrae 150 da un conto e li aggiunge a un altro. Le due UPDATE devono avvenire entrambe o nessuna.

Proprietà ACID

Atomicità (Atomicity): la transazione è un'unità di elaborazione indivisibile: o è eseguita per intero o per niente;
Consistenza (Consistency): una transazione eseguita da sola, dall'inizio alla fine, porta il database da uno stato consistente a un altro (rispetta i vincoli);
Isolamento (Isolation): la transazione appare come se fosse da sola, anche se molte girano in concorrenza;
Durabilità (Durability): gli effetti di una transazione che ha fatto commit persistono anche in caso di guasto.

Comandi

Comando	Effetto
`START TRANSACTION` (o `BEGIN`)	inizia la transazione: le operazioni non sono ancora definitive
`COMMIT`	le operazioni dall'inizio diventano permanenti
`SAVEPOINT nome`	segna un punto della transazione a cui si può tornare
`ROLLBACK`	annulla tutte le operazioni dall'inizio: nessun effetto sul database
`ROLLBACK TO SAVEPOINT nome`	annulla solo ciò che è stato fatto dopo il savepoint

sql

START TRANSACTION;
INSERT INTO Author VALUES ('VerdiM', 'Mario', 'Verdi');
INSERT INTO Author VALUES ('BianchiL', 'Luigi', 'Bianchi');
ROLLBACK;                       -- nessuno dei due autori viene inserito

Prove (SQLite): dopo i due INSERT la tabella ne contiene 2, dopo il ROLLBACK 0. Con SAVEPOINT s1 dopo il primo inserimento e ROLLBACK TO SAVEPOINT s1 dopo il secondo, un COMMIT finale lascia il solo primo autore. Bonifico con vincolo: con CHECK (saldo >= 0) sul conto, la seconda UPDATE (sottrarre 150 da un saldo di 100) fallisce; con ROLLBACK anche la prima UPDATE (accredito) viene annullata e i saldi tornano $(100,50)$ .

In PostgreSQL, fuori da una transazione esplicita, ogni istruzione è una transazione a sé (autocommit). Se un'istruzione di una transazione dà errore, la transazione è da annullare (ROLLBACK).

Concorrenza e isolamento (oltre le slide)

Senza isolamento, transazioni concorrenti producono anomalie: aggiornamento perso (due letture-modifiche-scritture sullo stesso dato si sovrappongono, come la race condition di Sincronizzazione - sezione critica, race condition e mutex), lettura sporca (si legge un dato non ancora confermato), lettura non ripetibile, fantasmi (righe nuove che compaiono in una seconda lettura). Gli standard definiscono livelli di isolamento (READ COMMITTED, REPEATABLE READ, SERIALIZABLE), con garanzie crescenti e costo crescente; il DBMS li realizza con lock o con versioni multiple dei dati (MVCC). Con i lock compare anche lo stallo, come in Deadlock - condizioni, prevenzione, evitamento e rilevamento: il DBMS lo rileva e annulla una delle transazioni.

Trigger

Un database è attivo quando ha un sistema per definire e gestire regole di produzione, nel paradigma Evento-Condizione-Azione: ogni regola reagisce a un evento (di solito una modifica dei dati), valuta una condizione ed esegue (o no) un'azione. Le regole permettono di definire vincoli di integrità, calcolare attributi derivati, gestire errori e codificare regole applicative: la conoscenza passa dal livello applicativo a quello dei dati (knowledge independence).

sql

CREATE TRIGGER <nome>
  {BEFORE | AFTER} {INSERT | DELETE | UPDATE [OF <colonne>]} [OR ...]
  ON <tabella>
  [FOR EACH {ROW | STATEMENT}]
  [WHEN (<condizione booleana>)]
  EXECUTE PROCEDURE <funzione>();       -- PostgreSQL

DROP TRIGGER <nome> ON <tabella> [CASCADE | RESTRICT];

BEFORE / AFTER: l'azione (la funzione) è invocata prima o dopo l'evento. Un trigger BEFORE può bloccare l'operazione sollevando un errore, o modificare la riga da scrivere;
ROW / STATEMENT: una volta per ogni riga coinvolta dall'istruzione oppure una sola volta per tutta l'istruzione;
WHEN: condizione che decide se invocare il trigger;
nella funzione di un trigger ROW si usano NEW (la riga che si sta scrivendo) e OLD (la riga prima della modifica).

Esempio: controllo della posizione degli autori

Il vincolo (non esprimibile con CHECK, che vede una sola riga): in Write(reference, author, authorNumber) il primo autore di un riferimento ha numero 1 e due autori dello stesso riferimento non hanno lo stesso numero. In PostgreSQL (non provato: PostgreSQL non è installato, ma sotto c'è la versione provata in SQLite):

sql

CREATE FUNCTION checkAuthorNumber() RETURNS TRIGGER AS $$
DECLARE
  numAuthors INT;      -- autori già presenti per questo riferimento
BEGIN
  SELECT COUNT(author)::INT INTO numAuthors FROM Write WHERE reference = NEW.reference;

  -- se è il primo autore, il suo numero deve essere 1
  IF numAuthors = 0 AND NEW.authorNumber <> 1 THEN
    RAISE EXCEPTION 'Numero % per % non valido: il primo autore deve avere numero 1',
                    NEW.authorNumber, NEW.author;
  END IF;

  -- nessun altro autore dello stesso riferimento con quel numero
  PERFORM author FROM Write
   WHERE reference = NEW.reference AND authorNumber = NEW.authorNumber;
  IF FOUND THEN
    RAISE EXCEPTION 'Numero % già usato per il riferimento %', NEW.authorNumber, NEW.reference;
  END IF;

  RETURN NEW;          -- in un BEFORE, RETURN NEW lascia proseguire l'operazione
END
$$ LANGUAGE plpgsql;

CREATE TRIGGER CheckWrite
  BEFORE INSERT OR UPDATE ON Write
  FOR EACH ROW EXECUTE PROCEDURE checkAuthorNumber();

La funzione conta gli autori già presenti, controlla il caso del primo autore e poi cerca un duplicato con PERFORM (una SELECT il cui risultato si scarta, con FOUND vero se ha trovato righe). Un'RAISE EXCEPTION interrompe l'istruzione.

Difetto della versione delle slide (sugli UPDATE). Con BEFORE INSERT OR UPDATE, se si modifica una riga senza cambiare authorNumber (per esempio si cambia solo author), il controllo del duplicato trova la riga stessa (che c'è ancora, con il vecchio valore) e solleva un errore a torto. Si corregge escludendo la riga corrente, per esempio con AND NOT (reference = OLD.reference AND author = OLD.author) sugli UPDATE, oppure con un trigger solo INSERT.

Prova (SQLite). Lo stesso controllo in SQLite si scrive con RAISE dentro un trigger, senza funzione a parte:

sql

CREATE TRIGGER CheckWrite BEFORE INSERT ON Write
FOR EACH ROW
BEGIN
  SELECT RAISE(ABORT, 'Il primo autore deve avere numero 1')
  WHERE (SELECT COUNT(*) FROM Write WHERE reference = NEW.reference) = 0 AND NEW.authorNumber <> 1;
  SELECT RAISE(ABORT, 'Numero autore già usato per questo riferimento')
  WHERE EXISTS (SELECT 1 FROM Write WHERE reference = NEW.reference AND authorNumber = NEW.authorNumber);
END;

Su un riferimento nuovo senza autori: INSERT ... ('Nuovo2025','BuckJR',2) è rifiutato (il primo autore deve avere numero 1); ('Nuovo2025','BuckJR',1) accettato; ('Nuovo2025','CornellG',1) rifiutato (numero già usato); ('Nuovo2025','CornellG',2) accettato.

Funzioni e procedure memorizzate

Una funzione o procedura memorizzata (stored routine) è codice, scritto nel linguaggio procedurale del DBMS (PL/pgSQL in PostgreSQL), salvato nel database e invocabile per nome. Il trigger ne è un caso. Una funzione normale ritorna un valore e si usa dentro le query; una procedura (CREATE PROCEDURE, CALL, da PostgreSQL 11) può anche gestire le transazioni.

sql

CREATE FUNCTION referencesOf(p VARCHAR) RETURNS BIGINT AS $$
  SELECT COUNT(*) FROM Reference WHERE publisher = p;
$$ LANGUAGE sql;

SELECT id, referencesOf(id) FROM Publisher;     -- usata come un'espressione

Vantaggi: la logica applicativa sta vicino ai dati (meno viaggi tra applicazione e database, regole uniche per tutte le applicazioni), le autorizzazioni si danno sulla routine; svantaggi: dipendono dal DBMS e sono più difficili da versionare e provare. Usi tipici nelle applicazioni: Organizzazione fisica dei dati e accesso programmatico alle basi di dati.

Errori tipici

Creare indici dappertutto: ogni indice rallenta le scritture e occupa spazio.
Aspettarsi che un indice su title serva per lower(title) o per LIKE '%x'.
Dimenticare che le chiavi esterne non sono indicizzate automaticamente in PostgreSQL.
Credere che COMMIT sia implicito: con START TRANSACTION va dato. Dimenticare ROLLBACK dopo un errore.
Fare in una transazione operazioni che dipendono da un valore letto prima, senza proteggerle da modifiche concorrenti (aggiornamento perso).
Nei trigger BEFORE, dimenticare RETURN NEW (l'operazione non avviene); usare NEW in un trigger DELETE o OLD in uno INSERT.
Scrivere un trigger che modifica la stessa tabella che lo fa scattare senza controllare la ricorsione.

Domande d'esame

1. Differenza tra indice primario e secondario; quanti accessi richiede la ricerca con un indice primario? Traccia. Il primario è sul campo di ordinamento del file ordinato, ha una chiave per blocco (non denso) e richiede $\log_2 m+1$ accessi, con $m$ blocchi d'indice; il secondario è su un campo qualunque, denso, e dà $\log_2 n$ invece di una scansione ( $n/2$ ).

2. Elencare le proprietà ACID e dire quale sarebbe violata se un bonifico fallisse dopo aver sottratto il denaro. Traccia. Atomicità, consistenza, isolamento, durabilità. Si viola l'atomicità: solo metà dell'operazione sarebbe eseguita; con una transazione e ROLLBACK si annulla anche la sottrazione.

3. Scrivere un trigger che impedisce di inserire un commento con data precedente a quella del post. Traccia. BEFORE INSERT ON Commento FOR EACH ROW, funzione che legge la data del post con NEW.post, RAISE EXCEPTION se NEW.data_ora < data_post, RETURN NEW altrimenti. Un CHECK non basta perché confronta due tabelle.

Versione ripasso

File di record: heap (ricerca in $n/2$ accessi), ordinato ( $\log_2 n$ ), hash (costante, solo uguaglianza), B-tree ( $\log_F n$ , anche intervalli). Base: SQL - interrogazioni, join e aggregazioni; per le strutture Multi-way search tree e alberi (2,4) e Tabelle hash.

Indice: struttura ausiliaria di coppie $(K,P)$ ordinate, molto più piccola della tabella, senza cambiare il layout dei dati.

Primario: sul campo di ordinamento di un file ordinato, una chiave per blocco, non denso, $\log_2 m+1$ accessi con $m$ blocchi d'indice.
Secondario: su un campo qualsiasi, di solito denso, $\log_2 n$ accessi invece di una scansione.
Gli indici velocizzano le letture e costano in scritture e spazio: si scelgono sul carico.

sql

CREATE [UNIQUE] INDEX RefTitle ON Reference (title);
CREATE UNIQUE INDEX RefTitleYear ON Reference (lower(title), year);

PostgreSQL usa tabelle heap con indici secondari: B-tree (predefinito, per <, =, intervalli) o hash (solo =). PRIMARY KEY e UNIQUE creano un indice implicito.
Un indice su lower(title) serve solo per query che scrivono lower(title); LIKE '%x' con % iniziale non lo usa.
Provato su 300 mila righe con SQLite: SCAN (circa 8 ms) diventa SEARCH ... USING INDEX (circa 0,002 ms); con due indici l'inserimento richiede circa il doppio.
Non conviene su colonne con pochi valori distinti o su tabelle piccole.

Transazioni: sequenza atomica di operazioni, corretta anche con concorrenza, con effetti permanenti.

ACID: Atomicità (tutto o niente), Consistenza (da stato consistente a stato consistente), Isolamento (come se fosse da sola), Durabilità (il commit sopravvive ai guasti).
Comandi: START TRANSACTION, COMMIT, SAVEPOINT s, ROLLBACK, ROLLBACK TO SAVEPOINT s.

sql

START TRANSACTION;
INSERT INTO Author VALUES ('VerdiM', 'Mario', 'Verdi');
INSERT INTO Author VALUES ('BianchiL', 'Luigi', 'Bianchi');
ROLLBACK;   -- nessuno dei due autori viene inserito

Bonifico con CHECK (saldo >= 0): se la seconda UPDATE fallisce, il ROLLBACK annulla anche l'accredito e i saldi tornano $(100,50)$ .
In PostgreSQL fuori da una transazione esplicita ogni istruzione è una transazione (autocommit). Dopo un errore la transazione va annullata.
Anomalie senza isolamento (oltre le slide): aggiornamento perso, lettura sporca, lettura non ripetibile, fantasmi. Livelli READ COMMITTED, REPEATABLE READ, SERIALIZABLE; con i lock può comparire lo stallo (Deadlock - condizioni, prevenzione, evitamento e rilevamento).

Trigger (evento-condizione-azione): una regola reagisce a un evento (una modifica), valuta una condizione ed esegue un'azione.

sql

CREATE TRIGGER CheckWrite BEFORE INSERT OR UPDATE ON Write
  FOR EACH ROW EXECUTE PROCEDURE checkAuthorNumber();

BEFORE/AFTER: prima o dopo l'evento; un BEFORE può bloccare l'operazione con un errore.
ROW (una volta per riga) o STATEMENT (una volta per istruzione); WHEN filtra quando scatta.
Nella funzione: NEW è la riga che si scrive, OLD quella prima della modifica; RAISE EXCEPTION interrompe, RETURN NEW lascia proseguire.

Esempio: posizione degli autori. Il primo autore di un riferimento ha numero 1 e non ci sono due autori con lo stesso numero per riferimento. Un CHECK non basta perché vede una sola riga. In PostgreSQL la funzione conta gli autori già presenti, controlla il primo autore e cerca il duplicato con PERFORM.

Difetto della versione delle slide. Su un UPDATE che non cambia authorNumber il controllo del duplicato trova la riga stessa e dà errore a torto. Va esclusa la riga corrente (NOT (reference = OLD.reference AND author = OLD.author)).

Errori tipici

Troppi indici: rallentano le scritture.
Aspettarsi che un indice serva per lower(c) o per LIKE '%x'.
Chiavi esterne non indicizzate da PostgreSQL.
Dimenticare COMMIT o ROLLBACK.
Nei trigger BEFORE dimenticare RETURN NEW: l'operazione non avviene.

Domande d'esame (tracce)

Indice primario: su campo di ordinamento, una chiave per blocco, $\log_2 m+1$ accessi. Il secondario è su un campo qualsiasi, denso, $\log_2 n$ .
Bonifico fallito dopo la sottrazione: si viola l'atomicità; con ROLLBACK si annulla anche la sottrazione.
Trigger che impedisce commenti con data precedente al post: BEFORE INSERT, RAISE EXCEPTION se NEW.data_ora < data_post, RETURN NEW altrimenti.

Prerequisiti: SQL - definizione dei dati e vincoli. Il costo in accessi è in Organizzazione fisica dei dati e accesso programmatico alle basi di dati.