Q:

PostgreSQL timestamps - indexing

I am running a query where I look for a record, and another record a certain amount of time later.
Table definition:
(
  id integer primary key,
  gpsstatus character(2),
  datetime timestamp without time zone,
  lat numeric(9,6),
  lon numeric(9,6),
  alt numeric(9,4),
  time integer,
  datafileid integer,
  shape geometry,
  speed double precision,
  dist double precision,
  shape_utm geometry,
  lokalitet character(128),
  cowid integer
)

There are indexes on datetime,lokalitet,cowid,gpsstatus, gist-index on shape and shape_utm. 
The points should be sampled every 5th seconds, so I tried to do
select <something more>,p1.timestamp 
from table p1, table p2 
where p1.timestamp + interval '5 secound' = p2.timestamp

That ran reasonably quick, but then I found out that I had lost quite a few points due to jitter in the sampling, so that the points may be from 4 to 6 seconds apart.
Then I tried:
where    (p2.timestamp, interval'0 second')
overlaps (p1.timestamp + interval '4 second', interval '2 second')

and that took for ages. I also tried the simpler solution:
WHERE p1.timestamp + interval '4 second' <= p2.timestamp
AND   p1.timestamp + interval '6 second' >= p2.timestamp

which also ended up being unusably slow.
The timestamp field has a normal index. Is there a special kind of index are something else that would make this query usable?
The query at the moment:
SELECT
    p1.cowid,
    p1.datetime,
    st_distance(p1.shape_utm, lead(p1.shape_utm)
      OVER (ORDER BY p1.datetime)) AS meters_obs,
    st_distance(p1.shape_utm, lead(p1.shape_utm, 720)
      OVER (ORDER BY p1.datetime)) AS meters_hour,
    observation.observation
  FROM (gpspoint p1 LEFT JOIN observation
                           ON (observation.gpspointid = p1.id)),
       status
  WHERE p1.gpsstatus = status.id
    AND status.use = true;

I may also get an an acceptable query time by asking for some specific intervals.

A:

If you just want the previous record, you can do:
SELECT  p, LAG(p) OVER (ORDER BY timestamp) AS pp
FROM    table p
ORDER BY
        timestamp

If you need a record 4 to 6 seconds before the current, use this:
SELECT  p1.*, p2.*
FROM    table p1
LEFT JOIN
        table p2
ON      p2.timestamp BETWEEN p1.timestamp - '4 seconds'::INTERVAL
                         AND p1.timestamp - '6 seconds'::INTERVAL
ORDER BY
        p1.timestamp

This may return multiple previous records if they all are in the range.

