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 = '[phone]';
                                  QUERY PLAN                                   
-------------------------------------------------------------------------------
 Index Scan using phone_idx on phonespersons  (cost=0.00..8.41 rows=1 width=4)
   Index Cond: (phone = '[phone]'::text)
(2 rows)

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

我明白（参见Mark Byers的非常好的解释），PostgreSQL可以决定在顺序扫描更快时不使用索引（例如，如果几乎所有元组匹配）。 但是，在这里，“不相等”的搜索确实较慢。

有没有办法使这些“不等于”搜索更快？

这里是另一个例子，用来解决Mark Byers所说的优秀评论。 索引用于“=”查询（返回绝大多数元组），但不用于“！=”查询：

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）。

- bortzmeyer

Answer 1

或许写成这样会更有帮助：

SELECT person FROM PhonesPersons WHERE phone < '[phone]'
UNION ALL
SELECT person FROM PhonesPersons WHERE phone > '[phone]'

或者简单地

SELECT person FROM PhonesPersons WHERE phone > '[phone]'
                                       OR phone < '[phone]'

PostgreSQL应该能够确定范围操作的选取性非常高，并考虑使用索引来执行。

我认为它不能直接使用索引来满足不等式谓词，尽管在规划期间重写不等式谓词可能会很好。如果有效，请向开发人员建议；）

原因：在索引中搜索所有值不等于特定值的数据需要扫描整个索引。相比之下，搜索所有小于某个键的元素意味着找到树中最大的不匹配项并向后扫描。同样地，向反方向搜索所有大于某个键的元素。这些操作可以使用B树结构轻松实现。此外，PostgreSQL收集的统计信息应该能够指出“[phone]”是已知的频繁值：通过从1中删除那些和空值的频率，我们得到剩余要选择的行的比例：直方图边界将指示这些是否偏斜一侧或不偏斜。但是，如果不包括null和频繁值使剩余行的比例降低到足够低（大约20%），那么索引扫描就是适当的。请检查pg_stats中列的统计信息以查看它实际计算了多少比例。

更新：我在本地表上尝试了一个大致相似的分布，以上两种形式都产生了与纯序列扫描不同的结果。后者（使用“OR”）是位图扫描，如果对常见值的偏向特别极端，则可能实际上会退化为仅是序列扫描...尽管规划器可以看到这一点，但我认为它不会自动重写为“附加（索引扫描，索引扫描）”内部表示。将“enable_bitmapscan”关闭只会使其恢复为序列扫描。

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

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

CREATE INDEX PhonesPersonsOthers ON PhonesPersons(phone) WHERE phone <> '[phone]'

这将使使用<>的select语句只扫描部分索引：因为它排除了表中的大多数条目，所以它应该很小。

- araqnid

---

我刚刚测试了你将“<>”重写为“< OR >”的想法，它有效。EXPLAIN显示索引被使用，性能得到了很大提升。我会进行更多的测试，并接受你的答案。问题：为什么PostgreSQL不能自己进行这种重写？ - bortzmeyer

@bortzmeyer 可能是因为操作系统太通用了-它需要一些将“=”/“<>”运算符对与“<”和“>”相关联的方法。建议将其作为PostgreSQL列表的一个功能提出可能值得一试。 - araqnid

好的，它运行得很好，谢谢。一个小警告：并不是所有的PostgreSQL索引都有排序功能。http://www.postgresql.org/docs/current/interactive/indexes-types.html - bortzmeyer

@bortzmeyer 刚刚意识到你也可以使用部分索引来实现这一点，请查看更新。 - araqnid

Answer 2

数据库能够使用索引来处理此查询，但它选择不这样做是因为这样会更慢。更新：这并不完全正确：您需要稍微改写查询。请参见Araqnid的答案。

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

如果您有一种不同类型的数据，其中大多数值都是“foo”，只有少数是“bar”，而您说“WHERE col <> 'foo'”，则可能会使用索引。

有什么方法可以使这些“不等于”搜索更快吗？

任何选择几乎1百万行的查询都会很慢。尝试添加限制子句。

- Mark Byers

---

好的，我经常忘记数据库管理系统比我更聪明，有时候会故意决定不使用索引。它甚至取决于查询中实际的值。然而，即使是在特别填充了数据的数据库中，我还没有能够使用索引进行NOT查询。即使只选择了80行，PostgreSQL也会使用Seq扫描。 - bortzmeyer

最终，我采用了araqnid的解决方案（将“<>”重写为“<或>”），并接受了他的解决方案。谢谢。 - bortzmeyer