PostgreSQL (big data): search by tags and order by timestamp

Question

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).

Answer 1

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.

Answer 2

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;

Answer 3

if you need fast reads create partial indices for each tag set.

CREATE INDEX items_tags_has_t2_t5 ON items created_at 
  WHERE tags @> ARRAY['t2', 't5']::varchar[];

the more indices you create the slower writes will become, so it's probably best to restrict these indices to only serve those queries that need it most.

Answer 4

You could make it a bit faster by replacing the TEXT array with an INT array referencing a separate table which would store the tag texts along with an integer key.

Now, here's an idea:

You're always ordering by "created_at DESC" with a LIMIT clause. Or you have a date range, because no-one is really interested in having a million search results dislayed: if the query returns lots of results, it will be slow, but it will also be useless, since the user will immediately not look at the results and enter a more specific search.

Therefore, I'd recommend searching by date slices:

SELECT * FROM items 
WHERE tags @> ARRAY['t2', 't5']::varchar[]
  AND created_at > now() - '1 week'::INTERVAL
ORDER BY created_at DESC
LIMIT 100;

Notice the extra line in the WHERE which restricts on date. This should result in a bitmap-and index scan for both the gin tag index and the created_at index, returning a much smaller number of rows than a search in the whole table, much less heap reads, and a much faster sort.

If it doesn't return enough rows to satisfy your LIMIT, then run it again with a date-range further in the past, and concatenate the results.

You could over-engineer it and have statistics on your tags, so if the searched tags are very common you know one day of logs will probably be enough, and adjust the date range. Or you could use the query itself as a statistics estimator, set a small date range, get results, and if you don't get enough run it again with a wider date range in proportion of the number of results you want.

Another, more evil version of this would be to add the date to the tags. You can create a new tag every week, for example "2021week2" or something. Then you add that to your tag search to restrict the number of rows the gin index will hit. Again, if it doesn't return enough rows you can always run it again with a previous week, but let's be honest, no-one ever scrolls past the first ten results anyway.

Another option would be to use a fast fulltext search engine which supports fast order by date, maybe xapian or lucene.

Answer 5

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.