Hacer esta pregunta, específicamente para Postgres, ya que tiene un buen supoort para los índices R-tree / espacial.

Tenemos la siguiente tabla con una estructura de árbol (modelo de conjunto anidado) de palabras y sus frecuencias:

lexikon
-------
_id   integer  PRIMARY KEY
word  text
frequency integer
lset  integer  UNIQUE KEY
rset  integer  UNIQUE KEY

Y la consulta:

SELECT word
FROM lexikon
WHERE lset BETWEEN @Low AND @High
ORDER BY frequency DESC
LIMIT @N

Supongo que (lset, frequency, word)sería útil un índice de cobertura, pero creo que puede no funcionar bien si hay demasiados lsetvalores en el (@High, @Low)rango.

Un índice simple en (frequency DESC)también puede ser suficiente a veces, cuando una búsqueda que usa ese índice produce temprano las @Nfilas que coinciden con la condición de rango.

Pero parece que el rendimiento depende mucho de los valores de los parámetros.

¿Hay alguna manera de hacer que funcione rápidamente, independientemente de si el rango (@Low, @High)es ancho o estrecho y si las palabras de frecuencia superior están afortunadamente en el rango seleccionado (estrecho)?

¿Ayudaría un árbol R / índice espacial?

Agregar índices, reescribir la consulta, rediseñar la tabla, no hay limitación.

Puede lograr un mejor rendimiento buscando primero en filas con frecuencias más altas. Esto se puede lograr 'granulando' las frecuencias y luego avanzando por ellas de manera procesal, por ejemplo, de la siguiente manera:

--testbed y lexikondatos ficticios:

begin;
set role dba;
create role stack;
grant stack to dba;
create schema authorization stack;
set role stack;
--
create table lexikon( _id serial, 
                      word text, 
                      frequency integer, 
                      lset integer, 
                      width_granule integer);
--
insert into lexikon(word, frequency, lset) 
select word, (1000000/row_number() over(order by random()))::integer as frequency, lset
from (select 'word'||generate_series(1,1000000) word, generate_series(1,1000000) lset) z;
--
update lexikon set width_granule=ln(frequency)::integer;
--
create index on lexikon(width_granule, lset);
create index on lexikon(lset);
-- the second index is not used with the function but is added to make the timings 'fair'

granule análisis (principalmente para información y ajuste):

create table granule as 
select width_granule, count(*) as freq, 
       min(frequency) as granule_start, max(frequency) as granule_end 
from lexikon group by width_granule;
--
select * from granule order by 1;
/*
 width_granule |  freq  | granule_start | granule_end
---------------+--------+---------------+-------------
             0 | 500000 |             1 |           1
             1 | 300000 |             2 |           4
             2 | 123077 |             5 |          12
             3 |  47512 |            13 |          33
             4 |  18422 |            34 |          90
             5 |   6908 |            91 |         244
             6 |   2580 |           245 |         665
             7 |    949 |           666 |        1808
             8 |    349 |          1811 |        4901
             9 |    129 |          4926 |       13333
            10 |     47 |         13513 |       35714
            11 |     17 |         37037 |       90909
            12 |      7 |        100000 |      250000
            13 |      2 |        333333 |      500000
            14 |      1 |       1000000 |     1000000
*/
alter table granule drop column freq;
--

función para escanear frecuencias altas primero:

create function f(p_lset_low in integer, p_lset_high in integer, p_limit in integer)
       returns setof lexikon language plpgsql set search_path to 'stack' as $$
declare
  m integer;
  n integer := 0;
  r record;
begin 
  for r in (select width_granule from granule order by width_granule desc) loop
    return query( select * 
                  from lexikon 
                  where width_granule=r.width_granule 
                        and lset>=p_lset_low and lset<=p_lset_high );
    get diagnostics m = row_count;
    n = n+m;
    exit when n>=p_limit;
  end loop;
end;$$;

resultados (los tiempos probablemente deberían tomarse con una pizca de sal, pero cada consulta se ejecuta dos veces para contrarrestar cualquier almacenamiento en caché)

primero usando la función que hemos escrito:

\timing on
--
select * from f(20000, 30000, 5) order by frequency desc limit 5;
/*
 _id |   word    | frequency | lset  | width_granule
-----+-----------+-----------+-------+---------------
 141 | word23237 |      7092 | 23237 |             9
 246 | word25112 |      4065 | 25112 |             8
 275 | word23825 |      3636 | 23825 |             8
 409 | word28660 |      2444 | 28660 |             8
 418 | word29923 |      2392 | 29923 |             8
Time: 80.452 ms
*/
select * from f(20000, 30000, 5) order by frequency desc limit 5;
/*
 _id |   word    | frequency | lset  | width_granule
-----+-----------+-----------+-------+---------------
 141 | word23237 |      7092 | 23237 |             9
 246 | word25112 |      4065 | 25112 |             8
 275 | word23825 |      3636 | 23825 |             8
 409 | word28660 |      2444 | 28660 |             8
 418 | word29923 |      2392 | 29923 |             8
Time: 0.510 ms
*/

y luego con un escaneo de índice simple:

select * from lexikon where lset between 20000 and 30000 order by frequency desc limit 5;
/*
 _id |   word    | frequency | lset  | width_granule
-----+-----------+-----------+-------+---------------
 141 | word23237 |      7092 | 23237 |             9
 246 | word25112 |      4065 | 25112 |             8
 275 | word23825 |      3636 | 23825 |             8
 409 | word28660 |      2444 | 28660 |             8
 418 | word29923 |      2392 | 29923 |             8
Time: 218.897 ms
*/
select * from lexikon where lset between 20000 and 30000 order by frequency desc limit 5;
/*
 _id |   word    | frequency | lset  | width_granule
-----+-----------+-----------+-------+---------------
 141 | word23237 |      7092 | 23237 |             9
 246 | word25112 |      4065 | 25112 |             8
 275 | word23825 |      3636 | 23825 |             8
 409 | word28660 |      2444 | 28660 |             8
 418 | word29923 |      2392 | 29923 |             8
Time: 51.250 ms
*/
\timing off
--
rollback;

Dependiendo de sus datos del mundo real, es probable que desee variar la cantidad de gránulos y la función utilizada para colocar filas en ellos. La distribución real de frecuencias es clave aquí, al igual que los valores esperados para la limitcláusula y el tamaño de los lsetrangos buscados.

Preparar

Estoy construyendo sobre la configuración de @ Jack para que sea más fácil para las personas seguir y comparar. Probado con PostgreSQL 9.1.4 .

CREATE TABLE lexikon (
   lex_id    serial PRIMARY KEY
 , word      text
 , frequency int NOT NULL  -- we'd need to do more if NULL was allowed
 , lset      int
);

INSERT INTO lexikon(word, frequency, lset) 
SELECT 'w' || g  -- shorter with just 'w'
     , (1000000 / row_number() OVER (ORDER BY random()))::int
     , g
FROM   generate_series(1,1000000) g

De aquí en adelante tomo una ruta diferente:

ANALYZE lexikon;

Mesa auxiliar

Esta solución no agrega columnas a la tabla original, solo necesita una pequeña tabla auxiliar. Lo puse en el esquema public, use cualquier esquema de su elección.

CREATE TABLE public.lex_freq AS
WITH x AS (
   SELECT DISTINCT ON (f.row_min)
          f.row_min, c.row_ct, c.frequency
   FROM  (
      SELECT frequency, sum(count(*)) OVER (ORDER BY frequency DESC) AS row_ct
      FROM   lexikon
      GROUP  BY 1
      ) c
   JOIN  (                                   -- list of steps in recursive search
      VALUES (400),(1600),(6400),(25000),(100000),(200000),(400000),(600000),(800000)
      ) f(row_min) ON c.row_ct >= f.row_min  -- match next greater number
   ORDER  BY f.row_min, c.row_ct, c.frequency DESC
   )
, y AS (   
   SELECT DISTINCT ON (frequency)
          row_min, row_ct, frequency AS freq_min
        , lag(frequency) OVER (ORDER BY row_min) AS freq_max
   FROM   x
   ORDER  BY frequency, row_min
   -- if one frequency spans multiple ranges, pick the lowest row_min
   )
SELECT row_min, row_ct, freq_min
     , CASE freq_min <= freq_max
         WHEN TRUE  THEN 'frequency >= ' || freq_min || ' AND frequency < ' || freq_max
         WHEN FALSE THEN 'frequency  = ' || freq_min
         ELSE            'frequency >= ' || freq_min
       END AS cond
FROM   y
ORDER  BY row_min;

La tabla se ve así:

row_min | row_ct  | freq_min | cond
--------+---------+----------+-------------
400     | 400     | 2500     | frequency >= 2500
1600    | 1600    | 625      | frequency >= 625 AND frequency < 2500
6400    | 6410    | 156      | frequency >= 156 AND frequency < 625
25000   | 25000   | 40       | frequency >= 40 AND frequency < 156
100000  | 100000  | 10       | frequency >= 10 AND frequency < 40
200000  | 200000  | 5        | frequency >= 5 AND frequency < 10
400000  | 500000  | 2        | frequency >= 2 AND frequency < 5
600000  | 1000000 | 1        | frequency  = 1

Como la columna condse va a usar en SQL dinámico más abajo, debe hacer que esta tabla sea segura . Siempre califique el esquema de la tabla si no puede estar seguro de una corriente apropiada search_pathy revoque los privilegios de escritura de public(y cualquier otra función no confiable):

REVOKE ALL ON public.lex_freq FROM public;
GRANT SELECT ON public.lex_freq TO public;

La tabla lex_freqtiene tres propósitos:

• Cree los índices parciales necesarios automáticamente.
• Proporcionar pasos para la función iterativa.
• Metainformación para afinar.

Índices

Esta DOdeclaración crea todos los índices necesarios:

DO
$$
DECLARE
   _cond text;
BEGIN
   FOR _cond IN
      SELECT cond FROM public.lex_freq
   LOOP
      IF _cond LIKE 'frequency =%' THEN
         EXECUTE 'CREATE INDEX ON lexikon(lset) WHERE ' || _cond;
      ELSE
         EXECUTE 'CREATE INDEX ON lexikon(lset, frequency DESC) WHERE ' || _cond;
      END IF;
   END LOOP;
END
$$

Todos estos índices parciales juntos abarcan la tabla una vez. Son aproximadamente del mismo tamaño que un índice básico en toda la tabla:

SELECT pg_size_pretty(pg_relation_size('lexikon'));       -- 50 MB
SELECT pg_size_pretty(pg_total_relation_size('lexikon')); -- 71 MB

Solo 21 MB de índices para una tabla de 50 MB hasta ahora.

Creo la mayoría de los índices parciales en (lset, frequency DESC). La segunda columna solo ayuda en casos especiales. Pero como ambas columnas involucradas son de tipo integer, debido a los detalles de la alineación de datos en combinación con MAXALIGN en PostgreSQL, la segunda columna no hace que el índice sea más grande. Es una pequeña victoria por casi ningún costo.

No tiene sentido hacerlo para índices parciales que solo abarcan una sola frecuencia. Esos son sólo en (lset). Los índices creados se ven así:

CREATE INDEX ON lexikon(lset, frequency DESC) WHERE frequency >= 2500;
CREATE INDEX ON lexikon(lset, frequency DESC) WHERE frequency >= 625 AND frequency < 2500;
-- ...
CREATE INDEX ON lexikon(lset, frequency DESC) WHERE frequency >= 2 AND frequency < 5;
CREATE INDEX ON lexikon(lset) WHERE freqency = 1;

Función

La función es algo similar en estilo a la solución de @ Jack:

CREATE OR REPLACE FUNCTION f_search(_lset_min int, _lset_max int, _limit int)
  RETURNS SETOF lexikon
$func$
DECLARE
   _n      int;
   _rest   int := _limit;   -- init with _limit param
   _cond   text;
BEGIN 
   FOR _cond IN
      SELECT l.cond FROM public.lex_freq l ORDER BY l.row_min
   LOOP    
      --  RAISE NOTICE '_cond: %, _limit: %', _cond, _rest; -- for debugging
      RETURN QUERY EXECUTE '
         SELECT * 
         FROM   public.lexikon 
         WHERE  ' || _cond || '
         AND    lset >= $1
         AND    lset <= $2
         ORDER  BY frequency DESC
         LIMIT  $3'
      USING  _lset_min, _lset_max, _rest;

      GET DIAGNOSTICS _n = ROW_COUNT;
      _rest := _rest - _n;
      EXIT WHEN _rest < 1;
   END LOOP;
END
$func$ LANGUAGE plpgsql STABLE;

Diferencias clave

• SQL dinámico con RETURN QUERY EXECUTE.
  A medida que avanzamos por los pasos, un plan de consulta diferente puede ser beneficiario. El plan de consulta para SQL estático se genera una vez y luego se reutiliza, lo que puede ahorrar algo de sobrecarga. Pero en este caso la consulta es simple y los valores son muy diferentes. El SQL dinámico será una gran victoria.

• DinámicoLIMIT para cada paso de consulta.
  Esto ayuda de varias maneras: primero, las filas solo se obtienen según sea necesario. En combinación con SQL dinámico, esto también puede generar diferentes planes de consulta para empezar. Segundo: no se necesita una LIMITllamada adicional en la función para recortar el excedente.

Punto de referencia

Preparar

Elegí cuatro ejemplos y realicé tres pruebas diferentes con cada uno. Tomé el mejor de cinco para comparar con el caché cálido:

1. La consulta SQL sin formato del formulario:

   SELECT * 
   FROM   lexikon 
   WHERE  lset >= 20000
   AND    lset <= 30000
   ORDER  BY frequency DESC
   LIMIT  5;

2. Lo mismo después de crear este índice.

   CREATE INDEX ON lexikon(lset);

   Necesita aproximadamente el mismo espacio que todos mis índices parciales juntos:

   SELECT pg_size_pretty(pg_total_relation_size('lexikon')) -- 93 MB

3. La función

   SELECT * FROM f_search(20000, 30000, 5);

Resultados

SELECT * FROM f_search(20000, 30000, 5);

1: Tiempo de ejecución total: 315.458 ms
2: Tiempo de ejecución total: 36.458 ms
3: Tiempo de ejecución total: 0.330 ms

SELECT * FROM f_search(60000, 65000, 100);

1: Tiempo de ejecución total: 294.819 ms
2: Tiempo de ejecución total: 18.915 ms
3: Tiempo de ejecución total: 1.414 ms

SELECT * FROM f_search(10000, 70000, 100);

1: Tiempo de ejecución total: 426.831 ms
2: Tiempo de ejecución total: 217.874 ms
3: Tiempo de ejecución total: 1.611 ms

SELECT * FROM f_search(1, 1000000, 5);

1: Tiempo de ejecución total: 2458.205 ms
2: Tiempo de ejecución total: 2458.205 ms - para grandes rangos de lset, la exploración seq es más rápida que el índice.
3: Tiempo de ejecución total: 0.266 ms

Conclusión

Como se esperaba, el beneficio de la función crece con rangos más grandes lsety más pequeños LIMIT.

Con rangos muy pequeños delset , la consulta sin procesar en combinación con el índice es en realidad más rápida . Querrá probar y quizás ramificar: consulta sin procesar para pequeños rangos de lset, de lo contrario, llamar a la función. Incluso podría incorporar eso en la función para "lo mejor de ambos mundos", eso es lo que haría.

Dependiendo de su distribución de datos y consultas típicas, más pasos lex_freqpueden ayudar al rendimiento. Prueba para encontrar el punto ideal. Con las herramientas presentadas aquí, debería ser fácil de probar.

No veo ningún motivo para incluir la palabra columna en el índice. Entonces este índice

CREATE INDEX lexikon_lset_frequency ON lexicon (lset, frequency DESC)

hará que su consulta se realice rápidamente.

UPD

Actualmente no hay formas de hacer un índice de cobertura en PostgreSQL. Hubo una discusión sobre esta característica en la lista de correo de PostgreSQL http://archives.postgresql.org/pgsql-performance/2012-06/msg00114.php

Usando un índice GIST

¿Hay alguna manera de hacer que funcione rápidamente, independientemente de si el rango (@Low, @High) es amplio o estrecho y si las palabras de frecuencia superior están afortunadamente en el rango seleccionado (estrecho)?

Depende de lo que quieras decir cuando ayunas: obviamente tienes que visitar cada fila del rango porque tu consulta es ORDER freq DESC. Tímido de eso, el planificador de consultas ya cubre esto si entiendo la pregunta,

Aquí creamos una tabla con 10k filas de (5::int,random()::double precision)

CREATE EXTENSION IF NOT EXISTS btree_gin;
CREATE TABLE t AS
  SELECT 5::int AS foo, random() AS bar
  FROM generate_series(1,1e4) AS gs(x);

Lo indexamos,

CREATE INDEX ON t USING gist (foo, bar);
ANALYZE t;

Lo consultamos

EXPLAIN ANALYZE
SELECT *
FROM t
WHERE foo BETWEEN 1 AND 6
ORDER BY bar DESC
FETCH FIRST ROW ONLY;

Tenemos a Seq Scan on t. Esto se debe simplemente a que nuestras estimaciones de selectividad permiten a pg concluir que el acceso al almacenamiento dinámico es más rápido que escanear un índice y volver a verificar. Así que lo hacemos más jugoso insertando 1,000,000 filas más (42::int,random()::double precision)que no se ajustan a nuestro "rango".

INSERT INTO t(foo,bar)
SELECT 42::int, x
FROM generate_series(1,1e6) AS gs(x);

VACUUM ANALYZE t;

Y luego preguntamos,

EXPLAIN ANALYZE
SELECT *
FROM t
WHERE foo BETWEEN 1 AND 6
ORDER BY bar DESC
FETCH FIRST ROW ONLY;

Se puede ver aquí completamos en 4,6 ms con un índice sólo Scan ,

                                                                 QUERY PLAN                                                                  
---------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=617.64..617.64 rows=1 width=12) (actual time=4.652..4.652 rows=1 loops=1)
   ->  Sort  (cost=617.64..642.97 rows=10134 width=12) (actual time=4.651..4.651 rows=1 loops=1)
         Sort Key: bar DESC
         Sort Method: top-N heapsort  Memory: 25kB
         ->  Index Only Scan using t_foo_bar_idx on t  (cost=0.29..566.97 rows=10134 width=12) (actual time=0.123..3.623 rows=10000 loops=1)
               Index Cond: ((foo >= 1) AND (foo <= 6))
               Heap Fetches: 0
 Planning time: 0.144 ms
 Execution time: 4.678 ms
(9 rows)

Ampliar el rango para incluir toda la tabla, produce otra exploración secuencial, lógicamente, y crecerla con otros mil millones de filas produciría otra Exploración de índice.

En resumen,

• Funcionará rápido, por la cantidad de datos.
• Rápido es relativo a la alternativa, si el rango no es lo suficientemente selectivo, un escaneo secuencial puede ser lo más rápido posible.