Creating Indexes to optimize query

Could it be related to stastics? Remember the same from a data warehouse job.

Table statistics were generated / refreshed not automatically but - once per night. Which can lead to exactly this behavior - first day they suck, then in the night they get refreshed and the query optimizer suddenly makes correct decisions.

Our solution was to manually regenerate statistics during the load processes.

An alternative would be locking behavior.

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 ;