0

To represent a sparse 2D matrix of float values, I use a simple Postgres 13 database table that stores a single matrix cell value per row. I'd like to improve a query that computes the dense version of the a matrix as a 2D array (e.g. real[][]), with empty cells defaulting to zero.

The schema of the matrix table looks like this:

           Table "public.similarity_score"
      Column      |  Type   | Collation | Nullable | Default 
------------------+---------+-----------+----------+---------
 query_object_id  | bigint  |           | not null | 
 target_object_id | bigint  |           | not null | 
 score            | real    |           | not null | 
 similarity_id    | integer |           | not null |

Multiple matrices can be stored in the same table (similarity_id) and for each existing row (query_object_id) and column (target_object_id), a single value can be stored (score).

Apart from many other fields, a similarity (as referenced by the table above) contains a list of all possible row and column options:

                                     Table "public.similarity"
         Column         |    Type   | Collation | Nullable |             Default              
------------------------+--------------------------+-----------+----------+-------------------
 id                     | integer   |           | not null | generated by default as identity
 query_objects          | bigint[]  |           |          | 
 target_objects         | bigint[]  |           |          | 
 …

When assembling the dense matrix for a specific similarity, I'd like to have the rows and columns in the order of those query_objects and target_objects, i.e. the result rows can be mapped to these arrays. Currently, I do this using the following query:

WITH qt AS MATERIALIZED (                                       
    SELECT query.id as query_id, query.o as query_o,            
            target.id AS target_id, target.o AS target_o        
    FROM similarity s,                                   
    UNNEST(s.query_objects) WITH ORDINALITY AS query(id, o),    
    UNNEST(s.target_objects) WITH ORDINALITY AS target(id, o)   
    WHERE s.id = %(similarity_id)s                              
),                                                              
scores AS (                                                     
    SELECT qt.*, COALESCE(nss.score, 0) AS score                
    FROM qt                                                     
    LEFT JOIN similarity_score nss                       
    ON nss.query_object_id = qt.query_id                        
    AND nss.target_object_id = qt.target_id                     
    AND nss.similarity_id = %(similarity_id)s                   
),                                                              
score_rows AS (                                                 
    SELECT query_o, array_agg(score ORDER BY target_o) as scores
    FROM scores                                                 
    GROUP BY query_o                                            
)                                                               
SELECT array_agg(scores ORDER BY query_o)                       
FROM score_rows;

The plan for a 1025*9097 element matrix looks like this:

 Aggregate  (cost=485.99..486.01 rows=1 width=32) (actual time=53124.869..53124.874 rows=1 loops=1)
   Buffers: shared hit=26513337
   CTE qt
     ->  Nested Loop  (cost=0.29..6.91 rows=100 width=32) (actual time=0.781..2812.748 rows=9324425 loops=1)
           Buffers: shared hit=9232
           ->  Nested Loop  (cost=0.28..2.91 rows=10 width=36) (actual time=0.085..1.624 rows=1025 loops=1)
                 Buffers: shared hit=7
                 ->  Index Scan using nblast_similarity_pkey on nblast_similarity s  (cost=0.28..2.51 rows=1 width=51) (actual time=0.010..0.012 rows=1 loops=1)
                       Index Cond: (id = 2282)
                       Buffers: shared hit=3
                 ->  Function Scan on unnest query  (cost=0.00..0.20 rows=10 width=16) (actual time=0.075..0.935 rows=1025 loops=1)
                       Buffers: shared hit=4
           ->  Function Scan on unnest target  (cost=0.00..0.20 rows=10 width=16) (actual time=0.662..1.803 rows=9097 loops=1025)
                 Buffers: shared hit=9225
   ->  GroupAggregate  (cost=473.82..476.82 rows=100 width=40) (actual time=50217.415..53062.468 rows=1025 loops=1)
         Group Key: qt.query_o
         Buffers: shared hit=26513337
         ->  Sort  (cost=473.82..474.07 rows=100 width=20) (actual time=50214.748..50650.740 rows=9324425 loops=1)
               Sort Key: qt.query_o
               Sort Method: quicksort  Memory: 832749kB
               Buffers: shared hit=26513337
               ->  Nested Loop Left Join  (cost=3.52..470.50 rows=100 width=20) (actual time=0.790..48459.027 rows=9324425 loops=1)
                     Buffers: shared hit=26513337
                     ->  CTE Scan on qt  (cost=0.00..4.00 rows=100 width=32) (actual time=0.782..5483.806 rows=9324425 loops=1)
                           Buffers: shared hit=9232
                     ->  Bitmap Heap Scan on nblast_similarity_score nss  (cost=3.52..4.65 rows=1 width=20) (actual time=0.004..0.004 rows=0 loops=9324425)
                           Recheck Cond: ((target_object_id = qt.target_id) AND (query_object_id = qt.query_id))
                           Filter: (similarity_id = 2282)
                           Heap Blocks: exact=78412
                           Buffers: shared hit=26504105
                           ->  BitmapAnd  (cost=3.52..3.52 rows=1 width=0) (actual time=0.003..0.003 rows=0 loops=9324425)
                                 Buffers: shared hit=26425693
                                 ->  Bitmap Index Scan on nblast_similarity_score_target_object_id  (cost=0.00..1.43 rows=21 width=0) (actual time=0.002..0.002 rows=9 loops=9324425)
                                       Index Cond: (target_object_id = qt.target_id)
                                       Buffers: shared hit=18648850
                                 ->  Bitmap Index Scan on nblast_similarity_score_query_object_id  (cost=0.00..1.84 rows=77 width=0) (actual time=0.003..0.003 rows=76 loops=3871425)
                                       Index Cond: (query_object_id = qt.query_id)
                                       Buffers: shared hit=7776843
 Planning:
   Buffers: shared hit=2
 Planning Time: 0.474 ms
 Execution Time: 53362.434 ms
(42 rows)

Time: 53363.526 ms (00:53.364)

It would be great if this timing could be brought down from currently 53 sec. I compare it to alternatives of storing the dense matrix explicitly either as real[][] (6 sec) or large object (4.5 sec), which are of course faster when reading the data entirely (comes with downsides like size limitations and slow SQL access to individual entries). The plan above suggests that some result size estimates are pretty low, maybe leading to bad plans (yes, it is ANALYZED and the default stats target is 5000)?

For context: this query is performed from a Django back-end (Python) and returned to a front-end as a response to a HTTP request.

Edit: As suggested by Laurenz Albe, some improvement is possible with better estimates. I tried both a custom large_unnest function as well as disabling nested loop joins for the query. Both are helpful suggestions and lead to better plans. The custom large_unset function leads ta runtime of 19 sec:

 Aggregate  (cost=1348212.99..1348213.01 rows=1 width=32) (actual time=18804.368..18804.374 rows=1 loops=1)
   Buffers: shared hit=9732
   CTE qt
     ->  Nested Loop  (cost=0.78..160083.01 rows=4000000 width=32) (actual time=2.180..3113.809 rows=9324425 loops=1)
           Buffers: shared hit=9232
           ->  Nested Loop  (cost=0.53..82.76 rows=2000 width=36) (actual time=0.391..2.654 rows=1025 loops=1)
                 Buffers: shared hit=7
                 ->  Index Scan using nblast_similarity_pkey on nblast_similarity s  (cost=0.28..2.51 rows=1 width=51) (actual time=0.018..0.021 rows=1 loops=1)
                       Index Cond: (id = 2282)
                       Buffers: shared hit=3
                 ->  Function Scan on large_unnest query  (cost=0.25..40.25 rows=2000 width=16) (actual time=0.365..1.633 rows=1025 loops=1)
                       Buffers: shared hit=4
           ->  Function Scan on large_unnest target  (cost=0.25..40.25 rows=2000 width=16) (actual time=1.834..2.252 rows=9097 loops=1025)
                 Buffers: shared hit=9225
   ->  GroupAggregate  (cost=1158120.98..1188125.48 rows=200 width=40) (actual time=15175.754..18745.797 rows=1025 loops=1)
         Group Key: scores.query_o
         Buffers: shared hit=9732
         ->  Sort  (cost=1158120.98..1168120.98 rows=4000000 width=20) (actual time=15172.036..15584.416 rows=9324425 loops=1)
               Sort Key: scores.query_o
               Sort Method: quicksort  Memory: 1121687kB
               Buffers: shared hit=9732
               ->  Subquery Scan on scores  (cost=607270.06..719489.61 rows=4000000 width=20) (actual time=10514.543..13821.419 rows=9324425 loops=1)
                     Buffers: shared hit=9732
                     ->  Limit  (cost=607270.06..639489.61 rows=4000000 width=36) (actual time=10514.536..13183.841 rows=9324425 loops=1)
                           Buffers: shared hit=9732
                           ->  Merge Right Join  (cost=607270.06..639489.61 rows=4000000 width=36) (actual time=10261.048..12382.913 rows=9324425 loops=1)
                                 Merge Cond: ((nss.query_object_id = qt.query_id) AND (nss.target_object_id = qt.target_id))
                                 Buffers: shared hit=9732
                                 ->  Sort  (cost=8638.69..8834.72 rows=78412 width=20) (actual time=33.814..43.757 rows=78412 loops=1)
                                       Sort Key: nss.query_object_id, nss.target_object_id
                                       Sort Method: quicksort  Memory: 9198kB
                                       Buffers: shared hit=500
                                       ->  Seq Scan on nblast_similarity_score nss  (cost=0.00..2264.27 rows=78412 width=20) (actual time=0.019..6.504 rows=78412 loops=1)
                                             Filter: (similarity_id = 2282)
                                             Buffers: shared hit=500
                                 ->  Sort  (cost=598631.37..608631.37 rows=4000000 width=32) (actual time=10227.173..11103.484 rows=9324425 loops=1)
                                       Sort Key: qt.query_id, qt.target_id
                                       Sort Method: quicksort  Memory: 1121687kB
                                       Buffers: shared hit=9232
                                       ->  CTE Scan on qt  (cost=0.00..160000.00 rows=4000000 width=32) (actual time=2.185..5524.025 rows=9324425 loops=1)
                                             Buffers: shared hit=9232
 Planning:
   Buffers: shared hit=2
 Planning Time: 0.680 ms
 JIT:
   Functions: 36
   Options: Inlining true, Optimization true, Expressions true, Deforming true
   Timing: Generation 1.907 ms, Inlining 6.672 ms, Optimization 151.239 ms, Emission 95.707 ms, Total 255.524 ms
 Execution Time: 19135.939 ms
(49 rows)

Time: 19137.368 ms (00:19.137)

Interestingly, disabling nested loop join altogether for the query and removing MATERIALIZED from the first CTE leads to an even better plan with a runtime of 8 sec, but only if the original UNNEST is used:

 Aggregate  (cost=20000004304.55..20000004304.57 rows=1 width=32) (actual time=8460.589..8460.594 rows=1 loops=1)
   Buffers: shared hit=9732
   ->  GroupAggregate  (cost=20000004303.34..20000004304.32 rows=10 width=40) (actual time=5628.507..8402.370 rows=1025 loops=1)
         Group Key: query.o
         Buffers: shared hit=9732
         ->  Sort  (cost=20000004303.34..20000004303.59 rows=100 width=20) (actual time=5625.952..6067.150 rows=9324425 loops=1)
               Sort Key: query.o
               Sort Method: quicksort  Memory: 832749kB
               Buffers: shared hit=9732
               ->  Hash Left Join  (cost=20000004224.85..20000004300.02 rows=100 width=20) (actual time=201.473..4356.689 rows=9324425 loops=1)
                     Hash Cond: ((query.id = nss.query_object_id) AND (target.id = nss.target_object_id))
                     Buffers: shared hit=9732
                     ->  Nested Loop  (cost=20000000000.28..20000000006.91 rows=100 width=32) (actual time=181.110..2089.076 rows=9324425 loops=1)
                           Buffers: shared hit=9232
                           ->  Nested Loop  (cost=10000000000.28..10000000002.91 rows=10 width=36) (actual time=180.056..181.406 rows=1025 loops=1)
                                 Buffers: shared hit=7
                                 ->  Index Scan using nblast_similarity_pkey on nblast_similarity s  (cost=0.28..2.51 rows=1 width=51) (actual time=179.859..179.861 rows=1 loops=1)
                                       Index Cond: (id = 2282)
                                       Buffers: shared hit=3
                                 ->  Function Scan on unnest query  (cost=0.00..0.20 rows=10 width=16) (actual time=0.186..0.939 rows=1025 loops=1)
                                       Buffers: shared hit=4
                           ->  Function Scan on unnest target  (cost=0.00..0.20 rows=10 width=16) (actual time=0.596..1.192 rows=9097 loops=1025)
                                 Buffers: shared hit=9225
                     ->  Hash  (cost=2264.27..2264.27 rows=78412 width=20) (actual time=20.286..20.287 rows=78412 loops=1)
                           Buckets: 131072  Batches: 1  Memory Usage: 5313kB
                           Buffers: shared hit=500
                           ->  Seq Scan on nblast_similarity_score nss  (cost=0.00..2264.27 rows=78412 width=20) (actual time=0.015..6.740 rows=78412 loops=1)
                                 Filter: (similarity_id = 2282)
                                 Buffers: shared hit=500
 Planning:
   Buffers: shared hit=2
 Planning Time: 0.650 ms
 JIT:
   Functions: 29
   Options: Inlining true, Optimization true, Expressions true, Deforming true
   Timing: Generation 1.608 ms, Inlining 6.629 ms, Optimization 102.178 ms, Emission 71.173 ms, Total 181.588 ms
 Execution Time: 8519.436 ms
(37 rows)

Time: 8520.675 ms (00:08.521)

I suppose there is no real way around the sorting though.

Improve this question

1 Answer 1

Reset to default
1

The root problem here is that the calls to unnest cannot be estimated properly by the optimizer: it estimates a result size of ten rows, when really it is over 1000.

I can think of two remedies:

  • create a custom unnest function that estimates 2000 result rows and use that:

    create function large_unnest(
   IN anyarray,
   OUT anyelement,
   OUT bigint
) RETURNS SETOF record
   ROWS 2000 IMMUTABLE LANGUAGE sql AS
'SELECT * FROM unnest($1) WITH ORDINALITY';

  • disable nested loop joins for the duration of the query to mitigate the problem of the bad estimate:

    BEGIN;

SET LOCAL enable_nestloop = off;

SELECT ...;

COMMIT;
Improve this answer
1
  • Thanks for these suggestions! Both are great ideas and I tried them. The resulting query plans are now added to my question. The custom unnest brings the runtime down to 19 sec and disabling nested loop joins altogether even 8 sec. Both feel like a hack, but given the big difference, I will likely go with disabling nested loop joins. I will wait a bit longer if more suggestions are brought up, but will otherwise accept your answer.
    – tomka
    Commented Jan 20, 2022 at 14:53

Your Answer

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

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