Poser cette question, en particulier pour Postgres, car elle a un bon supoort pour les index R-tree / spatial.

Nous avons le tableau suivant avec une structure arborescente (modèle Nested Set) de mots et leurs fréquences:

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

Et la requête:

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

Je suppose qu'un indice de couverture sur (lset, frequency, word)serait utile mais je pense qu'il peut ne pas bien fonctionner s'il y a trop de lsetvaleurs dans la (@High, @Low)plage.

Un simple index on (frequency DESC)peut également parfois suffire, lorsqu'une recherche utilisant cet index donne tôt les @Nlignes qui correspondent à la condition de plage.

Mais il semble que les performances dépendent beaucoup des valeurs des paramètres.

Existe-t-il un moyen de le faire fonctionner rapidement, que la plage (@Low, @High)soit large ou étroite et que les mots de fréquence supérieure soient heureusement dans la plage (étroite) sélectionnée?

Un arbre R / un indice spatial serait-il utile?

Ajouter des index, réécrire la requête, reconcevoir la table, il n'y a pas de limitation.

Vous pourrez peut-être obtenir de meilleures performances en recherchant d'abord dans les rangées avec des fréquences plus élevées. Cela peut être réalisé en «granulant» les fréquences, puis en les parcourant de manière procédurale, par exemple comme suit:

- lexikondonnées testées et factices:

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 analyse (principalement pour l'information et le réglage):

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

fonction de balayage des hautes fréquences en premier:

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

résultats (les timings doivent probablement être pris avec une pincée de sel mais chaque requête est exécutée deux fois pour contrer toute mise en cache)

en utilisant d'abord la fonction que nous avons écrite:

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

puis avec un simple scan d'index:

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;

En fonction de vos données réelles, vous souhaiterez probablement faire varier le nombre de granules et la fonction utilisée pour y placer des lignes. La distribution réelle des fréquences est ici clé, tout comme les valeurs attendues pour la limitclause et la taille des lsetplages recherchées.

Installer

Je m'appuie sur la configuration de @ Jack pour faciliter le suivi et la comparaison des utilisateurs. Testé avec 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 de là, je prends un itinéraire différent:

ANALYZE lexikon;

Table auxiliaire

Cette solution n'ajoute pas de colonnes à la table d'origine, elle a juste besoin d'une petite table auxiliaire. Je l'ai placé dans le schéma public, utilisez n'importe quel schéma de votre choix.

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;

Le tableau ressemble à ceci:

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

Comme la colonne condva être utilisée dans SQL dynamique plus bas, vous devez faire ce tableau sécurisé . Toujours qualifier la table par schéma si vous ne pouvez pas être sûr d'un courant approprié search_pathet révoquer les privilèges d'écriture de public(et de tout autre rôle non approuvé):

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

Le tableau lex_freqsert à trois fins:

• Créez automatiquement les index partiels nécessaires .
• Fournissez des étapes pour la fonction itérative.
• Méta-informations pour le réglage.

Index

Cette DOinstruction crée tous les index nécessaires:

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

Tous ces index partiels couvrent ensemble la table une fois. Ils ont à peu près la même taille qu'un index de base sur toute la table:

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

Jusqu'à présent, seuls 21 Mo d'index pour une table de 50 Mo.

Je crée la plupart des index partiels sur (lset, frequency DESC). La deuxième colonne n'aide que dans des cas particuliers. Mais comme les deux colonnes impliquées sont de type integer, en raison des spécificités de l' alignement des données en combinaison avec MAXALIGN dans PostgreSQL, la deuxième colonne n'agrandit pas l'index. C'est une petite victoire pour presque aucun coût.

Cela ne sert à rien de le faire pour des index partiels qui ne couvrent qu'une seule fréquence. Ce sont juste sur (lset). Les index créés ressemblent à ceci:

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;

Une fonction

La fonction est quelque peu similaire dans le style à la solution 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;

Différences clés:

• SQL dynamique avec RETURN QUERY EXECUTE.
  Au fur et à mesure que nous parcourons les étapes, un plan de requête différent peut être bénéficiaire. Le plan de requête pour le SQL statique est généré une fois, puis réutilisé, ce qui peut économiser des frais généraux. Mais dans ce cas, la requête est simple et les valeurs sont très différentes. Dynamic SQL sera une grande victoire.

• DynamiqueLIMIT pour chaque étape de requête.
  Cela aide de plusieurs façons: Premièrement, les lignes ne sont extraites que si nécessaire. En combinaison avec SQL dynamique, cela peut également générer différents plans de requête pour commencer. Deuxièmement: pas besoin d'un supplément LIMITdans l'appel de fonction pour couper le surplus.

Référence

Installer

J'ai choisi quatre exemples et effectué trois tests différents avec chacun. J'ai pris le meilleur des cinq pour comparer avec le cache chaud:

1. La requête SQL brute du formulaire:

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

2. La même chose après la création de cet index

   CREATE INDEX ON lexikon(lset);

   A besoin du même espace que tous mes index partiels ensemble:

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

3. La fonction

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

Résultats

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

1: Autonomie totale: 315,458 ms
2 : Autonomie totale: 36,458 ms
3: Autonomie totale: 0,330 ms

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

1: Autonomie totale: 294.819 ms
2 : Autonomie totale: 18.915 ms
3: Autonomie totale: 1.414 ms

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

1: Autonomie totale: 426.831 ms
2 : Autonomie totale: 217.874 ms
3: Autonomie totale: 1.611 ms

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

1: Durée totale d'exécution: 2458,205 ms
2 : Durée totale d'exécution: 2458,205 ms - pour de grandes plages de lset, le balayage séquentiel est plus rapide que l'index.
3: Durée d'exécution totale: 0,266 ms

Conclusion

Comme prévu, l'avantage de la fonction augmente avec des gammes plus grandes lsetet plus petitesLIMIT .

Avec de très petites plages delset , la requête brute en combinaison avec l'index est en fait plus rapide . Vous voudrez tester et peut-être branch: requête brute pour de petites plages de lset, sinon appel de fonction. Vous pouvez même simplement intégrer cela dans la fonction pour un "meilleur des deux mondes" - c'est ce que je ferais.

En fonction de la distribution de vos données et des requêtes typiques, d'autres étapes lex_freqpeuvent améliorer les performances. Testez pour trouver le bon endroit. Avec les outils présentés ici, cela devrait être facile à tester.

Je ne vois aucune raison d'inclure la colonne de mots dans l'index. Donc, cet indice

CREATE INDEX lexikon_lset_frequency ON lexicon (lset, frequency DESC)

rendra votre requête rapide.

UPD

Il n'existe actuellement aucun moyen de créer un index de couverture dans PostgreSQL. Il y a eu une discussion sur cette fonctionnalité dans la liste de diffusion PostgreSQL http://archives.postgresql.org/pgsql-performance/2012-06/msg00114.php

Utilisation d'un index GIST

Y a-t-il un moyen de le faire fonctionner rapidement, que la plage (@Low, @High) soit large ou étroite et que les mots de fréquence supérieure soient heureusement dans la plage (étroite) sélectionnée?

Cela dépend de ce que vous voulez dire lorsque vous jeûnez: vous devez évidemment visiter chaque ligne de la plage car votre requête est ORDER freq DESC . Timide que le planificateur de requêtes couvre déjà cela si je comprends la question,

Ici, nous créons un tableau avec 10k lignes 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);

Nous l'indexons,

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

Nous l'interrogons,

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

Nous obtenons un Seq Scan on t. C'est tout simplement parce que nos estimations de sélectivité permettent à pg de conclure que l'accès au segment de mémoire est plus rapide que l'analyse d'un index et la nouvelle vérification. Donc, nous le rendons plus juteux en insérant 1 000 000 de lignes supplémentaires (42::int,random()::double precision)qui ne correspondent pas à notre «gamme».

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

VACUUM ANALYZE t;

Et puis on demande,

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

Vous pouvez voir ici que nous complétons en 4.6 MS avec un scan d'index uniquement ,

                                                                 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)

Élargir la plage pour inclure la table entière, produit un autre scan séquentiel - logiquement, et l'agrandir avec un autre milliard de lignes produirait un autre scan d'index.

Donc en résumé,

• Il fonctionnera rapidement, pour la quantité de données.
• Rapide est relatif à l'alternative, si la plage n'est pas suffisamment sélective, un balayage séquentiel peut être aussi rapide que possible.