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;
실제 데이터에 따라 과립 수와 행에 넣는 데 사용되는 기능의 수를 변경하고 싶을 것입니다. 구절 limit
의 lset
범위 와 크기에 대한 예상 값과 마찬가지로 주파수의 실제 분포가 핵심 입니다.
답변
설정
나는에 건물입니다 잭의 설정 @ 쉽게 사람들이 따라와 비교 할 수 있도록 할 수 있습니다. 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
schema에 넣고, 원하는 스키마를 사용하십시오.
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
잉여를 다듬기 위해 추가 로 함수 호출이 필요하지 않습니다 .
기준
설정
나는 네 가지 예를 골라 각각 세 가지 다른 테스트를 수행했다. 웜 캐시와 비교하기 위해 최선을 다했습니다.
-
다음 형식의 원시 SQL 쿼리 :
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);
결과
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 스캔이 생성됩니다. 논리적으로 추가 행을 늘리면 또 다른 인덱스 스캔이 생성됩니다.
요약하면
- 데이터 양에 대해 빠르게 수행됩니다.
- 범위가 충분히 선택적이지 않으면 순차적 스캔 이 가능한 한 빠를 수 있습니다.