I have two large tables, tokens (100.000s of entries) and buy_orders (1.000.000s of entries) that I need to efficiently join and group by.
As seen below, tokens uniquely identified by a contract address (a 20 byte hex string) and an id (a 256 byte integer):
TABLE tokens (
contract TEXT NOT NULL
token_id NUMERIC(78, 0) NOT NULL
top_bid NUMERIC(78, 0)
PRIMARY KEY (contract, token_id)
)
Users can post bids on various tokens. The bids have a validity period (represented via a time range) and a price (which is a 256 byte integer). A bid can only one of two types:
contract + start_token_id + end_token_id)[(contract1 + token_id1), (contract2 + token_id2), ...])Below is the table for keeping the bids. It is highly denormalized to accommodate the 2 possible types a bid can have.
TABLE buy_orders (
id INT NOT NULL PRIMARY KEY
contract TEXT
start_token_id NUMERIC(78, 0)
end_token_id NUMERIC(78, 0)
token_list_id INT REFERENCES token_lists(id)
price NUMERIC(78, 0) NOT NULL,
valid_between TSTZRANGE NOT NULL,
cancelled BOOLEAN NOT NULL,
executed BOOLEAN NOT NULL
INDEX ON (contract, start_token_id, end_token_id DESC)
INDEX ON (token_list_id)
INDEX ON (price)
INDEX ON (cancelled, executed)
INDEX ON (valid_between) USING gist
)
Here are the corresponding tables holding the tokens belonging to each list:
TABLE token_lists (
id INT PRIMARY KEY
)
TABLE token_lists_tokens (
token_list_id INT NOT NULL REFERENCES token_lists(id)
contract TEXT NOT NULL
token_id NUMERIC(78, 0) NOT NULL
FOREIGN KEY (contract, token_id) REFERENCES tokens(address, id)
INDEX ON (contract, token_id)
)
As you can see in the tokens table, it keeps track of the top bid in order to make token data retrieval as efficiently as possible (we'll have a paginated API for retrieving all tokens of an address including their current top bid). As new bids come in, get cancelled/filled or expire, I need an efficient way to update the top bid for the tokens the bids are on. This is not a problem for bids of type 2, since those will most of the time reference an insignificant number of tokens, but it creates a problem for type 1 bids because in this case I might need to recalculate the top bid for 100.000s of tokens efficiently (eg. the type 2 bid could have a range of [1, 100.000]). Here's the query I'm using right now (I limited the results because otherwise it takes forever):
SELECT t.contract, t.token_id, max(b.price) FROM tokens t
JOIN buy_orders b ON t.contract = b.contract AND b.start_token_id <= t.token_id AND t.token_id <= b.end_token_id
WHERE t.contract = 'foo' AND NOT b.cancelled AND NOT b.filled AND b.valid_between @> now()
GROUP BY t.contract, t.token_id
LIMIT 1000
And here is the execution plan for it:
Limit (cost=5016.77..506906.79 rows=1000 width=81) (actual time=378.231..19260.361 rows=1000 loops=1)
-> GroupAggregate (cost=5016.77..37281894.72 rows=74273 width=81) (actual time=123.729..19005.567 rows=1000 loops=1)
Group Key: t.contract, t.token_id
-> Nested Loop (cost=5016.77..35589267.24 rows=225584633 width=54) (actual time=83.885..18953.853 rows=412253 loops=1)
Join Filter: ((b.start_token_id <= t.token_id) AND (t.token_id <= b.end_token_id))
Rows Removed by Join Filter: 140977658
-> Index Only Scan using tokens_pk on tokens t (cost=0.55..8186.80 rows=99100 width=49) (actual time=0.030..5.394 rows=11450 loops=1)
Index Cond: (contract = 'foo'::text)
Heap Fetches: 0
-> Materialize (cost=5016.21..51551.91 rows=20487 width=60) (actual time=0.001..0.432 rows=12348 loops=11450)
-> Bitmap Heap Scan on buy_orders b (cost=5016.21..51449.47 rows=20487 width=60) (actual time=15.245..116.099 rows=12349 loops=1)
Recheck Cond: (contract = 'foo'::text)
Filter: ((NOT cancelled) AND (NOT filled) AND (valid_between @> now()))
Rows Removed by Filter: 87771
Heap Blocks: exact=33525
-> Bitmap Index Scan on buy_orders_contract_start_token_id_end_token_id_index (cost=0.00..5011.09 rows=108072 width=0) (actual time=10.835..10.835 rows=100120 loops=1)
Index Cond: (contract = 'foo'::text)
Planning Time: 0.816 ms
JIT:
Functions: 15
Options: Inlining true, Optimization true, Expressions true, Deforming true
Timing: Generation 3.922 ms, Inlining 106.877 ms, Optimization 99.947 ms, Emission 47.445 ms, Total 258.190 ms
Execution Time: 19264.851 ms
What I'm looking for is a way to improve the efficiency of this particular query, if possible, or other suggestions to achieve the same result.
I'm using Postgres 13.
A partial, multi-column index may help. Such as;
CREATE INDEX ON buy_orders (contract, valid_between) -- Multiple fields
INCLUDE (price) -- non-key column for index only scan
WHERE -- represents partial index
NOT cancelled AND
NOT filled;
That will allow the index scan on buy_orders to remove more rows, so that you don't end up with
Rows Removed by Join Filter: 140977658
which is what makes your query expensive.