Индексы SQL для поиска "не равных"

Question

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

essais=> \d phone_idx
Index "public.phone_idx"
 Column | Type 
--------+------
 phone  | text
btree, for table "public.phonespersons"

essais=> EXPLAIN SELECT person FROM PhonesPersons WHERE phone = '+33 1234567';
                                  QUERY PLAN                                   
-------------------------------------------------------------------------------
 Index Scan using phone_idx on phonespersons  (cost=0.00..8.41 rows=1 width=4)
   Index Cond: (phone = '+33 1234567'::text)
(2 rows)

essais=> EXPLAIN SELECT person FROM PhonesPersons WHERE phone != '+33 1234567';
                              QUERY PLAN                              
----------------------------------------------------------------------
 Seq Scan on phonespersons  (cost=0.00..18621.00 rows=999999 width=4)
   Filter: (phone <> '+33 1234567'::text)
(2 rows)

Я понимаю (см. Очень хорошие объяснения Марка Байерса), что PostgreSQL может решить не использовать индекс, когда он видит, что последовательное сканирование будет быстрее (например, если почти все кортежи совпадают). Но, здесь «неравный» поиск действительно медленнее.

Можно ли как-нибудь ускорить поиск "не равно"?

Вот еще один пример, касающийся замечательных замечаний Марка Байерса. Индекс используется для запроса '=' (который возвращает подавляющее большинство кортежи), но не для запроса '! =':

essais=> \d tld_idx
 Index "public.tld_idx"
     Column      | Type 
-----------------+------
 pg_expression_1 | text
btree, for table "public.emailspersons"

essais=> EXPLAIN ANALYZE SELECT person FROM EmailsPersons WHERE tld(email) = 'fr';
                             QUERY PLAN                                                             
------------------------------------------------------------------------------------------------------------------------------------
 Index Scan using tld_idx on emailspersons  (cost=0.25..4010.79 rows=97033 width=4) (actual time=0.137..261.123 rows=97110 loops=1)
   Index Cond: (tld(email) = 'fr'::text)
 Total runtime: 444.800 ms
(3 rows)

essais=> EXPLAIN ANALYZE SELECT person FROM EmailsPersons WHERE tld(email) != 'fr';
                         QUERY PLAN                                                     
--------------------------------------------------------------------------------------------------------------------
 Seq Scan on emailspersons  (cost=0.00..27129.00 rows=2967 width=4) (actual time=1.004..1031.224 rows=2890 loops=1)
   Filter: (tld(email) <> 'fr'::text)
 Total runtime: 1037.278 ms
(3 rows)

СУБД - это PostgreSQL 8.3 (но я могу обновиться до 8.4).

Answer 1

База данных может использовать индекс для этого запроса, но предпочитает не использовать, потому что это будет медленнее. Обновление : Это не совсем верно: вам нужно слегка переписать запрос. См. Ответ Аракнида.

Предложение where выбирает почти все строки в вашей таблице (rows = 999999). База данных может видеть, что сканирование таблицы будет быстрее в этом случае и поэтому игнорирует индекс. Это быстрее, поскольку столбец person отсутствует в вашем индексе, поэтому для каждой строки потребуется выполнить два поиска: один раз в индексе, чтобы проверить предложение WHERE, а затем снова в основной таблице, чтобы получить столбец person. .

Если бы у вас был другой тип данных, где большинство значений были foo, и только некоторые из них были bar, а вы сказали WHERE col <> 'foo', то, вероятно, он использовал бы индекс.

Можно ли как-нибудь ускорить поиск "не равно"?

Любой запрос, который выбирает почти 1 миллион строк, будет медленным. Попробуйте добавить предложение limit.

Answer 2

Возможно, это поможет написать:

SELECT person FROM PhonesPersons WHERE phone < '+33 1234567'
UNION ALL
SELECT person FROM PhonesPersons WHERE phone > '+33 1234567'

или просто

SELECT person FROM PhonesPersons WHERE phone > '+33 1234567'
                                       OR phone < '+33 1234567'

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

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

Обоснование: поиск индекса по всем значениям, не равным определенному, требует сканирования полного индекса. В отличие от этого, поиск всех элементов, меньших определенного ключа, означает нахождение наибольшего несоответствующего элемента в дереве и сканирование назад. Аналогично, поиск всех элементов больше определенного ключа в обратном направлении. Эти операции легко выполнить с помощью структур b-дерева. Кроме того, статистика, которую собирает PostgreSQL, должна указывать на то, что «+33 1234567» является известным частым значением: удалив частоту этих значений и нулей из 1, мы получим пропорцию оставшихся строк: границы гистограммы укажите, перекошены ли они в одну сторону или нет. Но если исключение нулей и этого частого значения приводит к увеличению доли строк, оставшихся достаточно низкими (Istr около 20%), сканирование индекса должно быть уместным. Проверьте статистику для столбца в pg_stats, чтобы увидеть, какая пропорция фактически рассчитана.

Обновление : я пробовал это на локальной таблице с неопределенно похожим распределением, и обе формы выше дали что-то отличное от простого сканирования seq. Последнее (с использованием «ИЛИ») было растровым сканированием, которое может фактически превратиться в просто последовательное сканирование, если смещение к вашему общему значению особенно велико ... хотя планировщик может это увидеть, я не думаю, что он будет автоматически внутренне переписать в «Добавить (сканирование индекса, сканирование индекса)». Отключение «enable_bitmapscan» просто вернуло его к последующему сканированию.

PS : индексация текстового столбца и использование операторов неравенства могут быть проблемой, если ваша база данных не C. Это может потребоваться добавить дополнительный индекс, который использует text_pattern_ops или varchar_pattern_ops; это похоже на проблему индексации для предикатов column LIKE 'prefix%'.

Альтернатива : вы можете создать частичный индекс:

CREATE INDEX PhonesPersonsOthers ON PhonesPersons(phone) WHERE phone <> '+33 1234567'

это сделает оператор выбора, использующий <>, просто просканирует этот частичный индекс: поскольку он исключает большинство записей в таблице, он должен быть небольшим.