Задавая этот вопрос, специально для Postgres, так как он имеет хорошую поддержку для R-дерева / пространственных индексов.

У нас есть следующая таблица с древовидной структурой (модель Nested Set) слов и их частотами:

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

И запрос:

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

Я полагаю, что индекс покрытия (lset, frequency, word)был бы полезен, но я чувствую, что он может работать неэффективно, если lsetв (@High, @Low)диапазоне слишком много значений .

Простой индекс (frequency DESC)может также быть достаточным иногда, когда поиск, использующий этот индекс, возвращает ранние @Nстроки, которые соответствуют условию диапазона.

Но, похоже, производительность сильно зависит от значений параметров.

Есть ли способ заставить его работать быстро, независимо от того, (@Low, @High)является ли диапазон широким или узким, и независимо от того, находятся ли слова с высокой частотой, к счастью, в (узком) выбранном диапазоне?

Поможет ли R-дерево / пространственный индекс?

Добавление индексов, переписывание запроса, перепроектирование таблицы, ограничений нет.

Вы можете достичь лучшей производительности, выполняя поиск сначала в строках с более высокими частотами Это может быть достигнуто путем «гранулирования» частот и последующего пошагового их прохождения, например, следующим образом:

- тестовые и lexikonфиктивные данные:

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 анализ (в основном для информации и настройки):

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

функция для сканирования высоких частот в первую очередь:

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

результаты (время может быть взято с небольшим количеством соли, но каждый запрос выполняется дважды, чтобы противостоять кешированию)

сначала используя функцию, которую мы написали:

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

а затем с помощью простого сканирования индекса:

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;

В зависимости от ваших реальных данных, вы, вероятно, захотите изменить количество гранул и функцию, используемую для помещения в них строк. Ключевым здесь является фактическое распределение частот, а также ожидаемые значения для limitпредложения и размер lsetискомых диапазонов.

Настроить

Я основываюсь на настройке @ Jack, чтобы людям было легче следить и сравнивать. Протестировано с 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

С этого момента я выбираю другой маршрут:

ANALYZE lexikon;

Вспомогательный стол

Это решение не добавляет столбцы в исходную таблицу, ему просто нужна крошечная вспомогательная таблица. Я поместил его в схему public, используйте любую схему по вашему выбору.

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;

Таблица выглядит так:

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

Поскольку этот столбец condбудет использоваться в динамическом SQL ниже, вам необходимо обеспечить безопасность этой таблицы . Всегда проверяйте схему таблицы, если вы не можете быть уверены в соответствующем токе search_path, и отзывайте права на запись из public(и любой другой ненадежной роли):

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

Стол lex_freqслужит трем целям:

• Создайте необходимые частичные индексы автоматически.
• Укажите шаги для итеративной функции.
• Мета информация для тюнинга.

Индексы

Этот DOоператор создает все необходимые индексы:

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

Все эти частичные индексы вместе охватывают таблицу один раз. Они имеют примерно одинаковый размер с одним основным индексом на всю таблицу:

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

Пока только 21 МБ индексов для таблицы 50 МБ.

Я создаю большинство частичных индексов (lset, frequency DESC). Второй столбец помогает только в особых случаях. Но поскольку оба задействованных столбца имеют тип integer, из-за особенностей выравнивания данных в сочетании с MAXALIGN в PostgreSQL, второй столбец не делает индекс больше. Это маленькая победа едва ли любой ценой.

Нет смысла делать это для частичных индексов, которые охватывают только одну частоту. Это только на (lset). Созданные индексы выглядят так:

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;

функция

Функция несколько похожа по стилю на решение @ 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;

Ключевые отличия:

• динамический SQL с RETURN QUERY EXECUTE.
  Поскольку мы переходим по шагам, другой план запроса может быть выгодным. План запроса для статического SQL генерируется один раз, а затем используется повторно, что может сэкономить некоторые накладные расходы. Но в этом случае запрос прост и значения очень разные. Динамический SQL будет большой победой.

• ДинамическийLIMIT для каждого шага запроса.
  Это помогает несколькими способами: во-первых, строки выбираются только по мере необходимости. В сочетании с динамическим SQL это также может генерировать различные планы запросов для начала. Второе: нет необходимости в дополнительном LIMITвызове функции для обрезки излишков.

эталонный тест

Настроить

Я выбрал четыре примера и провел три разных теста с каждым. Я взял лучшее из пяти, чтобы сравнить с теплым кешем:

1. Необработанный SQL-запрос формы:

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

2. То же самое после создания этого индекса

   CREATE INDEX ON lexikon(lset);

   Нужно примерно столько же места, сколько все мои частичные индексы вместе:

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

3. Функция

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

Полученные результаты

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

1: общее время выполнения: 315,458 мс
2: общее время выполнения: 36,458 мс
3: общее время выполнения: 0,330 мс

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

1: общее время выполнения: 294,819 мс
2: общее время выполнения: 18,915 мс
3: общее время выполнения: 1,414 мс

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

1: общее время выполнения: 426,831 мс
2: общее время выполнения: 217,874 мс
3: общее время выполнения: 1,611 мс

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

1: общее время выполнения: 2458,205 мс
2: общее время выполнения: 2458,205 мс - для больших диапазонов lset сканирование seq выполняется быстрее индекса.
3: общее время выполнения: 0,266 мс

Вывод

Как и ожидалось, выгода от функции возрастает с увеличением диапазона lsetи уменьшением LIMIT.

С очень маленькими диапазонамиlset необработанный запрос в сочетании с индексом на самом деле быстрее . Вы захотите проверить и, возможно, выполнить ответвление: необработанный запрос для небольших диапазонов lset, иначе вызов функции. Вы могли бы даже встроить это в функцию для «лучшего из двух миров» - вот что я бы сделал.

В зависимости от вашего распределения данных и типичных запросов, дополнительные шаги lex_freqмогут помочь производительности. Тест, чтобы найти сладкое место. С инструментами, представленными здесь, это должно быть легко проверить.

Я не вижу смысла включать слово столбец в указатель. Итак, этот индекс

CREATE INDEX lexikon_lset_frequency ON lexicon (lset, frequency DESC)

сделает ваш запрос, чтобы выполнить быстро.

UPD

В настоящее время нет способов создать индекс покрытия в PostgreSQL. Об обсуждении этой функции в списке рассылки PostgreSQL было http://archives.postgresql.org/pgsql-performance/2012-06/msg00114.php.

Использование индекса GIST

Есть ли способ заставить его работать быстро, независимо от того, является ли диапазон (@Low, @High) широким или узким, и независимо от того, находятся ли слова с высокой частотой, к счастью, в (узком) выбранном диапазоне?

Это зависит от того, что вы имеете в виду, когда говорите быстро: вам, очевидно, нужно посетить каждую строку в диапазоне, потому что ваш запрос ORDER freq DESC . Застенчивый, что планировщик запросов уже покрывает это, если я понимаю вопрос,

Здесь мы создаем таблицу с 10k строк (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);

Мы индексируем это,

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

Мы запрашиваем это,

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

Мы получаем Seq Scan on t. Это просто потому, что наши оценки селективности позволяют pg сделать вывод, что доступ к куче быстрее, чем сканирование индекса и перепроверка. Поэтому мы делаем его более сочным, добавляя более 1 000 000 строк, (42::int,random()::double precision)которые не соответствуют нашему «диапазону».

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

VACUUM ANALYZE t;

И тогда мы запрашиваем,

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

Вы можете увидеть здесь, мы завершили в 4.6 мс с индексом только сканирование ,

                                                                 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)

Расширение диапазона для включения всей таблицы приводит к следующему логическому сканированию, а увеличение его еще на миллиард строк приведет к еще одному сканированию индекса.

Итак, в итоге,

• Это будет работать быстро, для количества данных.
• Быстрое относится к альтернативе, если диапазон недостаточно избирателен, последовательное сканирование может быть настолько быстрым, насколько это возможно.