1

I have a table market_trades with a timestamp column:

api_production=# \d market_trades; Table "public.market_trades" Column | Type | Modifiers ----------------+-----------------------------+------------------------------------------------------------ id | integer | not null default nextval('market_trades_id_seq'::regclass) market_id | integer | not null timestamp | timestamp without time zone | not null amount | numeric(16,8) | not null price | numeric(16,8) | not null created_at | timestamp without time zone | local_id | integer | not null Indexes: "market_trades_pkey" PRIMARY KEY, btree (id) "market_trades__uniqueness" UNIQUE, btree (market_id, "timestamp", local_id)

which has about 30 million rows.

In the simplest case, I need to take a time range and sub-interval length, break the time range into sub-intervals of the given length, and count the number of trades with timestamp in each sub-interval.

For example, if the time range is [2013-01-01 00:00, 2013-02-01 00:00) and the sub-interval length is 1 day, then my result set will include 31 rows (one for each day), and will list the total number of records for that day.

I already designed a query to do this:

WITH vals AS ( SELECT '2013-08-19 0:00'::timestamp AS frame_start, '2013-08-26 0:00'::timestamp AS frame_end, '17h'::interval AS interval_length ), intervals AS ( SELECT tsrange(start_time, lead(start_time, 1, frame_end) OVER (ORDER BY start_time NULLS FIRST)) AS time_range FROM ( SELECT generate_series(frame_start, frame_end, interval_length) AS start_time, frame_end FROM vals ) _ WHERE start_time < frame_end ) SELECT time_range, count(td.id) AS agg FROM intervals i LEFT JOIN market_trades td ON td.timestamp <@ i.time_range GROUP BY time_range ORDER BY time_range;

which outputs

 time_range | agg -----------------------------------------------+------- ["2013-08-19 00:00:00","2013-08-19 17:00:00") | 10852 ["2013-08-19 17:00:00","2013-08-20 10:00:00") | 4727 ["2013-08-20 10:00:00","2013-08-21 03:00:00") | 7875 ["2013-08-21 03:00:00","2013-08-21 20:00:00") | 12137 ["2013-08-21 20:00:00","2013-08-22 13:00:00") | 8454 ["2013-08-22 13:00:00","2013-08-23 06:00:00") | 10284 ["2013-08-23 06:00:00","2013-08-23 23:00:00") | 8385 ["2013-08-23 23:00:00","2013-08-24 16:00:00") | 4978 ["2013-08-24 16:00:00","2013-08-25 09:00:00") | 4709 ["2013-08-25 09:00:00","2013-08-26 00:00:00") | 8620 (10 rows) Time: 64433.256 ms

The problem is that it is VERY slow. (As you can see, that query took over a minute to run!). So, naturally, I tried adding a btree index on the timestamp column. But this didn't help at all. Also, I've found that the time it takes is proportional to the number of sub-intervals (i.e. doubling both the overall time range and the interval length takes about the same amount of time as the original).

Here is the output of EXPLAIN ANALYZE on the above query:

 QUERY PLAN ---------------------------------------------------------------------------------------------------------------------------------------------------------- Sort (cost=198931037.42..198931037.92 rows=200 width=36) (actual time=460481.744..460481.750 rows=10 loops=1) Sort Key: i.time_range Sort Method: quicksort Memory: 25kB CTE vals -> Result (cost=0.00..0.01 rows=1 width=0) (actual time=0.002..0.003 rows=1 loops=1) CTE intervals -> WindowAgg (cost=31.47..38.13 rows=333 width=16) (actual time=0.057..0.174 rows=10 loops=1) -> Sort (cost=31.47..32.30 rows=333 width=16) (actual time=0.047..0.063 rows=10 loops=1) Sort Key: _.start_time Sort Method: quicksort Memory: 25kB -> Subquery Scan on _ (cost=0.00..17.52 rows=333 width=16) (actual time=0.012..0.034 rows=10 loops=1) Filter: (_.start_time < _.frame_end) -> CTE Scan on vals (cost=0.00..5.02 rows=1000 width=32) (actual time=0.009..0.019 rows=10 loops=1) -> HashAggregate (cost=198930989.64..198930991.64 rows=200 width=36) (actual time=460481.713..460481.721 rows=10 loops=1) -> Nested Loop Left Join (cost=0.00..198881140.83 rows=9969761 width=36) (actual time=25612.620..460406.061 rows=81021 loops=1) Join Filter: (td."timestamp" <@ i.time_range) Rows Removed by Join Filter: 299306019 -> CTE Scan on intervals i (cost=0.00..6.66 rows=333 width=32) (actual time=0.060..0.221 rows=10 loops=1) -> Materialize (cost=0.00..875147.34 rows=29939223 width=12) (actual time=0.006..24275.128 rows=29938704 loops=10) -> Seq Scan on market_trades td (cost=0.00..579263.23 rows=29939223 width=12) (actual time=0.008..22103.565 rows=29938704 loops=1) Total runtime: 460617.278 ms (21 rows)

Any suggestions?

EDIT: The problem is clearly that it's checking td.timestamp <@ i.time_range for every pair of a trade and an interval. There must be a better way to filter records within a timestamp range.

EDIT 2: If I change the line

ON td.timestamp <@ i.time_range

to

ON td.timestamp >= lower(i.time_range) AND td.timestamp < upper(i.time_range)

then it executes MUCH faster, so long as timestamp is indexed.

But this is still not ideal, because the nice thing about time ranges is that they properly handle NULL bounds (no lower bound or no upper bound), and checking for those NULL conditions manually in the ON clause slows down the query even more than the original.

Is there an indexing strategy (or better query structure) that makes working with time ranges as fast as start/end points?

Improve this question
6
  • explain.depesz.com/s/KwaM Commented Aug 22, 2014 at 22:00
  • Yeah, so from that it seems unlikely that just adding indexes will help. It seems like there must be a more efficient way to structure this query, though. I mean, all I'm really doing is filtering by a timestamp range a handful of times. Commented Aug 22, 2014 at 22:33
  • Try generating a temp table like Tab(start_time, end_time) and then joining tables together. Postgree SQL is my flavour of SQL so not sure about code for temp table. Commented Aug 22, 2014 at 22:47
  • What's the benefit to that? And what would go in the temp table? One row per sub-interval? Commented Aug 22, 2014 at 22:50
  • Are you "appending" information, or are you inserting historical information as well? Commented Aug 22, 2014 at 22:58

1 Answer 1

Reset to default
1

A few thoughts. Consider range partitioning on "timestamp", it will reduce the amount of work your query have to do. Further optimization might be to calculate and store the agg for "closed" partitions. You will of course have to recalculate this when you modify historical information.

As a bonus it will be much easier to roll-out historical data that is no longer needed.

As mentioned this is just some thoughts and reflections, it may or it may not fit your situation. One pitfall may be the number of different intervals that you use for reporting. If larger intervals is not multiples of the partitioning interval this wont work well.

Edit: How is the plan affected by creating an temp table and an index on "timestamp"?

create index X on market_trades ( timestamp ); create temp table T ( time_range tsrange ); insert into T ( time_range ) WITH vals AS ( SELECT '2013-08-19 0:00'::timestamp AS frame_start, '2013-08-26 0:00'::timestamp AS frame_end, '17h'::interval AS interval_length ), intervals AS ( SELECT tsrange(start_time, lead(start_time, 1, frame_end) OVER (ORDER BY start_time NULLS FIRST)) AS time_range FROM ( SELECT generate_series(frame_start, frame_end, interval_length) AS start_time, frame_end FROM vals ) _ WHERE start_time < frame_end ) SELECT time_range FROM intervals i; create index x on T ( time_range ); analyze t; SELECT time_range, count(td.id) AS agg FROM T LEFT JOIN market_trades td ON td.timestamp <@ T.time_range GROUP BY T.time_range ORDER BY T.time_range;
Improve this answer
7
  • I had considered something like that, but as you said: "If larger intervals is not multiples of the partitioning interval this wont work well." That's not an acceptable restriction for me. Commented Aug 22, 2014 at 23:34
  • Since my intuition is that this query should be fast with proper indexing and query construction, I'm going to hold out for a more suitable answer for now, but will revisit your answer later if I have no luck. Commented Aug 22, 2014 at 23:36
  • I'll see if I can come up with something else. A silly question (I don't use postgres) what does <@ mean? Commented Aug 22, 2014 at 23:41
  • PostgreSQL 9.2 added range types. The tsrange() above creates a time range (it has a lower bound, an upper bound, and whether each bound is included in or excluded from the range). The <@ operator tests whether the value on the left is contained in the range on the right. Commented Aug 22, 2014 at 23:49
  • Answer to your Edit: It took the same amount of time to run as the original query. Commented Aug 23, 2014 at 0:25

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.