4

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

5 Answers 5

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.

8
  • "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, 2020 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. Mar 2, 2020 at 6:48
  • The problem is the PG implementation, not theoretical. For example: if PostgreSQL GIN indexes supported the INCLUDE, to keep extra data inside the index values, a filter on tags and then a sort (without access to the heap) would be extremely fast.
    – collimarco
    Apr 7, 2021 at 17:31
  • True. But very often a big sort is more expensive than the table scan. Apr 7, 2021 at 18:32
  • A table scan for big data is extremely inefficient and should never happen. Maybe you have an index + bitmap index scan... But again, why read millions of rows from the heap just to get the timestamp? By storing them with the index you have much less data to read and then you access to the heap only for the 10 rows fetched (e.g. if you have LIMIT 10).
    – collimarco
    Apr 7, 2021 at 21:26
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;
2
  • RUM seems really promising... are there any chances that it will be merged in the main PG project?
    – collimarco
    Feb 29, 2020 at 10:22
  • for implausibly distant 'infinity' is probably a better timestamp choice here.
    – Jasen
    Sep 20, 2020 at 2:27
0

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.

1
  • The problem in our case is that tags are arbitrary strings set by users and we don't have any control on that...
    – collimarco
    Sep 20, 2020 at 9:00
0

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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