Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

Asking this question, specifically for Postgres, as it has good supoort for R-tree/spatial indexes.

We have the following table with a tree structure (Nested Set model) of words and their frequencies:

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

And the query:

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

I suppose a covering index on (lset, frequency, word) would be useful but I feel it may not perform well if there are too many lset values in the (@High, @Low) range.

A simple index on (frequency DESC) may also be sufficient sometimes, when a search using that index yields early the @N rows that match the range condition.

But it seems that performance depends a lot on the parameter values.

Is there a way to make it perform fast, regardless of whether the range (@Low, @High) is wide or narrow and regardless of whether the top frequency words are luckily in the (narrow) selected range?

Would an R-tree/spatial index help?

Adding indexes, rewriting the query, re-designing the table, there is no limitation.

share|improve this question
2  
Covering indexes are introduced with 9.2 (now beta), btw. PostgreSQL people speak of Index-only scans. See this related answer: dba.stackexchange.com/a/7541/3684 and the PostgreSQL Wiki page –  Erwin Brandstetter Jun 1 '12 at 17:10
    
@Erwin: thnx, I didn't know that. –  ypercube Jun 1 '12 at 17:15
    
Two questions: (1) What kind of usage pattern do you expect for the table? Are there mostly reads or are there frequent updates (especially of the nested set variables)? (2) Is there any connection between the nested set integer variables lset and rset and the text variable word? –  j.p. Aug 7 '12 at 7:40
    
@jug: Mostly reads. No connection between the lset,rset and word. –  ypercube Aug 7 '12 at 7:42
2  
If you had many updates, the nested set model would be a bad choice with respect to performance (if you have access to the book "The art of SQL", take a look at the chapter about hierachic models). But anyway, your main problem is similar to finding the maximum/the highest values (of an independent variable) on an interval, for which it is hard to design an indexing method. To my knowledge, the closest match to the index you need is the knngist module, but you would have to modify it to fit your needs. A spatial index is unlikely to be helpful. –  j.p. Aug 7 '12 at 14:41

3 Answers 3

up vote 16 down vote accepted
+50

You may be able to achieve better performance by searching first in rows with higher frequencies. This can be achieved by 'granulating' the frequencies and then stepping through them procedurally, for example as follows:

--testbed and lexikon dummy data:

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 analysis (mostly for information and tuning):

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

function for scanning high frequencies first:

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

results (timings should probably be taken with a pinch of salt but each query is run twice to counter any caching)

first using the function we've written:

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

and then with a simple index scan:

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;

Depending on your real-world data, you will probably want to vary the number of granules and the function used for putting rows into them. The actual distribution of frequencies is key here, as is the expected values for the limit clause and size of lset ranges sought.

share|improve this answer
1  
This is one of those answers where a single upvote is hardly enough. –  Erwin Brandstetter Aug 15 '12 at 8:50
    
Why there's a gap starting from width_granule=8 between granulae_start and granulae_end of the previous level? –  vyegorov Feb 7 '13 at 8:14
    
@vyegorov because there aren't any values 1809 and 1810? This is randomly generated data so YMMV :) –  Jack Douglas Feb 7 '13 at 11:14
    
Hm, seems it has nothing to do with randomness, but rather with the way frequency is generated: a big gap between 1e6/2 and 1e6/3, the higher row number becomes, the smaller gap is. Anyway, Thank you for this awesome approach!! –  vyegorov Feb 7 '13 at 12:04
    
@vyegorov sorry, yes, you are right. Be sure to take a look at Erwins improvements if you haven't already! –  Jack Douglas Feb 7 '13 at 12:24

Setup

I am building on @Jack's setup, firstly because that saves time (kudos to Jack) and secondly to make it easier for people to follow and compare. Tested with PostgreSQL 9.1.4.

CREATE SCHEMA x;
SET search_path = x;

CREATE TABLE lexikon (
  id        serial
 ,word      text
 ,frequency int
 ,lset      int
);

INSERT INTO lexikon(word, frequency, lset) 
SELECT word
      ,(1000000/row_number() OVER (ORDER BY random()))::int AS frequency
      ,lset
FROM  (
   SELECT 'w'||generate_series(1,1000000) AS word -- shorter with just 'w'
          ,generate_series(1,1000000) AS lset) z;

From here on I take a different route:

ANALYZE lexikon;

Auxiliary table

This solution does not add any columns to the original table, it just need a tiny helper table, created by this query:

-- DROP TABLE lex_freq;
CREATE TEMP TABLE lex_freq AS
WITH x AS (
   SELECT DISTINCT ON (1) 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
      ORDER  BY 1 DESC
      ) c
   -- find the next greater number to match the
   -- list of steps you want to take in recursive search
   -- adapt to your need
   JOIN ( VALUES (400),(1600),(6400),(25000),(100000),(200000),(400000)
                ,(600000),(800000)) f(row_min) ON c.row_ct >= f.row_min
   ORDER BY 1, 2, 3 DESC
   )
   ,y AS (   
   SELECT DISTINCT ON (frequency)
          row_min, row_ct, frequency AS freq_min
         ,lag(frequency) OVER (ORDER BY row_min) - 1 AS freq_max
                                               -- -1 to exclude upper bound
   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;

SELECT * FROM lex_freq;

Looks like this:

row_min | row_ct  | freq_min | cond
--------+---------+----------+-------------
400     | 400     | 2500     | frequency >= 2500
1600    | 1600    | 625      | frequency >= 625 AND frequency <= 2499
6400    | 6410    | 156      | frequency >= 156 AND frequency <= 624
25000   | 25000   | 40       | frequency >= 40 AND frequency <= 155
100000  | 100000  | 10       | frequency >= 10 AND frequency <= 39
200000  | 200000  | 5        | frequency >= 5 AND frequency <= 9
400000  | 500000  | 2        | frequency >= 2 AND frequency <= 4
600000  | 1000000 | 1        | frequency = 1

As the column cond is going to be used in dynamic SQL further down, you have to make this table secure. Revoke write privileges from public.

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

Or something along this line.
The table lex_freq serves three purposes:

  • Create needed partial indexes automatically:
  • Provide steps for iterative function
  • Meta information for tuning.

Indexes

The following DO statement creates all needed indexes:

DO
$$
DECLARE
   _cond text;
BEGIN
   FOR _cond IN
      SELECT cond FROM lex_freq
   LOOP
      IF _cond ~~ '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;
$$

I create a number of indexes, but they are all partial and only span the whole table together, so they take about the same space than one basic index on the whole table. See for yourself:

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

Only 21 MB of indexes for 50 MB table so far.

You may have noticed that I created most of the partial indexes on (lset, frequency DESC). The second column will only help in special cases. But as both involved columns are of type integer, due to the specifics of data alignment in combination with MAXALIGN in PostgreSQL, the second column does not make the index any bigger. So it's a small win for hardly any cost.

But there is no point in doing that for partial indexes that span only a single frequency. Those are just on (lset). Created indexes look like this:

CREATE INDEX ON lexikon(lset, frequency DESC) WHERE frequency >= 2500;
CREATE INDEX ON lexikon(lset, frequency DESC)
WHERE frequency >= 625 AND frequency <= 2499;
-- ...
CREATE INDEX ON lexikon(lset, frequency DESC)
WHERE frequency >= 2 AND frequency <= 4;
CREATE INDEX ON lexikon(lset) WHERE freqency = 1;

Function

The function is somewhat similar in style to @Jack's solution:

CREATE OR REPLACE FUNCTION f_search(_lset_min int, _lset_max int, _limit int)
  RETURNS SETOF lexikon
  LANGUAGE plpgsql STRICT
  SET search_path = public, pg_temp AS -- provide actual schema
$func$
DECLARE
   _n      int;
   _rest   int := _limit;   -- init with _limit param
   _cond   text;
BEGIN 
FOR _cond IN
   SELECT l.cond FROM lex_freq l ORDER BY l.row_min
LOOP

--   RAISE NOTICE '_cond: %, _limit: %', _cond, _rest; -- for debugging

   RETURN QUERY EXECUTE '
   SELECT * 
   FROM   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$;

Key differences:

  • dynamic SQL with RETURN QUERY EXECUTE. As we loop through the steps, a different query plan may be beneficiary. The query plan for static SQL is generated once and then reused - which can save some overhead. But in this case the query is simple and the values are very different. Dynamic SQL will be a big win.

  • Dynamic LIMIT for every query step. This helps in multiple ways: First, rows are only fetched as needed. In combination with dynamic SQL this may also generate different query plans to begin with. Second: No need for an additional LIMIT in the function call to trim the surplus.

Executing dynamic SQL, this function should be secure. It doesn't have to run with SECURITY DEFINER but I added SET search_path = ... to the definition. Consider the chapter "Writing SECURITY DEFINER Functions Safely" in the manual.

Benchmark

Setup

As is my custom I took the best of five to let the cache populate. I picked four examples and run three different tests with each:

  1. The raw SQL query of the form:

    SELECT * 
    FROM   lexikon 
    WHERE  lset >= 20000
    AND    lset <= 30000
    ORDER  BY frequency DESC
    LIMIT  5;
    
  2. The same after creating this index

    CREATE INDEX ON lexikon(lset);
    

    Needs about the same space as all my partial indexes together:

    SELECT pg_size_pretty(pg_total_relation_size('lexikon')) -- 93 MB
    
  3. The function

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

Results

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

1: Total runtime: 315.458 ms
2: Total runtime: 36.458 ms
3: Total runtime: 0.330 ms

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

1: Total runtime: 294.819 ms
2: Total runtime: 18.915 ms
3: Total runtime: 1.414 ms

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

1: Total runtime: 426.831 ms
2: Total runtime: 217.874 ms
3: Total runtime: 1.611 ms

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

1: Total runtime: 2458.205 ms
2: Total runtime: 2458.205 ms -- for large ranges of lset, seq scan is faster than index.
3: Total runtime: 0.266 ms

Conclusion

As expected, the benefit from the function grows with bigger ranges of lset and smaller LIMIT.

With very small ranges of lset, the raw query in combination with the index is actually faster. You'll want to test and maybe branch: raw query for small ranges of lset, else function call. You could even just build that into the function for a "best of both worlds" - that's what I would do.

Depending on your data distribution and typical queries, more steps in lex_freq may help performance. Test to find the sweet spot. With the tools presented here, it should be easy to test.

share|improve this answer
2  
This is great stuff - two things stand out especially for me: the dynamic limit and the partial indexes. Thank you! –  Jack Douglas Aug 15 '12 at 8:01
1  
@JackDouglas: All in all it took me several hours. It's a problem that needed solving - but I assume you know the feeling. ;) Now it's non-invasive, almost fully automated and can be applied to a whole set of similar use cases. –  Erwin Brandstetter Aug 15 '12 at 8:39
1  
yes, I know the feeling. It has left me wondering if it would be practical to build it into the optimizer in some way and whether it would be worth suggesting to the pg team. It would involve a new 'nested loops' execution path that steps down an index filtering and stops when it reaches the limit. A bit like count stopkey on Oracle I think? –  Jack Douglas Aug 15 '12 at 8:53
1  
I guess an application of KNN GIST would be a superior approach for a general feature in Postgres (like @jug mentioned in the comments to the question). That's above my current level of expertise, though. This here is more like a poor man's solution for now - pretty effective at that, though. –  Erwin Brandstetter Aug 15 '12 at 9:43
3  
Do you know adding <!-- language-all: sql --> at the top gives you syntax highlighting? –  Jack Douglas Aug 15 '12 at 10:06

I do not see any reason to include the word column in the index. So this index

CREATE INDEX lexikon_lset_frequency ON lexicon (lset, frequency DESC)

will make your query to perform fast.

UPD

Currently there are no ways to make a covering index in PostgreSQL. There were a discussion about this feature in the PostgreSQL mailing list http://archives.postgresql.org/pgsql-performance/2012-06/msg00114.php

share|improve this answer
1  
It was included to make the index "covering". –  ypercube Aug 7 '12 at 11:04
    
But by not searching for that term in the query decision tree, are you sure that the covering index is helping here? –  jcolebrand Aug 9 '12 at 16:26
    
Okay, I see now. Currently there are no ways to make a covering index in PostgreSQL. There were a discussion about this feature in the mailing list archives.postgresql.org/pgsql-performance/2012-06/msg00114.php. –  grayhemp Aug 10 '12 at 8:20
    
About "Covering indexes" in PostgreSQL see also Erwin Brandstetter's comment to the question. –  j.p. Aug 10 '12 at 10:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.