Максимальное количество полезных индексов в таблице?

Question

Собрание

На встрече на прошлой неделе клиент обсуждал, как сделать важную страницу поиска быстрее.Страница ищет одну таблицу (12 столбцов, 20 миллионов строк), запрашивая значения (строки) в любом поле;он возвращает 50 строк (с разбиением на страницы), начиная с указанных критериев (каждый столбец может быть восходящим или нисходящим).Когда критерии не соответствуют существующим индексам, поиск замедляется, и клиент недоволен.

И затем - в середине встречи - полутехнический аналитик бросил этот вthe air: Почему бы нам не создать все возможные индексы на столе, чтобы все было быстро?

Я сразу ответил: "Нет, их слишком много, и это действительно сделает таблицумедленное изменение, поэтому нам нужно создать несколько хитроумно выбранных индексов, чтобы сделать это ".Мы закончили тем, что создали самые полезные, и страница теперь намного быстрее.Проблема решена.

Вопрос

Но все же ... Я продолжаю думать об этом вопросе и хочу лучше понять его, поэтому вот оно:

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

Я думаю, что полезными мы должны рассмотреть(Я могу ошибаться):

• Индексы, еще не охваченные другими: например, (a, b) не должны учитываться, если (a, b, c) включено.
• Для отображения нескольких строк (а не только равенства) восходящие и нисходящие индексы должны учитываться как отдельные, когда они являются частью составного индекса.То есть: (a) служит той же цели (DESC), но (a, b) служит другой цели, чем (DESC, b).

Итак, таблица с однимстолбец (a) может иметь только один индекс:

(a)

С двумя столбцами (a, b) я могу иметь четыре полезных индексов:

(a, b)
(b, a)
(a DESC, b)
(b DESC, a)
(a) -- already covered by #1
(b) -- already covered by #2
(a, b DESC) -- already coverred by #1 (reading index in reverse)
(b, a DESC) -- already covered by #2
(a DESC, b DESC) -- already covered by #3
(b DESC, a DESC) -- already covered by #4
(a DESC) -- already covered by #3
(b DESC) -- already covered by #4

С тремя столбцами (а, б, в):

(a, b, c)
(a, c, b)
(b, c, a)
(b, a, c)
(c, a, b)
(c, b, a)
...

Answer 1

Допустим, у вас есть таблица t со столбцами a, b и c.

Для запроса

select a from t where b = 1 order by c;

лучший индекс для t (b, c, a), потому что вы сначала просматриваете значения, используя b, затем упорядочиваете результаты по c и получаете a в результатах.

Для этого запроса:

select a from t where c = 1 order by b;

лучший индекс по t (c, b, a).

Для этого запроса:

select b from t where c = 1 order by a;

лучший индекс по t (c, a, b).

С большим количеством столбцов запрос может выглядеть так:

select a from t where b = 1 order by c, d, e;

и вам лучше всего нужен индекс для t (b, c, d, e, a).

Пока для

select a from t where b = 1 order by e, d, c;

вы хотите индекс для t (b, e, d, c, a).

Таким образом, максимальное количество полезных индексов для n столбцов равно n !, то есть всем перестановкам.

Это для индексов только по столбцам. Как Гордон Линофф упомянул в разделе комментариев к вашему запросу, вы также можете захотеть индексы функций (например, для t (верхний (a), нижний (b)). Число полезных индексов функций теоретически не ограничено. И да, Гордон также верно в отношении других типов индексов.

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

Answer 2

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

Нет точного ответа на вопрос, как вы его задали. В некотором смысле это все равно, что спросить & ldquo; Каков предел, за которым вы бы назвали человека сумасшедшим? & Rdquo; Большая серая зона.

Мои очки:

• Что произойдет, если вы добавите слишком много индексов:

  • Изменение таблицы происходит значительно медленнее. Даже с небольшим количеством индексов манипулирование данными уже станет на порядок медленнее. Если вы когда-нибудь захотите INSERT, UPDATE или DELETE, таблица со всеми возможными индексами сделает такую ​​операцию ледяной медленной.

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

• Что вы можете сделать, чтобы уменьшить количество необходимых индексов:

  • Посмотрите на операторов. Если операторы <, <=, >= и > никогда не используются, нет смысла добавлять индексы с нисходящими столбцами.

  • Помните, что индекс для (a, b, c) также можно использовать для запроса, который использует только 1010 * в своем состоянии, поэтому вам не нужен дополнительный индекс для (a).

    * 1042. *

• Какой практический путь вперед для вас?

  У меня есть два предложения:

  1. Один способ добавить простой индекс для каждого из ваших двенадцати столбцов.

     Двенадцать индексов уже довольно много, но вы все еще не находитесь в безумном диапазоне.

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

     Это потому, что PostgreSQL имеет сканирований растровых индексов . Посмотрите этот пример из документации :

     EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 100 AND unique2 > 9000;
     
                                          QUERY PLAN
     -------------------------------------------------------------------------------------
      Bitmap Heap Scan on tenk1  (cost=25.08..60.21 rows=10 width=244)
        Recheck Cond: ((unique1 < 100) AND (unique2 > 9000))
        ->  BitmapAnd  (cost=25.08..25.08 rows=10 width=0)
              ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..5.04 rows=101 width=0)
                    Index Cond: (unique1 < 100)
              ->  Bitmap Index Scan on tenk1_unique2  (cost=0.00..19.78 rows=999 width=0)
                    Index Cond: (unique2 > 9000)
     

     Каждый индекс сканируется и формируется растровое изображение, которое содержит 1 для каждой строки, соответствующей условию. Затем растровые изображения объединяются, и, наконец, строки выбираются из таблицы.

  2. Другая идея - использовать Фильтр Блума .

     Если единственным оператором в ваших условиях является =, вы можете

     CREATE EXTENSION bloom;
     

     и создайте одиночный индекс USING bloom для всех столбцов таблицы .

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

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

Answer 3

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

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

Первое, на что следует обратить внимание, - это то, что всех последовательных поисков следует избегать (если таблица очень мала). Под «очень маленьким» я подразумеваю всего несколько рядов (скажем, максимум 10). (Однако даже в такой таблице рекомендуется использовать первичный ключ для обеспечения уникальности. Это, конечно, будет реализовано в виде индекса.)

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

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

Так что такой подход предлагается - предупредить клиента соответственно.

При проверке важно убедиться, что в операторе SQL используются индексированные пути поиска (для каждой доступной таблицы), а не последовательный поиск. У ORACLE есть инструмент для этого, который называется EXPLAIN PLAN. Другие БД также должны иметь аналогичные инструменты.