0

I am trying to find an optimized way to query for some data given some very particular tables. Frankly, I think some of the optimization might involve a table refactor, but I am trying to stave that off for now. I am seeing poor performance (~150ms) on about 34k rows, which feels like it should be a trivial amount. I can potentially attempt a refactor if there are no other stopgap steps in the interim.

Of note: we do not directly update or delete from the DB. Instead, we append rows, incrementing the version number and possibly changing the isDeleted column. So far as I can tell, this tends to be a pretty gnarly performance bottleneck, especially coupled with other requirements to be able to search the DB. We basically have to double back for almost every row to get 'the latest' version.

Due to the above requirement, we basically need to always filter for the highest version, and also do a separate filter step wherein we check that the highest version is not deleted; if the highest version is deleted, then it is expected we will return no results. They cannot be done at the same time (as far as I can tell) because if we do, then we are actually querying for the latest non-deleted row, which might not be the latest row.

The other issue seems to be that Postgres is not (or is not capable of) using an index when combining two IN clauses. I understand that we are effectively creating a multiplication, wherein we need to check each combination of all the IDs from each list. If this were an imperative language, I would just run the filter step on the same result pool, hopefully saving time by only having to filter a much smaller result set.

Putting it all together, my questions are:

  1. How can I optimize a query for combining different sets of IDs on different columns (to reiterate -- these need to be ANDed)?
  2. How can I optimize the access for the latest row?
  3. Is it possible to combine the above optimizations?
  4. Is all of this extra work worth the effort compared to refactoring towards two tables, one that is updated and cleared out like a regular DB table, and one that is only appended to?

Table DDL

create table resource_operation
(
    id               bigint  not null primary key,
    createdatetime   timestamp,
    creatorrid       varchar(255),
    isdeleted        boolean not null,
    lastupdatedbyrid varchar(255),
    rid              varchar(255), --rids are just UUIDs, except we store them as varchar.
    updatedatetime   timestamp,
    version          bigint  not null,
    actorrid         varchar(255),
    resourcerid      varchar(255),
    -- other data columns
);

alter table resource_operation
    owner to postgres;

create index actor_resource_operation_index
    on resource_operation using hash (actorrid);

create index resource_rid_resource_operation_index
    on resource_operation using hash (resourcerid);

create index resource_operation_rid_index
    on resource_operation using hash (rid);

create index version_btree
    on resource_operation (version);

create index resource_operation_rid_hash
    on resource_operation (rid);

create index resource_operation_resource_rid_hash
    on resource_operation (resourcerid);

create index resource_operation_actor_rid_hash
    on resource_operation (actorrid);

create index resource_operation_latest_version
    on resource_operation (rid asc, version desc, isdeleted asc) include (id)
    where (isdeleted = false);

create index resource_operation_operations_search
    on resource_operation (actorrid, resourcerid, isdeleted) include (id);

Queries Attempted

I have tried a great number of different queries which are meant to help optimize the access patterns, but they don't seem to have a strong effect. A lot of the time, there is no usage of indexes, even when it seems like it would make sense to use them. I have attached the two 'best' queries I have managed to come up with in terms of performance, but to reiterate, I have also tried to make creative use of joins, window functions, other CTEs, and more. If you feel like it would be a worthwhile exercise to share more of these, please let me know.

Seemingly the fastest

This query is what is currently running in the product. I feel like we could probably optimize it a bit further by reducing some of the joins, but then again, a lot of my other 'bright' ideas did not pan out, so I am pasting it as is.

WITH preVersionFilteredView AS (SELECT rid, MAX(version) AS maxVersion
                                FROM resource_operation
                                WHERE isDeleted = false
                                  AND actorRid IN ('ID-1',
                                                   'ID-2')
                                  AND resourceRid IN ('ID-3',
                                                      'ID-4',
                                                      'ID-5')
                                GROUP BY rid),
     maxVersionView AS (SELECT rid, MAX(version) AS maxVersion
                        FROM resource_operation
                        WHERE rid IN (SELECT rid FROM preVersionFilteredView)
                        GROUP BY rid)
SELECT DISTINCT e1.*
FROM resource_operation e1
         INNER JOIN maxVersionView ON e1.rid = maxVersionView.rid AND e1.version = maxVersionView.maxVersion
         INNER JOIN preVersionFilteredView
                    ON e1.rid = preVersionFilteredView.rid AND e1.version = preVersionFilteredView.maxVersion;
QUERY PLAN
Unique  (cost=79.70..79.73 rows=1 width=1284) (actual time=0.408..0.415 rows=3 loops=1)
  CTE preversionfilteredview
    ->  GroupAggregate  (cost=47.09..47.14 rows=3 width=75) (actual time=0.332..0.336 rows=4 loops=1)
          Group Key: resource_operation_1.rid
          ->  Sort  (cost=47.09..47.10 rows=3 width=75) (actual time=0.328..0.329 rows=7 loops=1)
                Sort Key: resource_operation_1.rid
                Sort Method: quicksort  Memory: 25kB
                ->  Bitmap Heap Scan on resource_operation resource_operation_1  (cost=35.36..47.07 rows=3 width=75) (actual time=0.309..0.320 rows=7 loops=1)
"                      Recheck Cond: (((actorrid)::text = ANY ('{<Ids here>}'::text[])) AND ((resourcerid)::text = ANY ('{<IDs here>}'::text[])))"
                      Filter: (NOT isdeleted)
                      Heap Blocks: exact=5
                      ->  BitmapAnd  (cost=35.36..35.36 rows=3 width=0) (actual time=0.297..0.297 rows=0 loops=1)
                            ->  Bitmap Index Scan on actor_resource_operation_index  (cost=0.00..8.73 rows=99 width=0) (actual time=0.018..0.018 rows=143 loops=1)
"                                  Index Cond: ((actorrid)::text = ANY ('{<Other list of ids here>}'::text[]))"
                            ->  Bitmap Index Scan on resource_rid_resource_operation_index  (cost=0.00..26.38 rows=852 width=0) (actual time=0.274..0.274 rows=860 loops=1)
"                                  Index Cond: ((resourcerid)::text = ANY ('{<list of Ids here>}'::text[]))"
  ->  Sort  (cost=32.56..32.56 rows=1 width=1284) (actual time=0.407..0.409 rows=3 loops=1)
"        Sort Key: e1.id, e1.createdatetime, e1.creatorrid, e1.isdeleted, e1.lastupdatedbyrid, e1.rid, e1.updatedatetime, e1.version, e1.actorrid, e1.resourcerid, e1.scopescomposite, e1.rolerids"
        Sort Method: quicksort  Memory: 27kB
        ->  Nested Loop  (cost=24.45..32.55 rows=1 width=1284) (actual time=0.386..0.399 rows=3 loops=1)
              ->  Merge Join  (cost=24.45..24.52 rows=1 width=599) (actual time=0.382..0.389 rows=3 loops=1)
                    Merge Cond: (((resource_operation.rid)::text = (preversionfilteredview.rid)::text) AND ((max(resource_operation.version)) = preversionfilteredview.maxversion))
                    ->  Sort  (cost=24.37..24.38 rows=4 width=75) (actual time=0.373..0.374 rows=3 loops=1)
"                          Sort Key: resource_operation.rid, (max(resource_operation.version))"
                          Sort Method: quicksort  Memory: 25kB
                          ->  GroupAggregate  (cost=24.22..24.29 rows=4 width=75) (actual time=0.367..0.370 rows=3 loops=1)
                                Group Key: resource_operation.rid
                                ->  Sort  (cost=24.22..24.23 rows=4 width=75) (actual time=0.365..0.366 rows=6 loops=1)
                                      Sort Key: resource_operation.rid
                                      Sort Method: quicksort  Memory: 25kB
                                      ->  Nested Loop  (cost=0.07..24.18 rows=4 width=75) (actual time=0.347..0.360 rows=6 loops=1)
                                            ->  HashAggregate  (cost=0.07..0.10 rows=3 width=516) (actual time=0.342..0.343 rows=4 loops=1)
                                                  Group Key: (preversionfilteredview_1.rid)::text
                                                  ->  CTE Scan on preversionfilteredview preversionfilteredview_1  (cost=0.00..0.06 rows=3 width=516) (actual time=0.334..0.338 rows=4 loops=1)
                                            ->  Index Scan using resource_operation_rid_index on resource_operation  (cost=0.00..8.02 rows=1 width=75) (actual time=0.002..0.003 rows=2 loops=4)
                                                  Index Cond: ((rid)::text = (preversionfilteredview_1.rid)::text)
                    ->  Sort  (cost=0.08..0.09 rows=3 width=524) (actual time=0.006..0.007 rows=4 loops=1)
"                          Sort Key: preversionfilteredview.rid, preversionfilteredview.maxversion"
                          Sort Method: quicksort  Memory: 25kB
                          ->  CTE Scan on preversionfilteredview  (cost=0.00..0.06 rows=3 width=524) (actual time=0.000..0.001 rows=4 loops=1)
              ->  Index Scan using resource_operation_rid_index on resource_operation e1  (cost=0.00..8.02 rows=1 width=1284) (actual time=0.002..0.003 rows=1 loops=3)
                    Index Cond: ((rid)::text = (resource_operation.rid)::text)
                    Filter: ((max(resource_operation.version)) = version)
                    Rows Removed by Filter: 1
Planning Time: 1.028 ms
Execution Time: 0.497 ms

Attempt with Lateral Join

select t.*
from resource_operation t
 join lateral (
    select vf.id
    from resource_operation vf
    where t.rid = vf.rid
    order by vf.version desc
    limit 1
    ) as lat on t.id = lat.id
where t.actorRid IN ('ID-1',
                   'ID-2')
  AND t.resourceRid IN ('ID-3',
                      'ID-4',
                      'ID-5')
  and t.isDeleted = false;
QUERY PLAN
Nested Loop  (cost=43.39..71.23 rows=1 width=1284) (actual time=0.136..0.149 rows=3 loops=1)
  ->  Bitmap Heap Scan on resource_operation t  (cost=35.36..47.07 rows=3 width=75) (actual time=0.094..0.101 rows=7 loops=1)
"        Recheck Cond: (((actorrid)::text = ANY ('{<IDs>}'::text[])) AND ((resourcerid)::text = ANY ('{<IDs>}'::text[])))"
        Filter: (NOT isdeleted)
        Heap Blocks: exact=5
        ->  BitmapAnd  (cost=35.36..35.36 rows=3 width=0) (actual time=0.083..0.083 rows=0 loops=1)
              ->  Bitmap Index Scan on actor_resource_operation_index  (cost=0.00..8.73 rows=99 width=0) (actual time=0.019..0.019 rows=143 loops=1)
"                    Index Cond: ((actorrid)::text = ANY ('{<IDs}'::text[]))"
              ->  Bitmap Index Scan on resource_rid_resource_operation_index  (cost=0.00..26.38 rows=852 width=0) (actual time=0.059..0.059 rows=860 loops=1)
"                    Index Cond: ((resourcerid)::text = ANY ('{<IDs>}'::text[]))"
  ->  Subquery Scan on lat  (cost=8.03..8.04 rows=1 width=1284) (actual time=0.006..0.006 rows=0 loops=7)
        Filter: (t.id = lat.id)
        Rows Removed by Filter: 0
        ->  Limit  (cost=8.03..8.03 rows=1 width=1284) (actual time=0.006..0.006 rows=1 loops=7)
              ->  Sort  (cost=8.03..8.03 rows=1 width=1284) (actual time=0.005..0.005 rows=1 loops=7)
                    Sort Key: vf.version DESC
                    Sort Method: quicksort  Memory: 26kB
                    ->  Index Scan using resource_operation_rid_index on resource_operation vf  (cost=0.00..8.02 rows=1 width=1284) (actual time=0.002..0.003 rows=2 loops=7)
                          Index Cond: ((rid)::text = (t.rid)::text)
Planning Time: 0.337 ms
Execution Time: 0.183 ms

2 Answers 2

1

Test data:

CREATE UNLOGGED TABLE resource_operation
(
    id               bigint  not null primary key,
    isdeleted        boolean not null,
    rid              INTEGER NOT NULL, --rids are just UUIDs, except we store them as varchar.
    version          bigint  not null,
    actorrid         INTEGER NOT NULL,
    resourcerid      INTEGER NOT NULL
);

INSERT INTO resource_operation SELECT
    n, 
    random()<0.1,
    n/100,
    n%100,
    n%10000,
    n%10000
    FROM generate_series(1,10000000) n;

CREATE INDEX ON resource_operation( actorrid );
CREATE INDEX ON resource_operation( resourcerid );
CREATE INDEX ON resource_operation( rid );
VACUUM ANALYZE resource_operation;

This test set has 10M rows. Let's try the LATERAL query.

EXPLAIN ANALYZE select t.*
from resource_operation t
 join lateral (
    select vf.id
    from resource_operation vf
    where t.rid = vf.rid
    order by vf.version desc
    limit 1
    ) as lat on t.id = lat.id
where t.actorRid IN (99,10099)
  AND t.resourceRid IN (99,10099)
  and t.isDeleted = false;

Nested Loop  (cost=61.96..66.00 rows=1 width=29) (actual time=1.377..23.552 rows=897 loops=1)
   ->  Bitmap Heap Scan on resource_operation t  (cost=48.02..52.04 rows=1 width=29) (actual time=1.236..2.002 rows=897 loops=1)
         Recheck Cond: ((resourcerid = ANY ('{99,10099}'::integer[])) AND (actorrid = ANY ('{99,10099}'::integer[])))
         Filter: (NOT isdeleted)
         Rows Removed by Filter: 103
         Heap Blocks: exact=1000
         ->  BitmapAnd  (cost=48.02..48.02 rows=1 width=0) (actual time=0.794..0.794 rows=0 loops=1)
               ->  Bitmap Index Scan on resource_operation_resourcerid_idx  (cost=0.00..23.89 rows=2002 width=0) (actual time=0.349..0.349 rows=1000 loops=1)
                     Index Cond: (resourcerid = ANY ('{99,10099}'::integer[]))
               ->  Bitmap Index Scan on resource_operation_actorrid_idx  (cost=0.00..23.89 rows=2002 width=0) (actual time=0.334..0.334 rows=1000 loops=1)
                     Index Cond: (actorrid = ANY ('{99,10099}'::integer[]))
   ->  Subquery Scan on lat  (cost=13.94..13.95 rows=1 width=8) (actual time=0.024..0.024 rows=1 loops=897)
         Filter: (t.id = lat.id)
         ->  Limit  (cost=13.94..13.94 rows=1 width=16) (actual time=0.024..0.024 rows=1 loops=897)
               ->  Sort  (cost=13.94..14.44 rows=200 width=16) (actual time=0.023..0.023 rows=1 loops=897)
                     Sort Key: vf.version DESC
                     Sort Method: top-N heapsort  Memory: 25kB
                     ->  Index Scan using resource_operation_rid_idx on resource_operation vf  (cost=0.43..12.94 rows=200 width=16) (actual time=0.002..0.015 rows=100 loops=897)
                           Index Cond: (rid = t.rid)
 Planning Time: 0.475 ms
 Execution Time: 23.656 ms

So this query selects the rows satisfying the WHERE conditions which are also the latest version. A problem is that it has to read all the versions of a row, which is slower and will greatly increase the size of the working set.

Let's try multicolumn indices and run the same query again:

CREATE INDEX ON resource_operation( actorrid, resourcerid ) INCLUDE (id,rid) WHERE NOT isdeleted;
CREATE INDEX ON resource_operation( rid, version DESC ) INCLUDE ( id, isdeleted );

 Nested Loop  (cost=1.00..22.43 rows=1 width=29) (actual time=0.071..7.850 rows=897 loops=1)
   ->  Index Scan using resource_operation_actorrid_resourcerid_rid_idx on resource_operation t  (cost=0.43..21.79 rows=1 width=29) (actual time=0.040..0.830 rows=897 loops=1)
         Index Cond: ((actorrid = ANY ('{99,10099}'::integer[])) AND (resourcerid = ANY ('{99,10099}'::integer[])))
   ->  Subquery Scan on lat  (cost=0.56..0.63 rows=1 width=8) (actual time=0.007..0.007 rows=1 loops=897)
         Filter: (lat.id = t.id)
         ->  Limit  (cost=0.56..0.62 rows=1 width=16) (actual time=0.007..0.007 rows=1 loops=897)
               ->  Index Only Scan using resource_operation_rid_version_id_isdeleted_idx on resource_operation vf  (cost=0.56..12.06 rows=200 width=16) (actual time=0.007..0.007 rows=1 loops=897)
                     Index Cond: (rid = t.rid)
                     Heap Fetches: 0
 Planning Time: 0.351 ms
 Execution Time: 7.940 ms

The first index allows finding the rows with actorrid and resourcerid quickly. The second index allows checking these rows are the last version quickly.

However, it will still have to check all index rows for versions with values of actorrid and resourcerid that satisfy the where, then discard those which are not the latest versions, and it also hits the table for all versions.

Changing the query to "SELECT t.id..." only allows an index-only scan. The drawback is that it returns only the id, but the advantage is that it will do a lot less random accesses since it does not hit all old versions in the table. The query can then be joined with the table again to fetch the rows. So this reduces working set on the table, but not on the indices.

To avoid slowing down queries when old versions accumulate, you should really use two tables, with one having only the latest versions. This can be done with triggers, but there are subtle locking issues.

2
  • Thank you very much for the thorough insight! I ended up using a CTE to select only for IDs as you suggested, and then join back the original table. Indeed, it only uses index scans. This was about 3x faster on my existing test DB as well. It is worth noting that your suggested indexes seemed to make an important difference. They are subtly different from the indexes in my question. Your answer was very helpful!
    – Mrpebbles
    Feb 27 at 16:28
  • Great! I see you have plenty of indexes in your question, including hash. Hash is nice for uuid because it takes less space than btree. But there's probably some redundancy and a little bit of cleanup to do ;) Indeed multicolumn index with included columns is really powerful for those fast index only scans!
    – bobflux
    Feb 27 at 17:44
1

The query itself should be simple:

SELECT *
FROM (SELECT DISTINCT ON (rid) *
      FROM resource_operation
      WHERE actorrid IN ('ID-1', 'ID-2')
        AND resourcerid IN ('ID-3', 'ID-4', 'ID-5')
      ORDER BY rid, version DESC) AS q
WHERE NOT isdeleted;

PostgreSQL would use indexes on actorrid and resourcerid if the conditions are selective. More efficient might be a combined index over both columns (with the more selective column first).

2
  • Thank you very much for your time! This indeed seems to be about 3x faster on my existing test DB. Just as a note to future readers (as it won't let me edit to add just one character): I needed to add an additional * to the first select statement to make it return rows :).
    – Mrpebbles
    Feb 27 at 16:27
  • 1
    Sorry, I have fixed that. The * is only because you had it in your question. Really, you would only select those columns that you need. Feb 27 at 16:30

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.