Qu'est-ce qui remplace avantageusement l'opérateur SQL Like pour augmenter les performances?

Question

Je travaille sur une application fonctionnant sous Windows Mobile 6 qui doit pouvoir extraire tous les éléments d'une table d'éléments contenant une chaîne donnée (fournie par l'utilisateur final) dans le champ de description de l'élément. Le problème est qu’il ya environ 170 000 articles dans le tableau. Étant donné que je dois renvoyer tous les éléments contenant la chaîne n'importe où dans la description, je suis obligé d'utiliser une chaîne LIKE%, ce qui élimine toute possibilité d'utiliser l'index. Les données et la structure de la table sont basées à l'origine sur une base de données Progress, qui possède un opérateur contient des informations sur les champs indexés par mot. Ce n'est pas le cas sur notre application mobile, car elle utilise SQL Server Compact 3.5.

Fondamentalement, mon DAL exécute la requête, récupère un SqlCeDataReader, puis utilise un ItemFactory pour créer un objet List contenant uniquement les éléments correspondants. Cela nous permet évidemment de séparer nos objets de domaine / métier de la couche d'accès aux données.

Tout va bien, sauf pour les 8m et 42s nécessaires pour récupérer des éléments lorsque je recherche tous les éléments contenant quelque chose comme "golf". dans la description. Évidemment, ce n'est pas un délai acceptable pour l'utilisateur final.

Ma première tentative a été de récupérer tous les éléments de la base de données en utilisant SELECT * FROM Item " (avec une clause order by sur l'un des principaux champs indexés). À ce stade, j'ai exécuté une vérification IndexOf comme j'ai parcouru SqlCeDataReader et que ItemFactory n'ajoute des éléments à l'objet List que s'ils contenaient le texte de description demandé. Cela a amélioré la vitesse jusqu'à 1m 46s. Pas trop mal, mais toujours trop lent.

J'ai ensuite essayé une autre approche qui semblait prometteuse ... ou presque ... Lors du démarrage de l'application, j'ai essayé de créer une liste contenant tous les objets élément de la base de données (il faut environ 2 minutes pour exécuter la requête et remplir l'ensemble liste, mais au moins ce n’est qu’une fois que l’application est en cours d’initialisation ... encore ... beurk). Une fois la liste complète, je peux facilement exécuter des requêtes sur cette liste, en procédant comme suit (j'espère que ma syntaxe est correcte ... Je ne suis pas au travail pour le moment et je n'ai pas Visual Studio sur le PC. I suis assis à):

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

Cette approche l’a fait tomber à 21 ans. Très sympa (toujours lent mais dans le grand schéma des choses). Cependant, le problème est que l'utilisation de la mémoire est beaucoup trop importante si je charge tous les éléments de la base de données. En fait, j'ai dû couper les 20 000 derniers éléments (le délai de 21 secondes aurait probablement été plutôt de 25) lors du chargement initial, car une exception OutOfMemoryException était en cours de lancement. Selon le gestionnaire de mémoire de l'émulateur, il me restait environ 20 Mo de RAM disponible, mais j'ai entendu dire qu'un processus ne peut être associé qu'à 32 Mo ou à de la RAM (je ne sais pas si cela est vrai pour WM 6, mais cela semble oui).

Pour m'assurer que ce n'était pas parce que j'utilisais un objet List pour contenir tous les éléments (ce que j'avais instancié avec la capacité nécessaire dans son constructeur pour éviter le redimensionnement dynamique), ce que j'ai également lu peut provoquer une mémoire supplémentaire utilisation quand elle appelle implicitement EnsureCapacity, j’ai essayé d’utiliser un tableau Item [] (dimensionné à l’avance). Cela avait toujours un problème de mémoire et la différence de taille était négligeable.

Ok assez décousu. Je sais que je vais probablement devoir limiter le nombre d'enregistrements renvoyés par le datareader de la base de données (via une recherche indexée sur un type de champ différent), puis utiliserons probablement indexOf sur ce plus petit sous-ensemble d'éléments pour obtenir des performances maximales (sautant ainsi l'opérateur Like tous ensemble). Cela obligera l'utilisateur final à entrer plus que simplement une recherche par description (peut-être des informations sur la hiérarchie des éléments pour limiter le type d'éléments dans lequel effectuer une recherche).

Des idées? Est-ce que je m'y prends mal?

Merci d'avoir écouté (désolé, cet article est long, je réfléchis plutôt fort).

Oh, je devrais ajouter (juste en résumé) ce que j'utilise:

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

MISE À JOUR: Même si l’approche de Bloom Filter mentionnée ci-dessous semblait intéressante, je ne pouvais pas répondre à une exigence (ce que je n’ai pas vraiment précisé ci-dessus). Je ne peux pas vraiment faire correspondre les mots contenus dans d'autres mots (par exemple, "club" ne reviendrait pas "clubs"). Pour cette raison, j'ai été obligé d'adopter une approche totalement différente (Kent Fredric ... merci de l'avoir signalé). J'ai marqué la réponse de Kent comme étant la bonne, car son approche était celle qui répondait le plus aux exigences (Mitch, votre problème était similaire au filtre de Bloom proposé par Jaunder). Cependant, j’ai adopté une approche différente (pour le moment ...) de son côté également.

Ce que j'ai fait est de mettre tous les objets d'item en mémoire, avec seulement des numéros et des descriptions d'item (ce qui le maintient dans les limites de la mémoire, mais cela provoque toujours une initialisation plus longue que ce que je préfère ... multithreading et chargement de cette information. dans les coulisses pendant que l'application est en cours d'exécution peut prendre soin de cela, je suppose). Pour effectuer les recherches que j'ai écrites moi-même ma routine contient. La routine est écrite en code c # non géré qui utilise deux pointeurs et quelques boucles pour parcourir la description et le texte correspondant requis. S'il trouve une correspondance n'importe où dans la description, il ajoute le numéro d'élément à un tableau. Une fois que tous les éléments ont été recherchés, une nouvelle requête retourne à la base de données et ne récupère que les numéros d’éléments correspondants (ce qui est très rapide en raison de l’indexation d’un champ entier). Ensuite, ces éléments sont créés dans une liste avec toutes les informations (pas uniquement le numéro et la description de l'élément). L’opération prend environ 5 à 10 secondes (selon la description), ce qui est suffisant pour le moment.

Je continuerai d’optimiser l’optimisation (nous pourrons peut-être connaître le nombre de caractères du terme recherché ... s'il reste moins de caractères dans la description de l'élément que le texte requis, la boucle pourrait continuer directement au début de la page. article suivant).

Toutes les suggestions sont toujours les bienvenues. Pour l’instant, j’ai marqué la réponse de Kent comme "la plus correcte". pour ma question.

Merci à Dolch de m'avoir aidé à écrire la routine contient.

Answer 1

J'ai voté pour Mitch Wheat répond, mais il y a quelques astuces que je voudrais également tester pour l'efficacité.

Mon gros souci avec une table pleine de [caractère], [int], c'est que vous pouvez toujours vous trouver à exécuter de grands volumes de comparaisons de chaînes inutiles, en particulier si vous utilisez% word% sur cette nouvelle table. (Entrées dupliquées mais ne correspondant pas à notre recherche).

Je choisirais probablement d'expérimenter avec

Words
-----
chars  | word_id 

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

et voyez si la surcharge de la base de données est une solution valable à ce problème possible (je ne peux pas tester, désolé)

Answer 2

Qu'en est-il du prétraitement (une fois) de la table des éléments (et de chaque nouvelle entrée ajoutée à celle-ci doit être traitée), pour créer une table d'occurrences de mots comportant

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

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

Parcourez tous vos éléments, séparez-les en mots séparés et ajoutez des entrées à la table d'occurrences au fur et à mesure qu'elles se trouvent.

La création d’un index clusterisé sur [Word] et l’association à la table des éléments sur ItemId doivent être rapides.

Answer 3

Vous pouvez essayer d’utiliser un filtre de bloom.

1. wikipedia
2. utiliser Bloom filtres