pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
Proximity query with GIST and row estimation
5+ messages / 2 participants
[nested] [flat]

* Proximity query with GIST and row estimation
@ 2007-02-13 17:09  Guillaume Smet <guillaume.smet@gmail.com>
  0 siblings, 1 reply; 5+ messages in thread

From: Guillaume Smet @ 2007-02-13 17:09 UTC (permalink / raw)
  To: pgsql-performance

Hi all,

Following the work on Mark Stosberg on this list (thanks Mark!), I
optimized our slow proximity queries by using cube, earthdistance
(shipped with contrib) and a gist index. The result is globally very
interesting apart for a specific query and we'd like to be able to fix
it too to be more consistent (it's currently faster with a basic
distance calculation based on acos, cos and so on but it's slow
anyway).

The problem is that we have sometimes very few places near a given
location (small city) and sometimes a lot of them (in Paris, Bruxelles
and so on - it's the case we have here). The gist index I created
doesn't estimate the number of rows in the area very well.

Table: lieu (100k rows) with wgslat and wgslon as numeric
Table: lieugelieu (200k rows, 1k with codegelieu = 'PKG')
Index: "idx_lieu_earth" gist (ll_to_earth(wgslat::double precision,
wgslon::double precision))

The simplified query is:
SELECT DISTINCT l.numlieu, l.nomlieu, ROUND
(earth_distance(ll_to_earth(48.85957600, 2.34860800),
ll_to_earth(l.wgslat, l.wgslon))) as dist
	FROM lieu l, lieugelieu lgl
	WHERE lgl.codegelieu = 'PKG' AND earth_box(ll_to_earth(48.85957600,
2.34860800), 1750) @ ll_to_earth(l.wgslat, l.wgslon) AND lgl.numlieu =
l.numlieu ORDER BY dist ASC LIMIT 2;
It's used to find the nearest car parks from a given location.

The plan is attached plan_earthdistance_nestedloop.txt. It uses a
nested loop because the row estimate is pretty bad: (cost=0.00..3.38
rows=106 width=0) (actual time=30.229..30.229 rows=5864 loops=1).

If I disable the nested loop, the plan is different and faster (see
plan_earthdistance_hash.txt attached).

Is there any way to improve this estimation? I tried to set the
statistics of wgslat and wgslon higher but it doesn't change anything
(I don't know if the operator is designed to use the statistics).

Any other idea to optimize this query is very welcome too.

--
Guillaume

Attachments:

plan_earthdistance_nestedloop.txt (text/plain, 2.5K) download db=# explain analyze SELECT DISTINCT l.numlieu, l.nomlieu, ROUND (earth_distance(ll_to_earth(48.85957600, 2.34860800), ll_to_earth(l.wgslat, l.wgslon))) as dist db-# FROM lieu l, lieugelieu lgl db-# WHERE lgl.codegelieu = 'PKG' AND earth_box(ll_to_earth(48.85957600, 2.34860800), 1750) @ ll_to_earth(l.wgslat, l.wgslon) AND lgl.numlieu = l.numlieu ORDER BY dist ASC LIMIT 2; QUERY PLAN --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=626.84..626.85 rows=1 width=51) (actual time=449.287..449.298 rows=2 loops=1) -> Unique (cost=626.84..626.85 rows=1 width=51) (actual time=449.283..449.290 rows=2 loops=1) -> Sort (cost=626.84..626.84 rows=1 width=51) (actual time=449.278..449.279 rows=2 loops=1) Sort Key: round(sec_to_gc(cube_distance('(4192714.86111655, 171959.656483755, 4803394.52951123)'::cube, (ll_to_earth((l.wgslat)::double precision, (l.wgslon)::double precision))::cube))), l.numlieu, l.nomlieu -> Nested Loop (cost=3.38..626.83 rows=1 width=51) (actual time=258.877..448.651 rows=78 loops=1) -> Bitmap Heap Scan on lieu l (cost=3.38..201.34 rows=106 width=51) (actual time=32.988..60.197 rows=5786 loops=1) Recheck Cond: ('(4190964.86112204, 170209.656489245, 4801644.52951672),(4194464.86111106, 173709.656478266, 4805144.52950574)'::cube @ (ll_to_earth((wgslat)::double precision, (wgslon)::double precision))::cube) -> Bitmap Index Scan on idx_lieu_earth (cost=0.00..3.38 rows=106 width=0) (actual time=30.229..30.229 rows=5864 loops=1) Index Cond: ('(4190964.86112204, 170209.656489245, 4801644.52951672),(4194464.86111106, 173709.656478266, 4805144.52950574)'::cube @ (ll_to_earth((wgslat)::double precision, (wgslon)::double precision))::cube) -> Index Scan using idx_lieugelieu_codegelieu_numlieu_principal on lieugelieu lgl (cost=0.00..4.00 rows=1 width=4) (actual time=0.052..0.052 rows=0 loops=5786) Index Cond: (((lgl.codegelieu)::text = 'PKG'::text) AND (lgl.numlieu = "outer".numlieu)) Total runtime: 449.607 ms (12 rows)
plan_earthdistance_hash.txt (text/plain, 2.9K) download db=# explain analyze SELECT DISTINCT l.numlieu, l.nomlieu, ROUND (earth_distance(ll_to_earth(48.85957600, 2.34860800), ll_to_earth(l.wgslat, l.wgslon))) as dist db-# FROM lieu l, lieugelieu lgl db-# WHERE lgl.codegelieu = 'PKG' AND earth_box(ll_to_earth(48.85957600, 2.34860800), 1750) @ ll_to_earth(l.wgslat, l.wgslon) AND lgl.numlieu = l.numlieu ORDER BY dist ASC LIMIT 2; QUERY PLAN --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=787.07..787.09 rows=1 width=51) (actual time=168.623..168.635 rows=2 loops=1) -> Unique (cost=787.07..787.09 rows=1 width=51) (actual time=168.619..168.627 rows=2 loops=1) -> Sort (cost=787.07..787.08 rows=1 width=51) (actual time=168.614..168.615 rows=2 loops=1) Sort Key: round(sec_to_gc(cube_distance('(4192714.86111655, 171959.656483755, 4803394.52951123)'::cube, (ll_to_earth((l.wgslat)::double precision, (l.wgslon)::double precision))::cube))), l.numlieu, l.nomlieu -> Hash Join (cost=206.13..787.06 rows=1 width=51) (actual time=102.005..167.992 rows=78 loops=1) Hash Cond: ("outer".numlieu = "inner".numlieu) -> Bitmap Heap Scan on lieugelieu lgl (cost=4.52..583.26 rows=435 width=4) (actual time=1.137..3.909 rows=1095 loops=1) Recheck Cond: ((codegelieu)::text = 'PKG'::text) -> Bitmap Index Scan on idx_lieugelieu_codegelieu_numlieu_principal (cost=0.00..4.52 rows=435 width=0) (actual time=1.030..1.030 rows=1095 loops=1) Index Cond: ((codegelieu)::text = 'PKG'::text) -> Hash (cost=201.34..201.34 rows=106 width=51) (actual time=97.807..97.807 rows=5786 loops=1) -> Bitmap Heap Scan on lieu l (cost=3.38..201.34 rows=106 width=51) (actual time=32.921..76.736 rows=5786 loops=1) Recheck Cond: ('(4190964.86112204, 170209.656489245, 4801644.52951672),(4194464.86111106, 173709.656478266, 4805144.52950574)'::cube @ (ll_to_earth((wgslat)::double precision, (wgslon)::double precision))::cube) -> Bitmap Index Scan on idx_lieu_earth (cost=0.00..3.38 rows=106 width=0) (actual time=30.144..30.144 rows=5864 loops=1) Index Cond: ('(4190964.86112204, 170209.656489245, 4801644.52951672),(4194464.86111106, 173709.656478266, 4805144.52950574)'::cube @ (ll_to_earth((wgslat)::double precision, (wgslon)::double precision))::cube) Total runtime: 169.140 ms (16 rows)
^ permalink raw reply [nested|flat] 5+ messages in thread

* Re: Proximity query with GIST and row estimation
@ 2007-02-14 03:01  Paul Ramsey <pramsey@refractions.net>
  parent: Guillaume Smet <guillaume.smet@gmail.com>
  0 siblings, 2 replies; 5+ messages in thread

From: Paul Ramsey @ 2007-02-14 03:01 UTC (permalink / raw)
  To: Guillaume Smet <guillaume.smet@gmail.com>; +Cc: pgsql-performance

You'll find that PostGIS does a pretty good job of selectivity  
estimation.

P

On 13-Feb-07, at 9:09 AM, Guillaume Smet wrote:

> Hi all,
>
> Following the work on Mark Stosberg on this list (thanks Mark!), I
> optimized our slow proximity queries by using cube, earthdistance
> (shipped with contrib) and a gist index. The result is globally very
> interesting apart for a specific query and we'd like to be able to fix
> it too to be more consistent (it's currently faster with a basic
> distance calculation based on acos, cos and so on but it's slow
> anyway).
>
> The problem is that we have sometimes very few places near a given
> location (small city) and sometimes a lot of them (in Paris, Bruxelles
> and so on - it's the case we have here). The gist index I created
> doesn't estimate the number of rows in the area very well.
>
> Table: lieu (100k rows) with wgslat and wgslon as numeric
> Table: lieugelieu (200k rows, 1k with codegelieu = 'PKG')
> Index: "idx_lieu_earth" gist (ll_to_earth(wgslat::double precision,
> wgslon::double precision))
>
> The simplified query is:
> SELECT DISTINCT l.numlieu, l.nomlieu, ROUND
> (earth_distance(ll_to_earth(48.85957600, 2.34860800),
> ll_to_earth(l.wgslat, l.wgslon))) as dist
> 	FROM lieu l, lieugelieu lgl
> 	WHERE lgl.codegelieu = 'PKG' AND earth_box(ll_to_earth(48.85957600,
> 2.34860800), 1750) @ ll_to_earth(l.wgslat, l.wgslon) AND lgl.numlieu =
> l.numlieu ORDER BY dist ASC LIMIT 2;
> It's used to find the nearest car parks from a given location.
>
> The plan is attached plan_earthdistance_nestedloop.txt. It uses a
> nested loop because the row estimate is pretty bad: (cost=0.00..3.38
> rows=106 width=0) (actual time=30.229..30.229 rows=5864 loops=1).
>
> If I disable the nested loop, the plan is different and faster (see
> plan_earthdistance_hash.txt attached).
>
> Is there any way to improve this estimation? I tried to set the
> statistics of wgslat and wgslon higher but it doesn't change anything
> (I don't know if the operator is designed to use the statistics).
>
> Any other idea to optimize this query is very welcome too.
>
> --
> Guillaume
> <plan_earthdistance_nestedloop.txt>
> <plan_earthdistance_hash.txt>
>
> ---------------------------(end of  
> broadcast)---------------------------
> TIP 6: explain analyze is your friend




^ permalink  raw  reply  [nested|flat] 5+ messages in thread

* Re: Proximity query with GIST and row estimation
@ 2007-02-14 18:12  Guillaume Smet <guillaume.smet@gmail.com>
  parent: Paul Ramsey <pramsey@refractions.net>
  1 sibling, 0 replies; 5+ messages in thread

From: Guillaume Smet @ 2007-02-14 18:12 UTC (permalink / raw)
  To: Paul Ramsey <pramsey@refractions.net>; +Cc: pgsql-performance

Paul,

On 2/14/07, Paul Ramsey <pramsey@refractions.net> wrote:
> You'll find that PostGIS does a pretty good job of selectivity
> estimation.

PostGIS is probably what I'm going to experiment in the future. The
only problem is that it's really big for a very basic need.
With my current method, I don't even have to create a new column: I
create directly a functional index so it's really easy to use.
Using PostGIS requires to create a new column and triggers to maintain
it and install PostGIS of course. That's why it was not my first
choice.

Thanks for your answer.

--
Guillaume



^ permalink  raw  reply  [nested|flat] 5+ messages in thread

* Re: Proximity query with GIST and row estimation
@ 2007-02-15 16:13  Guillaume Smet <guillaume.smet@gmail.com>
  parent: Paul Ramsey <pramsey@refractions.net>
  1 sibling, 1 reply; 5+ messages in thread

From: Guillaume Smet @ 2007-02-15 16:13 UTC (permalink / raw)
  To: Paul Ramsey <pramsey@refractions.net>; +Cc: pgsql-performance

On 2/14/07, Paul Ramsey <pramsey@refractions.net> wrote:
> You'll find that PostGIS does a pretty good job of selectivity
> estimation.

So I finally have a working PostGIS and I fixed the query to use PostGIS.

The use of PostGIS is slower than the previous cube/earthdistance
approach (on a similar query and plan). But you're right, it does a
pretty good job to calculate the selectivity and the estimations are
really good.
It helps to select a good plan (or a bad one if the previous false
numbers led to a better plan which is my case for certain queries).
I suppose it's normal to be slower as it's more precise. I don't know
which approach is better in my case as I don't need the precision of
PostGIS.

For the record, here is what I did:
select AddGeometryColumn('lieu','earthpoint',32631,'POINT',2);
update lieu set earthpoint=Transform(SetSRID(MakePoint(wgslon,
wgslat), 4327), 32631);
create index idx_lieu_earthpoint on lieu using gist(earthpoint
gist_geometry_ops);

analyze lieu;

select numlieu, nomlieu, wgslon, wgslat, astext(earthpoint) from lieu
where earthpoint && Expand(Transform(SetSRID(MakePoint(12.49244400,
41.89103400), 4326), 32631), 3000);

(3000 is the distance in meters)

--
Guillaume



^ permalink  raw  reply  [nested|flat] 5+ messages in thread

* Re: Proximity query with GIST and row estimation
@ 2007-02-16 18:31  Guillaume Smet <guillaume.smet@gmail.com>
  parent: Guillaume Smet <guillaume.smet@gmail.com>
  0 siblings, 0 replies; 5+ messages in thread

From: Guillaume Smet @ 2007-02-16 18:31 UTC (permalink / raw)
  To: Paul Ramsey <pramsey@refractions.net>; +Cc: pgsql-performance

On 2/15/07, Guillaume Smet <guillaume.smet@gmail.com> wrote:
> The use of PostGIS is slower than the previous cube/earthdistance
> approach (on a similar query and plan).

For the record, here are new information about my proximity query work.

Thanks to Tom Lane, I found the reason of the performance drop. The
problem is that the gist index for operator && is lossy (declared as
RECHECK in the op class).
AFAICS, for the && operator it's done to prevent problems when SRIDs
are not compatible: it forces the execution of the filter and so even
with a "should be non lossy" bitmap index scan, it throws an error as
if we use a seqscan (Paul, correct me if I'm wrong) because it forces
the execution of the filter.

As I'm sure I won't have this problem (I will write a wrapper stored
procedure so that the end users won't see the SRID used), I created a
different opclass without the RECHECK clause:
CREATE OPERATOR CLASS gist_geometry_ops_norecheck FOR TYPE geometry
USING gist AS
        OPERATOR        3        &&,
        FUNCTION        1        LWGEOM_gist_consistent (internal,
geometry, int4),
        FUNCTION        2        LWGEOM_gist_union (bytea, internal),
        FUNCTION        3        LWGEOM_gist_compress (internal),
        FUNCTION        4        LWGEOM_gist_decompress (internal),
        FUNCTION        5        LWGEOM_gist_penalty (internal,
internal, internal),
        FUNCTION        6        LWGEOM_gist_picksplit (internal, internal),
        FUNCTION        7        LWGEOM_gist_same (box2d, box2d, internal);

UPDATE pg_opclass
	SET opckeytype = (SELECT oid FROM pg_type
                          WHERE typname = 'box2d'
                          AND typnamespace = (SELECT oid FROM pg_namespace
                                              WHERE nspname=current_schema()))
	WHERE opcname = 'gist_geometry_ops_norecheck'
        AND opcnamespace = (SELECT oid from pg_namespace
                            WHERE nspname=current_schema());

As I use only the && operator, I put only this one.

And I recreated my index using:
CREATE INDEX idx_lieu_earthpoint ON lieu USING gist(earthpoint
gist_geometry_ops_norecheck);

In the case presented before, the bitmap index scan is then non lossy
and I have similar performances than with earthdistance method.

--
Guillaume



^ permalink  raw  reply  [nested|flat] 5+ messages in thread


end of thread, other threads:[~2007-02-16 18:31 UTC | newest]

Thread overview: 5+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2007-02-13 17:09 Proximity query with GIST and row estimation Guillaume Smet <guillaume.smet@gmail.com>
2007-02-14 03:01 ` Paul Ramsey <pramsey@refractions.net>
2007-02-14 18:12   ` Guillaume Smet <guillaume.smet@gmail.com>
2007-02-15 16:13   ` Guillaume Smet <guillaume.smet@gmail.com>
2007-02-16 18:31     ` Guillaume Smet <guillaume.smet@gmail.com>

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox