Risultati della ricerca e problemi di prestazioni

Uno degli scenari tipici in tutte le applicazioni familiari è la ricerca di dati in base a criteri specifici e la loro visualizzazione in un formato leggibile. Qui possono esserci funzionalità aggiuntive per l'ordinamento, il raggruppamento e la paginazione. L'obiettivo, in teoria, è banale, ma nella sua risoluzione molti sviluppatori commettono diversi errori che influiscono negativamente sulle prestazioni. Cerchiamo di esaminare varie soluzioni a questo problema e formulare raccomandazioni per la scelta dell'implementazione più efficiente.

Opzione di paginazione #1

La soluzione più semplice che viene in mente è la paginazione dei risultati della ricerca nella sua forma più classica.

Supponiamo che nell'applicazione venga utilizzato un database relazionale. In questo caso, per visualizzare le informazioni in questo modo sarà necessario eseguire due query SQL:

• Ottenere le righe per la pagina corrente.
• Contare il numero totale di righe che corrispondono ai criteri di ricerca: questo è necessario per mostrare le pagine.

Esaminiamo la prima query utilizzando un esempio di un database di test MS SQL AdventureWorks per il server 2016. A questo scopo utilizzeremo la tabella Sales.SalesOrderHeader:

SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY

La query sopra riportata restituirà i primi 50 ordini dall'elenco, ordinati in base alla data di aggiunta in ordine decrescente, in altre parole, gli ultimi 50 ordini.

Viene eseguita rapidamente nel database di test, ma diamo un'occhiata al piano di esecuzione e alle statistiche di input/output:

Tabella 'SalesOrderHeader'. Count di scansione 1, letture logiche 698, letture fisiche 0, letture anticipate 0, letture logiche lob 0, letture fisiche lob 0, letture anticipate lob 0.

È possibile ottenere le statistiche di input/output per ogni query eseguendo il comando SET STATISTICS IO ON nell'ambiente di esecuzione delle query.

Come si può vedere dal piano di esecuzione, l'operazione più dispendiosa in termini di risorse è l'ordinamento di tutte le righe della tabella originale per data di aggiunta. E il problema è che più righe vengono aggiunte alla tabella, più sarà "pesante" l'ordinamento. Nella pratica, si dovrebbero evitare tali situazioni, quindi aggiungiamo un indice sulla data di aggiunta e vediamo se il consumo di risorse è cambiato:

Tabella 'SalesOrderHeader'. Count di scansione 1, letture logiche 165, letture fisiche 0, letture anticipate 5, letture logiche lob 0, letture fisiche lob 0, letture anticipate lob 0.

È evidente che è migliorato molto. Ma sono stati risolti tutti i problemi? Cambiamo la query per cercare gli ordini in cui il valore totale dei prodotti supera i 100 dollari:

SELECT * FROM Sales.SalesOrderHeader
WHERE SubTotal > 100
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY

Tabella 'SalesOrderHeader'. Conteggio scansionato 1, letture logiche 1081, letture fisiche 0, letture anticipate 0, letture logiche lob 0, letture fisiche lob 0, letture anticipate lob 0.

Abbiamo una situazione divertente: il piano della query è di poco inferiore a quello precedente, ma il numero effettivo di letture logiche è quasi il doppio rispetto a una scansione completa della tabella. C'è una soluzione: se trasformiamo l'indice esistente in un indice composito e aggiungiamo il prezzo totale dei prodotti come secondo campo, otteniamo di nuovo 165 letture logiche:

CREATE INDEX IX_SalesOrderHeader_OrderDate_SubTotal on Sales.SalesOrderHeader(OrderDate, SubTotal);

Questa serie di esempi può continuare a lungo, ma le due idee principali che voglio esprimere qui sono:

• Aggiungere qualsiasi nuovo criterio o ordine di ordinamento nella query di ricerca può influenzare notevolmente la velocità della sua esecuzione.
• Ma se dobbiamo estrarre solo una parte dei dati, e non tutti i risultati che soddisfano i criteri di ricerca, ci sono molti modi per ottimizzare tale query.

Ora passiamo alla seconda query, menzionata all'inizio - quella che conta il numero di record che soddisfano il criterio di ricerca. Prendiamo lo stesso esempio - cercare ordini che costano più di 100 dollari:

SELECT COUNT(1) FROM Sales.SalesOrderHeader
WHERE SubTotal > 100

Con l'indice composito indicato sopra, otteniamo:

Tabella 'SalesOrderHeader'. Count di scansione 1, letture logiche 698, letture fisiche 0, letture anticipate 0, letture logiche lob 0, letture fisiche lob 0, letture anticipate lob 0.

Non sorprende che la query scorra l'intero indice, poiché il campo SubTotal non è in prima posizione, quindi la query non può utilizzarlo. Il problema si risolve aggiungendo un ulteriore indice sul campo SubTotal, e alla fine otteniamo solo 48 letture logiche.

Si possono presentare ulteriori esempi di query contabili, ma il concetto rimane lo stesso: ottenere un insieme di dati e contare il totale sono due query fondamentalmente diverse, e ciascuna richiede misure proprie per l'ottimizzazione. In generale, non è possibile trovare una combinazione di indici che funzioni altrettanto bene per entrambe le query.

Pertanto, uno dei requisiti importanti da chiarire durante lo sviluppo di una tale soluzione di ricerca è se per l'azienda sia davvero importante vedere il numero totale degli oggetti trovati. Spesso non è così. E la navigazione tramite numeri di pagina specifici, a mio avviso, è una soluzione con un ambito di applicazione molto ristretto, poiché la maggior parte degli scenari di paging appare come "passare alla pagina successiva".

Opzione di paging n. 2

Supponiamo che agli utenti non importi conoscere il numero totale degli oggetti trovati. Proviamo a semplificare la pagina di ricerca:

In effetti, è cambiato solo il fatto che non c'è la possibilità di passare a numeri di pagina specifici, e ora questa tabella per la visualizzazione non ha bisogno di sapere quanti ce ne possono essere in totale. Ma sorge la domanda: come fa la tabella a sapere se ci sono dati per la pagina successiva (per visualizzare correttamente il link "Successivo")?

La risposta è molto semplice: si può leggere dal database un record in più rispetto a quanto necessario per la visualizzazione, e la presenza di questo record "aggiuntivo" indicherà se c'è un'altra porzione di dati. In questo modo, per ottenere una pagina di dati sarà necessaria solo una query, il che migliora notevolmente le prestazioni e semplifica il supporto di tale funzionalità. Ho avuto un caso nella mia pratica in cui l'abbandono del conteggio totale dei record ha accelerato il rilascio dei risultati di 4-5 volte.

Per questo approccio esistono diverse varianti di interfaccia utente: i comandi "indietro" e "avanti", come nell'esempio sopra, il pulsante "carica di più", che aggiunge semplicemente una nuova porzione ai risultati visualizzati, e "scorrimento infinito", che funziona secondo il principio di "carica di più", ma il segnale per ottenere la prossima porzione è quando l'utente scorre fino alla fine di tutti i risultati visualizzati. Qualunque sia la soluzione visiva, il principio di campionamento dei dati rimane lo stesso.

Aspetti dell'implementazione del paging

In tutti gli esempi di query sopra riportati, viene utilizzato l'approccio "offset + numero", in cui nella richiesta viene specificato da quale riga dell'insieme dei risultati e quante righe devono essere restituite. Prima vediamo come organizzare meglio la trasmissione dei parametri in questo caso. Nella pratica, ho trovato diversi modi:

• Numero ordinario della pagina richiesta (pageIndex), dimensione della pagina (pageSize).
• Numero ordinario del primo record da restituire (startIndex), numero massimo di record nel risultato (count).
• Numero ordinario del primo record da restituire (startIndex), numero ordinario dell'ultimo record da restituire (endIndex).

A prima vista potrebbe sembrare che sia così elementare da non esserci differenze. Ma non è così: l'opzione più comoda e versatile è la seconda (startIndex, count). Ci sono diverse ragioni per questo:

• Per l'approccio con lettura di +1 record riportato sopra, la prima opzione con pageIndex e pageSize è estremamente scomoda. Ad esempio, vogliamo visualizzare 50 record per pagina. Secondo l'algoritmo sopra riportato, è necessario leggere un record in più di quello richiesto. Se questo «+1» non è implementato sul server, risulta che per la prima pagina dobbiamo richiedere i record da 1 a 51, per la seconda — da 51 a 101, e così via. Se specifichiamo una dimensione della pagina di 51 e aumentiamo pageIndex, la seconda pagina restituirà da 52 a 102, e così via. Di conseguenza, nel primo caso l'unico modo per implementare correttamente il pulsante per passare alla pagina successiva è includere sul server la lettura di una “riga in eccesso”, che risulta essere una sfumatura poco chiara.
• Il terzo approccio non ha senso, poiché per eseguire le richieste, nella maggior parte dei database, sarà comunque necessario passare il numero, non l'indice dell'ultimo record. Anche se sottrarre startIndex da endIndex è un'operazione aritmetica elementare, qui è superflua.

Ora è importante descrivere gli svantaggi della realizzazione della paginazione tramite «offset + quantità»:

• Ottenere ogni pagina successiva richiederà più tempo e sarà più lento rispetto alla precedente, poiché il database dovrà comunque esaminare tutti i record «dall'inizio» in base ai criteri di ricerca e ordinamento, per poi fermarsi sul frammento desiderato.
• Non tutti i DBMS possono supportare questo approccio.

Ci sono alternative, ma non sono ideali. Il primo di questi approcci si chiama «keyset paging» o «seek method» e consiste nel: dopo aver ottenuto un lotto, è possibile memorizzare i valori dei campi nell'ultimo record della pagina, e poi utilizzarli per ottenere il lotto successivo. Ad esempio, abbiamo eseguito una richiesta del genere:

SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY

E nell'ultima registrazione abbiamo ottenuto il valore della data dell'ordine '2014-06-29'. Allora, per ottenere la pagina successiva, si potrà tentare di eseguire quanto segue:

SELECT * FROM Sales.SalesOrderHeader
WHERE OrderDate < '2014-06-29'
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY

Il problema è che OrderDate non è un campo unico e la condizione sopra indicata ha una grande probabilità di saltare molte righe necessarie. Per rendere univoco questa query, è necessario aggiungere alla condizione un campo unico (si supponga che 75074 sia l'ultimo valore della chiave primaria del primo lotto):

SELECT * FROM Sales.SalesOrderHeader
WHERE (OrderDate = '2014-06-29' AND SalesOrderID < 75074)
   OR (OrderDate < '2014-06-29')
ORDER BY OrderDate DESC, SalesOrderID DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY

Questa opzione funzionerà correttamente, ma in generale sarà difficile ottimizzarla, poiché la condizione contiene l'operatore OR. Se con l'aumento di OrderDate cresce il valore della chiave primaria, la condizione può essere semplificata, mantenendo solo il filtro su SalesOrderID. Tuttavia, se non c'è una correlazione rigorosa tra i valori della chiave primaria e il campo in base al quale viene ordinato il risultato, in molte DBMS sarà impossibile evitare questo OR. L'unica eccezione che conosco è PostgreSQL, dove è pienamente supportato il confronto delle tuple, e la condizione sopra indicata può essere scritta come "WHERE (OrderDate, SalesOrderID) < ('2014-06-29', 75074)". In presenza di una chiave composta con questi due campi, una simile query dovrebbe essere abbastanza leggera.

Un secondo approccio alternativo può essere trovato, ad esempio, in ElasticSearch scroll API o Cosmos DB — quando la query oltre ai dati restituisce un identificatore speciale, con cui è possibile ottenere il lotto successivo di dati. Se questo identificatore ha una durata illimitata (come in Comsos DB), è un ottimo modo per implementare il paging con transizioni sequenziali tra le pagine (il secondo metodo menzionato sopra). I suoi possibili svantaggi: non è supportato da tutte le DBMS; l'identificatore ottenuto per il lotto successivo può avere una durata limitata, il che in generale non è adatto per l'interazione con l'utente (come, ad esempio, l'ElasticSearch scroll API).

Filtraggio complesso

Complichiamo ulteriormente il compito. Supponiamo di avere la richiesta di implementare il cosiddetto faceted search, ben noto a tutti dagli e-commerce. Gli esempi forniti sopra basati sulla tabella degli ordini non sono molto significativi in questo caso, quindi passeremo alla tabella Product del database AdventureWorks:

Qual è l'idea del faceted search? Consiste nel mostrare il numero di record corrispondenti a ciascun criterio per ogni elemento del filtro. tenendo conto dei filtri selezionati in tutte le altre categorie..

Ad esempio, se in questo caso scegliamo la categoria Bikes e il colore Black, la tabella mostrerà solo biciclette di colore nero, ma:

• Per ogni criterio del gruppo «Categories» verrà mostrato il numero di prodotti di questa categoria di colore nero.
• Per ogni criterio del gruppo «Colors» verrà mostrato il numero di biciclette di quel colore.

Ecco un esempio di output del risultato per tali condizioni:

Se in aggiunta selezioniamo la categoria «Clothing», la tabella mostrerà anche i capi d'abbigliamento di colore nero disponibili. Il numero di prodotti di colore nero nella sezione «Color» sarà anch'esso ricalcolato secondo le nuove condizioni, mentre nella sezione «Categories» non cambierà nulla… Spero che questi esempi siano sufficienti per comprendere il consueto algoritmo di funzionamento del faceted search.

Ora immaginiamo come potrebbe essere implementato su un database relazionale. Ogni gruppo di criteri, come Category e Color, richiederà una query separata:

SELECT pc.ProductCategoryID, pc.Name, COUNT(1) FROM Production.Product p
  INNER JOIN Production.ProductSubcategory ps ON p.ProductSubcategoryID = ps.ProductSubcategoryID
  INNER JOIN Production.ProductCategory pc ON ps.ProductCategoryID = pc.ProductCategoryID
WHERE p.Color = 'Black'
GROUP BY pc.ProductCategoryID, pc.Name
ORDER BY COUNT(1) DESC

SELECT Color, COUNT(1) FROM Production.Product p
  INNER JOIN Production.ProductSubcategory ps ON p.ProductSubcategoryID = ps.ProductSubcategoryID
WHERE ps.ProductCategoryID = 1 --Bikes
GROUP BY Color
ORDER BY COUNT(1) DESC

Qual è il problema con questa soluzione? È semplice: non scala bene. Ogni sezione del filtro richiede una query separata per contare le quantità e queste query non sono proprio leggere. Negli e-commerce, in alcune categorie ci possono essere diverse decine di sezioni di filtro, il che può diventare un grave problema per le prestazioni.

Di solito, dopo queste affermazioni, mi vengono proposte alcune soluzioni, ovvero:

• Unire tutti i conteggi in una sola richiesta. Tecnicamente, è possibile farlo utilizzando la parola chiave UNION, ma in termini di prestazioni non sarà di grande aiuto: il database dovrà comunque eseguire "da zero" ciascuno dei frammenti.
• Memorizzare nella cache i conteggi. Questo è ciò che mi viene suggerito praticamente ogni volta che descrivo il problema. Il punto è che, in generale, è impossibile. Supponiamo di avere 10 "facette", ognuna con 5 valori. Questa è una situazione molto "modesta" rispetto a ciò che si può vedere negli stessi negozi online. La scelta di un elemento della facetta influisce sui conteggi in 9 altre facette; in altre parole, per ogni combinazione di criteri, i conteggi possono variare. Nel nostro esempio ci sono 50 criteri che l'utente può scegliere, quindi ci saranno 250 combinazioni possibili. Non ci sarà abbastanza memoria o tempo per popolare un tale array di dati. Si potrebbe obiettare che non tutte le combinazioni sono reali e che l'utente raramente seleziona più di 5-10 criteri. Sì, è possibile fare un caricamento pigro e memorizzare nella cache i conteggi solo per ciò che è stato selezionato in precedenza, ma più opzioni di scelta ci sono, meno efficace sarà questa cache e più evidenti saranno i problemi di tempo di risposta (soprattutto se il set di dati cambia regolarmente).

Fortunatamente, una tale esigenza ha già soluzioni abbastanza efficienti che funzionano in modo prevedibile su grandi volumi di dati. Per ognuna di queste opzioni ha senso separare il ricalcolo delle facette e l'ottenimento della pagina dei risultati in due richieste parallele al server e organizzare l'interfaccia utente in modo che il caricamento dei dati delle facette non "disturbi" la visualizzazione dei risultati della ricerca.

• Evitare di eseguire un ri-calcolo completo dei "facets" il più raramente possibile. Ad esempio, non calcolare tutto ad ogni modifica dei criteri di ricerca, ma piuttosto trovare il numero totale di risultati che corrispondono alle condizioni attuali e proporre all'utente di mostrarli — "1425 risultati trovati, mostrare?" L'utente può continuare a modificare le condizioni di ricerca o premere il pulsante "mostra". Solo nel secondo caso verranno eseguite tutte le richieste per ottenere risultati e ricalcolare i numeri su tutti i "facets". Inoltre, come si può facilmente notare, sarà necessario gestire una richiesta per ottenere il numero totale di risultati e la sua ottimizzazione. Questo metodo può essere trovato in molti piccoli negozi online. È ovvio che non è una panacea per questo problema, ma nei casi semplici può essere un buon compromesso.
• Utilizzare motori di ricerca per trovare risultati e calcolare i facets, come Solr, ElasticSearch, Sphinx e altri. Tutti sono progettati per costruire "facets" e lo fanno in modo piuttosto efficace grazie all'indice invertito. Come sono strutturati i motori di ricerca, perché in questi casi sono più efficaci rispetto ai database generali, quali sono le pratiche e gli aspetti da considerare — questo è un argomento per un articolo a parte. Qui voglio sottolineare che un motore di ricerca non può sostituire il principale archivio di dati, viene utilizzato come complemento: qualsiasi modifica nel database principale che abbia un impatto sulla ricerca viene sincronizzata nell'indice di ricerca; il meccanismo di ricerca interagisce normalmente solo con il motore di ricerca e non si rivolge al database principale. Uno degli aspetti più importanti qui è come organizzare questa sincronizzazione in modo affidabile. Tutto dipende dai requisiti riguardanti il "tempo di risposta". Se il tempo tra una modifica nel database principale e la sua "manifestazione" nella ricerca non è critico, è possibile implementare un servizio che ogni pochi minuti cerchi le voci recentemente modificate e le indicizzi. Se è necessario il tempo di risposta minimo possibile, è possibile implementare qualcosa come transactional outbox per inviare aggiornamenti al motore di ricerca.

Conclusioni

1. L'implementazione del paging lato server è un serio compito complesso e dovrebbe essere utilizzata solo per set di dati in rapida crescita o semplicemente ampi. Non esiste una ricetta esatta per valutare cosa sia "grande" o "in rapida crescita", ma io adotterei questo approccio:
   • Se l'ottenimento di un'intera raccolta di dati, considerando il tempo server e il trasferimento di rete, rientra normalmente nei requisiti di prestazione, non ha senso implementare il paging lato server.
   • Potrebbe verificarsi una situazione in cui, per il momento, non ci sono problemi di prestazioni poiché ci sono pochi dati, ma la raccolta di dati continua a crescere. Se un certo set di dati potrebbe nel tempo smettere di soddisfare il punto precedente, è meglio implementare subito il paging.
2. Se non ci sono requisiti rigorosi da parte dell'azienda riguardo alla visualizzazione del numero totale di risultati o alla visualizzazione dei numeri di pagina, e nello stesso tempo nel vostro sistema non c'è un motore di ricerca, è meglio non implementare questi aspetti e considerare l'opzione #2.
3. Se c'è un chiaro requisito per la ricerca facettata, avete due opzioni per non compromettere le prestazioni:
   • Non ricalcolare tutti i numeri ad ogni cambiamento dei criteri di ricerca.
   • Usare motori di ricerca come Solr, ElasticSearch, Sphinx e altri. Ma bisogna capire che non può sostituire il database principale e deve essere utilizzato come complemento per risolvere compiti di ricerca.
4. Inoltre, nel caso di ricerca facettata, ha senso separare l'ottenimento della pagina dei risultati della ricerca e il conteggio dei numeri in due richieste parallele. Il conteggio dei numeri potrebbe richiedere più tempo rispetto all'ottenimento dei risultati, mentre i risultati sono più importanti per l'utente.
5. Se utilizzate un database SQL per la ricerca, qualsiasi modifica del codice riguardante questa parte deve essere testata accuratamente in relazione alle prestazioni su un volume di dati corrispondente (superiore al volume del database "in produzione"). È inoltre consigliabile utilizzare il monitoraggio del tempo di esecuzione delle query su tutte le istanze del database, e in particolare su quella "in produzione". Anche se nella fase di sviluppo con i piani delle query tutto andava bene, con l'aumento del volume dei dati la situazione potrebbe cambiare notevolmente.

Fonte: habr.com