Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I am trying to determine which indexes to use for an SQL query with a WHERE condition and a GROUP BY which is currently running very slow.

My query:

SELECT group_id
FROM counter
WHERE ts between timestamp '2014-03-02 00:00:00.0' and timestamp '2014-03-05 12:00:00.0'
GROUP BY group_id

The table currently has 32.000.000 rows. The execution time of the query increases a lot when I increase the time-frame.

The table in question looks like this:

CREATE TABLE counter (
    id bigserial PRIMARY KEY
  , ts timestamp NOT NULL
  , group_id bigint NOT NULL
);

I currently have the following indexes, but the performance is still slow:

CREATE INDEX ts_index
  ON counter
  USING btree
  (ts);

CREATE INDEX group_id_index
  ON counter
  USING btree
  (group_id);

CREATE INDEX comp_1_index
  ON counter
  USING btree
  (ts, group_id);

CREATE INDEX comp_2_index
  ON counter
  USING btree
  (group_id, ts);

Running EXPLAIN on the query gives the following result:

"QUERY PLAN"
"HashAggregate  (cost=467958.16..467958.17 rows=1 width=4)"
"  ->  Index Scan using ts_index on counter  (cost=0.56..467470.93 rows=194892 width=4)"
"        Index Cond: ((ts >= '2014-02-26 00:00:00'::timestamp without time zone) AND (ts <= '2014-02-27 23:59:00'::timestamp without time zone))"

SQL Fiddle with example data: http://sqlfiddle.com/#!15/7492b/1

The Question

Can the performance of this query be improved by adding better indexes, or must I increase the processing power?

Edit 1

PostgreSQL version 9.3.2 is used.

Edit 2

I tried @Erwin 's proposal with EXISTS:

SELECT group_id
FROM   groups g
WHERE  EXISTS (
   SELECT 1
   FROM   counter c
   WHERE  c.group_id = g.group_id
   AND    ts BETWEEN timestamp '2014-03-02 00:00:00'
                 AND timestamp '2014-03-05 12:00:00'
   );

But unfortunetly this didn't seem to increase the performance. The Query Plan:

"QUERY PLAN"
"Nested Loop Semi Join  (cost=1607.18..371680.60 rows=113 width=4)"
"  ->  Seq Scan on groups g  (cost=0.00..2.33 rows=133 width=4)"
"  ->  Bitmap Heap Scan on counter c  (cost=1607.18..158895.53 rows=60641 width=4)"
"        Recheck Cond: ((group_id = g.id) AND (ts >= '2014-01-01 00:00:00'::timestamp without time zone) AND (ts <= '2014-03-05 12:00:00'::timestamp without time zone))"
"        ->  Bitmap Index Scan on comp_2_index  (cost=0.00..1592.02 rows=60641 width=0)"
"              Index Cond: ((group_id = g.id) AND (ts >= '2014-01-01 00:00:00'::timestamp without time zone) AND (ts <= '2014-03-05 12:00:00'::timestamp without time zone))"

Edit 3

The query plan for the LATERAL query from ypercube:

"QUERY PLAN"
"Nested Loop  (cost=8.98..1200.42 rows=133 width=20)"
"  ->  Seq Scan on groups g  (cost=0.00..2.33 rows=133 width=4)"
"  ->  Result  (cost=8.98..8.99 rows=1 width=0)"
"        One-Time Filter: ($1 IS NOT NULL)"
"        InitPlan 1 (returns $1)"
"          ->  Limit  (cost=0.56..4.49 rows=1 width=8)"
"                ->  Index Only Scan using comp_2_index on counter c  (cost=0.56..1098691.21 rows=279808 width=8)"
"                      Index Cond: ((group_id = $0) AND (ts IS NOT NULL) AND (ts >= '2010-03-02 00:00:00'::timestamp without time zone) AND (ts <= '2014-03-05 12:00:00'::timestamp without time zone))"
"        InitPlan 2 (returns $2)"
"          ->  Limit  (cost=0.56..4.49 rows=1 width=8)"
"                ->  Index Only Scan Backward using comp_2_index on counter c_1  (cost=0.56..1098691.21 rows=279808 width=8)"
"                      Index Cond: ((group_id = $0) AND (ts IS NOT NULL) AND (ts >= '2010-03-02 00:00:00'::timestamp without time zone) AND (ts <= '2014-03-05 12:00:00'::timestamp without time zone))"
share|improve this question

migrated from stackoverflow.com Mar 12 at 15:21

This question came from our site for professional and enthusiast programmers.

    
I bet the cost of comparing timestamps is pretty high. Why don't you try to store the timestamp as millis (using some long int column) and change your where clause to use it instead? –  Leo Mar 12 at 14:17
    
also try creating a hash index for the primary key (default is tree) –  Leo Mar 12 at 14:21
    
Can you try this query:? SELECT group_id FROM counter AS c GROUP BY group_id HAVING EXISTS (SELECT 1 FROM counter AS cc WHERE cc.group_id = c.group_id AND cc.ts BETWEEN timestamp '2014-03-02 00:00:00.0' AND timestamp '2014-03-05 12:00:00.0') ; –  ypercube Mar 12 at 14:33
    
How many different group_id values are there on the table? –  ypercube Mar 12 at 14:43
    
There are 133 different group_id's. –  uldall Mar 12 at 14:44

3 Answers 3

up vote 5 down vote accepted

Another idea, that also uses the groups table and a construction called LATERAL join (for SQL-Server fans, this is almost identical to OUTER APPLY). It has the advantage that aggregates can be calculated in the subquery:

SELECT group_id, min_ts, max_ts
FROM   groups g,                    -- notice the comma here, is required
  LATERAL 
       ( SELECT MIN(ts) AS min_ts,
                MAX(ts) AS max_ts
         FROM counter c
         WHERE c.group_id = g.group_id
           AND c.ts BETWEEN timestamp '2011-03-02 00:00:00'
                        AND timestamp '2013-03-05 12:00:00'
       ) x 
WHERE min_ts IS NOT NULL ;

Test at SQL-Fiddle shows that the query does index scans on the (group_id, ts) index.

Similar plans are produced using 2 lateral joins, one for min and one for max and also with 2 inline correlated subqueries. They could also be used if you need to show the whole counter rows besides the min and max dates:

SELECT group_id, 
       min_ts, min_ts_id, 
       max_ts, max_ts_id 
FROM   groups g
  , LATERAL 
       ( SELECT ts AS min_ts, c.id AS min_ts_id
         FROM counter c
         WHERE c.group_id = g.group_id
           AND c.ts BETWEEN timestamp '2012-03-02 00:00:00'
                        AND timestamp '2014-03-05 12:00:00'
         ORDER BY ts ASC
         LIMIT 1
       ) xmin
  , LATERAL 
       ( SELECT ts AS max_ts, c.id AS max_ts_id
         FROM counter c
         WHERE c.group_id = g.group_id
           AND c.ts BETWEEN timestamp '2012-03-02 00:00:00'
                        AND timestamp '2014-03-05 12:00:00'
         ORDER BY ts DESC 
         LIMIT 1
       ) xmax
WHERE min_ts IS NOT NULL ;
share|improve this answer
    
+1 Interesting use of LATERAL. Should be noted that this addresses the later comments of the OP. The question did not mention additional aggregates. –  Erwin Brandstetter Mar 14 at 2:14
    
@ypercube I added the query plan for your query to the original question. The query runs in under 50 ms even on large time spans. –  uldall Mar 14 at 10:24
    
Is there an easy way in which I could retrieve the corresponding counter id of the MIN and the MAX ? –  uldall Mar 17 at 17:07
    
You mean the counter.id with the min and max date? –  ypercube Mar 17 at 17:20
1  
@uldall: You have gradually changed the original question into something rather different. It's generally better to start a new question for a different question. You can always add a link to this one for reference ... –  Erwin Brandstetter Mar 17 at 17:37

Since you have no aggregate in the select list, the the group by is pretty much the same as putting a distinct in the select list, right?

If that is what you want, you might be able to get a fast index lookup on comp_2_index by rewriting this to use a recursive query, as described on the PostgreSQL wiki.

Make a view to efficiently return the distinct group_ids:

create or replace view groups as
WITH RECURSIVE t AS (
             SELECT min(counter.group_id) AS group_id
               FROM counter
    UNION ALL
             SELECT ( SELECT min(counter.group_id) AS min
                       FROM counter
                      WHERE counter.group_id > t.group_id) AS min
               FROM t
              WHERE t.group_id IS NOT NULL
    )
     SELECT t.group_id
       FROM t
      WHERE t.group_id IS NOT NULL
UNION ALL
     SELECT NULL::bigint AS col
      WHERE (EXISTS ( SELECT counter.id,
                counter.ts,
                counter.group_id
               FROM counter
              WHERE counter.group_id IS NULL));

And then use that view in place of the lookup table in Erwin's exists semi-join.

share|improve this answer
1  
+1 This is a clever way to make the query planner use an index with a DISTINCT query when the list of possible values for group_id is unknown. –  Erwin Brandstetter Mar 12 at 22:06

Since there are only 133 different group_id's, you could use integer (or even smallint) for the group_id. It won't buy you much, though, because padding to 8 bytes will eat the rest in your table and possible multicolumn indexes. Processing of plain integer should be a bit faster, though. More on int vs. int2.

CREATE TABLE counter (
    id bigserial PRIMARY KEY
  , ts timestamp NOT NULL
  , group_id int NOT NULL
);

@Leo: timestamps are stored as 8-byte integers in modern installations and can be processed perfectly fast. Details.

@ypercube: The index on (group_id, ts) can't help, since there is no condition on group_id in the query.

Your main problem is the massive amount of data that has to be processed:

Index Scan using ts_index on counter (cost=0.56..467470.93 rows=194892 width=4)

I see you are only interested in existence of a group_id, and no actual count. Also, there are only 133 different group_ids. Therefore your query can be satisfied with the first hit per gorup_id in the time frame. Hence this suggestion for an alternative query with an EXISTS semi-join:

Assuming a lookup table for groups:

SELECT group_id
FROM   groups g
WHERE  EXISTS (
   SELECT 1
   FROM   counter c
   WHERE  c.group_id = g.group_id
   AND    ts BETWEEN timestamp '2014-03-02 00:00:00'
                 AND timestamp '2014-03-05 12:00:00'
   );

Your index comp_2_index on (group_id, ts) becomes instrumental now.

SQL Fiddle (building on the fiddle supplied by @ypercube in the comments)

Here, the query prefers the index on (ts, group_id), but I think that's because of the test setup with "clustered" timestamps. If you remove the indexes with leading ts (more about that), the planner will happily use the index on (group_id, ts) as well - notably in an Index Only Scan.

If that works, you might not need this other possible improvement: Pre-aggregate data in a materialized view to drastically reduce the number of rows. This would make sense in particular, if you also need actual counts additionally. Then you have the cost to process many rows once when updating the mv. You could even combine daily and hourly aggregates (two separate tables) and adapt your query to that.

Are time frames in your queries arbitrary? Or mostly on full minutes / hours / days?

CREATE MATERIALIZED VIEW counter_mv AS
SELECT date_trunc('hour', ts) AS hour
     , group_id
     , count(*) AS ct
GROUP BY 1,2
ORDER BY 1,2;

Create the necessary index(es) on counter_mv and adapt your query to work with it ...

share|improve this answer
1  
I tried several similar things in SQL-Fiddle, with 10k rows, but all showed some sequential scan. Does using the groups table make the difference? –  ypercube Mar 12 at 18:27
    
@ypercube: I think so. Also, ANALYZE makes a difference. But indexes on counter even get used without ANALYZE as soon as I introduce the groups table. Point is, without that table, a seqscan is needed anyway to build the set of possible group_id´s. I added more to my answer. And thanks for your fiddle! –  Erwin Brandstetter Mar 12 at 18:48
    
That's odd. You saying that Postgres' optimizer won't use the index on group_id even for a SELECT DISTINCT group_id FROM t; query? –  ypercube Mar 12 at 18:51
1  
@ErwinBrandstetter That is what I thought as well, and was very surprised to find out otherwise. Without a LIMIT 1, it can choose a bitmap index scan, which does not benefit from early stopping and takes a lot longer. (But if the table is freshly vacuumed, it might prefer the indexonly scan over the bitmap scan, so which behavior you see depends on the vacuum status of the table). –  jjanes Mar 12 at 22:50
1  
@uldall: Daily aggregates will drastically reduce the number of rows. That should do the trick. But be sure to give the EXISTS-query a try. It might be surprisingly fast. Won't work for min / max additionally. I would be interested in the resulting performance, though, if you'd be so kind as to drop a line here. –  Erwin Brandstetter Mar 13 at 9:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.