Qual è un sostituto adatto per l'operatore SQL Like per aumentare le prestazioni?

Question

Sto lavorando su un'applicazione che gira su Windows Mobile 6 che deve essere in grado di recuperare tutti gli elementi da una tabella di articoli che contiene una determinata stringa (fornita dall'utente finale) all'interno del campo di descrizione dell'elemento. Il problema è che ci sono circa 170.000 articoli nella tabella. Dal momento che ho bisogno di restituire tutti gli elementi che contengono la stringa ovunque all'interno della descrizione, sono costretto a utilizzare una stringa LIKE%%, che elimina ogni possibilità di utilizzare l'indice. I dati e la struttura della tabella sono originariamente basati su un database Progress, che ha un meraviglioso operatore contiene tutti i campi indicizzati a parole. Questo non è il caso della nostra applicazione mobile, poiché utilizza SQL Server Compact 3.5.

Fondamentalmente, il mio DAL esegue la query e recupera un oggetto SqlCeDataReader e quindi utilizza una ItemFactory per creare un oggetto List che contiene solo gli elementi corrispondenti. Questo ovviamente ci consente di mantenere i nostri oggetti dominio / business separati dal livello di accesso ai dati.

Bene e dandy, ad eccezione degli 8m e 42s che servono per recuperare gli oggetti quando cerco tutti gli oggetti che contengono qualcosa come "golf". nella descrizione. Ovviamente questo non è un lasso di tempo accettabile per l'utente finale.

Il mio primo tentativo è stato invece di recuperare tutti gli elementi dal database utilizzando SELECT * FROM Item " (con una clausola order by su uno dei principali campi indicizzati). A questo punto ho eseguito un controllo IndexOf mentre attraversavo SqlCeDataReader e avevo ItemFactory solo aggiungere elementi all'oggetto List se contenevano il testo di descrizione richiesto. Ciò ha migliorato la velocità fino a 1 m 46 s. Non troppo malandato, ma ancora troppo lento.

Ho quindi provato un altro approccio che ha mostrato risultati promettenti ... quasi ... Durante l'avvio dell'applicazione, ho provato a creare un elenco che conteneva tutti gli oggetti oggetto all'interno del database (impiega circa 2 minuti per eseguire la query e popolare l'intero elenco, ma almeno è solo una volta mentre l'app si sta inizializzando ... ancora ... ugh). Una volta che l'elenco è completo, posso facilmente eseguire query su quell'elenco facendo cose come le seguenti (spero che la mia sintassi sia corretta ... Non sono al lavoro in questo momento e non ho Visual Studio sul PC Sono seduto a):

List<Item> specificItems = 
    AllItems.FindAll(i => i.Description.IndexOf(searchString, StringComparison.OrdinalIgnoreCase) >= 0);

Questo approccio lo ha ridotto a 21 secondi. Molto bello (ancora lento anche se nel grande schema delle cose). Tuttavia, il problema è che l'utilizzo della memoria è troppo grande se carico tutti gli elementi dal database. Ho dovuto effettivamente tagliare gli ultimi 20.000 elementi (quindi il periodo di tempo 21 sarebbe stato probabilmente più simile a 25) durante il caricamento iniziale, perché veniva lanciata una OutOfMemoryException. Secondo il gestore della memoria sull'emulatore, avevo ancora circa 20 MB di RAM libera, ma ho sentito che un processo può avere solo 32 MB o RAM associati (non sono sicuro che sia vero per WM 6, ma sembra così).

Per essere sicuro che non fosse perché stavo usando un oggetto List per contenere tutti gli elementi (che stavo istanziando con la capacità necessaria nel suo costruttore per evitare il ridimensionamento dinamico), che ho anche letto potrebbe causare memoria aggiuntiva utilizzo quando implica che implicitamente chiama GuaranteCapacity, ho provato a usare un array Item [] (dimensionato in anticipo). Questo aveva ancora il problema di memoria e la differenza di dimensioni era trascurabile.

Ok abbastanza sconclusionato. So che probabilmente dovrò limitare in qualche modo i record restituiti dal database dal datareader (attraverso una ricerca indicizzata su un diverso tipo di campo) e quindi probabilmente userò indexOf su quel sottoinsieme più piccolo di elementi per ottenere le massime prestazioni (saltando così l'operatore Like tutti insieme). Ciò farà sì che l'utente finale debba inserire più di una semplice ricerca di descrizione (forse informazioni sulla gerarchia degli articoli per limitare il tipo di oggetti da cercare).

Qualche idea? Sto andando nel modo sbagliato?

Grazie per l'ascolto (mi dispiace che questo post sia lungo, sto pensando a voce alta).

Oh, dovrei aggiungere (solo in sintesi) quello che sto usando:

• Windows Mobile 6
• SQL Server Compact Edition 3.5
• C # 3.5

AGGIORNAMENTO: Mentre l'approccio del filtro Bloom menzionato di seguito sembrava interessante, non ho potuto soddisfare un requisito (che non ho specificato sopra). Non riesco davvero ad abbinare le parole contenute in altre parole (ad es. "Club" non restituirebbe "club". Per questo motivo, sono stato costretto a usare un approccio completamente diverso (Kent Fredric ... grazie per averlo sottolineato). Ho contrassegnato la risposta di Kent come quella corretta, dal momento che il suo approccio è stato quello che ha soddisfatto la maggior parte dei requisiti (Mitch, il tuo ha avuto un problema simile al filtro Bloom suggerito da Jaunder). Tuttavia, ho adottato un approccio diverso (per ora ...) rispetto alla sua strada.

Quello che ho fatto è stato trascinare in memoria tutti gli oggetti oggetto, con solo i numeri e le descrizioni degli oggetti (che lo mantengono sotto i limiti della memoria, tuttavia causa comunque un'inizializzazione più lunga di quanto mi piaccia ... multithreading e caricamento di tali informazioni dietro le quinte mentre l'applicazione è in esecuzione può occuparmene, immagino). Per eseguire le ricerche che ho scritto la mia contiene routine. La routine è scritta in codice c # non gestito che utilizza due puntatori e un paio di loop per scorrere la descrizione e il testo corrispondente richiesto. Se trova una corrispondenza in qualsiasi punto della descrizione, aggiunge il numero dell'articolo a un array. Una volta che tutti gli articoli sono stati cercati, una nuova query torna al database e prende solo i numeri degli articoli corrispondenti (che è molto veloce a causa dell'indice su un campo intero). Quindi tali elementi vengono creati in un elenco con tutte le informazioni (non solo il numero e la descrizione dell'articolo). L'intera operazione richiede circa 5-10 secondi (a seconda della descrizione), il che è abbastanza buono per ora.

Esaminerò ancora ulteriormente l'ottimizzazione di questo (potrebbe essere in grado di tenere traccia di quanti caratteri è il termine di ricerca ... se nella descrizione dell'oggetto rimangono meno caratteri rispetto al testo richiesto, il ciclo potrebbe continuare direttamente al prossimo articolo).

Eventuali suggerimenti sono comunque ben accetti. Per ora ho contrassegnato la risposta di Kent come "la più corretta" per la mia domanda.

Propone a Dolch per avermi aiutato a scrivere la routine contiene.

Answer 1

Ho votato per La risposta di Mitch Wheat , ma ci sono alcuni trucchi che vorrei testare anche per l'efficacia.

La mia grande preoccupazione di avere una tabella piena di [char], [int] è che potresti ancora trovarti a eseguire grandi volumi di confronti di stringhe inutili, specialmente se usi% word% su questa nuova tabella. (Voci duplicate ma non corrispondenti alla nostra ricerca).

Probabilmente opterei per sperimentare con

Words
-----
chars  | word_id 

WordsToEntry
------------
word_id | entry_id 

e vedi se l'overhead del database è una degna mitigazione di questo possibile problema (non posso testare, scusa)

Answer 2

Che ne pensi della pre-elaborazione (una volta) della tabella degli elementi (e ogni nuova voce aggiunta ad essa dovrebbe essere elaborata), per creare una tabella delle occorrenze di parole avente

CREATE TABLE WordItemOccurance
(
    [Word] varchar(50) not null,

    ItemId int not null
        constraint FK_Items references ItemTable(ID)
)

Scorri su tutti i tuoi oggetti, spezzali in parole separate e aggiungi voci alla tabella degli eventi man mano che vengono trovati.

La creazione di un indice cluster su [Word] e l'unione alla tabella Item su ItemId dovrebbe essere veloce.

Answer 3

Potresti provare a usare un filtro bloom.

1. wikipedia
2. usando bloom filtri