Mengajukan pertanyaan ini, khususnya untuk Postgres, karena memiliki dukungan yang baik untuk indeks R-tree / spasial.

Kami memiliki tabel berikut dengan struktur pohon (model Nested Set) kata-kata dan frekuensinya:

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

Dan pertanyaannya:

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

Saya kira indeks penutup pada (lset, frequency, word)akan berguna tetapi saya merasa itu mungkin tidak berkinerja baik jika ada terlalu banyak lsetnilai dalam (@High, @Low)kisaran.

Indeks sederhana (frequency DESC)terkadang juga mencukupi, ketika pencarian menggunakan indeks itu menghasilkan lebih awal @Nbaris yang cocok dengan kondisi rentang.

Tetapi tampaknya kinerja sangat tergantung pada nilai parameter.

Apakah ada cara untuk membuatnya berkinerja cepat, terlepas dari apakah rentangnya (@Low, @High)lebar atau sempit dan terlepas dari apakah kata-kata frekuensi teratas untungnya dalam rentang (sempit) yang dipilih?

Apakah indeks R-tree / spasial membantu?

Menambahkan indeks, menulis ulang kueri, mendesain ulang tabel, tidak ada batasan.

Anda mungkin dapat mencapai kinerja yang lebih baik dengan mencari terlebih dahulu di baris dengan frekuensi lebih tinggi. Ini dapat dicapai dengan 'granulasi' frekuensi dan kemudian melangkah secara prosedural, misalnya sebagai berikut:

- lexikondata pengujian dan tiruan:

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 analisis (kebanyakan untuk informasi dan penyetelan):

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

fungsi untuk memindai frekuensi tinggi terlebih dahulu:

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

hasil (timing mungkin harus diambil dengan sejumput garam tetapi setiap kueri dijalankan dua kali untuk melawan caching apa pun)

pertama menggunakan fungsi yang kami tulis:

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

dan kemudian dengan pemindaian indeks sederhana:

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;

Tergantung pada data dunia nyata Anda, Anda mungkin ingin memvariasikan jumlah butiran dan fungsi yang digunakan untuk menempatkan baris ke dalamnya. Distribusi frekuensi yang sebenarnya adalah kuncinya di sini, seperti juga nilai yang diharapkan untuk limitklausa dan ukuran lsetrentang yang dicari.

Mendirikan

Saya sedang membangun pengaturan @ Jack untuk memudahkan orang untuk mengikuti dan membandingkan. Diuji dengan 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

Dari sini saya mengambil rute yang berbeda:

ANALYZE lexikon;

Meja bantu

Solusi ini tidak menambahkan kolom ke tabel asli, hanya membutuhkan tabel pembantu kecil. Saya menempatkannya di skema public, gunakan skema apa pun pilihan Anda.

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;

Tabelnya terlihat seperti ini:

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

Karena kolom condakan digunakan dalam SQL dinamis lebih jauh ke bawah, Anda harus membuat tabel ini aman . Selalu sediakan skema-tabel jika Anda tidak yakin dengan arus yang sesuai search_path, dan cabut hak istimewa menulis dari public(dan peran tidak tepercaya lainnya):

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

Tabel ini lex_freqmemiliki tiga tujuan:

• Buat indeks parsial yang diperlukan secara otomatis.
• Berikan langkah-langkah untuk fungsi berulang.
• Informasi meta untuk penyetelan.

Indeks

DOPernyataan ini menciptakan semua indeks yang dibutuhkan:

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

Semua indeks parsial ini bersama-sama merentang tabel sekali. Ukurannya hampir sama dengan satu indeks dasar di seluruh tabel:

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

Sejauh ini, hanya 21 MB indeks untuk 50 MB tabel.

Saya membuat sebagian besar indeks parsial (lset, frequency DESC). Kolom kedua hanya membantu dalam kasus khusus. Tetapi karena kedua kolom yang terlibat adalah tipe integer, karena kekhususan penyelarasan data dalam kombinasi dengan MAXALIGN di PostgreSQL, kolom kedua tidak membuat indeks lebih besar. Ini adalah kemenangan kecil tanpa biaya.

Tidak ada gunanya melakukan itu untuk indeks parsial yang hanya menjangkau satu frekuensi. Itu baru saja menyala (lset). Indeks yang dibuat terlihat seperti ini:

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;

Fungsi

Fungsi ini agak mirip dengan gaya solusi @ 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;

Perbedaan utama:

• SQL dinamis dengan RETURN QUERY EXECUTE.
  Saat kami mengulangi langkah-langkah, rencana kueri yang berbeda mungkin penerima. Rencana kueri untuk SQL statis dihasilkan sekali dan kemudian digunakan kembali - yang dapat menghemat biaya tambahan. Tetapi dalam hal ini kueri itu sederhana dan nilainya sangat berbeda. SQL dinamis akan menjadi kemenangan besar.

• DinamisLIMIT untuk setiap langkah kueri.
  Ini membantu dalam berbagai cara: Pertama, baris hanya diambil sesuai kebutuhan. Dalam kombinasi dengan SQL dinamis, ini juga dapat menghasilkan rencana kueri yang berbeda untuk memulai. Kedua: Tidak perlu tambahan LIMITdalam pemanggilan fungsi untuk memotong surplus.

Tolok ukur

Mendirikan

Saya mengambil empat contoh dan menjalankan tiga tes berbeda dengan masing-masing. Saya mengambil yang terbaik dari lima untuk membandingkan dengan cache hangat:

1. Kueri SQL mentah dari formulir:

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

2. Hal yang sama setelah membuat indeks ini

   CREATE INDEX ON lexikon(lset);

   Membutuhkan ruang yang sama dengan semua indeks parsial saya bersama-sama:

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

3. Fungsinya

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

Hasil

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 - untuk rentang lset yang besar, pemindaian seq lebih cepat daripada indeks.
3: Total runtime: 0,266 ms

Kesimpulan

Seperti yang diharapkan, manfaat dari fungsi tumbuh dengan rentang yang lebih besar lsetdan lebih kecil LIMIT.

Dengan rentang yang sangat kecillset , kueri mentah dalam kombinasi dengan indeks sebenarnya lebih cepat . Anda ingin menguji dan mungkin bercabang: kueri mentah untuk rentang kecil lset, atau fungsi lainnya panggil. Anda bahkan bisa membuatnya menjadi fungsi untuk "yang terbaik dari kedua dunia" - itulah yang akan saya lakukan.

Bergantung pada distribusi data Anda dan pertanyaan umum, langkah-langkah lebih dalam lex_freqdapat membantu kinerja. Tes untuk menemukan sweet spot. Dengan alat yang disajikan di sini, seharusnya mudah untuk menguji.

Saya tidak melihat alasan untuk memasukkan kolom kata dalam indeks. Jadi indeks ini

CREATE INDEX lexikon_lset_frequency ON lexicon (lset, frequency DESC)

akan membuat kueri Anda berkinerja cepat.

UPD

Saat ini tidak ada cara untuk membuat indeks penutup di PostgreSQL. Ada diskusi tentang fitur ini di milis PostgreSQL http://archives.postgresql.org/pgsql-performance/2012-06/msg00114.php

Menggunakan indeks GIST

Apakah ada cara untuk membuatnya bekerja cepat, terlepas dari apakah kisaran (@Low, @High) lebar atau sempit dan terlepas dari apakah kata-kata frekuensi teratas untungnya berada dalam rentang (sempit) yang dipilih?

Itu tergantung pada apa yang Anda maksudkan saat berpuasa: Anda jelas harus mengunjungi setiap baris dalam rentang karena permintaan Anda ORDER freq DESC. Tidak tahu bahwa perencana permintaan sudah membahas ini jika saya mengerti pertanyaannya,

Di sini kita membuat tabel dengan 10k baris (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);

Kami mengindeksnya,

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

Kami menanyakannya,

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

Kami mendapat Seq Scan on t. Ini hanya karena perkiraan selektivitas kami membiarkan pg menyimpulkan akses tumpukan lebih cepat daripada memindai indeks dan memeriksa ulang. Jadi kami membuatnya lebih menarik dengan memasukkan 1.000.000 baris lebih (42::int,random()::double precision)yang tidak sesuai dengan "jangkauan" kami.

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

VACUUM ANALYZE t;

Dan kemudian kita meminta,

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

Anda dapat melihat di sini kami menyelesaikan dalam 4.6 MS dengan Scan Indeks Saja ,

                                                                 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)

Memperluas rentang untuk menyertakan seluruh tabel, menghasilkan pemindaian seq lain - secara logis, dan menumbuhkannya dengan miliaran baris lainnya akan menghasilkan Pemindaian Indeks lainnya.

Jadi dalam ringkasan,

• Ini akan bekerja cepat, untuk jumlah data.
• Cepat relatif terhadap alternatif, jika kisaran tidak cukup selektif pemindaian sekuensial mungkin secepat yang Anda bisa.