1

We need to add a search feature on a large table (200M+ rows):

item_id | tags                          | created_at          | ...
-------------------------------------------------------------------
1       | ['tag1', 'bar2']              | 2020-01-06 12:43:32 |
2       | ['example5', 'tag9', 'foo2']  | 2020-01-10 10:40:00 |
3       | ['test1', 'tag5']             | 2020-01-11 12:43:32 |
...

The queries would be similar to this one:

SELECT * FROM items 
WHERE tags @> ARRAY['t2', 't5']::varchar[]
ORDER BY created_at DESC
LIMIT 100;

Basically it's like searching some logs by tags and ordering them by timestamp. Seems a common scenario...

What index should we use? Have you ever tested something similar in production?

  • Example 1: create a GIN index on tags. The problem is that the search may return millions of results and in order to apply order / limit you need to make millions of reads from the table on disk (in order to get the created_at value for each row).
  • Example 2: add the btree_gin extension and create a composite index on created_at and tags. The problem is the same as above: I think that PostgreSQL cannot use ordering since the index is declared as a GIN index and not as a btree.
  • Example 3: create a btree index on created_at and tags. PostgreSQL needs to scan the whole index, since btree doesn't support array operators. I also fear that due to the SELECT * PostgreSQL will not use an index-only scan, thus resulting in millions of reads from disk (that would be actually useless since it only needs 100 reads from disk).
0

There are two approaches:

  1. create an index on the array:

    CREATE INDEX ON items USING gin (tags);
    

    That allows the database to quickly find the matching rows, but then it has to perform a top-n sort.

  2. create a B-tree index on created_at:

    CREATE INDEX ON items (created_at);
    

    That will allow the database to avoid the sort, but it has to scan and discard the rows that don't match the condition.

Unfortunately, the two strategies are mutually exclusive, and which is best depends on the data. You'll have to experiment.

|improve this answer|||||
  • "the two strategies are mutually exclusive"... That is the actual problem: we need a solution that includes both filtering on array and ordering on timestamp. – collimarco Feb 29 at 10:27
  • I believe that is theoretically impossible, but that may be lack of imagination. If you have a good algorithm, that might advance database development. – Laurenz Albe Mar 2 at 6:48
0

Have you ever tested something similar in production?

As a general rule, I don't test things in production if I can avoid it. I have certainly tested them in test, however.

Example 2: add the btree_gin extension and create a composite index on created_at and tags. The problem is the same as above: I think that PostgreSQL cannot use ordering since the index is declared as a GIN index and not as a btree

Correct, it will not use this for ordering.

Example 3: create a btree index on created_at and tags. PostgreSQL needs to scan the whole index, since btree doesn't support array operators.

It will walk the index until the LIMIT is satisfied. It will only read the entire index if the tags are so selective that the LIMIT can never be satisfied. If that were the case, it would hopefully realize that it would be a problem, and choose to use your index from example 1 instead. It is not always very good at realizing this, however.

I also fear that due to the SELECT * PostgreSQL will not use an index-only scan, thus resulting in millions of reads from disk (that would be actually useless since it only needs 100 reads from disk).

Correct, it won't use index-only scan for this. But there is a way around it. Assuming item_id is a primary key, you can create the index on (created_at, tags, item_id) and then do:

with t as (SELECT item_id FROM items 
    WHERE tags @> ARRAY['t2', 't5']
    ORDER BY created_at DESC
    LIMIT 100)
select * from t join items using (item_id);

Another option is to use a RUM index. It allows you to attach an ORDER BY column to an index over an array column.

CREATE INDEX ON items USING rum (tags rum_anyarray_addon_ops, created_at)
    WITH (attach = 'created_at', to = 'tags');

But RUM indexes don't support ordinary ORDER BY, but only ordering by a distance. So to get a reverse chronological order, you would pick some date in the implausibly distant future, and order by distance to that date.

SELECT * FROM items 
WHERE tags @> ARRAY['t2', 't5']
ORDER BY created_at <=> '2200-01-01'
LIMIT 100;
|improve this answer|||||
  • RUM seems really promising... are there any chances that it will be merged in the main PG project? – collimarco Feb 29 at 10:22
-1

Generate the current explain plan using explain select * from table_name; Create a gin index on tags column and btree index on created at column. Generate the new query/explain plan post index creation to notice the cost difference and execution times.

|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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