Find integer in array is very slow

Question

PostgreSQL Version PostgreSQL 15.0, compiled by Visual C++ build 1914, 64-bit

This is my "victim" table.

create table if not exists "KeywordsStats" (
  id bigserial primary key, "totalProducts" integer, 
  products integer[] not null, "createdAt" timestamp with time zone not null, 
  "RegionId" integer not null references "Regions" on update cascade on delete cascade, 
  "KeywordId" integer not null references "Keywords" on update cascade on delete cascade, 
  "CatalogDataId" integer not null references "CatalogData" on update cascade
);

alter table 
  "KeywordsStats" owner to postgres;

create index if not exists keywords_stats_products on "KeywordsStats" using gin (products gin__int_ops);

This table contains ~ 2 000 000 rows with 1-1000 of productIds inside each "products" array

Elements of array have special order. In some queries i also get their positions using idx()

But the main problem in basic selection using contains operator

I want to get all rows where productId exists inside "products" array

EXPLAIN ANALYSE SELECT *
FROM "KeywordsStats" as "ks"
WHERE "ks"."products" @> ARRAY[60059650]::integer[]

"Bitmap Heap Scan on ""KeywordsStats"" ks  (cost=4827499.28..4893737.18 rows=20036 width=831) (actual time=15214.038..15215.936 rows=85 loops=1)"
  Recheck Cond: (products @> '{60059650}'::integer[])
  Heap Blocks: exact=85
  ->  Bitmap Index Scan on keywords_stats_products  (cost=0.00..4827494.27 rows=20036 width=0) (actual time=15214.012..15214.013 rows=85 loops=1)
        Index Cond: (products @> '{60059650}'::integer[])
Planning Time: 0.080 ms
Execution Time: 15215.966 ms

15 seconds is very slow in my situation. Is there any idea how to speed it up without changing table schema? Or if there is no chance to achive atleast 1 second per query... What would be the best solution in my case?

This table collects 2 millions of rows every day.

I've tried to not to use array.

Storing ProductId separatly. Using ProductId and Position columns

In this schema I save 1 to 1000 rows per each "CatalogDataId". So instead of 2 000 000 of rows, I created ~ 2 000 000 000 of rows with index on ProductID. Selecting performance was a lot diffeerent 500ms - 1000ms. But the table size was HUGE...

Answer 1

If I were you, I would do the following (all the code below is available on the fiddle here):

You should definitely consider redesigning your schema - having up to 1000 elements in an array is not conducive to quick searches/JOINs!

You should redesign your tables as follows:

CREATE TABLE keyword_stat
(
  keyword_stat_id INT8 NOT NULL GENERATED ALWAYS AS IDENTITY,
  created_at      TIMESTAMPTZ NOT NULL DEFAULT NOW(),
  region_id        INT2 NOT NULL,
  keyword_id       INT4, -- maybe INT2 would do?
  category_data_id INT4, -- maybe INT2 would do?

  CONSTRAINT keyword_stat_pk PRIMARY KEY (keyword_stat_id)

  -- I haven't included the FOREIGN KEY REFERENCES because they're not relevant for this answer!

);

This is basically the same as your original table, minus the product field. As you'll see below, it'll be relatively easy to move your data - this will require rejigging some queries, but will definitely be worth it in the long run - your query run times will be reduced to sub-second values.

Your product table should look like this:

CREATE TABLE product
(
  product_id INT4 NOT NULL,
  kw_id      INT4 NOT NULL, 
  CONSTRAINT product_id_pk PRIMARY KEY (product_id),
  CONSTRAINT kw_id_fk      FOREIGN KEY (kw_id) REFERENCES keyword_stat (keyword_stat_id)
);

and then populate your tables:

INSERT INTO keyword_stat (region_id, keyword_id, category_data_id) VALUES
(1, 101, 1001),
(2, 202, 2002),
(3, 303, 3003);

and

INSERT INTO product VALUES

(100001, 1),
(111111, 1),
(111, 1),

(200001, 2),
(22222, 2),
(222, 2),

(300003, 3),
(333333, 3),
(333, 3);

So, your queries would now look like:

SELECT 
  kw.*, p.*
FROM 
 keyword_stat kw
JOIN
  product p
ON kw.keyword_stat_id = p.kw_id
WHERE product_id = '22222';

Result:

keyword_stat_id  created_at                    region_id  keyword_id    category_data_id    product_id  kw_id
              2  2022-12-26 15:29:26.670169+00 2          202                   2002        22222          2 

This also has the benefit of being more legible than a report with an array with a large number of elements.

Now for the interesting part.

First we use the SET enable_seqscan = OFF; command.

The reason I'm doing it here is to force the optimiser to choose the index over a sequential scan. Without enable_seqscan = OFF, the very small sample tables here would cause the optimiser to automatically choose a sequential scan. With a large number of records on a production system, this should not be a problem.

• This doesn't actually disable sequential table scans, it just makes them very expensive - see discussion below.

• Do not do this on production systems, or at least don't do it globally. You could, if and only if you fully understand any consequences, do it on a case-by-case, query-by-query basis, but it's not to be recommended. Today's query hints are tomorrow's bugs - use with caution.

From the documentation here:

• enable_seqscan (boolean)

  Enables or disables the query planner's use of sequential scan plan types. It is impossible to suppress sequential scans entirely, but turning this variable off discourages the planner from using one if there are other methods available. The default is on.

Then we run:

EXPLAIN (ANALYZE, BUFFERS, VERBOSE)
SELECT 
  kw.*, p.*
FROM 
 keyword_stat kw
JOIN
  product p
ON kw.keyword_stat_id = p.kw_id
WHERE product_id = '22222'

Result:

QUERY PLAN
Nested Loop  (cost=0.27..20.31 rows=1 width=34) (actual time=0.031..0.032 rows=1 loops=1)
  Output: kw.keyword_stat_id, kw.created_at, kw.region_id, kw.keyword_id, kw.category_data_id, p.product_id, p.kw_id
  Inner Unique: true
  Buffers: shared hit=7
  ->  Index Scan using product_id_pk on public.product p  (cost=0.14..8.15 rows=1 width=8) (actual time=0.009..0.010 rows=1 loops=1)
        Output: p.product_id, p.kw_id
        Index Cond: (p.product_id = 22222)
        Buffers: shared hit=2
  ->  Index Scan using keyword_stat_pk on public.keyword_stat kw  (cost=0.13..8.15 rows=1 width=26) (actual time=0.018..0.018 rows=1 loops=1)
        Output: kw.keyword_stat_id, kw.created_at, kw.region_id, kw.keyword_id, kw.category_data_id
        Index Cond: (kw.keyword_stat_id = p.kw_id)
        Buffers: shared hit=5
Planning:
  Buffers: shared hit=4
Planning Time: 0.126 ms
Execution Time: 0.057 ms

Now, this is good! We have two Index Scans on PRIMARY KEY fields using BTree indexes... This will be fast with sub-second respnose times.

Now, how are you going to do the changes (all the code below is available on a second fiddle here). I recreated your table:

CREATE TABLE keyword_stat
(
  kw_id INT8 NOT NULL GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  product INTEGER[] NOT NULL,
  created_at TIMESTAMPTZ NOT NULL DEFAULT NOW(),
  region_id  INT2 NOT NULL,        -- possibly INT4?
  keyword_id INT4 NOT NULL,        -- possibly INT2?
  catalog_data_id INT4 NOT NULL    --      "

and:

CREATE TABLE keyword_stat
(
  kw_id INT8 NOT NULL GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  product INTEGER[] NOT NULL,
  created_at TIMESTAMPTZ NOT NULL DEFAULT NOW(),
  region_id  INT2 NOT NULL,        -- possibly INT4?
  keyword_id INT4 NOT NULL,        -- possibly INT2?
  catalog_data_id INT4 NOT NULL    --      "
);

and populated it as follows:

INSERT INTO keyword_stat (product, region_id, keyword_id, catalog_data_id) VALUES

(ARRAY[100001, 111111, 111], 77, 777, 7777),  -- the last three fields are aribitrary here
(ARRAY[200002, 222222, 222], 88, 888, 8888),
(ARRAY[300003, 333333, 333], 99, 999, 9999),
(ARRAY[100001, 222222, 444], 44, 444, 4444);  -- note the products are the same here as in various fields above!

Now we add our product table:

--
-- Same product table as the other fiddle
--

CREATE TABLE product
(
  product_id INT4 NOT NULL,
  kw_id      INT4 NOT NULL
  -- CONSTRAINT product_id_pk PRIMARY KEY (product_id, kw_id),                      note composite PK - delay these until
  -- CONSTRAINT kw_id_fk      FOREIGN KEY (kw_id) REFERENCES keyword_stat (kw_id)                       after loading!
);

and to populate it, we run:

INSERT INTO product (kw_id, product_id)
SELECT
  kw_id, UNNEST(product)
FROM
  keyword_stat;

and we SELECT * FROM product; - result:

product_id  kw_id
100001  1
111111  1
111     1
200002  2
222222  2
222     2
300003  3
333333  3
333     3
100001  4
222222  4
444     4

We now add the PK:

ALTER TABLE product
ADD CONSTRAINT product_id_pk PRIMARY KEY (product_id, kw_id);  

and now we take a look:

SELECT 
  kw.*, p.*
FROM 
 keyword_stat kw
JOIN
  product p
ON kw.kw_id = p.kw_id
WHERE product_id = '222222';

Result:

kw_id   product     created_at  region_id   keyword_id  catalog_data_id     product_id  kw_id
2   {200002,222222,222}     2022-12-26 20:01:20.026183+00   88  888     8888    222222  2
4   {100001,222222,444}     2022-12-26 20:01:20.026183+00   44  444     4444    222222  4

The main point here is that we wish to eliminate the redundant arrays in keyword_stat.

We do this by:

creating a temp table to hold the keyword_stat data minus the product data:

CREATE TABLE kw_temp AS
SELECT kw_id, created_at, region_id, keyword_id, catalog_data_id
FROM keyword_stat;

adding the data to the temp table:

BEGIN TRANSACTION;
DROP TABLE keyword_stat CASCADE;
ALTER TABLE kw_temp
RENAME TO keyword_stat;
COMMIT;

A couple of things to note here. We're making use of PostgreSQL's transactional DDL capabilities. By using CASCADE we remove the FOREIGN KEY on the product table.

Now, we have our data in the table, time to add (back) CONSTRAINTs:

ALTER TABLE keyword_stat
ADD CONSTRAINT keyword_stat_pk PRIMARY KEY (kw_id);

and

--
-- NOW, we can add the FOREIGN KEY to product, since we have a PK/UNIQUE field to use as the
-- REFERENCEd column
--

ALTER TABLE product
ADD CONSTRAINT kw_id_fk FOREIGN KEY (kw_id) REFERENCES keyword_stat (kw_id);

and then we can again SET enable_seqscan = OFF; and again, we run our EXPLAIN ANALYZE

EXPLAIN (ANALYZE, BUFFERS, VERBOSE)
SELECT 
  kw.*, p.*
FROM 
 keyword_stat kw
JOIN
  product p
ON kw.kw_id = p.kw_id
WHERE product_id = '222222';

Result:

QUERY PLAN
Nested Loop  (cost=0.27..19.51 rows=1 width=34) (actual time=0.060..0.065 rows=2 loops=1)
  Output: kw.kw_id, kw.created_at, kw.region_id, kw.keyword_id, kw.catalog_data_id, p.product_id, p.kw_id
  Inner Unique: true
  Buffers: shared hit=4 read=2
  ->  Index Only Scan using product_id_pk on public.product p  (cost=0.14..8.15 rows=1 width=8) (actual time=0.043..0.045 rows=2 loops=1)
        Output: p.product_id, p.kw_id
        Index Cond: (p.product_id = 222222)
        Heap Fetches: 2
        Buffers: shared hit=1 read=1
  ->  Index Scan using keyword_stat_pk on public.keyword_stat kw  (cost=0.13..8.15 rows=1 width=26) (actual time=0.008..0.008 rows=1 loops=2)
        Output: kw.kw_id, kw.created_at, kw.region_id, kw.keyword_id, kw.catalog_data_id
        Index Cond: (kw.kw_id = p.kw_id)
        Buffers: shared hit=3 read=1
Planning Time: 0.081 ms
Execution Time: 0.079 ms

Note an Index Only Scan which is even quicker than an Index Scan - the heap is never visited, saving time. Using a B-Tree index for scans such as these often results in sub-second query times - I've had these with tables of 750GB when properly indexed.

A few final notes:

• As a "rule of thumb", in an RDBMS you're better off (as with supermodels) having your tables tall and skinny rather than short and fat. Far better a B-Tree index over a large no. of records with a relatively small number of fields than any sort of index over a large number of datums in a single record - as with ARRAY fields, particularly those with a large number of elements.

• As for sizes, the original table for, say, 1M records will give you a size of

• 8 bytes for kw_id

CREATE TABLE keyword_stat
(
  kw_id INT8 NOT NULL GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  product INTEGER[] NOT NULL,
  created_at TIMESTAMPTZ NOT NULL DEFAULT NOW(),
  region_id  INT2 NOT NULL,        -- possibly INT4?
  keyword_id INT4 NOT NULL,        -- possibly INT2?
  catalog_data_id INT4 NOT NULL    --      "
);

• You should think about using names_like_this for your tables as per the recommendation hereenter link description here. I would recommend this latter SQL style guide - just pick a style and stick to it. No guide that I know of recommends quoted identifiers! These are small points.