Обсуждение: Proximity query with GIST and row estimation

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

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

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

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

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