Какова подходящая замена оператору SQL Like для повышения производительности?

https://stackoverflow.com/questions/402022

03-07-2019
|

Вопрос

Я работаю над приложением, которое работает на Windows Mobile 6, которое должно иметь возможность извлекать все элементы из таблицы элементов, которые содержат заданную строку (предоставленную конечным пользователем) в поле описания элемента.Проблема в том, что в таблице содержится примерно 170 000 элементов.Поскольку мне нужно вернуть все элементы, содержащие строку в любом месте описания, я вынужден использовать LIKE %string%, что исключает любую возможность использования индекса.Данные и структура таблицы изначально основаны на базе данных Progress, в которой есть замечательный оператор contains для любых полей, индексированных word.Это не относится к нашему мобильному приложению, поскольку оно использует SQL Server Compact 3.5.

По сути, мой DAL запускает запрос и извлекает SqlCeDataReader, а затем использует ItemFactory для создания объекта списка, который содержит только совпадающие элементы.Это, очевидно, позволяет нам хранить наш домен / бизнес-объекты отдельно от уровня доступа к данным.

Отлично, за исключением 8 м и 42 с, которые требуются для извлечения предметов, когда я ищу все предметы, содержащие что-то вроде "golf" в описании.Очевидно, что это неприемлемые временные рамки для конечного пользователя.

Моей первой попыткой было вместо этого извлечь все элементы обратно из базы данных, используя SELECT * FROM Item" (с предложением order by в одном из основных индексированных полей).На этом этапе я выполнил проверку indexOf при запуске через SqlCeDataReader и попросил ItemFactory добавлять элементы в объект List только в том случае, если они содержали запрошенный текст описания.Это позволило снизить скорость до 1 м 46 с.Не слишком потрепанный, но все равно слишком медленный.

Затем я попробовал другой подход, который оказался многообещающим...почти...Пока приложение запускается, я попытался создать список, содержащий все объекты item в базе данных (выполнение запроса и заполнение всего списка занимает около 2 минут, но, по крайней мере, это происходит только один раз при инициализации приложения...и все же...тьфу).Как только список будет завершен, я смогу легко запускать запросы по этому списку, выполняя такие действия, как следующие (я надеюсь, что мой синтаксис правильный...Я сейчас не на работе, и у меня нет Visual Studio на компьютере, за которым я сижу):

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

Такой подход сократил его до 21 секунды.Очень приятно (хотя по большому счету все еще медленно).Однако проблема в том, что использование памяти слишком велико, если я загружаю все элементы из базы данных.Мне пришлось фактически отключить последние 20 000 элементов (так что временной интервал в 21 секунду, вероятно, был бы больше похож на 25 секунд) во время начальной загрузки, потому что вызывалось исключение OutOfMemoryException.Согласно диспетчеру памяти в эмуляторе, у меня все еще было около 20 МБ свободной оперативной памяти, но я слышал, что к процессу может быть привязано только 32 МБ ОЗУ (не уверен, верно ли это для WM 6, но похоже, что так).

Чтобы убедиться, что это было не потому, что я использовал объект List для хранения всех элементов (который я создавал с необходимой емкостью в его конструкторе, чтобы избежать динамического изменения размера), который, как я также читал, может вызвать дополнительное использование памяти, когда он неявно вызывает ensureCapacity , я попытался использовать массив Item [] (размер которого был задан заранее).При этом все еще была проблема с памятью, и разница в размерах была незначительной.

Ладно, хватит болтать.Я знаю, что мне, вероятно, придется каким-то образом ограничить записи, возвращаемые из базы данных datareader (посредством некоторого индексированного поиска по полю другого типа), а затем, вероятно, использовать indexOf для этого меньшего подмножества элементов, чтобы получить максимальную производительность (таким образом, пропуская оператор Like все вместе).Это приведет к тому, что конечному пользователю придется вводить нечто большее, чем просто поиск по описанию (возможно, информацию об иерархии элементов, чтобы ограничить, по какому типу элементов производить поиск).

Есть какие-нибудь идеи?Неужели я иду по этому пути неправильно?

Спасибо, что выслушали (извините, что этот пост такой длинный, я как бы размышляю вслух).

О, я должен добавить (просто вкратце), что я использую:

Windows Mobile 6
Sql Server Compact Edition 3.5
C# 3.5

Обновить:Хотя подход с использованием фильтра Блума, упомянутый ниже, показался интересным, я не смог выполнить одно требование (которое я на самом деле не указал выше).Я действительно не могу сопоставить слова, которые содержатся внутри других слов (например"клуб" не вернул бы "трефы").Из-за этого я был вынужден использовать совершенно другой подход (Кент Фредрик...спасибо, что указали на это).Я отметил ответ Кента как правильный, поскольку его подход соответствовал большинству требований (Митч, у вас была аналогичная проблема с фильтром Блума, предложенным Jaunder).Тем не менее, я выбрал другой подход (на данный момент ...), отличный от его пути.

То, что я сделал, - это извлек все объекты item в память, только с номерами элементов и описаниями (что ограничивает его память, однако это по-прежнему вызывает более длительную инициализацию, чем мне нравится...я думаю, об этом может позаботиться многопоточность и загрузка этой информации за кулисами во время работы приложения).Для выполнения поиска я написал свою собственную процедуру contains.Процедура написана на неуправляемом коде c #, который использует два указателя и пару циклов для выполнения описания и требуемого соответствующего текста.Если он находит совпадение где-либо в описании, он добавляет номер элемента в массив.После поиска по всем элементам новый запрос возвращается к базе данных и захватывает только соответствующие номера элементов (что происходит очень быстро из-за индекса в целочисленном поле).Затем эти элементы создаются в виде списка со всей информацией (не только номером элемента и описанием).Вся операция занимает примерно 5-10 секунд (в зависимости от описания), чего на данный момент вполне достаточно.

Я все еще буду заниматься дальнейшей оптимизацией этого (возможно, удастся отследить, сколько символов содержит поисковый запрос...если в описании элемента осталось меньше символов, чем требуется для текста, цикл может быть продолжен непосредственно к следующему элементу).

Любые предложения по-прежнему приветствуются.На данный момент я отметил ответ Кента как "наиболее правильный" на мой вопрос.

Спасибо Долчу за помощь в написании процедуры contains.

Решение

Я голосовал за Митч Уитз ответ, но есть несколько приемов, которые я бы также проверил на эффективность.

Мое большое беспокойство по поводу наличия таблицы, полной [char], [int], заключается в том, что вы все еще можете обнаружить, что выполняете большие объемы бессмысленных сравнений строк, особенно если вы используете %word% в этой новой таблице.(Дублированные, но не соответствующие нашему поиску записи).

Я бы, вероятно, предпочел поэкспериментировать с

Words
-----
chars  | word_id 

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

и посмотрите, являются ли накладные расходы базы данных достойным решением этой возможной проблемы (я не могу проверить, извините)

Другие советы

Как насчет предварительной обработки (один раз) таблицы items (и каждая новая добавленная в нее запись должна быть обработана), чтобы создать таблицу вхождения слов, содержащую

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

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

Выполните итерацию по всем вашим элементам, разбейте на отдельные слова и добавляйте записи в таблицу встречаемости по мере их нахождения.

Создание кластеризованного индекса в [Word] и присоединение к таблице элементов в ItemId должно быть быстрым.

Вы могли бы попробовать использовать фильтр bloom.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow