5

I have a large partitioned table that stores monetary transactions between accounts.

CREATE TABLE "transactions" (
  "from" BYTEA        NOT NULL  -- sender account
  ,"to" BYTEA         NOT NULL  -- receiver account
  ,"type" INTEGER     NOT NULL  -- type of transfer
  ,"ts" TIMESTAMP     NOT NULL  -- timestamp of transfer
) PARTITION BY RANGE ("ts");

"transactions" has indexes on "ts", "from" and "to" (with "ts" for ordering).

CREATE INDEX "transactions_ts_idx"   ON "transactions" USING BTREE ("ts");
CREATE INDEX "transactions_from_idx" ON "transactions" USING BTREE ("from", "ts");
CREATE INDEX "transactions_to_idx"   ON "transactions" USING BTREE ("to",   "ts");

I would like to query all transactions involving a given account, or no account, something like:

-- given an account <account>
SELECT * FROM "transactions"
WHERE "from" = '<account>' OR "to" = '<account>'
ORDER BY "ts" DESC;

and

-- all transactions irrespective of account
SELECT * FROM "transactions"
ORDER BY "ts" DESC;
SELECT * FROM "transactions"
WHERE "from" = '<account>' OR "to" = '<account>'
ORDER BY "ts" DESC;

The subsequent query plan for the first query given an <account> involves BITMAP INDEX SCANs on the "from" and "to" indexes followed by BITMAP OR, over each partition, as expected.

...
|  ->  BitmapOr  (cost=535.22..535.22 rows=17744 width=0) (actual time=6.355..6.356 rows=0 loops=1)                                     |
|    ->  Bitmap Index Scan on transactions_2022_12_from_idx  (cost=0.00..185.51 rows=7058 width=0) (actual time=2.742..2.742 rows=0 loops=1)  |
|      Index Cond: (("from")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea)                                            |
|    ->  Bitmap Index Scan on transactions_2022_12_to_idx  (cost=0.00..340.84 rows=10686 width=0) (actual time=3.613..3.613 rows=0 loops=1)     |
|      Index Cond: (("to")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea)                                              |
...

However I'm concerned about the CPU and memory of this query plan given how frequent it will be.

Is there an alternative way to construct the table/s or indexes to make queries more efficient?

For example the table could switch from a single entry to a double entry structure where each row in the table instead becomes three rows with new columns "account" ("from", "to", or null for querying regardless of "account"), "counterparty" ("to", "from", or null -> counter-party of "account"), and "role" ("sender", "receiver", or null) instead of "from" and "to".

EDIT

in response to @a_horse_with_no_name, here is the full query plan

explain analyze
select "ts", "from", "to", "value"
from "transactions"
where
  "from" = '\xc5db3df907e7aa97f2da491e328578be27e9e644'
  or "to" = '\xc5db3df907e7aa97f2da491e328578be27e9e644'
order by "ts" desc
limit 10;

+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| QUERY PLAN                                                                                                                                                                             |
|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| Limit  (cost=306390.44..306390.46 rows=10 width=55) (actual time=0.268..0.272 rows=10 loops=1)                                                                                         |
|   ->  Sort  (cost=306390.44..306585.11 rows=77870 width=55) (actual time=0.267..0.270 rows=10 loops=1)                                                                                 |
|         Sort Key: transactions.ts DESC                                                                                                                                                 |
|         Sort Method: top-N heapsort  Memory: 27kB                                                                                                                                      |
|         ->  Append  (cost=50.80..304707.70 rows=77870 width=55) (actual time=0.099..0.241 rows=120 loops=1)                                                                            |
|               ->  Bitmap Heap Scan on transactions_2022_04 transactions_1  (cost=50.80..6666.09 rows=1709 width=58) (actual time=0.041..0.041 rows=0 loops=1)                          |
|                     Recheck Cond: ((("from")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea) OR (("to")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea))   |
|                     ->  BitmapOr  (cost=50.80..50.80 rows=1709 width=0) (actual time=0.039..0.040 rows=0 loops=1)                                                                      |
|                           ->  Bitmap Index Scan on transactions_2022_04_from_ts_idx  (cost=0.00..23.55 rows=932 width=0) (actual time=0.034..0.034 rows=0 loops=1)                     |
|                                 Index Cond: (("from")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea)                                                                    |
|                           ->  Bitmap Index Scan on transactions_2022_04_to_ts_idx  (cost=0.00..26.39 rows=777 width=0) (actual time=0.005..0.005 rows=0 loops=1)                       |
|                                 Index Cond: (("to")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea)                                                                      |
|               ->  Bitmap Heap Scan on transactions_2022_05 transactions_2  (cost=535.22..69369.48 rows=17744 width=56) (actual time=0.011..0.012 rows=0 loops=1)                       |
|                     Recheck Cond: ((("from")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea) OR (("to")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea))   |
|                     ->  BitmapOr  (cost=535.22..535.22 rows=17744 width=0) (actual time=0.011..0.011 rows=0 loops=1)                                                                   |
|                           ->  Bitmap Index Scan on transactions_2022_05_from_ts_idx  (cost=0.00..185.51 rows=7058 width=0) (actual time=0.005..0.005 rows=0 loops=1)                   |
|                                 Index Cond: (("from")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea)                                                                    |
|                           ->  Bitmap Index Scan on transactions_2022_05_to_ts_idx  (cost=0.00..340.84 rows=10686 width=0) (actual time=0.006..0.006 rows=0 loops=1)                    |
|                                 Index Cond: (("to")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea)                                                                      |
|               ->  Bitmap Heap Scan on transactions_2022_06 transactions_3  (cost=389.80..48846.95 rows=12582 width=54) (actual time=0.011..0.011 rows=0 loops=1)                       |
|                     Recheck Cond: ((("from")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea) OR (("to")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea))   |
|                     ->  BitmapOr  (cost=389.80..389.80 rows=12582 width=0) (actual time=0.011..0.011 rows=0 loops=1)                                                                   |
|                           ->  Bitmap Index Scan on transactions_2022_06_from_ts_idx  (cost=0.00..127.32 rows=4634 width=0) (actual time=0.006..0.006 rows=0 loops=1)                   |
|                                 Index Cond: (("from")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea)                                                                    |
|                           ->  Bitmap Index Scan on transactions_2022_06_to_ts_idx  (cost=0.00..256.19 rows=7949 width=0) (actual time=0.005..0.005 rows=0 loops=1)                     |
|                                 Index Cond: (("to")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea)                                                                      |
|               ->  Bitmap Heap Scan on transactions_2022_07 transactions_4  (cost=469.78..58879.05 rows=15080 width=55) (actual time=0.010..0.010 rows=0 loops=1)                       |
|                     Recheck Cond: ((("from")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea) OR (("to")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea))   |
|                     ->  BitmapOr  (cost=469.78..469.78 rows=15080 width=0) (actual time=0.010..0.010 rows=0 loops=1)                                                                   |
|                           ->  Bitmap Index Scan on transactions_2022_07_from_ts_idx  (cost=0.00..142.28 rows=5028 width=0) (actual time=0.005..0.005 rows=0 loops=1)                   |
|                                 Index Cond: (("from")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea)                                                                    |
|                           ->  Bitmap Index Scan on transactions_2022_07_to_ts_idx  (cost=0.00..319.96 rows=10052 width=0) (actual time=0.005..0.005 rows=0 loops=1)                    |
|                                 Index Cond: (("to")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea)                                                                      |
|               ->  Bitmap Heap Scan on transactions_2022_08 transactions_5  (cost=269.33..33314.79 rows=8524 width=55) (actual time=0.025..0.077 rows=77 loops=1)                       |
|                     Recheck Cond: ((("from")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea) OR (("to")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea))   |
|                     Heap Blocks: exact=65                                                                                                                                              |
|                     ->  BitmapOr  (cost=269.33..269.33 rows=8524 width=0) (actual time=0.017..0.017 rows=0 loops=1)                                                                    |
|                           ->  Bitmap Index Scan on transactions_2022_08_from_ts_idx  (cost=0.00..81.88 rows=2841 width=0) (actual time=0.010..0.010 rows=64 loops=1)                   |
|                                 Index Cond: (("from")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea)                                                                    |
|                           ->  Bitmap Index Scan on transactions_2022_08_to_ts_idx  (cost=0.00..183.19 rows=5683 width=0) (actual time=0.007..0.007 rows=30 loops=1)                    |
|                                 Index Cond: (("to")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea)                                                                      |
|               ->  Bitmap Heap Scan on transactions_2022_09 transactions_6  (cost=247.75..30679.40 rows=7826 width=55) (actual time=0.015..0.030 rows=21 loops=1)                       |
|                     Recheck Cond: ((("from")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea) OR (("to")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea))   |
|                     Heap Blocks: exact=20                                                                                                                                              |
|                     ->  BitmapOr  (cost=247.75..247.75 rows=7826 width=0) (actual time=0.013..0.013 rows=0 loops=1)                                                                    |
|                           ->  Bitmap Index Scan on transactions_2022_09_from_ts_idx  (cost=0.00..76.60 rows=2671 width=0) (actual time=0.007..0.007 rows=19 loops=1)                   |
|                                 Index Cond: (("from")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea)                                                                    |
|                           ->  Bitmap Index Scan on transactions_2022_09_to_ts_idx  (cost=0.00..167.23 rows=5155 width=0) (actual time=0.005..0.005 rows=4 loops=1)                     |
|                                 Index Cond: (("to")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea)                                                                      |
|               ->  Bitmap Heap Scan on transactions_2022_10 transactions_7  (cost=215.28..26566.61 rows=6767 width=55) (actual time=0.016..0.030 rows=21 loops=1)                       |
|                     Recheck Cond: ((("from")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea) OR (("to")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea))   |
|                     Heap Blocks: exact=20                                                                                                                                              |
|                     ->  BitmapOr  (cost=215.28..215.28 rows=6767 width=0) (actual time=0.013..0.013 rows=0 loops=1)                                                                    |
|                           ->  Bitmap Index Scan on transactions_2022_10_from_ts_idx  (cost=0.00..59.88 rows=2041 width=0) (actual time=0.007..0.008 rows=19 loops=1)                   |
|                                 Index Cond: (("from")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea)                                                                    |
|                           ->  Bitmap Index Scan on transactions_2022_10_to_ts_idx  (cost=0.00..152.01 rows=4726 width=0) (actual time=0.006..0.006 rows=5 loops=1)                     |
|                                 Index Cond: (("to")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea)                                                                      |
|               ->  Bitmap Heap Scan on transactions_2022_11 transactions_8  (cost=213.57..25724.08 rows=6554 width=55) (actual time=0.011..0.012 rows=1 loops=1)                        |
|                     Recheck Cond: ((("from")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea) OR (("to")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea))   |
|                     Heap Blocks: exact=1                                                                                                                                               |
|                     ->  BitmapOr  (cost=213.57..213.57 rows=6554 width=0) (actual time=0.010..0.010 rows=0 loops=1)                                                                    |
|                           ->  Bitmap Index Scan on transactions_2022_11_from_ts_idx  (cost=0.00..53.07 rows=1667 width=0) (actual time=0.006..0.006 rows=1 loops=1)                    |
|                                 Index Cond: (("from")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea)                                                                    |
|                           ->  Bitmap Index Scan on transactions_2022_11_to_ts_idx  (cost=0.00..157.22 rows=4887 width=0) (actual time=0.004..0.004 rows=0 loops=1)                     |
|                                 Index Cond: (("to")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea)                                                                      |
|               ->  Bitmap Heap Scan on transactions_2022_12 transactions_9  (cost=57.80..4271.89 rows=1084 width=55) (actual time=0.009..0.009 rows=0 loops=1)                          |
|                     Recheck Cond: ((("from")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea) OR (("to")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea))   |
|                     ->  BitmapOr  (cost=57.80..57.80 rows=1084 width=0) (actual time=0.008..0.009 rows=0 loops=1)                                                                      |
|                           ->  Bitmap Index Scan on transactions_2022_12_from_ts_idx  (cost=0.00..14.46 rows=253 width=0) (actual time=0.004..0.004 rows=0 loops=1)                     |
|                                 Index Cond: (("from")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea)                                                                    |
|                           ->  Bitmap Index Scan on transactions_2022_12_to_ts_idx  (cost=0.00..42.80 rows=831 width=0) (actual time=0.004..0.004 rows=0 loops=1)                       |
|                                 Index Cond: (("to")::bytea = '\xc5db3df907e7aa97f2da491e328578be27e9e644'::bytea)                                                                      |
| Planning Time: 0.410 ms                                                                                                                                                                |
| Execution Time: 0.334 ms                                                                                                                                                               |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
EXPLAIN 74
4
  • That part runs in 6 milliseconds. How fast do you need that to be?
    – user1822
    Commented Dec 12, 2022 at 22:20
  • @a_horse_with_no_name that example is running on test data with an account that doesn't have much usage. I included the explain to demonstrate the plan. I'm concerned about the CPU and memory on the real dataset cybertec-postgresql.com/en/avoid-or-for-better-performance
    – nick314
    Commented Dec 12, 2022 at 22:32
  • 2
    Well, if you want a better answer, include the complete plan generated with real data
    – user1822
    Commented Dec 12, 2022 at 22:38
  • @a_horse_with_no_name thanks, I've added the query plan
    – nick314
    Commented Dec 12, 2022 at 23:37

1 Answer 1

9

That query won't become much faster. Note that you won't be able to support both the WHERE condition and the ORDER BY with indexes; you have to decide which one you want. To support the WHERE condition, have indexes on from and to; to support ORDER BY, have an index on ts.

If you are willing to rewrite the query, it could be faster:

((SELECT ts, "from", "to", value
  FROM transactions
  WHERE "from" = '\xc5db3df907e7aa97f2da491e328578be27e9e644'
  ORDER BY ts DESC
  LIMIT 10)
 UNION ALL
 (SELECT ts, "from", "to", value
  FROM transactions
  WHERE "to" = '\xc5db3df907e7aa97f2da491e328578be27e9e644'
  ORDER BY ts DESC
  LIMIT 10))
ORDER BY ts DESC
LIMIT 10;

That query would benefit from two indexes, one on ("from", ts), and one on ("to", ts).

You should avoid column names that are SQL keywords.

7
  • Both of the "from" and "to" indexes are multicolumn indexes sorted at the end by "ts" so shouldn't the Bitmap Index Scan's on "from" and "to" also be ordered by "ts"? and therefore each "Bitmap Index Scan" only need to scan LIMIT rows each? And therefore the "Bitmap Or" only have at most 20 rows and therefore the "Bitmap Heap Scan" only scan 20 rows? (all per partition)?
    – nick314
    Commented Dec 13, 2022 at 6:15
  • 1
    No, a bitmap index scan will always return rows as they are physically sorted in the table, not in index order. That's the idea behind a bitmap index scan. You see that there is an explicit "sort" node in your plan. Commented Dec 13, 2022 at 6:20
  • Ouch. So the Bitmap Scan has to scan the entire index which may contain hundreds of millions of rows. For both the "from" and "to" filter clauses. Then heap scan every hit (could be hundreds of thousands) and sort them. That's nasty! Seems I can just do this better with a sub-query of the union of the query against "from" and "to" separately then sort and limit the results. How does that sound?
    – nick314
    Commented Dec 13, 2022 at 6:31
  • 1
    No. The bitmap index scan only scans those parts of the index that match the index condition. And yes, it has to fetch all the rows that match the OR condition, otherwise it cannot sort them. You can do better with UNION; I'll edit my answer for that. Commented Dec 13, 2022 at 7:25
  • 1
    To remove duplicate rows you can use UNION instead of UNION ALL
    – bobflux
    Commented Dec 13, 2022 at 13:23

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.