Risultati di ricerca e problemi di prestazioni

Uno degli scenari comuni in tutte le applicazioni che conosciamo è la ricerca di dati in base a criteri specifici e la loro visualizzazione in un formato leggibile. Qui possono esserci ulteriori possibilità di ordinamento, raggruppamento e visualizzazione paginata. L'obiettivo, in teoria, è semplice, ma nella sua soluzione molti sviluppatori fanno una serie di errori che compromettono le prestazioni. Proviamo a esaminare diverse opzioni per risolvere questo problema e a formulare raccomandazioni per scegliere l'implementazione più efficace.

Opzione di paginazione #1

L'opzione più semplice che viene in mente è la visualizzazione paginata dei risultati della ricerca nella sua forma più classica.

Supponiamo che nell'applicazione sia 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 visualizzare le pagine.

Esaminiamo la prima query utilizzando un esempio di database di prova 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 restituirà i primi 50 ordini dall'elenco, ordinati in base alla data di inserimento in modo decrescente, in altre parole, gli ultimi 50 ordini.

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

Tabella 'SalesOrderHeader'. Count degli scan 1, letture logiche 698, letture fisiche 0, letture anticipate 0, letture logiche lob 0, letture fisiche lob 0, letture anticipate lob 0.

Per ottenere statistiche di input/output per ogni query, è possibile eseguire nel contesto di esecuzione della query il comando SET STATISTICS IO ON.

Come si evince dal piano di esecuzione, la parte più dispendiosa in termini di risorse è l'ordinamento di tutte le righe della tabella originale in base alla data di inserimento. E il problema è che più righe verranno aggiunte alla tabella, più pesante diventerà l'ordinamento. In pratica, situazioni di questo tipo dovrebbero essere evitate, quindi aggiungeremo un indice sulla data di inserimento e vedremo se il consumo di risorse è cambiato:

Tabella 'SalesOrderHeader'. Count degli scan 1, letture logiche 165, letture fisiche 0, letture anticipate 5, letture logiche lob 0, letture fisiche lob 0, letture anticipate lob 0.

È evidente che le cose siano migliorate notevolmente. 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 scansioni 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 curiosa: il piano della query non è molto diverso da quello precedente, ma il numero effettivo di letture logiche è quasi raddoppiato rispetto a una scansione completa della tabella. La soluzione c'è: se creiamo un indice composito aggiungendo come secondo campo il totale dei prezzi dei prodotti, torneremo a ottenere 165 letture logiche:

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

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

• Aggiungere qualsiasi nuovo criterio o ordine di ordinamento in una query può influenzare notevolmente la velocità di esecuzione.
• Tuttavia, se abbiamo bisogno di leggere solo una parte dei dati, anziché tutti i risultati che soddisfano i criteri di ricerca, esistono molti modi per ottimizzare tale query.

Passiamo ora alla seconda query, menzionata all'inizio — quella che conta il numero di record che soddisfano il criterio di ricerca. Prendiamo lo stesso esempio — la ricerca degli ordini superiori a 100 dollari:

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

Con l'indice composto indicato sopra, otteniamo:

Tabella 'SalesOrderHeader'. Count degli scan 1, letture logiche 698, letture fisiche 0, letture anticipate 0, letture logiche lob 0, letture fisiche lob 0, letture anticipate lob 0.

Che la query scorra completamente attraverso l'indice non sorprende, dato che il campo SubTotal non è in prima posizione e quindi la query non può avvalersene. Il problema si risolve aggiungendo un altro indice sul campo SubTotal, portando così il totale a 48 letture logiche.

Posso fornire ulteriori esempi di query di conteggio, ma il principio rimane lo stesso: ottenere un insieme di dati e contare il numero totale sono due query fondamentalmente diverse, e ciascuna richiede misure specifiche per l'ottimizzazione. In generale, non sarà possibile trovare una combinazione di indici che funzioni altrettanto bene per entrambe le query.

Pertanto, una delle importanti richieste da chiarire durante lo sviluppo di tale soluzione di ricerca è se sia davvero importante per l'azienda vedere il numero totale di oggetti trovati. Spesso non lo è. E la navigazione per numeri di pagina specifici, a mio avviso, è una soluzione con un ambito di applicazione molto ristretto, poiché la maggior parte degli scenari di paging si presenta come «vai alla pagina successiva».

Opzione di paging #2

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

Infatti, è cambiato solo il fatto che non è possibile passare a numeri di pagina specifici, e ora a questa tabella non è necessario sapere quante pagine ci possono essere in totale. Ma sorge la domanda: come farà la tabella a sapere se ci sono dati per la pagina successiva (per mostrare correttamente il link «Successivo»)?

La risposta è molto semplice: è possibile leggere dal database un record in più rispetto a quello necessario per visualizzare, e la presenza di questo "record aggiuntivo" indicherà se ci sono ulteriori dati da mostrare. In questo modo, per ottenere una singola pagina di dati sarà sufficiente eseguire una sola query, il che migliora notevolmente le prestazioni e semplifica il supporto di tale funzionalità. Nella mia esperienza, ho avuto un caso in cui rinunciare al conteggio totale dei record ha accelerato l'emissione dei risultati di 4-5 volte.

Per questo approccio esistono diverse opzioni di interfaccia utente: i pulsanti "indietro" e "avanti", come nell'esempio sopra, il pulsante "carica altro", che semplicemente aggiunge nuovi risultati visualizzati, e lo "scroll infinito", che funziona sul principio del "carica altro", ma il segnale per recuperare il prossimo set di dati è lo scorrimento da parte dell'utente fino alla fine dei risultati visualizzati. Qualunque sia la soluzione visiva, il principio di campionamento dei dati rimane lo stesso.

Aspetti da considerare per l'implementazione del paging

In tutti gli esempi di richieste sopra indicati, si utilizza l'approccio "offset + limit", in cui nella richiesta si specifica da quale riga del risultato e quante righe restituire. Innanzitutto, vediamo come organizzare al meglio il passaggio dei parametri in questo caso. Nella pratica, ho incontrato diversi metodi:

• Numero della pagina richiesta (pageIndex), dimensione della pagina (pageSize).
• Numero della prima registrazione da restituire (startIndex), numero massimo di registrazioni nel risultato (count).
• Numero della prima registrazione da restituire (startIndex), numero dell'ultima registrazione da restituire (endIndex).

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

• Per l'approccio con la lettura di +1 record, come descritto sopra, la prima opzione con pageIndex e pageSize è estremamente scomoda. Ad esempio, vogliamo visualizzare 50 record per pagina. Secondo l'algoritmo sopra esposto, è necessario leggere un record in più rispetto al necessario. Se questo «+1» non è previsto 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 si imposta la dimensione della pagina a 51 e si aumenta pageIndex, la seconda pagina restituirà da 52 a 102 e così via. Pertanto, nella prima opzione, l'unico modo per implementare correttamente il pulsante per passare alla pagina successiva è prevedere sul server la lettura di una «riga extra», il che sarebbe un dettaglio poco chiaro.
• La terza opzione non ha senso, poiché per eseguire richieste nella maggior parte dei database è comunque necessario passare il numero, non l'indice dell'ultimo record. Sebbene sottrarre startIndex da endIndex sia un'operazione aritmetica elementare, è superflua in questo contesto.

Ora è opportuno descrivere le carenze dell'implementazione del paging tramite «offset + quantità»:

• Il recupero di ciascuna pagina successiva sarà più costoso e più lento rispetto a quella precedente, poiché il database deve comunque esaminare tutte le voci «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 anche esse non sono perfette. Il primo di questi approcci è chiamato «keyset paging» o «metodo di ricerca» e consiste nel seguente: dopo aver ottenuto un batch, è possibile memorizzare i valori dei campi nell'ultima riga della pagina e poi usarli per ottenere il batch successivo. Ad esempio, abbiamo eseguito una query del genere:

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

Nell'ultima registrazione abbiamo ottenuto il valore della data dell'ordine '2014-06-29'. Quindi, per ottenere la pagina successiva, si può provare ad 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 univoco e la condizione indicata sopra probabilmente salterà molte righe necessarie. Per rendere univoco questa query, è necessario aggiungere un campo univoco alla condizione (supponiamo che 75074 sia l'ultimo valore della chiave primaria della prima porzione):

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 anche il valore della chiave primaria, si può semplificare la condizione mantenendo solo il filtro su SalesOrderID. Ma se non c'è una correlazione rigorosa tra i valori della chiave primaria e il campo secondo cui è ordinato il risultato, nella maggior parte dei DBMS non si potrà evitare questo OR. L'unica eccezione a mia conoscenza è PostgreSQL, dove il confronto delle tuple è pienamente supportato, e la condizione sopra indicata può essere scritta come «WHERE (OrderDate, SalesOrderID) < ('2014-06-29', 75074)». Se esiste una chiave composita con questi due campi, tale query dovrebbe essere abbastanza leggera.

Un secondo approccio alternativo si può trovare, ad esempio, in ElasticSearch scroll API o Cosmos DB — quando la richiesta restituisce, oltre ai dati, un identificatore speciale che permette di ottenere il successivo set di dati. Se questo identificatore ha una durata illimitata (come nel caso di Cosmos DB), è un ottimo modo per implementare il paging con passaggi sequenziali tra le pagine (opzione #2 menzionata sopra). I suoi possibili svantaggi: non è supportato da tutti i DBMS; l'identificatore ottenuto per il prossimo set può avere una durata limitata, il che non è generalmente adatto per realizzare interazioni con l'utente (come nel caso di ElasticSearch scroll API).

Filtraggio complesso

Complichiamo ulteriormente la questione. Supponiamo che ci sia la necessità di implementare quello che viene chiamato faceted search, particolarmente noto negli e-commerce. Gli esempi precedenti basati sulla tabella degli ordini non sono molto significativi in questo caso, quindi passiamo alla tabella Product del database AdventureWorks:

Qual è l'idea del faceted search? Quella di mostrare, per ogni elemento del filtro, il numero di record che corrispondono a quel criterio. tenendo conto dei filtri selezionati in tutte le altre categorie.

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

• Per ogni criterio del gruppo "Categories" sarà mostrato il numero di prodotti in questa categoria di colore nero.
• Per ogni criterio del gruppo "Colors" sarà mostrato il numero di biciclette di quel colore.

Ecco un esempio di output del risultato per tali condizioni:

Se oltre a questo selezioniamo la categoria "Abbigliamento", la tabella mostrerà anche indumenti di colore nero disponibili. Il numero di prodotti di colore nero nella sezione "Color" verrà nuovamente calcolato in base alle nuove condizioni, ma nella sezione "Categories" nulla cambierà... Spero che questi esempi siano sufficienti per capire il consueto algoritmo di funzionamento della ricerca per faccette.

Immaginiamo ora come ciò può essere implementato in un database relazionale. Ogni gruppo di criteri, come Categoria e Colore, richiederà una query separata:

SELEZIONA pc.ProductCategoryID, pc.Name, COUNT(1) DA Production.Product p
  INNER JOIN Production.ProductSubcategory ps ON p.ProductSubcategoryID = ps.ProductSubcategoryID
  INNER JOIN Production.ProductCategory pc ON ps.ProductCategoryID = pc.ProductCategoryID
DOVE p.Color = 'Nero'
RAGGRUPPA PER pc.ProductCategoryID, pc.Name
ORDINA PER COUNT(1) DISC

SELEZIONA Colore, COUNT(1) DA Production.Product p
  INNER JOIN Production.ProductSubcategory ps ON p.ProductSubcategoryID = ps.ProductSubcategoryID
DOVE ps.ProductCategoryID = 1 --Biciclette
RAGGRUPPA PER Colore
ORDINA PER COUNT(1) DISC

Qual è il problema con questa soluzione? Molto semplice: non scala bene. Ogni sezione del filtro richiede una richiesta separata per contare le quantità e queste richieste non sono tra le più leggere. Nei negozi online in alcune categorie possono esserci anche decine di sezioni del filtro, il che può diventare un serio problema per le prestazioni.

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

• Unire tutti i conteggi in un'unica richiesta. Tecnologicamente è possibile utilizzare la parola chiave UNION, ma questo non aiuterà molto le prestazioni: il database dovrà comunque eseguire "da zero" ognuno dei frammenti.
• Memorizzare le quantità. Questo è ciò che mi viene proposto praticamente ogni volta che descrivo un problema. La nuance è che, in generale, ciò è impossibile. Supponiamo di avere 10 "faccette", ognuna con 5 valori. Questa è una situazione molto "umile" rispetto a ciò che si può vedere nei negozi online. La selezione di un elemento della faccetta influisce sulle quantità nelle altre 9, in altre parole, per ogni combinazione di criteri le quantità possono variare. In tutto, nel nostro esempio, ci sono 50 criteri che l'utente può selezionare, rispettivamente le combinazioni possibili saranno 250. Non ci sarà abbastanza memoria o tempo per riempire 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ì, si può implementare un caricamento pigro e memorizzare nella cache le quantità solo per quanto è stato scelto in passato, ma più opzioni di scelta ci saranno, meno efficace sarà questa cache e più evidenti saranno i problemi con i tempi di risposta (soprattutto se il set di dati cambia regolarmente).

Fortunatamente, questa sfida ha ormai diverse soluzioni efficaci, che funzionano in modo prevedibile su grandi volumi di dati. Per ciascuna di queste opzioni, ha senso separare il ricalcolo dei faccetti 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 sui faccetti "non interferisca" con la visualizzazione dei risultati di ricerca.

• Eseguire il ricalcolo completo dei "facets" il meno possibile. Ad esempio, non ricalcolare tutto ad ogni modifica dei criteri di ricerca, ma piuttosto trovare il numero totale di risultati che corrispondono alle attuali condizioni e offrire all'utente la possibilità di mostrarli: "Trovati 1425 risultati, mostrare?" L'utente può continuare a modificare i criteri di ricerca oppure cliccare sul pulsante "mostra". Solo in quest'ultimo caso verranno eseguite tutte le richieste per ottenere i risultati e ricalcolare i quantitativi su tutti i "facets". È evidente che sarà necessario affrontare una richiesta per ottenere il numero totale dei risultati e la sua ottimizzazione. Questo approccio è comune in molti piccoli negozi online. Ovviamente, non è una soluzione miracolosa per questo problema, ma nei casi semplici può rappresentare un buon compromesso.
• Utilizzare un motore di ricerca per trovare risultati e calcolare i faccetti, come Solr, ElasticSearch, Sphinx e altri. Tutti sono progettati per costruire 'facette' e lo fanno in modo abbastanza efficace grazie all'indice invertito. Come sono strutturati i motori di ricerca, perché sono più efficaci in questi casi rispetto ai database generali, quali sono le pratiche e le insidie — questo è un tema per un articolo a parte. Qui, voglio sottolineare che il motore di ricerca non può sostituire il principale archivio dati; è utilizzato come complemento: qualsiasi modifica nel database principale che è rilevante per la ricerca viene sincronizzata nell'indice di ricerca; il meccanismo di ricerca interagisce di solito solo con il motore di ricerca e non si rivolge al database principale. Uno dei punti più importanti qui è come organizzare questa sincronizzazione in modo affidabile. Tutto dipende dalle esigenze relative ai 'tempi di risposta'. Se il tempo tra la modifica nel database principale e la sua 'manifestazione' nella ricerca non è critico, si può creare un servizio che ogni pochi minuti cerca le registrazioni recentemente modificate e le indicizza. Se è necessario un tempo di risposta minimo, si può implementare qualcosa di simile. cassetta di transazione per l'invio di aggiornamenti al servizio di ricerca.

Conclusioni

1. Implementare il paging sul lato server è un notevole complicazione e ha senso applicarlo solo per set di dati in rapida crescita o semplicemente grandi. Non c'è una ricetta assolutamente precisa per valutare cosa significhi 'grande' o 'in rapida crescita', ma seguirei questo approccio:
   • Se l'ottenimento dell'intera collezione di dati, tenendo conto del tempo di server e del trasferimento attraverso la rete, rientra normalmente nei requisiti di prestazione, non ha senso implementare il paging sul lato server.
   • Potrebbe esserci una situazione in cui nel prossimo futuro non ci si prevede problemi di prestazioni, poiché ci sono pochi dati, ma la collezione di dati continua a crescere. Se qualche set di dati potrebbe non soddisfare più il punto precedente in futuro, è meglio considerare subito l'implementazione del paging.
2. Se non c'è una rigorosa richiesta aziendale per mostrare il numero totale di risultati o per visualizzare i numeri di pagina, e nel contempo nel vostro sistema non c'è un motore di ricerca, è meglio non implementare questi aspetti e considerare l'opzione #2.
3. Se c'è una chiara esigenza per la ricerca con facce, hai due opzioni per non compromettere le prestazioni:
   • Non ricalcolare tutti i quantitativi ad ogni modifica dei criteri di ricerca.
   • Utilizzare motori di ricerca come Solr, ElasticSearch, Sphinx e altri. Ma è importante comprendere che non può sostituire il database principale e dovrebbe essere usato come complemento al repository principale per affrontare le problematiche di ricerca.
4. Inoltre, nel caso della ricerca con facce, ha senso separare l'ottenimento della pagina dei risultati di ricerca e il conteggio dei quantitativi in due richieste parallele. Il conteggio dei quantitativi potrebbe richiedere più tempo rispetto all'ottenimento dei risultati, mentre i risultati sono più importanti per l'utente.
5. Se utilizzi un database SQL per le ricerche, ogni modifica al codice relativa a questa parte deve essere testata approfonditamente in termini di prestazioni su un volume di dati adeguato (superiore a quello presente nel database "live"). È consigliabile anche monitorare il tempo di esecuzione delle query su tutti gli istanze del database, e in particolare su quella "live". Anche se durante la fase di sviluppo i piani delle query sembravano corretti, con l'aumento del volume dei dati la situazione potrebbe cambiare notevolmente.

Fonte: habr.com