Zadanie tego pytania, szczególnie postgresowi, ponieważ ma dobre wsparcie dla indeksów R / drzewa / przestrzennych.

Mamy następującą tabelę ze strukturą drzewa (model zestawu zagnieżdżonego) słów i ich częstotliwości:

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

I zapytanie:

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

Podejrzewam, że indeks pokrycia (lset, frequency, word)byłby przydatny, ale uważam, że może nie działać dobrze, jeśli w zakresie jest zbyt wiele lsetwartości (@High, @Low).

Zwykły włączony indeks (frequency DESC)może być czasem wystarczający, gdy wyszukiwanie za pomocą tego indeksu daje wczesne @Nwiersze pasujące do warunków zakresu.

Ale wydaje się, że wydajność zależy w dużej mierze od wartości parametrów.

Czy istnieje sposób, aby działał szybko, niezależnie od tego, czy zakres (@Low, @High)jest szeroki czy wąski i niezależnie od tego, czy słowa najwyższej częstotliwości znajdują się na szczęście w (wąskim) wybranym zakresie?

Czy pomógłby R-drzewo / indeks przestrzenny?

Dodanie indeksów, przepisanie zapytania, ponowne zaprojektowanie tabeli, nie ma ograniczeń.

Możesz być w stanie osiągnąć lepszą wydajność, wyszukując najpierw w rzędach o wyższych częstotliwościach. Można to osiągnąć poprzez „granulowanie” częstotliwości, a następnie przechodzenie przez nie proceduralnie, na przykład w następujący sposób:

- dane testowane i lexikonpozorowane:

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 analiza (głównie dla informacji i strojenia):

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

najpierw funkcja skanowania wysokich częstotliwości:

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

wyniki (czasy należy prawdopodobnie wziąć ze szczyptą soli, ale każde zapytanie jest uruchamiane dwa razy, aby przeciwdziałać buforowaniu)

najpierw używając napisanej przez nas funkcji:

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

a następnie za pomocą prostego skanu indeksu:

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;

W zależności od rzeczywistych danych prawdopodobnie będziesz chciał zmienić liczbę granulek i funkcję używaną do umieszczania w nich wierszy. Kluczowy jest tutaj rzeczywisty rozkład częstotliwości, podobnie jak oczekiwane wartości limitklauzuli i wielkości lsetposzukiwanych zakresów.

Ustawiać

Buduję na @ konfiguracji Jacka , aby ułatwić ludziom śledzić i porównywać. Testowane z 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

Odtąd wybieram inną trasę:

ANALYZE lexikon;

Stolik pomocniczy

To rozwiązanie nie dodaje kolumn do oryginalnej tabeli, potrzebuje jedynie niewielkiej tabeli pomocniczej. Umieściłem go w schemacie public, użyj dowolnego wybranego schematu.

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;

Tabela wygląda następująco:

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

Ponieważ kolumna condbędzie dalej używana w dynamicznym SQL, musisz zabezpieczyć tę tabelę . Zawsze kwalifikuj się do schematu tabeli, jeśli nie masz pewności co do odpowiedniego prądu search_pathi cofnij uprawnienia do zapisu z public(i jakiejkolwiek innej niezaufanej roli):

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

Tabela lex_freqsłuży trzem celom:

• Automatycznie twórz potrzebne indeksy częściowe .
• Podaj kroki dla funkcji iteracyjnej.
• Meta informacje do strojenia.

Indeksy

Ta DOinstrukcja tworzy wszystkie potrzebne indeksy:

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

Wszystkie te częściowe indeksy razem obejmują tabelę jeden raz. Są mniej więcej tego samego rozmiaru co jeden podstawowy indeks na całej tabeli:

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

Dotychczas tylko 21 MB indeksów dla tabeli 50 MB.

Tworzę większość indeksów częściowych (lset, frequency DESC). Druga kolumna pomaga tylko w szczególnych przypadkach. Ponieważ obie zaangażowane kolumny są tego samego typu integer, ze względu na specyfikę wyrównywania danych w połączeniu z MAXALIGN w PostgreSQL, druga kolumna nie powiększa indeksu. To niewielka wygrana za niewielką opłatą.

Nie ma sensu tego robić w przypadku indeksów częściowych, które obejmują tylko jedną częstotliwość. Te są po prostu włączone (lset). Utworzone indeksy wyglądają następująco:

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;

Funkcjonować

Funkcja jest nieco podobna stylem do rozwiązania @ Jacka:

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;

Kluczowe różnice:

• dynamiczny SQL z RETURN QUERY EXECUTE.
  Gdy wykonujemy kolejne kroki, beneficjentem może być inny plan zapytań. Plan zapytań dla statycznego SQL jest generowany raz, a następnie ponownie wykorzystywany - co może zaoszczędzić trochę narzutu. Ale w tym przypadku zapytanie jest proste, a wartości są bardzo różne. Dynamiczny SQL będzie wielką wygraną.

• DynamicznyLIMIT dla każdego kroku zapytania.
  Pomaga to na wiele sposobów: Po pierwsze, wiersze są pobierane tylko w razie potrzeby. W połączeniu z dynamicznym SQL może to na początku generować różne plany zapytań. Po drugie: nie ma potrzeby wprowadzania dodatkowego LIMITwywołania funkcji w celu przycięcia nadwyżki.

Reper

Ustawiać

Wybrałem cztery przykłady i każdy z nich przeprowadziłem trzy różne testy. Wziąłem najlepsze z pięciu, aby porównać z ciepłą pamięcią podręczną:

1. Surowe zapytanie SQL formularza:

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

2. To samo po utworzeniu tego indeksu

   CREATE INDEX ON lexikon(lset);

   Potrzebuje mniej więcej tej samej przestrzeni, co wszystkie moje częściowe indeksy razem:

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

3. Funkcja

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

Wyniki

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

1: Całkowity czas działania: 315,458 ms
2: Całkowity czas działania: 36,458 ms
3: Całkowity czas działania: 0,330 ms

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

1: Całkowity czas działania: 294,819 ms
2: Całkowity czas działania: 18,915 ms
3: Całkowity czas działania: 1,414 ms

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

1: Całkowity czas działania: 426,831 ms
2: Całkowity czas działania: 217,874 ms
3: Całkowity czas działania: 1,611 ms

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

1: Całkowity czas działania: 2458.205 ms
2: Całkowity czas działania: 2458.205 ms - dla dużych zakresów lset skanowanie seq jest szybsze niż indeks.
3: Całkowity czas działania: 0,266 ms

Wniosek

Zgodnie z oczekiwaniami, korzyści płynące z funkcji rosną wraz z większymi zakresami lseti mniejszymi LIMIT.

Przy bardzo małych zakresachlset zapytanie surowe w połączeniu z indeksem jest w rzeczywistości szybsze . Będziesz chciał przetestować, a może rozgałęzić: surowe zapytanie dla małych zakresów lset, w przeciwnym razie wywołanie funkcji. Możesz nawet po prostu wbudować to w funkcję „najlepszego z obu światów” - tak bym zrobił.

W zależności od dystrybucji danych i typowych zapytań więcej kroków lex_freqmoże poprawić wydajność. Przetestuj, aby znaleźć najsłodsze miejsce. Dzięki narzędziom przedstawionym tutaj testowanie powinno być łatwe.

Nie widzę żadnego powodu, aby kolumna słów znajdowała się w indeksie. Więc ten indeks

CREATE INDEX lexikon_lset_frequency ON lexicon (lset, frequency DESC)

sprawi, że twoje zapytanie będzie działać szybko.

UPD

Obecnie nie ma możliwości utworzenia indeksu obejmującego w PostgreSQL. Dyskusje na temat tej funkcji można znaleźć na liście mailingowej PostgreSQL http://archives.postgresql.org/pgsql-performance/2012-06/msg00114.php

Korzystanie z indeksu GIST

Czy istnieje sposób, aby działał szybko, niezależnie od tego, czy zakres (@ Low, @High) jest szeroki czy wąski i niezależnie od tego, czy słowa najwyższej częstotliwości znajdują się na szczęście w (wąskim) wybranym zakresie?

To zależy od tego, co masz na myśli, kiedy pościsz: oczywiście musisz odwiedzić każdy wiersz w zakresie, ponieważ twoje zapytanie jest ORDER freq DESC. Nieśmiałe, że planista zapytań już to obejmuje, jeśli rozumiem pytanie,

Tutaj tworzymy tabelę z 10 tys. Rzędów (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);

Indeksujemy to,

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

Pytamy o to,

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

Dostajemy Seq Scan on t. Jest tak po prostu dlatego, że nasze szacunki selektywności pozwalają pg stwierdzić, że dostęp do sterty jest szybszy niż skanowanie indeksu i ponowne sprawdzanie. Sprawiamy, że jest bardziej soczysty, wstawiając kolejne 1 000 000 wierszy (42::int,random()::double precision), które nie pasują do naszego „zakresu”.

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

VACUUM ANALYZE t;

A następnie wymagamy

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

Tutaj możesz zobaczyć, że wykonujemy w 4.6 MS ze skanem tylko indeksu ,

                                                                 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)

Poszerzenie zakresu o całą tabelę, logicznie generuje kolejny skan sekwencyjny, a powiększenie go o kolejny miliard wierszy spowoduje kolejne skanowanie indeksu.

Podsumowując

• Będzie działać szybko, jak na ilość danych.
• Szybkość jest względna w stosunku do alternatywy, jeśli zakres nie jest wystarczająco selektywny, skanowanie sekwencyjne może być tak szybkie, jak to tylko możliwe.