"不等于"搜索的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)

我理解(参见Mark Byers的非常好的解释),当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)

DBMS是PostgreSQL 8.3(但我可以升级到8.4).

Answer 1

可能会有助于编写：

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扫描以外的结果。后者（使用“ OR”）是位图扫描，如果对您的共同价值的偏向特别极端，则实际上可能会演变成只是seq扫描...尽管计划人员可以看到，但我认为它不会自动进行在内部重写为“追加（索引扫描，索引扫描）”。关闭“ enable_bitmapscan”只会使其恢复到seq扫描。

PS：如果您的数据库位置不是C，则为文本列建立索引并使用不等式运算符可能会成为一个问题。您可能需要添加使用text_pattern_ops或varchar_pattern_ops的额外索引；这类似于column LIKE 'prefix%'谓词索引的问题。

替代方案：您可以创建部分索引：

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

这将使<>-using select语句仅扫描该部分索引：由于它不包含表中的大多数条目，因此它应该很小。

Answer 2

数据库能够使用此查询的索引,但它选择不这样做,因为它会更慢.更新:这不太正确:您必须稍微重写查询.见Araqnid的答案.

您的where子句选择表中的几乎所有行(rows = 999999).在这种情况下,数据库可以看到表扫描速度更快,因此忽略了索引.它更快,因为列person不在索引中,所以它必须为每一行进行两次查找,一次在索引中检查WHERE子句,然后在主表中再次获取列person.

如果你有一个不同类型的数据,其中有大多数值foo,只有少数bar,你说,WHERE col <> 'foo'那么它可能会使用索引.

任何方法使这些"不等于"搜索更快？

任何选择近100万行的查询都会很慢.尝试添加限制子句.