空间索引可以帮助“范围-按限制范围”查询

问这个问题，特别是对于Postgres，因为它对R树/空间索引有很好的支持。

我们有下表，其中包含单词及其频率的树结构（嵌套集模型）：

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树/空间索引是否有帮助？

添加索引，重写查询，重新设计桌子，没有任何限制。

覆盖索引由9.2（现为beta）（顺便说一句）引入。 PostgreSQL人们谈论仅索引扫描。请参阅以下相关答案：dba.stackexchange.com/a/7541/3684和PostgreSQL Wiki页面

两个问题：（1）您期望该表使用哪种模式？读取次数最多还是经常更新（尤其是嵌套的set变量）？（2）嵌套集合整数变量lset和rset与文本变量word之间是否有任何联系？

@jug：大多读。 lset，rset和单词之间没有连接。

如果您有许多更新，那么就性能而言，嵌套集模型将是一个糟糕的选择（如果您可以阅读《 SQL的艺术》一书，请参阅有关层次模型的章节）。但是无论如何，您的主要问题类似于找到一个间隔上的（自变量的）最大值/最大值，为此很难设计索引方法。据我所知，最接近您需要的索引的是knngist模块，但是您必须对其进行修改以适合您的需求。空间索引不太可能会有所帮助。

#1 楼

通过在频率较高的行中进行首先搜索，可能会获得更好的性能。这可以通过“划分”频率然后按程序逐步执行，例如，如下所示：

-测试床和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范围的大小也是如此。

#2 楼

设置

我正在建立@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
$$

仅到目前为止，用于50 MB表的索引为21 MB。

我在

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

上创建了大多数部分索引。第二列仅在特殊情况下有帮助。但是由于涉及的两列均为(lset, frequency DESC)类型，由于结合PostgreSQL中MAXALIGN的数据对齐方式的特殊性，第二列不会使索引变大。对于几乎不付出任何代价的人来说，这是一个小小的胜利。

对于仅跨越单个频率的部分索引，这样做是没有意义的。这些只是在integer上。创建的索引如下所示：

 (lset)

函数

函数的风格与@Jack的解决方案有点相似：

 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;

主要区别：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 >= AND lset <= ORDER BY frequency DESC LIMIT ' 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。随着我们循环执行这些步骤，可能会受益于其他查询计划。静态SQL的查询计划生成一次，然后重新使用-这样可以节省一些开销。但是在这种情况下，查询很简单，值也非常不同。动态SQL将是一个巨大的胜利。
每个查询步骤都具有动态RETURN QUERY EXECUTE。
这在多种方面都有帮助：首先，仅根据需要提取行。结合动态SQL，这可能还会生成不同的查询计划。第二：在函数调用中不需要额外的LIMIT来修剪多余的内容。

基准测试

设置

我选择了四个示例并运行了三个每个都有不同的测试。我采用了五个最佳方法来与温暖的缓存进行比较：

原始SQL查询的形式为：

 LIMIT

创建此索引后的相同

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

需要与我所有的部分索引在一起的空间相同：

 CREATE INDEX ON lexikon(lset);

函数

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

结果

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

1：总运行时间：315.458 ms
2：总运行时间：36.458 ms
3：总运行时间：0.330 ms

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

1：总运行时间：294.819 ms
2：总运行时间：18.915 ms
3：总运行时间：1.414毫秒

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

1：总运行时间：426.831毫秒
2：总运行时间：217.874毫秒
3：总运行时间：1.611毫秒

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

1：总运行时间：2458.205 ms
2：总运行时间：2458.205 ms-对于较大范围的lset，seq扫描比索引快。
3：总运行时间：0.266 ms

结论

如预期的那样，该功能的好处随着SELECT * FROM f_search(1, 1000000, 5);的较大范围和较小的lset的增长而增加。

LIMIT的范围很小，原始查询与索引的组合实际上更快。您将要测试并可能分支：对lset的小范围进行原始查询，否则调用函数。您甚至可以将其构建为“两全其美”的功能-这就是我要做的。

根据您的数据分布和典型查询，lset中的更多步骤可能会提高性能。测试以找到最佳位置。使用此处提供的工具，它应该很容易测试。

#3 楼

我认为没有任何理由在索引中包含单词列。因此，此索引

CREATE INDEX lexikon_lset_frequency ON lexicon (lset, frequency DESC)

将使您的查询快速执行。

UPD

当前没有办法在PostgreSQL中建立覆盖索引。 PostgreSQL邮件列表http://archives.postgresql.org/pgsql-performance/2012-06/msg00114.php
中对此功能进行了讨论。

#4 楼

使用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 MS中完成了仅索引扫描，

                                                                 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)

扩展范围以包括整个表产生另一个seq扫描-从逻辑上讲，再增加十亿行将产生另一个索引扫描。

总之，

它'对于数据量，它可以快速执行。
相对于替代方法而言，快速是可行的，如果范围选择不够充分，则顺序扫描可能会尽可能快。

编程黑洞网

空间索引可以帮助“范围-按限制范围”查询

评论

#1 楼

#2 楼

#3 楼

#4 楼