Array containment queries in Postgres

Question

Question on GIN index on array.

I have 2 million rows in a work table.And I need to find work that a user can do, based on the skills he has and also the highest priority work. User always will have more skills.

Started with RDMS standard way of doing this, but performance of the queries is bad, so in search for other options found postgres supports arrays containment queries and Also arrays can be indexed.

Table:

CREATE TABLE
    work
    (
        work_id TEXT DEFAULT nextval('work_id_seq'::regclass) NOT NULL,
        priority_score BIGINT NOT NULL,
        work_data JSONB,
        created_date TIMESTAMP(6) WITHOUT TIME ZONE NOT NULL,
        current_status CHARACTER VARYING,
        PRIMARY KEY (work_id)
    );

Index:

CREATE INDEX test_gin_1 ON work USING gin(jsonarray2intarray((work_data ->> 'skills'::text);

Function: 

CREATE OR REPLACE FUNCTION jsonarray2intarray" (text)  RETURNS integer[]
  IMMUTABLE
AS $body$
SELECT translate($1, '[]', '{}')::int[]
$body$ LANGUAGE sql

Sample data:

282941 1564 {"skills": [213, 311, 374, 554]}

With the below query the response is slow. There is only one record with 254,336,391,485 as skill array

with T as (
SELECT   work_id,
        priority_score,
        current_status,
        work_data
FROM     work
WHERE    jsonarray2intarray( work.work_data ->> 'skills') <@ '{254,336,391,485 }'
AND      work.current_status = 'ASSIGNABLE'
ORDER BY priority_score DESC, created_date  ) 
select * from t  LIMIT 1 FOR UPDATE skip locked

Limit  (cost=45095.54..45095.56 rows=1 width=296) (actual time=3776.169..3776.170 rows=1 loops=1)                                                                                                                                                                                                                                                                                                                    
  Output: t.work_id,t.priority_score, t.current_status,t.work_data                                                                                                                                                                            
  CTE t                                                                                                                                                                                                                                                                                                                                                                                                              
    ->  Sort  (cost=45059.29..45095.54 rows=14503 width=325) (actual time=3776.166..3776.166 rows=1 loops=1)                                                                                                                                                                                                                                                                                                         
          Output: work.work_id,work.priority_score, work.current_status,work.work_data        
          Sort Key: work.priority_score DESC, work.created_date                                                                                                                                                                                                                                                                                                                                    
          Sort Method: quicksort  Memory: 25kB                                                                                                                                                                                                                                                                                                                                                                       
          ->  Bitmap Heap Scan on work  (cost=524.44..41872.83 rows=14503 width=325) (actual time=37.718..3776.159 rows=1 loops=1)                                                                                                                                                                                                                                             
                Output: work.work_id,work.priority_score, work.current_status,work.work_data  
                Recheck Cond: (jsonarray2intarray((work.work_data ->> 'skills'::text)) <@ '{254,336,391,485}'::integer[])                                                                                                                                                                                                                                                                               
                Rows Removed by Index Recheck: 1072296                                                                                                                                                                                                                                                                                                                                                               
                Filter: ((work.current_status)::text = 'ASSIGNABLE'::text)                                                                                                                                                                                                                                                                                                                             
                Heap Blocks: exact=41243 lossy=26451                                                                                                                                                                                                                                                                                                                                                                 
                ->  Bitmap Index Scan on test_gin_1  (cost=0.00..520.81 rows=14509 width=0) (actual time=30.699..30.699 rows=154888 loops=1)                                                                                                                                                                                                                                                                         
                      Index Cond: (jsonarray2intarray((work.work_data ->> 'skills'::text)) <@ '{254,336,391,485}'::integer[])                                                                                                                                                                                                                                                                           
  ->  CTE Scan on t  (cost=0.00..290.06 rows=14503 width=296) (actual time=3776.168..3776.168 rows=1 loops=1)                                                                                                                                                                                                                                                                                                        
        Output: t.work_id,t.priority_score, t.current_status,t.work_data                                                                                                                                                                      
Planning time: 0.161 ms                                                                                                                                                                                                                                                                                                                                                                                              
Execution time: 3776.202 ms                                                                                                                                                                                                                                                              

Same query with different input is fast. There are around 26K records with skill 101, 103:

with T as (
SELECT   work_id,
        priority_score,
        current_status,
        work_data
FROM     work
WHERE    jsonarray2intarray( work.work_data ->> 'skills') <@ '{101, 103 }'
AND      work.current_status = 'ASSIGNABLE'
ORDER BY priority_score DESC, created_date  ) 
select * from t  LIMIT 1 FOR UPDATE skip locked

Limit  (cost=45076.55..45076.57 rows=1 width=296) (actual time=116.185..116.186 rows=1 loops=1)                                                                                                                                                                                                                                                                                                                      
  Output: t.work_id,t.priority_score, t.current_status,t.work_data                                                                                                                                                                         
 CTE t                                                                                                                                                                                                                                                                                                                                                                                                              
    ->  Sort  (cost=45040.26..45076.55 rows=14513 width=325) (actual time=116.182..116.182 rows=1 loops=1)                                                                                                                                                                                                                                                                                                           
          Output: work.work_id,work.priority_score, work.current_status,work.work_data        
          Sort Key: work.priority_score DESC, work.created_date                                                                                                                                                                                                                                                                                                                                    
          Sort Method: external merge  Disk: 8088kB                                                                                                                                                                                                                                                                                                                                                                  
          ->  Bitmap Heap Scan on work  (cost=476.52..41853.05 rows=14513 width=325) (actual time=9.223..94.591 rows=26301 loops=1)                                                                                                                                                                                                                                            
                Output: work.work_id,work.priority_score, work.current_status,work.work_data  
                Recheck Cond: (jsonarray2intarray((workd.work_data ->> 'skills'::text)) <@ '{101,103}'::integer[])                                                                                                                                                                                                                                                                                       
                Filter: ((workd.current_status)::text = 'ASSIGNABLE'::text)                                                                                                                                                                                                                                                                                                                             
                Rows Removed by Filter: 1357                                                                                                                                                                                                                                                                                                                                                                         
                Heap Blocks: exact=2317                                                                                                                                                                                                                                                                                                                                                                              
                ->  Bitmap Index Scan on test_gin_1  (cost=0.00..472.89 rows=14519 width=0) (actual time=4.638..4.638 rows=39871 loops=1)                                                                                                                                                                                                                                                                            
                      Index Cond: (jsonarray2intarray((workd.work_data ->> 'skills'::text)) <@ '{101,103}'::integer[])                                                                                                                                                                                                                                                                                   
  ->  CTE Scan on t  (cost=0.00..290.26 rows=14513 width=296) (actual time=116.184..116.184 rows=1 loops=1)                                                                                                                                                                                                                                                                                                          
        Output: t.work_id,t.priority_score, t.current_status,t.work_data                                                                                                                                                                       
Planning time: 0.160 ms                                                                                                                                                                                                                                                                                                                                                                                              
Execution time: 117.278 ms                                                                                                                               

I am looking for suggestions on getting a consistent responses.

NOTE: Approach which is not postgres specific:

The query is taking around 40 to 50 secs which is very bad

I added a new table work_data apart from the work table as defined above

CREATE TABLE work_data
(
    skill_id bigint,
    work_id bigint

)

Query:

 select work.id 
    from work  
       inner join work_data on (work.id=work_data.work_id) 
    group by work.id 
    having sum(case when work_data.skill_id in (2269,3805,828,9127) then 0 else 1 end)=0 

Answer 1

Indexing containment in this direction is inherently troublesome. If you do column @> const_array, it can take the element of const_array which is rarest in "column", and check only the rows which have that rare value to make sure they also have all the rest.

But to do column <@ const_array, it has to check all rows which contain any of the values listed in const_array, plus all rows which have an empty list for "column". That can be an awful lot of rows to check, unless every skill listed in const_array is a rare one.

Also, you are not doing yourself any favors here by storing the array as JSONB and converting to a postgresql array on the fly. That is going to make any rechecks you do have to do be extra expensive. Why not create a column of type int[] directly in the table, rather than wrapping it in JSONB?

I think you have a business problem here as well as a database problem. If someone has a rare skill, they should work on items which require that skill, not on easy items almost anyone can do. And then fall back on easy items only if there are none requiring the rare skill. The queries to solve this modification of the business problem should be faster for the database to implement, as well as more useful.

Answer 2

I see multiple problems. Some have been pointed out by jjanes and Laurenz already. I have some more comments in addition to those.

Combining a predicate in the WHERE clause with an uncorrelated ORDER BY before returning the top 1 (or few) rows. Very hard to optimize. This related question and answers should be of help:

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

Also:

LIMIT 1 FOR UPDATE skip locked

Since you only want to return a single row, don't wrap the query with a huge result set in a CTE, only to select a single row in the outer query. That's a worst-case scenario on top of all the other problems. Before Postgres 12, CTEs are always materialized, and there is really no need for that in your case. Merge into a single query instead:

SELECT work_id, priority_score, current_status, work_data
FROM   work
WHERE  jsonarray2intarray(work.work_data ->> 'skills') <@ '{254,336,391,485 }'
AND    current_status = 'ASSIGNABLE'
ORDER  BY priority_score DESC, created_date
LIMIT  1
FOR    UPDATE SKIP LOCKED;

For more optimization, any available meta-data on the columns in ORDER BY (priority_score, created_date) might be useful.

Table design

You have (and I added comments):

CREATE TABLE public.work(
    work_id TEXT DEFAULT nextval('work_id_seq'::regclass) NOT NULL,
    -- text is nonsense. Use integer. bigint, if you must (I doubt it)
    priority_score BIGINT NOT NULL,
    -- why bigint? while PK is int, this seems uncalled for
    work_data JSONB,
    -- very inefficient, as was pointed out.
    -- and it reeks of a design error that this column can be NULL
    created_date TIMESTAMP(6) WITHOUT TIME ZONE NOT NULL,
    -- typically you really want timestamptz
    current_status CHARACTER VARYING,
    -- should probably be an enum or FK column referencing a lookup table
    -- or something smaller for only few possible states.
    PRIMARY KEY (work_id)
)

If work_data can be NULL, there can never be a match for the row. And if you allow an empty array ('{}'), the row matches always. Neither seems to make sense.

Something like this would already help quite a bit (order of columns is also relevant):

CREATE TABLE public.work (
   work_id        serial PRIMARY KEY
 , priority_score int NOT NULL,  -- ?
 , created_date   timestamptz NOT NULL DEFAULT now()
 , work_data      int[] NOT NULL CHECK (work_data <> '{}'),
 , current_status int,           -- ?
);

Normalization?

As to your attempt at normalization:

CREATE TABLE public.work_data (
    skill_id bigint,  -- I doubt bigint makes sense, int
    work_id bigint    -- again, probably just int
)

Consider instead:

CREATE TABLE public.work_data (
   skill_id int
 , work_id  int
 , PRIMARY KEY (skill_id, work_id)  -- columns in *this* order
);

Depending on the queries used, you may or may not need another index on (work_id, skill_id). See:

• Is a composite index also good for queries on the first field?

And your query can be faster without the join to work:

SELECT work_id 
FROM   work_data
GROUP  BY 1
HAVING count(*) FILTER (WHERE skill_id NOT IN (2269,3805,828,9127)) = 0 

But this should be substantially faster, yet:

SELECT id 
FROM   work w
WHERE  NOT EXISTS (
   SELECT FROM work_data
   WHERE  work_id = w.id 
   AND    skill_id NOT IN (2269,3805,828,9127)
   );

In your original, Postgres has to count all matches for every row in work. NOT EXISTS can stop as soon as the first violating row is found. Faster, but still not very fast.
And since ORDER BY like you display in your first query is missing, it's also not equivalent. And it's unclear what you need in the first place ...

So this is sophisticated stuff. Requires someone with experience. Judging from all we have discussed so far, that person may not be you (no offense). Consider professional help.

Answer 3

Your main problem seems to be

Heap Blocks: exact=41243 lossy=26451

That means that work_mem isn't big enough to contain a bitmap with one bit per table row. PostgreSQL then degrades to one bit per 8 KB block. This causes a lot of false positive matches, which have to be rechecked during the bitmap heap scan phase.

So increasing work_mem should boost performance.

It is possible that an index on work.current_status can further improve performance.