• Stars
    star
    725
  • Rank 62,504 (Top 2 %)
  • Language
    C
  • License
    Other
  • Created over 8 years ago
  • Updated about 1 month ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

RUM access method - inverted index with additional information in posting lists

Build Status PGXN version GitHub license

Postgres Professional

RUM - RUM access method

Introduction

The rum module provides an access method to work with a RUM index. It is based on the GIN access method's code.

A GIN index allows performing fast full-text search using tsvector and tsquery types. But full-text search with a GIN index has several problems:

  • Slow ranking. It needs positional information about lexemes to do ranking. A GIN index doesn't store positions of lexemes. So after index scanning, we need an additional heap scan to retrieve lexeme positions.
  • Slow phrase search with a GIN index. This problem relates to the previous problem. It needs positional information to perform phrase search.
  • Slow ordering by timestamp. A GIN index can't store some related information in the index with lexemes. So it is necessary to perform an additional heap scan.

RUM solves these problems by storing additional information in a posting tree. For example, positional information of lexemes or timestamps. You can get an idea of RUM with the following diagram:

How RUM stores additional information

A drawback of RUM is that it has slower build and insert times than GIN. This is because we need to store additional information besides keys and because RUM uses generic Write-Ahead Log (WAL) records.

License

This module is available under the license similar to PostgreSQL.

Installation

Before building and installing rum, you should ensure following are installed:

  • PostgreSQL version is 9.6+.

Typical installation procedure may look like this:

Using GitHub repository

$ git clone https://github.com/postgrespro/rum
$ cd rum
$ make USE_PGXS=1
$ make USE_PGXS=1 install
$ make USE_PGXS=1 installcheck
$ psql DB -c "CREATE EXTENSION rum;"

Using PGXN

$ USE_PGXS=1 pgxn install rum

Important: Don't forget to set the PG_CONFIG variable in case you want to test RUM on a custom build of PostgreSQL. Read more here.

Common operators and functions

The rum module provides next operators.

Operator Returns Description
tsvector <=> tsquery float4 Returns distance between tsvector and tsquery.
timestamp <=> timestamp float8 Returns distance between two timestamps.
timestamp <=| timestamp float8 Returns distance only for left timestamps.
timestamp |=> timestamp float8 Returns distance only for right timestamps.

The last three operations also work for types timestamptz, int2, int4, int8, float4, float8, money and oid.

Operator classes

rum provides the following operator classes.

rum_tsvector_ops

For type: tsvector

This operator class stores tsvector lexemes with positional information. It supports ordering by the <=> operator and prefix search. See the example below.

Let us assume we have the table:

CREATE TABLE test_rum(t text, a tsvector);

CREATE TRIGGER tsvectorupdate
BEFORE UPDATE OR INSERT ON test_rum
FOR EACH ROW EXECUTE PROCEDURE tsvector_update_trigger('a', 'pg_catalog.english', 't');

INSERT INTO test_rum(t) VALUES ('The situation is most beautiful');
INSERT INTO test_rum(t) VALUES ('It is a beautiful');
INSERT INTO test_rum(t) VALUES ('It looks like a beautiful place');

To create the rum index we need create an extension:

CREATE EXTENSION rum;

Then we can create new index:

CREATE INDEX rumidx ON test_rum USING rum (a rum_tsvector_ops);

And we can execute the following queries:

SELECT t, a <=> to_tsquery('english', 'beautiful | place') AS rank
    FROM test_rum
    WHERE a @@ to_tsquery('english', 'beautiful | place')
    ORDER BY a <=> to_tsquery('english', 'beautiful | place');
                t                |  rank
---------------------------------+---------
 It looks like a beautiful place | 8.22467
 The situation is most beautiful | 16.4493
 It is a beautiful               | 16.4493
(3 rows)

SELECT t, a <=> to_tsquery('english', 'place | situation') AS rank
    FROM test_rum
    WHERE a @@ to_tsquery('english', 'place | situation')
    ORDER BY a <=> to_tsquery('english', 'place | situation');
                t                |  rank
---------------------------------+---------
 The situation is most beautiful | 16.4493
 It looks like a beautiful place | 16.4493
(2 rows)

rum_tsvector_hash_ops

For type: tsvector

This operator class stores a hash of tsvector lexemes with positional information. It supports ordering by the <=> operator. It doesn't support prefix search.

rum_TYPE_ops

For types: int2, int4, int8, float4, float8, money, oid, time, timetz, date, interval, macaddr, inet, cidr, text, varchar, char, bytea, bit, varbit, numeric, timestamp, timestamptz

Supported operations: <, <=, =, >=, > for all types and <=>, <=| and |=> for int2, int4, int8, float4, float8, money, oid, timestamp and timestamptz types.

This operator supports ordering by the <=>, <=| and |=> operators. It can be used with rum_tsvector_addon_ops, rum_tsvector_hash_addon_ops' and rum_anyarray_addon_ops` operator classes.

rum_tsvector_addon_ops

For type: tsvector

This operator class stores tsvector lexemes with any supported by module field. See the example below.

Let us assume we have the table:

CREATE TABLE tsts (id int, t tsvector, d timestamp);

\copy tsts from 'rum/data/tsts.data'

CREATE INDEX tsts_idx ON tsts USING rum (t rum_tsvector_addon_ops, d)
    WITH (attach = 'd', to = 't');

Now we can execute the following queries:

EXPLAIN (costs off)
    SELECT id, d, d <=> '2016-05-16 14:21:25' FROM tsts WHERE t @@ 'wr&qh' ORDER BY d <=> '2016-05-16 14:21:25' LIMIT 5;
                                    QUERY PLAN
-----------------------------------------------------------------------------------
 Limit
   ->  Index Scan using tsts_idx on tsts
         Index Cond: (t @@ '''wr'' & ''qh'''::tsquery)
         Order By: (d <=> 'Mon May 16 14:21:25 2016'::timestamp without time zone)
(4 rows)

SELECT id, d, d <=> '2016-05-16 14:21:25' FROM tsts WHERE t @@ 'wr&qh' ORDER BY d <=> '2016-05-16 14:21:25' LIMIT 5;
 id  |                d                |   ?column?
-----+---------------------------------+---------------
 355 | Mon May 16 14:21:22.326724 2016 |      2.673276
 354 | Mon May 16 13:21:22.326724 2016 |   3602.673276
 371 | Tue May 17 06:21:22.326724 2016 |  57597.326724
 406 | Wed May 18 17:21:22.326724 2016 | 183597.326724
 415 | Thu May 19 02:21:22.326724 2016 | 215997.326724
(5 rows)

Warning: Currently RUM has bogus behaviour when one creates an index using ordering over pass-by-reference additional information. This is due to the fact that posting trees have fixed length right bound and fixed length non-leaf posting items. It isn't allowed to create such indexes.

rum_tsvector_hash_addon_ops

For type: tsvector

This operator class stores a hash of tsvector lexemes with any supported by module field.

It doesn't support prefix search.

rum_tsquery_ops

For type: tsquery

It stores branches of query tree in additional information. For example, we have the table:

CREATE TABLE query (q tsquery, tag text);

INSERT INTO query VALUES ('supernova & star', 'sn'),
    ('black', 'color'),
    ('big & bang & black & hole', 'bang'),
    ('spiral & galaxy', 'shape'),
    ('black & hole', 'color');

CREATE INDEX query_idx ON query USING rum(q);

Now we can execute the following fast query:

SELECT * FROM query
    WHERE to_tsvector('black holes never exists before we think about them') @@ q;
        q         |  tag
------------------+-------
 'black'          | color
 'black' & 'hole' | color
(2 rows)

rum_anyarray_ops

For type: anyarray

This operator class stores anyarray elements with length of the array. It supports operators &&, @>, <@, =, % operators. It also supports ordering by <=> operator. For example, we have the table:

CREATE TABLE test_array (i int2[]);

INSERT INTO test_array VALUES ('{}'), ('{0}'), ('{1,2,3,4}'), ('{1,2,3}'), ('{1,2}'), ('{1}');

CREATE INDEX idx_array ON test_array USING rum (i rum_anyarray_ops);

Now we can execute the query using index scan:

SET enable_seqscan TO off;

EXPLAIN (COSTS OFF) SELECT * FROM test_array WHERE i && '{1}' ORDER BY i <=> '{1}' ASC;
                QUERY PLAN
------------------------------------------
 Index Scan using idx_array on test_array
   Index Cond: (i && '{1}'::smallint[])
   Order By: (i <=> '{1}'::smallint[])
(3 rows

SELECT * FROM test_array WHERE i && '{1}' ORDER BY i <=> '{1}' ASC;
     i
-----------
 {1}
 {1,2}
 {1,2,3}
 {1,2,3,4}
(4 rows)

rum_anyarray_addon_ops

For type: anyarray

This operator class stores anyarray elements with any supported by module field.

Todo

  • Allow multiple additional information (lexemes positions + timestamp).
  • Improve ranking function to support TF/IDF.
  • Improve insert time.
  • Improve GENERIC WAL to support shift (PostgreSQL core changes).

Authors

Alexander Korotkov [email protected] Postgres Professional Ltd., Russia

Oleg Bartunov [email protected] Postgres Professional Ltd., Russia

Teodor Sigaev [email protected] Postgres Professional Ltd., Russia

Arthur Zakirov [email protected] Postgres Professional Ltd., Russia

Pavel Borisov [email protected] Postgres Professional Ltd., Russia

Maxim Orlov [email protected] Postgres Professional Ltd., Russia

More Repositories

1

pg_probackup

Backup and recovery manager for PostgreSQL
Python
711
star
2

jsquery

JsQuery – json query language with GIN indexing support
C
702
star
3

pg_pathman

Partitioning tool for PostgreSQL
C
583
star
4

zson

ZSON is a PostgreSQL extension for transparent JSONB compression
C
539
star
5

aqo

Adaptive query optimization for PostgreSQL
C
428
star
6

imgsmlr

Similar images search for PostgreSQL
C
255
star
7

mamonsu

Python
186
star
8

vops

C
165
star
9

postgres_cluster

Various experiments with PostgreSQL clustering
C
151
star
10

pg_query_state

Tool for query progress monitoring in PostgreSQL
C
150
star
11

pg_wait_sampling

Sampling based statistics of wait events
C
144
star
12

testgres

Testing framework for PostgreSQL and its extensions
Python
141
star
13

hunspell_dicts

Hunspell dictionaries for PostgreSQL
TSQL
63
star
14

pg_credereum

Prototype of PostgreSQL extension bringing some properties of blockchain to the relational DBMS
C
62
star
15

sr_plan

Save and restore query plans in PostgreSQL
C
61
star
16

mmts

multimaster
C
57
star
17

raft

Raft protocol implementation in C
C
49
star
18

ptrack

Block-level incremental backup engine for PostgreSQL
C
45
star
19

pg_trgm_pro

C
44
star
20

sqljson

C
38
star
21

postgresql.pthreads

Port of postgresql for pthreads
C
31
star
22

postgresql.builtin_pool

Version of PostgreSQL with built-in connection pooling
C
29
star
23

pg_dtm

Distributed transaction manager
C
27
star
24

postgrespro

Postgres Professional fork of PostgreSQL
C
27
star
25

lsm3

LSM tree implementation based on standard B-Tree
C
26
star
26

lsm

RocksDB FDW for PostgreSQL
C
24
star
27

tsvector2

Extended tsvector type for PostgreSQL
C
20
star
28

pg_backtrace

Show backtrace for errors and signals
C
20
star
29

pgwininstall

PostgreSQL Windows installer
Roff
19
star
30

monq

MonQ - PostgreSQL extension for MongoDB-like queries to jsonb data
C
17
star
31

pg_tsparser

pg_tsparser - parser for text search
C
16
star
32

pgsphere

PgSphere provides spherical data types, functions, operators, and indexing for PostgreSQL.
C
16
star
33

hstore_ops

Better operator class for hstore: smaller index and faster @> queries.
C
16
star
34

undam

Undo storage implementation
C
15
star
35

pg_logging

PostgreSQL logging interface
C
15
star
36

pg_ycsb

YCSB-like benchmark for pgbench
PLpgSQL
15
star
37

tsexample

Example of custom postgresql full text search parser, dictionaries and configuration
C
14
star
38

libblobstamper

Framework for Structure Aware Fuzzing. Allows to build own stamps that would convert pulp-data that came from fuzzer to data with structure you need
C++
14
star
39

pg_oltp_bench

Extension and scripts to run analogue of sysbench OLTP test using pgbench
PLpgSQL
13
star
40

pg_grab_statement

PostgreSQL extension for recoding workload of specific database
C
12
star
41

tsexact

PostgreSQL fulltext search addon
C
11
star
42

jsonbd

JSONB compression method for PostgreSQL
C
10
star
43

rusmorph

Russian morphological dictionary (rusmorph) for Postgres based on libmorph library: https://github.com/big-keva/libmorph
C++
10
star
44

pg_parallizator

C
9
star
45

memstat

C
9
star
46

plantuner

C
8
star
47

pg_pageprep

PostgreSQL extension which helps to prepare heap pages for migration to 64bit XID page format (PostgresPro Enterprise)
C
8
star
48

wildspeed

C
7
star
49

pgbouncer

C
6
star
50

bztree

C++
6
star
51

pg_pathman_build

Prerequisites for pg_pathman building
Shell
5
star
52

snapfs

Fast recoverry and snapshoting
C
4
star
53

pq2jdbc

Java
4
star
54

jsonb_schema

Store jsonb schema separately from data
C
4
star
55

postgrespro-os-templates

Packer templates for building minimal baseboxes
Shell
3
star
56

pg_variables

Session wide variables for PostgreSQL
C
3
star
57

pg_hint_plan

C
2
star
58

pgpro_redefinition

PLpgSQL
2
star
59

snowball_ext

The Snowball dictionary template extension for PostgreSQL
C
2
star
60

jsonb_plpython

PLpgSQL
1
star
61

dict_regex

C
1
star
62

pg-mark

Postgres benchmarking framework
R
1
star
63

anyarray

contrib package for working with 1-D arrays
C
1
star
64

libpq_compression

C
1
star