Как вы проектируете базу данных для быстрого поиска по нескольким столбцам?

Question

Я создаю поиск недвижимости по данным RETS, используя MySQL, но это общий вопрос. Если у вас есть несколько столбцов, по которым вы хотите, чтобы пользователь мог фильтровать свои результаты поиска, как вы оптимизируете это?

Например, http://www.charlestonrealestateguide.com/listings.php имеет 16 или около того дополнительных фильтров. Конечно, он имеет только до 11 000 записей (у меня есть те же данные), но я не думаю, что поиск выполняется с помощью гигантского предложения WHERE AND AND AND ... Или это обычно достигается с помощью одного гигантского многоколоночного индекса?

Newegg, Amazon и многие другие также имеют крутые и быстрые системы фильтрации больших объемов данных. Как они это делают? И есть ли причина оптимизации базы данных для тенденции предоставлять диапазоны вместо пустых входных данных, или это просто для удобства пользователя?

Answer 1

Я верю это сообщение от Объясните Расширенное отвечает на ваш вопрос.Это долго и подробно показывает много примеров.Я обрежу / вставлю его резюме, чтобы умерить ваш аппетит:

В некоторых случаях предикат диапазона (например, «меньше чем», «больше чем» или «между») можно переписать какПредикат IN для списка значений, которые могут удовлетворять условию диапазона.

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

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

Всякий раз, когда оптимизатор создает план для запроса, который содержит предикат диапазона, он должен рассмотреть возможность переписать условие диапазона как предикат IN и использоватьпоследний метод, если он окажется более эффективным.

Answer 2

MySQL Edit

Похоже, что некоторые СУБД имеют определенные возможности в этом отношении.

Mysql имеет некоторые индексные "объединения" в соответствии с документацией .

[До MySQL5] MySQL мог использовать не более одного индекса для каждой ссылочной таблицы

Но в 5 он поддерживает ограниченное слияние индексов.

Вам действительно нужно понять, как работают индексы и когда они полезны. При каком проценте строк полное сканирование таблицы имеет больше смысла, чем индекс? Вы поверите, что в некоторых случаях FTS дешевле, чем сканирование индекса, которое возвращает 2% строк? Если гистограмма вашей спальни выглядит следующим образом: 1 = 25%, 2 = 50%, 3 = 20%,> 3 = 5% ... единственный раз, когда индекс в этом столбце полезен, это найти более 3 спален, и он выиграл ' тогда его нельзя использовать из-за переменных связывания и факторов кластеризации.

думай об этом так. Предположим, мой процент спален правильный. Допустим, у вас есть 8 тыс. Страниц (не знаю, что использует Mysql), и каждая строка имеет длину 80 байт. Игнорируя накладные расходы, у вас есть 100 строк (списков) на страницу диска. Так как дома добавляются в произвольном порядке (случайным образом, поскольку спальни переходят) на каждой странице у вас будет 50 домов с 2 спальнями, 25 домов с 1 спальней, 20 домов с 3 спальнями и, возможно, дом с 4 или 5 или около того на этой странице , У КАЖДОЙ страницы будет хотя бы один дом с 1 спальней, поэтому вы будете читать КАЖДУЮ страницу для СПАЛЬНЕЙ = 1, то же самое для 2, то же самое для 3. Это может помочь для 5-комнатных домов ... но если переменная привязки MySQL работает как Oracle, тогда это не будет переключать планы для данного значения Спальни.

Как видите, многое нужно понять ... Гораздо больше, чем указал Джон Скит.

Оригинальный пост

Большинство СУБД не могут объединять индексы в одной таблице. Если у вас есть таблица со столбцами A, B и C, с индексами из одного столбца для A, B и C. и вы ищете, где A = a и B = b и C = c. Он выберет наиболее селективный индекс и будет использовать только этот.

Если вы создадите одиночный многоколонный индекс для A, B, C, тогда этот индекс не будет работать, если вы не включите A = a в WHERE. Если вы где B = b и C = c, то этот индекс игнорируется - в большинстве СУБД.

Вот почему Oracle изобрел индекс Bitmap. Битовый индекс для A, B и C может быть объединен с побитовым И и побитовым ИЛИ операциями. Пока не будет определен окончательный набор Rowids и не будут выбраны выбранные столбцы.

В последних четырех столбцах показан растровый индекс в столбце REGION.

    Row     Region   North   East   West   South
    1       North        1      0      0       0
    2       East         0      1      0       0
    3       West         0      0      1       0
    4       West         0      0      1       0
    5       South        0      0      0       1
    6       North        1      0      0       0

Так что, если вы говорите, что хотите дом, где регион в (север, восток). Вы бы побитовые ИЛИ индекс Севера и Индекс Востока и получили бы строки 1, 2, 6

Если у вас был другой столбец с количеством спален, например

  Row     Bedrooms   1BR   2BR
    1       1        1      0 
    2       2        0      1
    3       1        1      0
    4       1        1      0
    5       2        0      1 
    6       2        0      1 

если вы AND Спальни = 2, этот индекс вернет 2, 5, 6, а при битовом И в столбце Регион появятся строки 2 и 6.

Но так как вы не упомянули СУРБД, я, возможно, полностью потратил свое время. Ну хорошо.

Answer 3

Я предполагаю, что ваши критерии поиска являются дискретными, а не произвольными, то есть вы фильтруете что-то, что вы можете определить количественно, например, количество спален, размер участка и т. Д. Независимо от того, находится ли он в "солнечном" место нахождения." В этом случае я бы посоветовал вам динамически построить запрос, чтобы он учитывал только интересующие столбцы в базе данных. Индексы из одного столбца, вероятно, адекватны, особенно если учесть, что у вас мало данных. Однако если вы обнаружите, что люди всегда указывают пару столбцов - например, количество спален и количество ванных комнат - тогда может быть полезным добавление составного индекса для этой комбинации столбцов. Я бы, конечно, позволил статистике и производительности определять эти решения.

Если вы запрашиваете только одну таблицу, она выберет лучший индекс для использования, если он применим. С этой точки зрения вы хотите выбрать столбцы, которые являются хорошими дискриминаторами и, вероятно, будут использоваться в фильтре. Ограничение числа индексов может быть полезным, если вы знаете, что определенные столбцы либо быстро ограничат число возвращаемых результатов, либо, наоборот, тот или иной столбец не является хорошим распознавателем. Если, например, 90% ваших домов в списке имеют размер участка меньше акра, и большинство людей ищут участки меньше акра (или не заботятся), то сканирование индекса на основе этого индекса обычно не лучше, чем сканирование таблицы, и индекс не нужен. Индексы действительно стоят чего-то для вычисления, хотя для небольшой базы данных, такой как ваша, с нечастыми вставками, это, вероятно, не проблема.

@ Джон прав, я думаю, вы, вероятно, хотите объединить свойства фильтра, используя AND, а не OR. То есть люди обычно ищут дом с 3 спальнями И 2 ванными комнатами, а не с 3 спальнями ИЛИ 2 ванными комнатами. Если у вас есть фильтр, который допускает множественный выбор, то вы можете использовать IN - скажем, PropertyType IN ('Ranch','SplitLevel',...) вместо явного ИЛИ (работает так же, но более читабельно). Обратите внимание, что вы, скорее всего, используете внешний ключ для таблицы PropertyTypes, а не текст здесь, но я использовал значения только для иллюстрации.

Answer 4

Разве это не будет WHERE x='y' AND a='b' и т. Д. Запрос вместо этого?

Я бы подумал, что несколько отдельных индексов должны быть в порядке - не нужно ничего особенного.

Answer 5

Что вам нужно, это полнотекстовая поисковая система. Amazon и другие используют то же самое. Взгляните на http://lucene.apache.org/, и если ваша платформа основана на Java, гораздо более высокий уровень абстракций может быть www.elasticsearch.com и Hibernate Search.