Índices SQL para búsquedas "no iguales"

Question

El índice SQL permite encontrar rápidamente una cadena que coincida con mi consulta. Ahora, tengo que buscar en una tabla grande las cadenas que hacen no coincide con. Por supuesto, el índice normal no ayudará y tengo que hacer una exploración secuencial lenta:

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) 

entiendo (ver explicaciones muy buenas Marcos Byers') que PostgreSQL puede decidir no utilizar un índice cuando se ve que un escaneo secuencial sería más rápido (por ejemplo, si casi todas las tuplas coinciden). Pero, aquí, las búsquedas "no iguales" son realmente más lentas.

¿Alguna manera de hacer que estas búsquedas "no sean iguales" más rápido?

Aquí hay otro ejemplo, para abordar las excelentes observaciones de Mark Byers. El índice se utiliza para la consulta '=' (que devuelve la gran mayoría de tuplas), pero no para la consulta '=':

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 es PostgreSQL 8.3 (pero puede actualizar a 8.4) .

Answer 1

Posiblemente que ayudaría a escribir:

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

o simplemente

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

PostgreSQL debe ser capaz de determinar que la selectividad de la operación gama es muy alta y considerar el uso de un índice para eso.

No creo que pueda usar un índice directamente para satisfacer un predicado no igual, aunque sería bueno si pudiera intentar volver a escribir los no iguales como los anteriores (si es que lo ayuda) durante la planificación. Si funciona, sugiérelo a los desarrolladores;)

Justificación: buscar en un índice todos los valores que no sean iguales requiere escanear el índice completo.Por el contrario, buscar todos los elementos con menos de una clave determinada significa encontrar el elemento más grande que no coincide en el árbol y escanear hacia atrás. Del mismo modo, busca todos los elementos superiores a una determinada clave en la dirección opuesta. Estas operaciones son fáciles de cumplir usando estructuras de árbol b. Además, las estadísticas que recopila PostgreSQL deberían ser capaces de señalar que "+33 1234567" es un valor frecuente conocido: al eliminar la frecuencia de esos y nulos de 1, tenemos la proporción de filas que quedan por seleccionar: los límites del histograma Indique si están sesgados hacia un lado o no. Pero si la exclusión de valores nulos y ese valor frecuente empuja la proporción de filas que permanecen lo suficientemente bajas (Istr aproximadamente 20%), un escaneo de índice debería ser apropiado. Verifique las estadísticas de la columna en pg_stats para ver qué proporción se calcula realmente.

Actualización: Intenté esto en una tabla local con una distribución vagamente similar, y ambas formas de lo anterior produjeron algo más que un escaneo seq simple. El último (usando "O") era un escaneo de mapa de bits que en realidad podría convertirse en un escaneo seq si el sesgo hacia su valor común es particularmente extremo ... aunque el planificador puede ver eso, no creo que sea automático reescriba a "Anexar (Escaneo de índice, Escaneo de índice)" internamente. Al desactivar "enable_bitmapscan", se volvió a escanear seq.

PS: indexar una columna de texto y el uso de los operadores de desigualdad puede ser un problema, si la ubicación de la base de datos no es C. Es posible que necesite añadir un índice adicional que utiliza text_pattern_ops o varchar_pattern_ops; esto es similar al problema de la indexación para los predicados column LIKE 'prefix%'.

Alternativa: se puede crear un índice parcial:

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

Esto hará que el <> -utilizando instrucción de selección acaba de escanear a través de ese índice parcial: ya que excluye a la mayor parte de las entradas de la tabla, debe ser pequeño

Answer 2

La base de datos puede usar el índice para esta consulta, pero elige no hacerlo porque sería más lento. Actualización: Esto no es del todo correcto: tiene que volver a escribir la consulta ligeramente. Vea la respuesta de Araqnid.

Su cláusula where selecciona casi todas las filas en su tabla (filas = 999999). La base de datos puede ver que un escaneo de tabla sería más rápido en este caso y, por lo tanto, ignora el índice. Es más rápido porque la columna person no está en su índice, por lo que tendría que realizar dos búsquedas para cada fila, una vez en el índice para verificar la cláusula WHERE y luego nuevamente en la tabla principal para buscar la columna person.

Si tenía un tipo diferente de datos donde la mayoría de los valores eran foo y solo unos pocos eran bar y dijo WHERE col <> 'foo' entonces probablemente usaría el índice.

¿Hay alguna manera de hacer que estas búsquedas "no sean iguales" se hagan más rápido?

Cualquier consulta que seleccione casi 1 millón de filas va a ser lenta. Intenta agregar una cláusula de límite.