title: SQL indexes for "not equal" searches
body: <p>The SQL index allows to find quickly a string which matches my query. Now, I have to search in a big table the strings which do <strong>not</strong> match. Of course, the normal index does not help and I have to do a slow sequential scan:</p>
  
  <pre><code>essais=&gt; \d phone_idx
  Index "public.phone_idx"
   Column | Type 
  --------+------
   phone  | text
  btree, for table "public.phonespersons"
  
  essais=&gt; 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=&gt; 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 &lt;&gt; '+33 1234567'::text)
  (2 rows)
  </code></pre>
  
  <p>I understand (see Mark Byers' very good explanations) that PostgreSQL
  can decide not to use an index when it sees that a sequential scan
  would be faster (for instance if almost all the tuples match). But,
  here, "not equal" searches are really slower.</p>
  
  <p>Any way to make these "is not equal to" searches faster?</p>
  
  <p>Here is another example, to address Mark Byers' excellent remarks. The
  index is used for the '=' query (which returns the vast majority of
  tuples) but not for the '!=' query:</p>
  
  <pre><code>essais=&gt; \d tld_idx
   Index "public.tld_idx"
       Column      | Type 
  -----------------+------
   pg_expression_1 | text
  btree, for table "public.emailspersons"
  
  essais=&gt; 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=&gt; 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) &lt;&gt; 'fr'::text)
   Total runtime: 1037.278 ms
  (3 rows)
  </code></pre>
  
  <p>DBMS is PostgreSQL 8.3 (but I can upgrade to 8.4).</p>