Diese Frage speziell für Postgres zu stellen, da es eine gute Unterstützung für R-Tree / Spatial-Indizes bietet.

Wir haben die folgende Tabelle mit einer Baumstruktur (Nested Set-Modell) von Wörtern und ihren Häufigkeiten:

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

Und die Abfrage:

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

Ich nehme an, dass ein Deckungsindex (lset, frequency, word)für nützlich wäre, aber ich bin der Meinung, dass er möglicherweise keine gute Leistung erbringt, wenn zu viele lsetWerte im (@High, @Low)Bereich liegen.

(frequency DESC)Manchmal kann auch ein einfacher Index für ausreichend sein, wenn eine Suche mit diesem Index zu einem frühen Zeitpunkt die @NZeilen ergibt, die der Bereichsbedingung entsprechen.

Es scheint jedoch, dass die Leistung stark von den Parameterwerten abhängt.

Gibt es eine Möglichkeit, die Leistung zu steigern, unabhängig davon, ob der Bereich (@Low, @High)groß oder klein ist und ob die Wörter mit der höchsten Frequenz zum Glück im (engen) ausgewählten Bereich liegen?

Würde ein R-Baum / räumlicher Index helfen?

Das Hinzufügen von Indizes, das Umschreiben der Abfrage und das Neuentwerfen der Tabelle unterliegen keinen Einschränkungen.

Möglicherweise können Sie eine bessere Leistung erzielen, indem Sie zuerst in Zeilen mit höheren Frequenzen suchen. Dies kann erreicht werden, indem die Frequenzen "granuliert" und dann prozedural durchlaufen werden, zum Beispiel wie folgt:

--Prüf- und lexikonDummy-Daten:

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 (hauptsächlich zur Information und Abstimmung):

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

Funktion zum Scannen hoher Frequenzen zuerst:

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

Ergebnisse (Timings sollten wahrscheinlich mit einer Prise Salz genommen werden, aber jede Abfrage wird zweimal ausgeführt, um jeglichem Caching entgegenzuwirken.)

Verwenden Sie zuerst die Funktion, die wir geschrieben haben:

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

und dann mit einem einfachen Index-Scan:

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;

Abhängig von Ihren realen Daten möchten Sie wahrscheinlich die Anzahl der Granulate und die Funktion zum Einfügen von Zeilen in diese variieren. Die tatsächliche Häufigkeitsverteilung ist hier ebenso entscheidend wie die erwarteten Werte für die limitKlausel und die Größe der lsetgesuchten Bereiche.

Installieren

Ich baue auf @ Jacks Setup auf, um es den Leuten einfacher zu machen, zu folgen und zu vergleichen. Getestet mit 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

Ab hier gehe ich einen anderen Weg:

ANALYZE lexikon;

Hilfstisch

Diese Lösung fügt der Originaltabelle keine Spalten hinzu, sondern benötigt lediglich eine winzige Hilfstabelle. Ich habe es in das Schema eingefügt publicund ein beliebiges Schema Ihrer Wahl verwendet.

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;

Tabelle sieht so aus:

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

Da die Spalte condspäter in dynamischem SQL verwendet werden soll, müssen Sie diese Tabelle sicher machen . Führen Sie immer eine Schemaqualifizierung der Tabelle durch, wenn Sie sich nicht sicher sind, ob ein entsprechender Stand vorliegt search_path, und widerrufen Sie Schreibberechtigungen für public(und jede andere nicht vertrauenswürdige Rolle):

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

Die Tabelle lex_freqdient drei Zwecken:

• Erstellen Sie benötigte Teilindizes automatisch.
• Stellen Sie Schritte für die iterative Funktion bereit.
• Metainformationen zur Abstimmung.

Indizes

Diese DOAnweisung erstellt alle benötigten Indizes:

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

Alle diese Teilindizes spannen zusammen , um die Tabelle einmal. Sie sind ungefähr so ​​groß wie ein Basisindex für die gesamte Tabelle:

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

Bisher nur 21 MB Indizes für eine Tabelle mit 50 MB.

Ich erstelle die meisten Teilindizes auf (lset, frequency DESC). Die zweite Spalte hilft nur in Sonderfällen. Da beide beteiligten Spalten vom Typ sind integer, wird der Index aufgrund der Besonderheiten der Datenausrichtung in Kombination mit MAXALIGN in PostgreSQL durch die zweite Spalte nicht größer. Es ist ein kleiner Gewinn für kaum Kosten.

Dies hat keinen Sinn für Teilindizes, die nur eine Frequenz umfassen. Die sind gerade an (lset). Erstellte Indizes sehen so aus:

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;

Funktion

Die Funktion ähnelt in etwa der @ Jack-Lösung:

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;

Hauptunterschiede:

• dynamisches SQL mit RETURN QUERY EXECUTE.
  Während wir die Schritte durchlaufen, kann ein anderer Abfrageplan nützlich sein. Der Abfrageplan für statisches SQL wird einmal generiert und dann wiederverwendet. Dies spart möglicherweise zusätzlichen Aufwand. In diesem Fall ist die Abfrage jedoch einfach und die Werte sind sehr unterschiedlich. Dynamic SQL wird ein großer Gewinn sein.

• DynamischLIMIT für jeden Abfrageschritt.
  Dies hat mehrere Vorteile: Erstens werden Zeilen nur bei Bedarf abgerufen. In Kombination mit dynamischem SQL können dadurch auch verschiedene Abfragepläne erstellt werden. Zweitens: Es ist kein zusätzlicher LIMITFunktionsaufruf erforderlich , um den Überschuss zu kürzen.

Benchmark

Installieren

Ich habe vier Beispiele ausgewählt und mit jedem drei verschiedene Tests durchgeführt. Ich habe das Beste aus fünf genommen, um es mit dem warmen Cache zu vergleichen:

1. Die rohe SQL-Abfrage des Formulars:

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

2. Dasselbe nach dem Erstellen dieses Index

   CREATE INDEX ON lexikon(lset);

   Benötigt ungefähr den gleichen Platz wie alle meine Teilindizes zusammen:

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

3. Die Funktion

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

Ergebnisse

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

1: Gesamtlaufzeit: 315,458 ms
2: Gesamtlaufzeit: 36,458 ms
3: Gesamtlaufzeit: 0,330 ms

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

1: Gesamtlaufzeit: 294.819 ms
2: Gesamtlaufzeit: 18.915 ms
3: Gesamtlaufzeit: 1.414 ms

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

1: Gesamtlaufzeit: 426.831 ms
2: Gesamtlaufzeit: 217.874 ms
3: Gesamtlaufzeit: 1.611 ms

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

1: Gesamtlaufzeit: 2458.205 ms
2: Gesamtlaufzeit: 2458.205 ms - Für große Bereiche von lset ist der seq-Scan schneller als der Index.
3: Gesamtlaufzeit: 0,266 ms

Fazit

Wie erwartet wächst der Nutzen der Funktion mit größeren lsetund kleineren Reichweiten LIMIT.

Mit sehr kleinen Reichweiten vonlset ist die unformatierte Abfrage in Kombination mit dem Index tatsächlich schneller . Sie wollen testen und vielleicht verzweigen: rohe Abfrage für kleine Bereiche lset, sonst Funktionsaufruf. Das könnte man sogar einfach in die Funktion für ein "Beste aus beiden Welten" einbauen - das würde ich tun.

Je nach Datenverteilung und typischen Abfragen werden weitere Schritte ausgeführt lex_freq zur Leistungsverbesserung beitragen. Testen Sie, um den Sweet Spot zu finden. Mit den hier vorgestellten Tools sollte es einfach zu testen sein.

Ich sehe keinen Grund, die Wortspalte in den Index aufzunehmen. Also dieser Index

CREATE INDEX lexikon_lset_frequency ON lexicon (lset, frequency DESC)

Ihre Anfrage wird schnell ausgeführt.

UPD

Derzeit gibt es in PostgreSQL keine Möglichkeiten, einen Deckungsindex zu erstellen. Es gab eine Diskussion über diese Funktion in der PostgreSQL-Mailingliste http://archives.postgresql.org/pgsql-performance/2012-06/msg00114.php

Verwenden eines GIST-Index

Gibt es eine Möglichkeit, die Leistung zu steigern, unabhängig davon, ob der Bereich (@Low, @High) groß oder klein ist und ob die Wörter mit der höchsten Frequenz zum Glück im (engen) ausgewählten Bereich liegen?

Es kommt darauf an, was Sie mit Fasten meinen: Sie müssen offensichtlich jede Zeile im Bereich besuchen, weil Ihre Abfrage lautet ORDER freq DESC . Schüchtern deckt der Abfrageplaner dies bereits ab, wenn ich die Frage verstehe,

Hier erstellen wir eine Tabelle mit 10k Zeilen (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);

Wir indizieren es,

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

Wir fragen es ab,

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

Wir bekommen eine Seq Scan on t. Dies liegt einfach daran, dass unsere Selektivitätsschätzungen pg zu dem Schluss kommen lassen, dass der Heap-Zugriff schneller ist als das Scannen eines Index und das erneute Überprüfen. Wir machen es saftiger, indem wir 1.000.000 weitere Zeilen (42::int,random()::double precision)einfügen, die nicht zu unserem "Sortiment" passen.

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

VACUUM ANALYZE t;

Und dann fordern wir,

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

Sie können hier sehen, dass wir in 4.6 MS einen Index-Only-Scan durchführen .

                                                                 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)

Wenn Sie den Bereich auf die gesamte Tabelle ausweiten, wird logischerweise ein weiterer seq-Scan erstellt, und wenn Sie ihn mit einer weiteren Milliarde Zeilen ausweiten, wird ein weiterer Index-Scan erstellt.

Also zusammenfassend

• Bei der Datenmenge wird es schnell gehen.
• Schnell ist in Bezug auf die Alternative, wenn der Bereich nicht selektiv genug , um eine sequentielle Scan kann so schnell sein , wie Sie bekommen können.