Speed up PostgreSQL query with timestamp OVERLAPS and "PARTITION BY"

I ended up using PostgreSQL inheritance to solve this, so each specific_feature_timeslice table inherits from feature_timeslice (rather than referencing it, as before). This allows the "selectivity of the feature can take effect first" - the query plan starts by narrowing it down to the few rows I want. So the schema now looks like this:

CREATE TABLE feature_timeslice
(
  timeslice_id int NOT NULL,
  feature_id int NOT NULL,
  valid_time_begin timestamp NOT NULL,
  valid_time_end timestamp,
  sequence_number smallint,
  -- Some other columns
  CONSTRAINT pk_feature_timeslice PRIMARY KEY (timeslice_id)
  -- Some other constraints
)

CREATE TABLE specific_feature_timeslice
(
  -- Feature-specific columns only, eg.
  name character varying(100),

  CONSTRAINT pk_specific_feature_timeslice PRIMARY KEY (timeslice_id)
)
INHERITS (feature_timeslice);

CREATE INDEX ix_specific_feature_timeslice_feature_id
ON specific_feature_timeslice (feature_id);

Each such derived table has its own function to select the row current at the specified time:

CREATE FUNCTION specific_feature_asof(effective_time timestamp)
RETURNS SETOF specific_feature_timeslice
AS $BODY$
    SELECT candidate.*
    FROM specific_feature_timeslice candidate
    WHERE ($1, '0'::interval) OVERLAPS (candidate.valid_time_begin, COALESCE(candidate.valid_time_end, 'infinity'::timestamp))
        AND NOT EXISTS
        (
            SELECT *
            FROM specific_feature_timeslice better
            WHERE ($1, '0'::interval) OVERLAPS (better.valid_time_begin, COALESCE(better.valid_time_end, 'infinity'::timestamp))
                AND better.feature_id = candidate.feature_id AND better.timeslice_id != candidate.timeslice_id AND better.sequence_number > candidate.sequence_number
        )
$BODY$ LANGUAGE SQL STABLE;

I auto-generate these functions, of course - they are the same except for the table name. The typical query then becomes:

SELECT *
FROM specific_feature_asof('2011-09-30')
WHERE name = 'SOMETHING'

and the query plan looks like this:

Nested Loop Anti Join  (cost=0.00..412.84 rows=3 width=177) (actual time=0.044..7.038 rows=10 loops=1)
  Join Filter: (((better.timeslice_id)::integer <> (candidate.timeslice_id)::integer) AND ((better.sequence_number)::smallint > (candidate.sequence_number)::smallint))
  ->  Seq Scan on specific_feature_timeslice candidate  (cost=0.00..379.66 rows=3 width=177) (actual time=0.018..6.688 rows=10 loops=1)
        Filter: (((name)::text = 'SOMETHING'::text) AND overlaps(('2011-09-30 00:00:00'::timestamp without time zone)::timestamp without time zone, (('2011-09-30 00:00:00'::timestamp without time zone)::timestamp without time zone + '00:00:00'::interval), (valid_time_begin)::timestamp without time zone, COALESCE((valid_time_end)::timestamp without time zone, 'infinity'::timestamp without time zone)))
  ->  Index Scan using ix_specific_feature_timeslice_feature_id on specific_feature_timeslice better  (cost=0.00..8.28 rows=1 width=14) (actual time=0.008..0.011 rows=1 loops=10)
        Index Cond: ((feature_id)::integer = (candidate.feature_id)::integer)
        Filter: overlaps(('2011-09-30 00:00:00'::timestamp without time zone)::timestamp without time zone, (('2011-09-30 00:00:00'::timestamp without time zone)::timestamp without time zone + '00:00:00'::interval), (valid_time_begin)::timestamp without time zone, COALESCE((valid_time_end)::timestamp without time zone, 'infinity'::timestamp without time zone))
Total runtime: 7.150 ms

The performance difference is pretty dramatic: a simple select like the query above takes 30-60 ms. Joining two such functions takes it up to 300-400 ms, which is a bit more than I'd expect, but still quite acceptable.

With these changes I think it's no longer necessary to normalise feature_timeslice, ie. extract the valid begin/end time into a separate table, so I haven't done this.

First normalize your entities. Your setup might look like this:

CREATE TABLE feature
( feature_id int primary key,
  name text
  -- Some other columns
);

CREATE TABLE timeslice
( timeslice_id int primary key,
  valid_begin timestamp NOT NULL,
  valid_end timestamp
  -- Some other columns?
);

CREATE TABLE feature_timeslice
( feature_id int references feature (feature_id),
  timeslice_id int references timeslice (timeslice_id),
  sequence_number smallint,             -- guess it should live here?
  -- Some other columns?
  CONSTRAINT pk_feature_timeslice PRIMARY KEY (feature_id, timeslice_id)
);

Then, try combining the two SELECTs in one. Thereby the selectivity of the feature can take effect first. IOW, get rid of the view!

SELECT DISTINCT ON (1) ft.feature_id, first_value(ft.timeslice_id) OVER (PARTITION BY ft.feature_id ORDER BY ft.sequence_number DESC, ft.timeslice_id DESC) AS timeslice_id 
  FROM feature f
  JOIN feature_timeslice ft USING (feature_id)
  JOIN timeslice t USING (timeslice_id)
 WHERE f.name = 'SOMETHING'
AND t.valid_begin <= now()::timestamp
AND (t.valid_end >= now()::timestamp OR t.valid_end IS NULL);

If the feature is as selective as you implied (max. 10 timeslices per feature), then there is not much use for indexes on valid_begin or sequence_number.
Index on feature.name might help, though!
The most prominent feature here is to combine DISTINCT with a WINDOW function.

You have a normalisation problem.

• timeslice_id is a surrogate key.
• (feature_id, sequence_number} are a candidate key
• (feature_id, valid_time_begin ( valid_time_end) ) is also a candidate key.

You are misusing the windowing function, just to pick the candidate with rank=1. A self-join is probably cheaper.

EDIT:

CREATE index feature_timeslice_alt2 ON feature_timeslice
  ( feature_id,valid_time_begin);
CREATE UNIQUE index feature_timeslice_alt ON feature_timeslice
  ( feature_id,sequence_number);


CREATE VIEW feature_timeslice_id_encore AS
   SELECT timeslice_id FROM feature_timeslice t0
   WHERE (current_timestamp AT TIME ZONE 'UTC', '0'::interval)
          OVERLAPS (t0.valid_time_begin, COALESCE(t0.valid_time_end, 'infinity'::timestamp))
   AND NOT EXISTS ( 
      SELECT timeslice_id FROM feature_timeslice t1
      WHERE (current_timestamp AT TIME ZONE 'UTC', '0'::interval)
             OVERLAPS (t1.valid_time_begin, COALESCE(t1.valid_time_end, 'infinity'::timestamp))
      -- EDIT: forgot this
      AND t1.feature_id = t0.feature_id
      AND t1.sequence_number < t0.sequence_number
  );      

EDIT: the resulting query plan:

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Hash Anti Join  (cost=9090.62..18428.34 rows=45971 width=4) (actual time=110.053..222.897 rows=9030 loops=1)
   Hash Cond: (t0.feature_id = t1.feature_id)
   Join Filter: (t1.sequence_number < t0.sequence_number)
   ->  Seq Scan on feature_timeslice t0  (cost=0.00..8228.67 rows=68956 width=12) (actual time=0.031..106.646 rows=9030 loops=1)
         Filter: "overlaps"(timezone('UTC'::text, now()), (timezone('UTC'::text, now()) + '00:00:00'::interval), valid_time_begin, COALESCE(valid_time_end, 'infinity'::timestamp without time zone))
   ->  Hash  (cost=8228.67..8228.67 rows=68956 width=8) (actual time=109.979..109.979 rows=9030 loops=1)
         Buckets: 8192  Batches: 1  Memory Usage: 353kB
         ->  Seq Scan on feature_timeslice t1  (cost=0.00..8228.67 rows=68956 width=8) (actual time=0.016..106.995 rows=9030 loops=1)
               Filter: "overlaps"(timezone('UTC'::text, now()), (timezone('UTC'::text, now()) + '00:00:00'::interval), valid_time_begin, COALESCE(valid_time_end, 'infinity'::timestamp without time zone))
 Total runtime: 223.488 ms

The query plan for the OP query was similar to his's, and had a "Total runtime: 1404.092 ms ". (but it will probably scale worse, cause of the sort step)