AllYouNeedIsBackend

Sono un grande fan dei database. Ho persino voluto creare il mio DBMS quando ero all’università. Ora lavoro sia con RDBMS che con soluzioni NoSQL, e ne sono molto entusiasta. Sai, non c’è un martello d’oro, ogni problema ha la sua soluzione. In alternativa, un sottoinsieme di soluzioni.

Nella serie di post del blog The SQL I Love <3 ti guido attraverso alcuni problemi risolti con SQL che ho trovato particolarmente interessanti. Le soluzioni sono testate usando una tabella con più di 100 milioni di record. Tutti gli esempi usano MySQL, ma le idee si applicano ad altri data store relazionali come PostgreSQL, Oracle e SQL Server.

Questo capitolo si concentra sulla scansione efficiente di una grande tabella usando la paginazione con offset sulla chiave primaria. Questo è anche conosciuto come paginazione keyset.

Sfondo

Nel capitolo, usiamo la seguente struttura di database come esempio. L’esempio canonico sugli utenti dovrebbe adattarsi a qualsiasi dominio.

CREATE TABLE `users` ( `user_id` int(11) unsigned NOT NULL AUTO_INCREMENT, `external_id` varchar(32) NOT NULL, `name` varchar(100) COLLATE utf8_unicode_ci NOT NULL, `metadata` text COLLATE utf8_unicode_ci, `date_created` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP, PRIMARY KEY (`user_id`), UNIQUE KEY `uf_uniq_external_id` (`external_id`), UNIQUE KEY `uf_uniq_name` (`name`), KEY `date_created` (`date_created`)) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;

Alcuni commenti sulla struttura:

• external_id colonna memorizza il riferimento allo stesso utente in altri sistemi in formato UUID
• name rappresenta Firstname Lastname
• metadata colonna contiene JSON blob con tutti i tipi di dati non strutturati

La tabella è relativamente grande e contiene circa 100 000 000 record. Iniziamo il nostro viaggio di apprendimento.

Scansione di una grande tabella

Problema: è necessario percorrere la tabella, estrarre ogni record, trasformarlo nel codice della vostra applicazione e inserirlo in un altro posto. Nel post ci concentriamo sulla prima fase – la scansione della tabella.

Soluzione ovvia e sbagliata

SELECT user_id, external_id, name, metadata, date_createdFROM users;

Nel mio caso con 100 000 000 record, la query non è mai finita. Il DBMS la uccide e basta. Perché? Probabilmente perché ha portato al tentativo di caricare l’intera tabella in RAM. Prima di restituire i dati al client. Un’altra ipotesi – ci è voluto troppo tempo per precaricare i dati prima dell’invio e la query è andata in time out. Comunque, il nostro tentativo di ottenere tutti i record in tempo è fallito. Dobbiamo trovare qualche altra soluzione.

Soluzione #2

Possiamo provare ad ottenere i dati in pagine. Poiché i record non sono garantiti per essere ordinati in una tabella a livello fisico o logico – abbiamo bisogno di ordinarli sul lato DBMS con la clausola ORDER BY.

SELECT user_id, external_id, name, metadata, date_createdFROM usersORDER BY user_id ASCLIMIT 0, 10 000;10 000 rows in set (0.03 sec)

Dolce. Ha funzionato. Abbiamo chiesto la prima pagina di 10 000 record, e ci sono voluti solo 0.03 sec per restituirla. Tuttavia, come funzionerebbe per la 5000esima pagina?

SELECT user_id, external_id, name, metadata, date_createdFROM usersORDER BY user_id ASCLIMIT 50 000 000, 10 000; --- 5 000th page * 10 000 page size10 000 rows in set (40.81 sec)

In effetti, questo è molto lento. Vediamo quanto tempo è necessario per ottenere i dati dell’ultima pagina.

SELECT user_id, external_id, name, metadata, date_createdFROM usersORDER BY user_id ASCLIMIT 99 990 000, 10 000; --- 9999th page * 10 000 page size10 000 rows in set (1 min 20.61 sec)

Questo è folle. Tuttavia, può essere OK per soluzioni che vengono eseguite in background. Un altro problema nascosto con l’approccio può essere rivelato se si tenta di eliminare un record dalla tabella nel mezzo della scansione. Diciamo che hai finito la decima pagina (100 000 record sono già visitati), andando a scansionare i record tra 100 001 e 110 000. Ma i record 99 998 e 99 999 vengono cancellati prima della prossima esecuzione SELECT. In questo caso, la seguente query restituisce il risultato inaspettato:

 SELECT user_id, external_id, name, metadata, date_created FROM users ORDER BY user_id ASC LIMIT 100 000, 10 000; N, id, ... 1, 100 003, ... 2, 100 004, ...

Come potete vedere, la query ha saltato i record con id 100 001 e 100 002. Essi non saranno trattati dal codice dell’applicazione con l’approccio perché dopo le due operazioni di cancellazione appaiono nei primi 100 000 record. Pertanto, il metodo è inaffidabile se il set di dati è mutevole.

Soluzione #3 – l’ultima per oggi

L’approccio è molto simile al precedente perché usa ancora la paginazione, ma ora invece di basarsi sul numero di record scansionati, usiamo il user_id dell’ultimo record visitato come offset.

Algoritmo semplificato:

1. Abbiamo ottenuto PAGE_SIZE numero di record dalla tabella. Il valore di offset iniziale è 0.
2. Utilizziamo il valore massimo restituito per user_id nel lotto come offset per la pagina successiva.
3. Prendiamo il lotto successivo dai record che hanno user_id valore superiore all’attuale offset.

La query in azione per la 5.000a pagina, ogni pagina contiene dati su 10.000 utenti:

SELECT user_id, external_id, name, metadata, date_createdFROM usersWHERE user_id > 51 234 123 --- value of user_id for 50 000 000th recordORDER BY user_id ASCLIMIT 10 000;10 000 rows in set (0.03 sec)

Nota, che i valori di user_id non sono sequenziali e possono avere spazi vuoti come 25 348 è subito dopo 25 345. La soluzione funziona anche se tutti i record delle pagine future vengono cancellati – anche in questo caso la query non salta i record. Dolce, vero?

Spiegazione delle prestazioni

Per un ulteriore apprendimento, consiglio di indagare i risultati di EXPLAIN EXTENDED per ogni versione della query per ottenere i prossimi 10 000 record dopo 50 000 000.

Si concentri sulla differenza chiave tra i piani di esecuzione per la 2a e 3a soluzione poiché la 1a non è praticamente utile per tabelle grandi.

• Tipo di join: index vs range. Il primo significa che l’intero albero degli indici viene scansionato per trovare i record. Il tipo range ci dice che l’indice è usato solo per trovare le righe corrispondenti entro un intervallo specificato. Quindi, il tipo range è più veloce di index.
• Possibili chiavi: NULL vs PRIMARY. La colonna mostra le chiavi che possono essere utilizzate da MySQL. BTW, guardando nella colonna delle chiavi, possiamo vedere che alla fine la chiave PRIMARY è usata per entrambe le query.
• Righe: 50 010 000 vs 50 000 000. Il valore mostra il numero di record analizzati prima di restituire il risultato. Per la seconda query, il valore dipende da quanto è profondo il nostro scroll. Per esempio, se cerchiamo di ottenere i prossimi 10 000 record dopo la 9999a pagina, allora vengono esaminati 99 990 000 record. Al contrario, la 3a domanda ha un valore costante; non importa se carichiamo i dati per la 1a pagina o per l’ultimissima. È sempre la metà della dimensione della tabella.
• Filtrato: 200.00 vs 100.00. La colonna indica la percentuale stimata della tabella da filtrare prima dell’elaborazione. Avere il valore più alto è meglio. Il valore di 100.00 significa che la query guarda attraverso l’intera tabella. Per la seconda query, il valore non è costante e dipende dal numero di pagina: se chiediamo la prima pagina il valore della colonna filtrata sarebbe 1000000.00. Per l’ultimissima pagina, sarebbe 100.00.
• Extra: NULL vs Using where. Fornisce informazioni aggiuntive su come MySQL risolve la query. L’uso di WHERE sulla chiave PRIMARY rende l’esecuzione della query più veloce.

Sospetto che il tipo di join sia il parametro della query che ha dato il maggior contributo alle prestazioni per rendere la 3° query più veloce. Un’altra cosa importante è che la 2a query è estremamente dipendente dal numero delle pagine da scorrere. Una paginazione più profonda è più lenta in questo caso.

Più indicazioni su come capire l’output del comando EXPLAIN possono essere trovate nella documentazione ufficiale del vostro RDBMS.

Sommario

L’argomento principale del post sul blog era legato alla scansione di una grande tabella con 100 000 000 record usando offset con una chiave primaria (paginazione keyset). Nel complesso, sono stati esaminati e testati 3 approcci diversi sul set di dati corrispondente. Raccomando solo uno di loro se avete bisogno di scansionare una grande tabella mutabile.

Inoltre, abbiamo rivisto l’uso del comando EXPLAIN EXTENDED per analizzare il piano di esecuzione delle query MySQL. Sono sicuro che altri RDBMS hanno analoghi per questa funzionalità.

Nel prossimo capitolo, presteremo attenzione all’aggregazione dei dati e all’ottimizzazione dello storage. Restate sintonizzati!

Qual è il vostro metodo di scansione delle tabelle grandi?

Ricordate qualche altro scopo dell’uso della paginazione del keyset come nella soluzione #3?