README.md

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:

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.

Tests

$ make check

This command runs:

• regression tests;

• isolation tests;

• tap tests.

  One of the tap tests downloads a 1GB archive and then unpacks it into a file weighing almost 3GB. It is disabled by default.

  To run this test, you need to set an environment variable:

   $ export PG_TEST_EXTRA=big_values 

  The way to turn it off again:

   $ export -n PG_TEST_EXTRA 

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:

CREATETABLEtest_rum(t text, a tsvector); CREATETRIGGERtsvectorupdate BEFORE UPDATEOR 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:

CREATEINDEXrumidxON 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:

CREATETABLEtsts (id int, t tsvector, d timestamp); \copy tsts from'rum/data/tsts.data'CREATEINDEXtsts_idxON 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'LIMIT5; 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'LIMIT5; id | d | ?column? -----+---------------------------------+---------------355 | Mon May 1614:21:22.3267242016 | 2.673276354 | Mon May 1613:21:22.3267242016 | 3602.673276371 | Tue May 1706:21:22.3267242016 | 57597.326724406 | Wed May 1817:21:22.3267242016 | 183597.326724415 | Thu May 1902:21:22.3267242016 | 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:

CREATETABLEquery (q tsquery, tag text); INSERT INTO query VALUES ('supernova & star', 'sn'), ('black', 'color'), ('big & bang & black & hole', 'bang'), ('spiral & galaxy', 'shape'), ('black & hole', 'color'); CREATEINDEXquery_idxON 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:

CREATETABLEtest_array (i int2[]); INSERT INTO test_array VALUES ('{}'), ('{0}'), ('{1,2,3,4}'), ('{1,2,3}'), ('{1,2}'), ('{1}'); CREATEINDEXidx_arrayON 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 a.korotkov@postgrespro.ru Postgres Professional Ltd., Russia

Oleg Bartunov o.bartunov@postgrespro.ru Postgres Professional Ltd., Russia

Teodor Sigaev teodor@postgrespro.ru Postgres Professional Ltd., Russia

Arthur Zakirov a.zakirov@postgrespro.ru Postgres Professional Ltd., Russia

Pavel Borisov p.borisov@postgrespro.com Postgres Professional Ltd., Russia

Maxim Orlov m.orlov@postgrespro.ru Postgres Professional Ltd., Russia