Fazendo esta pergunta, especificamente para o Postgres, pois possui boa sustentação para índices R-tree / espaciais.

Temos a tabela a seguir com uma estrutura em árvore (modelo Nested Set) de palavras e suas frequências:

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

E a consulta:

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

Suponho que um índice de cobertura (lset, frequency, word)seria útil, mas acho que pode não ter um bom desempenho se houver muitos lsetvalores no (@High, @Low)intervalo.

(frequency DESC)Às vezes, um índice simples ativado também pode ser suficiente, quando uma pesquisa usando esse índice gera antecipadamente as @Nlinhas que correspondem à condição do intervalo.

Mas parece que o desempenho depende muito dos valores dos parâmetros.

Existe uma maneira de fazê-lo funcionar rapidamente, independentemente de o intervalo (@Low, @High)ser amplo ou estreito e de as palavras de frequência mais altas estarem afortunadamente no intervalo selecionado (estreito)?

Um índice de árvore R / espacial ajudaria?

Adicionando índices, reescrevendo a consulta, redesenhando a tabela, não há limitações.

Você pode conseguir um melhor desempenho pesquisando primeiro nas linhas com frequências mais altas. Isso pode ser conseguido 'granulando' as frequências e depois percorrendo-as proceduralmente, por exemplo, da seguinte maneira:

--dados de teste e lexikonfictícios:

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álise (principalmente para informações e ajustes):

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;
--

função para digitalizar altas frequências primeiro:

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 (os horários provavelmente devem ser tomados com uma pitada de sal, mas cada consulta é executada duas vezes para combater qualquer cache)

primeiro usando a função que escrevemos:

\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
*/

e depois com uma simples verificação de índice:

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;

Dependendo dos dados do mundo real, você provavelmente desejará variar o número de grânulos e a função usada para inserir linhas neles. A distribuição real de frequências é fundamental aqui, assim como os valores esperados para a limitcláusula e o tamanho dos lsetintervalos procurados.

Configuração

Estou desenvolvendo a configuração do @ Jack para facilitar o acompanhamento e a comparação das pessoas. Testado com 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

A partir daqui, tomo uma rota diferente:

ANALYZE lexikon;

Mesa auxiliar

Esta solução não adiciona colunas à tabela original, apenas precisa de uma pequena tabela auxiliar. Coloquei-o no esquema public, use qualquer esquema de sua escolha.

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;

A tabela fica assim:

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 a coluna condserá usada no SQL dinâmico mais adiante, é necessário tornar essa tabela segura . Sempre qualifique a tabela com esquema se você não puder ter certeza de uma corrente apropriada search_pathe revogue os privilégios de gravação de public(e de qualquer outra função não confiável):

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

A tabela lex_freqserve para três propósitos:

• Crie índices parciais necessários automaticamente.
• Forneça etapas para a função iterativa.
• Meta informações para ajuste.

Índices

Esta DOdeclaração cria todos os índices necessários:

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 esses índices parciais juntos abrangem a tabela uma vez. Eles têm o mesmo tamanho de um índice básico em toda a tabela:

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

Apenas 21 MB de índices para a tabela de 50 MB até agora.

Eu crio a maioria dos índices parciais (lset, frequency DESC). A segunda coluna ajuda apenas em casos especiais. Porém, como as duas colunas envolvidas são do tipo integer, devido às especificidades do alinhamento de dados em combinação com MAXALIGN no PostgreSQL, a segunda coluna não aumenta o índice. É uma pequena vitória por quase nenhum custo.

Não faz sentido fazer isso para índices parciais que abrangem apenas uma única frequência. Aqueles estão apenas começando (lset). Os índices criados são assim:

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;

Função

A função é um pouco semelhante à solução @ 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;

Principais diferenças:

• SQL dinâmico com RETURN QUERY EXECUTE.
  À medida que percorremos as etapas, um plano de consulta diferente pode ser beneficiário. O plano de consulta para SQL estático é gerado uma vez e depois reutilizado - o que pode economizar um pouco de sobrecarga. Mas, neste caso, a consulta é simples e os valores são muito diferentes. SQL dinâmico será uma grande vitória.

• DinâmicoLIMIT para cada etapa da consulta.
  Isso ajuda de várias maneiras: Primeiro, as linhas são buscadas apenas conforme necessário. Em combinação com o SQL dinâmico, isso também pode gerar planos de consulta diferentes para começar. Segundo: Não é necessário um adicional LIMITna chamada de função para reduzir o excedente.

Referência

Configuração

Escolhi quatro exemplos e fiz três testes diferentes com cada um. Tirei o melhor de cinco para comparar com o cache quente:

1. A consulta SQL bruta do formulário:

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

2. O mesmo depois de criar este índice

   CREATE INDEX ON lexikon(lset);

   Precisa aproximadamente do mesmo espaço que todos os meus índices parciais juntos:

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

3. A função

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

Resultados

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

1: Tempo de execução total: 315,458 ms
2: Tempo de execução total: 36,458 ms
3: Tempo de execução total: 0,330 ms

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

1: Tempo de execução total: 294,819 ms
2: Tempo de execução total: 18,915 ms
3: Tempo de execução total: 1,414 ms

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

1: Tempo de execução total: 426,831 ms
2: Tempo de execução total: 217,874 ms
3: Tempo de execução total: 1,611 ms

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

1: Tempo de execução total: 2458,205 ms
2: Tempo de execução total: 2458,205 ms - para grandes faixas de lset, a verificação seq é mais rápida que o índice.
3: Tempo de execução total: 0,266 ms

Conclusão

Como esperado, o benefício da função cresce com intervalos maiores lsete menores LIMIT.

Com intervalos muito pequenos delset , a consulta bruta em combinação com o índice é realmente mais rápida . Você deseja testar e talvez ramificar: consulta bruta para pequenos intervalos de lset, ou outra chamada de função. Você pode até incorporar isso na função para um "melhor dos dois mundos" - é o que eu faria.

Dependendo da distribuição dos dados e das consultas típicas, mais etapas lex_freqpodem ajudar no desempenho. Teste para encontrar o ponto ideal. Com as ferramentas apresentadas aqui, deve ser fácil testar.

Não vejo motivo para incluir a coluna da palavra no índice. Então esse índice

CREATE INDEX lexikon_lset_frequency ON lexicon (lset, frequency DESC)

fará com que sua consulta seja executada rapidamente.

UPD

Atualmente, não há maneiras de criar um índice de cobertura no PostgreSQL. Houve uma discussão sobre esse recurso na lista de discussão do PostgreSQL http://archives.postgresql.org/pgsql-performance/2012-06/msg00114.php

Usando um índice GIST

Existe uma maneira de fazê-lo funcionar rapidamente, independentemente de o intervalo (@Low, @High) ser largo ou estreito e se as palavras de maior frequência estiverem com sorte no intervalo selecionado (estreito)?

Depende do que você quer dizer quando você jejua: obviamente, você precisa visitar todas as linhas do intervalo porque sua consulta é ORDER freq DESC. Apesar disso, o planejador de consultas já cobre isso se eu entender a pergunta,

Aqui, criamos uma tabela com 10 mil linhas 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);

Nós indexamos,

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

Nós consultamos,

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

Nós temos um Seq Scan on t. Isso ocorre simplesmente porque nossas estimativas de seletividade permitem que a página conclua que o acesso ao heap é mais rápido do que verificar um índice e verificar novamente. Portanto, tornamos mais interessante inserindo mais 1.000.000 de linhas (42::int,random()::double precision)que não se encaixam no nosso "intervalo".

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

VACUUM ANALYZE t;

E então solicitamos,

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

Você pode ver aqui o preenchimento em 4.6 MS com uma varredura de índice apenas ,

                                                                 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)

Expandir o intervalo para incluir a tabela inteira, produz outra varredura seq - logicamente, e aumentá-la com mais um bilhão de linhas produziria outra varredura de índice.

Então, em resumo,

• Ele terá um desempenho rápido para a quantidade de dados.
• Rápido é relativo à alternativa, se o intervalo não for seletivo o suficiente, uma varredura seqüencial pode ser a mais rápida possível.