DISTINCT forces re-sorting of data on PostgreSQL

Question

I have a table recording transactions between accounts, looking like this:

txid    varchar(64)
account varchar(64)
ts      timestamp
amount  numeric

(there are more fields but they are irrelevant for this question). For each transaction there could be multiple accounts participating in it, and each account can participate in a transaction once or more times (or not at all of course), with different amounts and different other fields. There's an index on (account, ts)

I am trying to find all transactions where account has participated in given time frame, like this:

with txs as (
    SELECT txid FROM tx_items 
    WHERE account='...' and ts BETWEEN 1234 and 5678
    ORDER BY ts
)           
select distinct txid from txs limit 100 offset 100;

(limit/offset is needed for pagination on the frontend) But I get rather slow query because for some reason PostgreSQL insists on re-sorting the data after subquery:

Limit  (cost=224950.81..224954.60 rows=100 width=65) (actual time=4246.597..4246.751 rows=100 loops=1)
  ->  Unique  (cost=224947.01..228949.22 rows=105542 width=65) (actual time=4246.431..4246.731 rows=200 loops=1)
        ->  Sort  (cost=224947.01..226948.12 rows=800442 width=65) (actual time=4246.427..4246.678 rows=200 loops=1)
              Sort Key: txs.txid
              Sort Method: external merge  Disk: 58736kB
              ->  Subquery Scan on txs  (cost=0.56..80794.93 rows=800442 width=65) (actual time=0.038..441.496 rows=799292 loops=1)
                    ->  Index Only Scan using tx_accounts on tx_items  (cost=0.56..72790.51 rows=800442 width=74) (actual time=0.037..314.638 rows=799292 loops=1)
                          Index Cond: ((account = '...'::text) AND (ts >= ...) AND (ts <= ...))
                          Heap Fetches: 0
Planning Time: 0.177 ms
Execution Time: 4258.410 ms

In fact, I don't want it to do it - I want it to just give me first 100 unique IDs, in whatever order the internal query produces them. If I remove "distinct" it is fast:

Limit  (cost=10.66..20.76 rows=100 width=65) (actual time=0.148..0.214 rows=100 loops=1)
  ->  Subquery Scan on txs  (cost=0.56..3734.02 rows=36968 width=65) (actual time=0.084..0.197 rows=200 loops=1)
        ->  Index Only Scan using tx_accounts on tx_items  (cost=0.56..3364.34 rows=36968 width=74) (actual time=0.083..0.168 rows=200 loops=1)
              Index Cond: ((account = '...'::text) AND (ts >= ...) AND (ts <= ...))
              Heap Fetches: 0
Planning Time: 0.183 ms
Execution Time: 0.244 ms

but of course I'd get repeats, which I need to eliminate. Is there a way to make Postgres not try to re-sort all the data but just apply "unique" filter to it as they are already sorted?

The weird thing is that if I choose really small time window, I get what I want:

Limit  (cost=3827.44..3828.44 rows=100 width=65) (actual time=68.942..69.015 rows=100 loops=1)
  ->  HashAggregate  (cost=3826.44..3875.18 rows=4874 width=65) (actual time=68.872..68.995 rows=200 loops=1)
        Group Key: tx_items.txid
        ->  Index Only Scan using tx_accounts on tx_items  (cost=0.56..3364.34 rows=36968 width=74) (actual time=0.045..31.967 rows=82872 loops=1)
              Index Cond: ((account = '...'::text) AND (ts >= ...) AND (ts <= ...))
              Heap Fetches: 0
Planning Time: 0.277 ms
Execution Time: 69.132 ms

but if I expland the window, it goes back to sorting. What's going on? Is there a better way to do this task?

Answer 1

Is there a way to make Postgres not try to re-sort all the data but just apply "unique" filter to it as they are already sorted?

No. The existing "Unique" node only removes adjacent duplicates. So its input must be already ordered on the columns used to determine uniqueness, or it would not behave as expected. PostgreSQL provides no way to get access to the "Unique" node without its input being ordered correctly to start with, and if it would let you, you would not get the right answer.

The weird thing is that if I choose really small time window, I get what I want [a hash agg]

You don't get what you said you want. It does a hash-agg on the entire subquery, then reads out 200 rows from the hash table in an order determined by the internal hashtable mechanism, not "in whatever order the internal query produces them" (assuming "internal query" means subquery). Because of this way it works, it first stores all unique values in memory. If you expand the subquery enough, the planner no longer thinks it can fit them all in work_mem, so it no longer chooses that plan. (In the newest version it might spill the hash-agg data to disk if it is too big). To get this method to be used for larger datasets, you could increase work_mem.

You could make an argument for a "fast start" hashing uniquify node, which would emit rows as soon as it determined they were not emitted before, by comparing and inserting them to a growing hash table. Then it could stop reading its input (and stop growing its memory usage) once the LIMIT on emitted rows was reached. But this doesn't currently exist, and if it did exist it is not clear how to hook it up to the planner and to the SQL language itself.