Best indexing strategy for spatial join and ranged lookup

Question

Context

We have two tables (not the real tables used in the examples below. They are from a toy DB im using for testing):

• Incidents_2 (Columns of interest are a geom, and a reported_at (int8))
• tmp_points (Columns of interest are a geom, timeframe integer representing days, radius integer in meters)

Each row in the tmp_points table has a location and we are looking for incidents near it, within a timeframe. Each could have a different radius and timeframe.

For my dummy data I have 350000 incidents, and 1500 tmp_points.

I have a gist index on both area columns, and a btree on incidents_2.reported_at.

The incidents table contains 6 years of data. The tmp_points maximum timeframe is 30 days.

The first query was returning in around 6 seconds on a cold run, and 600ms ish for subsequent. I tried partitioning the incidents table in two partitions. One that would cover the effective range of the query, and one for the rest. This was partitioned on reported_at.

The first query still scan BOTH partitions. The second query scans only the smaller partition for most recent incidents.

explain analyze 
select to_timestamp(i.reported_at), i.id, i.description, i.area, tp.point, tp."name", tp.radius 
from incidents_2 i
join tmp_points tp
on to_timestamp(i.reported_at) >= now() - (tp.days*2 || 'days')::interval
and ST_Dwithin(i.area, tp.point, tp.radius)


explain analyze 
select reported_at, i.id, i.description, i.area, tp.point, tp."name", tp.radius 
from incidents_2 i
join tmp_points tp
    on i.reported_at > 1583586702
    and ST_Dwithin(i.area, tp.point, tp.radius )

Problem

Whilst I am aware that the second query is taking a fixed figure so the planner knows it can knock out a partition, the first query which is actually what I need is not.

Ive tried a few ways of rewriting this but cant think of a way of getting the same result but accessing only one partition. Other than accessing the partition directly.

QUERY PLAN                                                                                                                                                                                                                                                     |
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
Nested Loop  (cost=0.41..185299.97 rows=51 width=319) (actual time=102.313..662.713 rows=2 loops=1)                                                                                                                                                            |
  ->  Seq Scan on tmp_points tp  (cost=0.00..28.33 rows=1333 width=61) (actual time=0.008..0.259 rows=1333 loops=1)                                                                                                                                            |
  ->  Append  (cost=0.41..138.97 rows=2 width=262) (actual time=0.497..0.497 rows=0 loops=1333)                                                                                                                                                                |
        ->  Index Scan using incidents2_old_area_idx on incidents2_old i  (cost=0.41..137.65 rows=1 width=262) (actual time=0.479..0.479 rows=0 loops=1333)                                                                                                    |
              Index Cond: (area && _st_expand((tp.point)::geography, (tp.radius)::double precision))                                                                                                                                                           |
              Filter: ((to_timestamp((reported_at)::double precision) >= (now() - ((((tp.days * 2))::text || 'days'::text))::interval)) AND ((tp.point)::geography && _st_expand(area, (tp.radius)::double precision)) AND _st_dwithin(area, (tp.point)::geogra|
              Rows Removed by Filter: 90                                                                                                                                                                                                                       |
        ->  Index Scan using incidents2_new_area_idx on incidents2_new i_1  (cost=0.27..1.31 rows=1 width=299) (actual time=0.015..0.015 rows=0 loops=1333)                                                                                                    |
              Index Cond: (area && _st_expand((tp.point)::geography, (tp.radius)::double precision))                                                                                                                                                           |
              Filter: ((to_timestamp((reported_at)::double precision) >= (now() - ((((tp.days * 2))::text || 'days'::text))::interval)) AND ((tp.point)::geography && _st_expand(area, (tp.radius)::double precision)) AND _st_dwithin(area, (tp.point)::geogra|
              Rows Removed by Filter: 1                                                                                                                                                                                                                        |
Planning Time: 0.717 ms                                                                                                                                                                                                                                        |
Execution Time: 662.747 ms                                                                                                                                                                                                                                     |

My only other thought is to create a materialized view of the query and periodically refresh it. This would enable me to keep sub 50ms responses, but create stale data. I'm negotiating with the business over the freshness of the data but I'd prefer to do this at query time anyway if possible!

UPDATE 16/05 Based on some feedback I have tidied this up a little.

PG Version: 11.2.

Incidents Table

CREATE TABLE public.incidents_tz (
    id varchar(255) NOT NULL,
    description text NOT NULL,
    area geography NULL,
    reported_at_tz timestamptz NOT NULL,
    CONSTRAINT incidents_tz_pkey PRIMARY KEY (reported_at_tz, id)
)
PARTITION BY RANGE (reported_at_tz);
CREATE INDEX incidents_tz_area_gist_index ON ONLY public.incidents_tz USING gist (area);
CREATE INDEX incidentstz_started_at_index ON ONLY public.incidents_tz USING btree (reported_at_tz);

Tmp points table

CREATE TABLE public.tmp_points (
    point geometry NULL,
    "name" varchar NULL,
    radius int4 NULL,
    days int4 NULL
);
CREATE INDEX tmp_points_st_expand_idx ON public.tmp_points USING gist (st_expand(point, (radius)::double precision));

I am now using the example given in the first answer:

explain analyze
SELECT i.reported_at_tz, i.id, i.description, i.area, tp.point, tp."name", tp.radius, tp.days 
FROM   incidents_tz i
JOIN   tmp_points  tp 
 ON i.reported_at_tz >= now() - interval '1 day' * tp.days  -- 1 day?
 AND ST_Dwithin(i.area, tp.point, tp.radius)

Which still unfortunately results in the plan (which is using both partitions):

UERY PLAN                                                                                                                                                                                                                                                     |
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
ested Loop  (cost=0.41..57673.48 rows=22 width=298) (actual time=0.241..178.554 rows=6111 loops=1)                                                                                                                                                            |
 ->  Seq Scan on tmp_points tp  (cost=0.00..27.79 rows=1279 width=61) (actual time=0.007..0.159 rows=1279 loops=1)                                                                                                                                            |
 ->  Append  (cost=0.41..45.05 rows=2 width=238) (actual time=0.094..0.138 rows=5 loops=1279)                                                                                                                                                                 |
       ->  Index Scan using incidents_tz_old_area_idx on incidents_tz_old i  (cost=0.41..39.30 rows=1 width=245) (never executed)                                                                                                                             |
             Index Cond: (area && _st_expand((tp.point)::geography, (tp.radius)::double precision))                                                                                                                                                           |
             Filter: ((reported_at_tz >= (now() - ('1 day'::interval * (tp.days)::double precision))) AND ((tp.point)::geography && _st_expand(area, (tp.radius)::double precision)) AND _st_dwithin(area, (tp.point)::geography, (tp.radius)::double precisio|
       ->  Index Scan using incidents_tz_new_area_idx on incidents_tz_new i_1  (cost=0.41..5.74 rows=1 width=211) (actual time=0.093..0.136 rows=5 loops=1279)                                                                                                |
             Index Cond: (area && _st_expand((tp.point)::geography, (tp.radius)::double precision))                                                                                                                                                           |
             Filter: ((reported_at_tz >= (now() - ('1 day'::interval * (tp.days)::double precision))) AND ((tp.point)::geography && _st_expand(area, (tp.radius)::double precision)) AND _st_dwithin(area, (tp.point)::geography, (tp.radius)::double precisio|
             Rows Removed by Filter: 12                                                                                                                                                                                                                       |
lanning Time: 0.314 ms                                                                                                                                                                                                                                        |
xecution Time: 178.857 ms                                                                                                                                                                                                                                     |

Answer 1

Why reported_at (int8)? The generally preferable implementation for timestamps is timestamptz. You save the cost and hassle to convert back and forth. And you have built-in sanity checks for the values.

Plus, it is the root of a major problem in your query:

...
join tmp_points tp
on to_timestamp(i.reported_at) >= now() - (tp.days*2 || 'days')::interval
...

This is bad for multiple reasons.

1. Replace (tp.days*2 || 'days')::interval with interval '2 days' * tp.days. That's a single multiplication instead of relatively expensive string concatenation, multiplication and type cast.

2. More importantly, move the computation away from the table column with this equivalent expression:

   ON i.reported_at >= EXTRACT (EPOCH FROM now() - interval '2 days' * tp.days)
   

   This way, the value has to be computed once before being compared to many column values. The expression is "sargable", meaning an index on reported_at can be used, and partition pruning is an option now if the partition key is based on reported_at - exactly what you seem to be looking for.

Query:

SELECT to_timestamp(i.reported_at), i.id, i.description, i.area, tp.point, tp."name", tp.radius 
FROM   incidents_2 i
JOIN   tmp_points tp ON ST_Dwithin(i.area, tp.point, tp.radius)
WHERE  i.reported_at >= EXTRACT (EPOCH FROM now() - interval '2 days' * tp.days);

I also converted to a WHERE clause since the predicate only applies to one table. That's more intuitive while being 100 % equivalent. See:

• Postgres JOIN conditions vs WHERE conditions

With incidents_2.reported_at implemented as timestamptz this could be simpler and faster, yet:

SELECT i.reported_at, i.id, i.description, i.area, tp.point, tp."name", tp.radius 
FROM   incidents_2 i
JOIN   tmp_points  tp ON ST_Dwithin(i.area, tp.point, tp.radius)
WHERE  i.reported_at >= now() - interval '1 day' * tp.days;  -- 1 day?

I also cut the interval in half. The apparent logic would be to check for events since once the number of days.

Effects of applied advice

After applying the suggested improvements, you seem unconvinced:

Which still unfortunately results in the plan (which is using both partitions):

But only the one plan for the "new" partition is actually executed. Exactly what I was aiming for:

        ->  Index Scan using incidents_tz_old_area_idx on incidents_tz_old i
            (cost=0.41..39.30 rows=1 width=245) (never executed)

Bold emphasis mine. Big quote from the manual about Partition Pruning:

Partition pruning can be performed not only during the planning of a given query, but also during its execution. This is useful as it can allow more partitions to be pruned when clauses contain expressions whose values are not known at query planning time, for example, parameters defined in a PREPARE statement, using a value obtained from a subquery, or using a parameterized value on the inner side of a nested loop join. Partition pruning during execution can be performed at any of the following times:

• During initialization of the query plan. Partition pruning can be performed here for parameter values which are known during the initialization phase of execution. Partitions which are pruned during this stage will not show up in the query's EXPLAIN or EXPLAIN ANALYZE. It is possible to determine the number of partitions which were removed during this phase by observing the “Subplans Removed” property in the EXPLAIN output.

• During actual execution of the query plan. Partition pruning may also be performed here to remove partitions using values which are only known during actual query execution. This includes values from subqueries and values from execution-time parameters such as those from parameterized nested loop joins. Since the value of these parameters may change many times during the execution of the query, partition pruning is performed whenever one of the execution parameters being used by partition pruning changes. Determining if partitions were pruned during this phase requires careful inspection of the loops property in the EXPLAIN ANALYZE output. Subplans corresponding to different partitions may have different values for it depending on how many times each of them was pruned during execution. Some may be shown as (never executed) if they were pruned every time.

Bold emphasis mine again.

Since the index is accessed in a nested loop for every (point, radius)in tmp_points (rows=1333), Postgres cannot apply partition pruning during the planning phase, but it can during the execution.

Consequently, the new query retrieved rows=6111 in 179 ms, while your old query retrieved rows=2 (!!) in 663 ms, while. That's an improvement if I have ever seen one.

Smarter index instead of separate partition?

A separate partition for the latest rows entails a lot of overhead and complications. With huge tables, declarative partitioning with more partitions might still make sense.

But consider a single table with smarter indexing. For starters, a multicolumn index like:

CREATE INDEX foo ON incidents USING gist (reported_at_tz, area);

With the typically more selective expression first. The additional module btree_gist has to be installed. See:

• Optimizing queries on a range of timestamps (two columns)
• PostgreSQL EXCLUDE USING error: Data type integer has no default operator class

Since your query exclusively targets the few latest rows, a partial index might make more sense. Unfortunately, the time frame of interest is a moving target, depending on the current time (now()). This makes optimization harder (for partitioning as well). Start with a constant cutoff time:

CREATE INDEX foo ON incidents USING gist (area, reported_at_tz)
WHERE  reported_at_tz >= '2020-05-01 00:00+0';

Adjust the cutoff time '2020-05-01 00:00+0' to what you used for the partition.

Now, area as first index expression. Depending on how selective reported_at_tz still is, you might drop it as additional index expression.

Then continue reading here:

• Row with latest timestamp