Использование индекса снижает производительность. Если процент совпадений составляет небольшую долю от всей таблицы, эта стоимость больше, чем восполняется отсутствием необходимости сканирования всей таблицы. Но если есть большой процент совпадений, быстрее просто прочитать таблицу.
Существует стоимость чтения индекса. Небольшой, часто используемый индекс может находиться в памяти, но большой или редко используемый индекс может находиться на диске. Это означает медленный доступ к диску для поиска в индексе и получения соответствующих номеров строк. Если запрос соответствует небольшому количеству строк, эти издержки выигрывают при поиске по всей таблице. Если запрос соответствует большому количеству строк, эти издержки являются пустой тратой; в любом случае вам придется читать всю таблицу.
Тогда есть затраты на ввод-вывод. С дисками намного, намного быстрее читать и писать последовательно, чем случайно . Мы говорим в 10-100 раз быстрее.
У вращающегося диска есть физическая часть, головка, и он должен двигаться, чтобы читать разные части диска. Время, необходимое для перемещения, известно как «время поиска». Когда вы пропускаете между строками в таблице, возможно, не по порядку, это произвольный доступ и вызывает время поиска. Напротив, чтение всей таблицы, вероятно, будет одним длинным непрерывным чтением; голова не должна прыгать, нет времени на поиск.
SSD намного, намного быстрее, нет физических частей для перемещения, но они все еще намного быстрее для последовательного доступа, чем случайные .
Кроме того, произвольный доступ увеличивает нагрузку на операционную систему и диск; требуется больше инструкций.
Так что, если база данных решит, что запрос будет соответствовать большинству строк таблицы, она может решить, что быстрее читать их последовательно и отсеивать несоответствия, чем ищите строки по индексу и используя более медленный произвольный доступ.
Рассмотрим банк почтовых ящиков, каждый из которых пронумерован в большой сетке. Довольно быстро искать каждую коробку по номеру, но гораздо быстрее начать с коробки и открыть их по порядку. И у нас есть индекс того, кто владеет какой коробкой и где они живут.
Вам нужно получить почту для Саут Нортпорт. Вы просматриваете в индексе, какие ящики принадлежат кому-то из Саут-Нортпорта, видите, что их всего несколько, и получаете почту по отдельности. Это индексированный запрос и произвольный доступ. Это быстро, потому что есть только несколько почтовых ящиков для проверки.
Теперь я прошу вас получить почту для всех , но Южный Нортпорт. Вы можете использовать индекс в обратном порядке: получить список ящиков для Саут-Нортпорта, вычесть их из списка каждого ящика, а затем по отдельности получить почту для каждого ящика. Но это будет медленный, произвольный доступ. Вместо этого, поскольку вам все равно придется открывать почти каждый ящик, быстрее проверить каждый ящик по очереди и посмотреть, является ли он почтовым для Южного Нортпорта.
Более формально индексированная таблица против таблицы Производительность сканирования примерно такая.
# Indexed query
C[index] + (C[random] * M)
# Full table scan
(C[sequential] + C[match]) * N
Где C - это различные постоянные затраты (или почти постоянные значения), M - это количество совпадающих строк, а N - количество строк. в таблице.
Мы знаем, что C[sequential] в 10-100 раз быстрее, чем C[random]. Поскольку доступ к диску намного медленнее, чем операции с процессором или памятью, C[match] (стоимость проверки соответствия строки) будет относительно небольшим по сравнению с C[sequential]. Более формально ...
C[random] >> C[sequential] >> C[match]
Используя это, мы можем предположить, что C[sequential] + C[match] равно C[sequential].
# Indexed query
C[index] + (C[random] * M)
# Full table scan
C[sequential] * N
Когда M << N индексированный запрос побеждает. Когда M приближается к N, выигрывает полное сканирование таблицы.
Обратите внимание, что стоимость использования индекса на самом деле не постоянна. C[index] - это такие вещи, как загрузка индекса, поиск ключа и чтение идентификаторов строк. Это может быть весьма изменчиво в зависимости от размера индекса, типа индекса и от того, находится ли он на диске (холодный) или в памяти (горячий). Вот почему первые несколько запросов часто довольно медленные, когда вы впервые запускаете сервер базы данных.
В реальном мире все сложнее. В действительности строки разбиты на страницы данных , а в базах данных есть много хитростей для оптимизации запросов и доступа к диску. Но, как правило, если вы сопоставляете большинство строк, полное сканирование таблицы превзойдет индексированный поиск.
Ха sh индексы в настоящее время используются ограниченно. Это простая пара ключ / значение и может использоваться только для проверки на равенство. Большинство баз данных используют B-Tree в качестве стандартного индекса. Они немного дороже, но могут обрабатывать более широкий диапазон операций, включая равенство, диапазоны, сравнения и поиск префиксов, например like 'foo%'.
Документация Postgres Типы индексов довольно хороший высокий уровень различных преимуществ и недостатков типов индексов.