공간 인덱스가 “범위 별 순서별”쿼리를 도울 수 있습니까? R- 트리 / 공간 인덱스에

R- 트리 / 공간 인덱스에 대한 좋은 지원이 있기 때문에 특히 Postgres에 대해이 질문을하십시오.

단어와 그 빈도의 트리 구조 (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- 트리 / 공간 인덱스가 도움이됩니까?

인덱스 추가, 쿼리 재 작성, 테이블 재 설계 등 제한이 없습니다.



답변

더 높은 주파수의 행을 먼저 검색하여 더 나은 성능을 달성 할 수 있습니다. 이것은 주파수를 ‘과립 화 (granulating)’한 다음 절차 적으로 단계별로 실행함으로써 달성 할 수 있습니다. 예를 들면 다음과 같습니다.

-테스트 베드 및 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;

실제 데이터에 따라 과립 수와 행에 넣는 데 사용되는 기능의 수를 변경하고 싶을 것입니다. 구절 limitlset범위 와 크기에 대한 예상 값과 마찬가지로 주파수의 실제 분포가 핵심 입니다.


답변

설정

나는에 건물입니다 잭의 설정 @ 쉽게 사람들이 따라와 비교 할 수 있도록 할 수 있습니다. 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;

보조 테이블

이 솔루션은 원래 테이블에 열을 추가하지 않으며 작은 도우미 테이블 만 필요합니다. 나는 그것을 publicschema에 넣고, 원하는 스키마를 사용하십시오.

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에서 더 많이 사용되므로이 테이블을 안전하게 만들어야합니다 . 적절한 current를 확신 할 수없는 경우 항상 테이블을 스키마로 규정 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

지금까지 50MB 테이블에는 21MB의 인덱스 만 있습니다.

에 부분 인덱스의 대부분을 만듭니다 (lset, frequency DESC). 두 번째 열은 특별한 경우에만 도움이됩니다. 그러나 PostgreSQL의 MAXALIGN과 조합 된integer 데이터 정렬 의 특성으로 인해 관련된 두 열이 모두 유형 이기 때문에 두 번째 열은 인덱스를 더 크게 만들지 않습니다. 비용이 거의 들지 않는 작은 승리입니다.

단일 빈도에만 적용되는 부분 인덱스에 대해서는 그렇게 할 필요가 없습니다. 그들은 단지에있다 (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 MS
2 : 총 런타임 : 36.458 MS
3 : 총 런타임 : 0.330 MS

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

1 : 총 런타임 : 294.819 MS
2 : 총 런타임 : 18.915 MS
3 : 총 런타임 : 1.414 MS

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

1 : 총 런타임 : 426.831ms
2 : 총 런타임 : 217.874ms
3 : 총 런타임 : 1.611ms

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

1 : 총 런타임 : 2458.205ms
2 : 총 런타임 : 2458.205ms-광범위한 lset의 경우 seq 스캔이 인덱스보다 빠릅니다.
3 : 총 런타임 : 0.266ms

결론

예상대로,이 기능의 이점은 범위가 넓을수록 커 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 힙 액세스가 인덱스 스캔 및 재검사보다 빠르다는 결론을 내릴 수 있기 때문입니다. 따라서 우리는 (42::int,random()::double precision)“범위”에 맞지 않는 1,000,000 개 이상의 행을 삽입하여 더 육즙을 만듭니다 .

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에서 Index Only Scan으로 완성 된 것을 볼 수 있습니다 .

                                                                 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 스캔이 생성됩니다. 논리적으로 추가 행을 늘리면 또 다른 인덱스 스캔이 생성됩니다.

요약하면

  • 데이터 양에 대해 빠르게 수행됩니다.
  • 범위가 충분히 선택적이지 않으면 순차적 스캔 가능한 한 빠를 수 있습니다.

답변