Filter on array text[] and sort on timestamp

Question

Description

PostgreSQL 9.6 on Linux, size of tags_tmp table ~ 30 GB (10 million rows), tags is a text[] and has only 6 values.

tags_tmp(id int, tags text[], maker_date timestamp, value text)

id  tags        maker_date      value
1   {a,b,c}     2016-11-09      This is test 
2   {a}         2016-11-08      This is test 
3   {b,c}       2016-11-07      This is test 
4   {c}         2016-11-06      This is test 
5   {d}         2016-11-05      This is test 

I need to retrieve data with filter on tags as well as order by on maker_date desc. Can I create an index on both tags & maker_date desc columns?

If not, could you suggest other ideas?

Query example

select id, tags, maker_date, value
from tags_tmp
where  tags && array['a','b']
order by maker_date desc
limit 5 offset 0

SQL code:

create index idx1 on tags_tmp using gin (tags);
create index idx2 on tags_tmp using btree(maker_date desc);

explain (analyse on, costs on, verbose)
select id, tags, maker_date, value
from tags_tmp
where tags && array['funny','inspiration']
order by maker_date desc
limit 5 offset 0 ;

Explain result:

Limit  (cost=233469.63..233469.65 rows=5 width=116) (actual time=801.482..801.483 rows=5 loops=1)
  Output: id, tags, maker_date, value
  ->  Sort  (cost=233469.63..234714.22 rows=497833 width=116) (actual time=801.481..801.481 rows=5 loops=1)
        Output: id, tags, maker_date, value
        Sort Key: tags_tmp.maker_date DESC
        Sort Method: top-N heapsort  Memory: 25kB
        ->  Bitmap Heap Scan on public.tags_tmp  (cost=6486.58..225200.81 rows=497833 width=116) (actual time=212.982..696.650 rows=366392 loops=1)
              Output: id, tags, maker_date, value
              Recheck Cond: (tags_tmp.tags && '{funny,inspiration}'::text[])
              Heap Blocks: exact=120034
              ->  Bitmap Index Scan on idx1  (cost=0.00..6362.12 rows=497882 width=0) (actual time=171.742..171.742 rows=722612 loops=1)
                    Index Cond: (tags_tmp.tags && '{funny,inspiration}'::text[])
Planning time: 0.185 ms
Execution time: 802.128 ms

More information

I tested with using partial index for only one tag, of course, it's faster. But I have many tag , for example: create index idx_tmp on tags_tmp using btree (maker_date desc) where (tags && array['tag1') or tags && array['tag2'] or ... or tags && array['tag6'] . And I tested between tags && array['tag1'] and 'tag1' = any(tags), performance is same.

1. text[] has only 6 values = a, b, c, d, e, f . For example: tags={a,b,c}, tags={a}, tags={a,c}, tags={a,b,c,d,e,f}, tags={b,f} and so on. But it cannot has value g->z, A-Z and etc.

2. create table tags_tmp(id int primary key not null, tags text[] not null, maker_date timestamp not null, value text)

3. In terms of distinct array values , the tags which contains a takes 20% rows of table where 'a' = any(tags), b=20% where 'b' = any(tags), c=20% where 'c' = any(tags), d=20% where 'd' = any(tags), e=10% where 'e' = any(tags),f=10% where 'f' = any(tags).

4. In addition, (tags, maker_date) is not unique.

5. This table is not read only.

6. It is sort on timestamp, but my example shows dates, sorry about that.

Current situation: tags = 'a' or tags = 'b' or tags = 'c' and more

(1) With GIN index or convert text[] to int[] as well as convert text[] to int and more, it will use bitmap index on multi tags. Finally, after testing, I decided to use old solution, change OR into many UNION clauses, each UNION will limit the number of data. Of course, I will create partial index for each tag value as well as I can combine with (1) above . In terms of OFFSET, it will use one or more condition in WHERE clause instead.

Example

EXPLAIN (ANALYSE ON, costs ON, VERBOSE)
SELECT rs.*
FROM (
        (SELECT tags,
                id,
                maker_date
         FROM tags_tmp
         WHERE 'a' = any(tags)
           AND maker_date <= '2016-03-28 05:43:57.779528'::TIMESTAMP
         ORDER BY maker_date DESC LIMIT 5)
      UNION
        (SELECT tags,
                id,
                maker_date
         FROM tags_tmp
         WHERE 'b' = any(tags)
           AND maker_date <= '2016-03-28 05:43:57.779528'::TIMESTAMP
         ORDER BY maker_date DESC LIMIT 5)
      UNION
        (SELECT tags,
                id,
                maker_date
         FROM tags_tmp
         WHERE 'c' = any(tags)
           AND maker_date <= '2016-03-28 05:43:57.779528'::TIMESTAMP
         ORDER BY maker_date DESC LIMIT 5)) rs
ORDER BY rs.maker_date DESC LIMIT 5 ;

Answer 1

General considerations

Index optimization always depends on the complete picture. Table size, row size, cardinalities, value frequencies, selectivity of typical queries, Postgres version, typical access patterns, etc.

Your case is particularly difficult for two reasons:

1. Different columns used in WHERE and ORDER BY.

2. Filter on array is most efficient with GIN or GiST index, but neither index type produces sorted output. The manual:

   Of the index types currently supported by PostgreSQL, only B-tree can produce sorted output — the other index types return matching rows in an unspecified, implementation-dependent order.

You can create a multicolumn GIN index on (tags, maker_date) or even more columns (the order of index columns is irrelevant for GIN indexes). But you need to have the additional module btree_gin installed. Instructions:

• Inner join using an array column

And it's not going to help for the ORDER BY component of your problem.

One more clarification: OFFSET m LIMIT n is typically almost as expensive as LIMIT m+n.

Solution for added specifications

You clarified: only 6 distinct tags possible. That's crucial.

Your table is big and your table definition leaves room for improvements. Size matters for big tables. Your numbers (30 GB, 10 million rows) also suggest a big avg. row size of ~ 3 KB. Either you have more columns than you show or table bloat and need a VACUUM FULL run (or similar) or your value column is big and TOASTed, which would make my improvements even more effective since the main relation is cut down to half its size or less with this:

CREATE TABLE tags_tmp (
  id         int PRIMARY KEY -- assuming PK
, tags       int NOT NULL    -- also assuming NOT NULL
, value      text
, maker_date timestamp NOT NULL  -- NOT NULL!
);

The order of columns is relevant because of alignment padding. Details:

• Configuring PostgreSQL for read performance

More importantly, this: tags int. Why?

Arrays have a sizeable overhead of 24 byte (similar to a row), plus actual items.

• Calculating and saving space in PostgreSQL

So a text[] with 1-6 items like you demonstrate ('funny', 'inspiration', ...) occupies ~ 56 bytes on avg. And 6 distinct values can be represented by only 6 bits of information (assuming that sort order of the array is irrelevant). We could compress even more, but I chose the convenient integer type (occupies 4 bytes), which provides space for up to 31 distinct tags. That leaves room for later additions without changes to the table schema. Detailed rationale:

• Should I use the PostgreSQL bit string?

Your tags map to bits in a bitmap, 'a' being the least significant bit (to the right):

tag:       a | b | c | d |  e |  f
position:  0 | 1 | 2 | 3 |  4 |  5
int value: 1 | 2 | 4 | 8 | 16 | 32

So the tag array '{a,d,f}' maps to 41. You can use any arbitrary strings instead of 'a'-'f', doesn't matter.

To encapsulate the logic I suggest two auxiliary functions, easily expandable:

tags -> integer:

CREATE OR REPLACE FUNCTION f_tags2int(text[])
  RETURNS int AS
$func$
SELECT bit_or(CASE x
            WHEN 'a' THEN  1
            WHEN 'b' THEN  2
            WHEN 'c' THEN  4
            WHEN 'd' THEN  8
            WHEN 'e' THEN 16
            WHEN 'f' THEN 32
            -- more?
           END)
FROM    unnest ($1) x
$func$  LANGUAGE SQL IMMUTABLE;

integer -> tags:

CREATE OR REPLACE FUNCTION f_int2tags(int)
  RETURNS text[] AS
$func$
SELECT array_remove(ARRAY [CASE WHEN $1 &  1 > 0 THEN 'a' END
                         , CASE WHEN $1 &  2 > 0 THEN 'b' END
                         , CASE WHEN $1 &  4 > 0 THEN 'c' END
                         , CASE WHEN $1 &  8 > 0 THEN 'd' END
                         , CASE WHEN $1 & 16 > 0 THEN 'e' END
                         , CASE WHEN $1 & 32 > 0 THEN 'f' END], NULL)
                         -- more? 
$func$  LANGUAGE SQL IMMUTABLE;

Basics here:

• Can I convert a bunch of boolean columns to a single bitmap in PostgreSQL?

For convenience, you can add a view to display tags as text array like you had it:

CREATE VIEW tags_tmp_pretty AS
SELECT id, tags
     , f_int2tags(tags) AS tags_pretty
     , maker_date, value
FROM   tags_tmp;

Now your basic query can be:

SELECT id, tags, maker_date, value
FROM   tags_tmp
WHERE  tags & f_tags2int('{a,b}') > 0  -- any of the tags matched
ORDER  by maker_date DESC
LIMIT  5;

Using the binary AND operator &. There are more operators to manipulate the column. get_bit() and set_bit() from the binary string operators are also convenient.

The above query should be faster already, for the smaller size and cheaper operators alone, but nothing revolutionary, yet. To make it fast we need indices, and the above cannot use an index, yet.

One partial index for every tag:

CREATE INDEX foo_tag_a ON tags_tmp(maker_date DESC) WHERE tags & 1 > 0;
CREATE INDEX foo_tag_b ON tags_tmp(maker_date DESC) WHERE tags & 2 > 0;
...
CREATE INDEX foo_tag_f ON tags_tmp(maker_date DESC) WHERE tags & 32 > 0;

This query is equivalent to the above, but can utilize the indexes:

SELECT *
FROM   tags_tmp_pretty
WHERE (tags & f_tags2int('{a}') > 0   -- same as tags & 1
    OR tags & f_tags2int('{e}') > 0)  -- same as tags & 32
ORDER  BY maker_date DESC
LIMIT  10;

Postgres can combine several bitmap index scans in a BitmapOr step very efficiently - as demonstrated in this SQL Fiddle.

You could add another index condition to limit indexes to maker_date > some constant timestamp (and repeat the verbatim condition in queries) to cut down their size (massively). Related example:

• Index optimization with dates

More sophisticated:

• Add datetime constraint to a PostgreSQL multi-column partial index

Other related answers:

• How to speed up ORDER BY sorting when using GIN index in PostgreSQL?

• Can spatial index help a "range - order by - limit" query

Or just 6 boolean columns ...

Simply 6 boolean columns might be an even better choice. There are some pros & cons to either solution ...

CREATE TABLE tags_tmp (
  id         int PRIMARY KEY -- assuming PK
, tag_a      bool 
, tag_b      bool 
  ...
, tag_f      bool 
, value      text
, maker_date timestamp NOT NULL  -- NOT NULL!
);

You might define the flags NOT NULL, depending on your complete use case.

Consider:

• Should I use the PostgreSQL bit string?

Partial indexes simply:

CREATE INDEX foo_tag_a ON tags_tmp(maker_date DESC) WHERE tag_a;
CREATE INDEX foo_tag_b ON tags_tmp(maker_date DESC) WHERE tag_b;

Etc.

Alternative for your special case

Thinking some more, since all of your few tags are so common, and combining multiple tags with OR is even less selective, it will be fastest to only have a btree index on maker_date DESC. Postgres can traverse the index and filter qualifying rows on tags. This will work in combination with separate boolean columns instead of the array or encoded integer, because Postgres has more useful columns statistics for separate columns.

CREATE INDEX tags_tmp_date ON tags_tmp(maker_date DESC);

And then:

SELECT *
FROM   tags_tmp_pretty
WHERE  tag_a
   OR  tag_b
ORDER  BY maker_date DESC
LIMIT  10;

Paging

You need an unambiguous sort order for result sets, to make paging work. I did not bother in this answer, it's too long already. Typically you would add more columns to ORDER BY. How to make paging work efficiently with that:

• Optimize query with OFFSET on large table

Answer 2

Various problems with your test case:

1. id is int8 now. You declared it as int in your original question Not a huge difference, but why the confusion to begin with? It matters for row size and alignment padding. Please remember to declare your actual, exact and complete table definition in questions.

2. Data distribution in your test data is unrealistic. You only have 6 distinct combinations of tags, and *all rows have tag '1'. I assume, you have all 63 possible combinations in your live table, with tags distributed like you added in the question.

3. You test table includes old and new tag columns, which negates the effect on storage size I was after. Now the row size is even bigger. Your row size is 124 - 164 bytes, vs. only 68 bytes in my test (incl. padding & item identifier). More than twice the size makes a difference.

4. You write size = 4163 MB. What size?

5. You have order by random() for the test data. Is your productive table really that random? Typically, you would have data roughly sorted by timestamp. What's your actual situation?

6. To see which plan will be picked, test with EXPLAIN only to see the query plan before actually running the query. Saves a lot of time with big tables. But always provide the output of EXPLAIN (ANALYZE, BUFFERS) here. In your answer (as opposed to the question), cost= estimates are missing. That makes it hard to guess the problem.

But none of these issues can explain why you see a sequential scan even with enable_seqscan = off; A quick test on my laptop with Postgres 9.5 works. The same should be true for pg 9.6.

CREATE TABLE tags_tmp(
   id         bigserial PRIMARY KEY, 
   maker_date timestamp NOT NULL,
   tags       int NOT NULL,
   value      text
);

INSERT INTO tags_tmp (tags, maker_date, value)
SELECT EXTRACT('minute' FROM ts)::int    -- int between 1 and 60 (no 61,62,63), pretty good.
     , ts + random() * interval '5 min'  -- some limited randomness
     , 'This is test on ' || EXTRACT('minute' FROM ts)
FROM   generate_series(timestamp '2016-01-01 00:00'
                     , timestamp '2016-01-13 00:00', '10 second') ts;
-- 103681 rows affected, 836 msec execution time.

-- create adapted function f_tags2int
-- create adapted function f_int2tags

CREATE INDEX tags_tmp_1 ON tags_tmp(maker_date DESC) WHERE tags &  1 > 0;
CREATE INDEX tags_tmp_2 ON tags_tmp(maker_date DESC) WHERE tags &  2 > 0;
CREATE INDEX tags_tmp_3 ON tags_tmp(maker_date DESC) WHERE tags &  4 > 0;
CREATE INDEX tags_tmp_4 ON tags_tmp(maker_date DESC) WHERE tags &  8 > 0;
CREATE INDEX tags_tmp_5 ON tags_tmp(maker_date DESC) WHERE tags & 16 > 0;
CREATE INDEX tags_tmp_6 ON tags_tmp(maker_date DESC) WHERE tags & 32 > 0;

SELECT id, tags, maker_date, value
FROM   tags_tmp
WHERE (tags & f_tags2int(array['5']) > 0 OR
       tags & f_tags2int(array['6']) > 0)
ORDER  BY maker_date DESC
LIMIT  5;

QUERY PLAN
Limit  (cost=3811.93..3811.94 rows=5 width=38) (actual time=46.586..46.586 rows=5 loops=1)
  Buffers: shared hit=1132
  ->  Sort  (cost=3811.93..3955.93 rows=57601 width=38) (actual time=46.584..46.585 rows=5 loops=1)
        Sort Key: maker_date DESC
        Sort Method: top-N heapsort  Memory: 25kB
        Buffers: shared hit=1132
        ->  Bitmap Heap Scan on tags_tmp  (cost=607.78..2855.20 rows=57601 width=38) (actual time=13.699..27.674 rows=76032 loops=1)
              Recheck Cond: (((tags & 16) > 0) OR ((tags & 32) > 0))
              Heap Blocks: exact=864
              Buffers: shared hit=1132
              ->  BitmapOr  (cost=607.78..607.78 rows=69121 width=0) (actual time=13.549..13.549 rows=0 loops=1)
                    Buffers: shared hit=268
                    ->  Bitmap Index Scan on tags_tmp_5 cost=0.00..289.49 rows=34560 width=0) (actual time=8.745..8.745 rows=48384 loops=1)
                          Buffers: shared hit=134
                    ->  Bitmap Index Scan on tags_tmp_6 (cost=0.00..289.49 rows=34560 width=0) (actual time=4.800..4.800 rows=48384 loops=1)
                          Buffers: shared hit=134
Planning time: 3.976 ms
Execution time: 46.653 ms

Just like I already demonstrated in the SQL Fiddle.

Are you sure you created all indexes properly?