Re: [postgis-users] GIST index speed

classic Classic list List threaded Threaded
24 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Re: [postgis-users] GIST index speed

Paul Ramsey
Mark,

Is it possible something terrible is happening in LWGEOM_gist_consistent?

The place the slow differs from the fast is that the slow spends a
great deal of time in _memcpy, which is driven by toast fetching,
which is driven by LWGEOM_gist_consistent.

There's lots of activity in the operating system, as well, in
vm_fault, which again reflects the idea that we are doing a lot of
memory allocation.

P.

On Mon, Jun 9, 2008 at 7:48 AM, Mark Cave-Ayland
<[hidden email]> wrote:

> Paul Ramsey wrote:
>>
>> Bummer. Well if you need any other cock-eyed theories, let me know :)
>>
>> P
>
> Hi Paul,
>
> Please feel free to add more: I think it's that we're doing something
> strange with palloc/pfree/TOAST, maybe casting, or it's something in the
> PostgreSQL index AM. Do you have any success with profiling under OS X? If
> so, it would be good to get at least a working profile output of both query
> cases, so we can try and determine where the time is being swallowed during
> the index scan.
>
>
> ATB,
>
> Mark.
>
> --
> Mark Cave-Ayland
> Sirius Corporation - The Open Source Experts
> http://www.siriusit.co.uk
> T: +44 870 608 0063
> _______________________________________________
> postgis-users mailing list
> [hidden email]
> http://postgis.refractions.net/mailman/listinfo/postgis-users
>

screenshot_01.gif (139K) Download Attachment
report.txt (15K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [postgis-users] GIST index speed

Mark Cave-Ayland-4
Paul Ramsey wrote:

> Mark,
>
> Is it possible something terrible is happening in LWGEOM_gist_consistent?
>
> The place the slow differs from the fast is that the slow spends a
> great deal of time in _memcpy, which is driven by toast fetching,
> which is driven by LWGEOM_gist_consistent.
>
> There's lots of activity in the operating system, as well, in
> vm_fault, which again reflects the idea that we are doing a lot of
> memory allocation.
>
> P.

Righto. After a reasonably small thread on -hackers, we've got as far as
determining what the problem is. The issue comes with the query plan
looking like this:


postgis=# explain analyze select count(*) from geography where centroid
&& (select the_geom from geography where id=69495);

QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------
  Aggregate  (cost=7157.29..7157.30 rows=1 width=0) (actual
time=2691.783..2691.784 rows=1 loops=1)
    InitPlan
      ->  Seq Scan on geography  (cost=0.00..7149.00 rows=1 width=4559)
(actual time=60.987..61.373 rows=1 loops=1)
            Filter: (id = 69495::numeric)
    ->  Index Scan using geography_geom_centroid_idx on geography
(cost=0.00..8.28 rows=1 width=0) (actual time=79.241..2645.722
rows=32880 loops=1)
          Index Cond: (centroid && $0)
          Filter: (centroid && $0)
  Total runtime: 2692.288 ms
(8 rows)


Since the geometry which is returned as the result of a sub-select is so
large, it has been stored on disk in TOAST (compressed) format, and so
it must be decompressed before its content can be accessed. The problem
is that every time we read each one of the 32880 results from the
geography_geom_centroid_idx index scan, the large geometry is being
de-TOASTed, compared against the index, and then thrown away. Hence a
large proportion of the query is being wasted constantly de-TOASTing the
geometry from the sub-select.

If you look at the wrapper function I posted earlier in thread, it
should be reasonably apparent why everything suddenly becomes much quicker:


Datum LWGEOM_mcatest(PG_FUNCTION_ARGS);
PG_FUNCTION_INFO_V1(LWGEOM_mcatest);
Datum LWGEOM_mcatest(PG_FUNCTION_ARGS)
{
         PG_LWGEOM *pgl = (PG_LWGEOM *)
                 PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
         void *mem;

         /* Copy somewhere else */
         mem = palloc(VARSIZE(pgl));
         memcpy(mem, pgl, VARSIZE(pgl));

         PG_RETURN_POINTER(mem);
}


CREATE OR REPLACE FUNCTION mcatest(geometry)
         RETURNS geometry
         AS '$libdir/lwpostgis','LWGEOM_mcatest'
         LANGUAGE 'C';


Here we are de-TOASTING the incoming geometry once and creating a new
geometry, which will not be compressed since TOAST is only invoked
during storage. So the reason the query below is so quick is because the
mcatest() wrapper function is effectively acting as a TOAST cache.


postgis=# explain analyze select count(*) from geography where centroid
&& (select mcatest(the_geom) from geography where id=69495);

QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------
  Aggregate  (cost=7157.29..7157.30 rows=1 width=0) (actual
time=283.126..283.127 rows=1 loops=1)
    InitPlan
      ->  Seq Scan on geography  (cost=0.00..7149.00 rows=1 width=4559)
(actual time=48.712..49.040 rows=1 loops=1)
            Filter: (id = 69495::numeric)
    ->  Index Scan using geography_geom_centroid_idx on geography
(cost=0.00..8.28 rows=1 width=0) (actual time=49.321..215.524 rows=32880
loops=1)
          Index Cond: (centroid && $0)
          Filter: (centroid && $0)
  Total runtime: 283.221 ms
(8 rows)


The question is: what can we do about this, especially as this is a very
common case within PostGIS? According to the thread on -hackers, Tom
suggested it may be possible to get PostgreSQL to automatically de-TOAST
index scan keys. Unfortunately while this would solve the problem, it
requires some non-trivial development work (i.e. it isn't exactly clear
how to do it), and wouldn't help existing users.

Other than that, I think our options are limited :(  I've tried changing
all the spatial operators to work on BOX2D objects instead (hoping that
the implicit cast from geometry to box2d would kick in), but with this
in place it is then impossible to create an index since the opclass type
of box2d no longer matches the geometry type of the column.

So I'm not really sure what we can do about this... it's so frustrating
as I know people will be seeing bad performance from PostGIS in a large
number of real cases because of this, yet there doesn't seem to be a
viable solution that I can think of at the moment. Does anyone else have
any bright ideas?


ATB,

Mark.

--
Mark Cave-Ayland
Sirius Corporation - The Open Source Experts
http://www.siriusit.co.uk
T: +44 870 608 0063

Reply | Threaded
Open this post in threaded view
|

Re: [postgis-users] GIST index speed

Paul Ramsey
On Wed, Jun 11, 2008 at 8:26 AM, Mark Cave-Ayland
<[hidden email]> wrote:

> So I'm not really sure what we can do about this... it's so frustrating as I
> know people will be seeing bad performance from PostGIS in a large number of
> real cases because of this, yet there doesn't seem to be a viable solution
> that I can think of at the moment. Does anyone else have any bright ideas?

As performance problems go, it's not the worst case scenario.
Re-writing the query as a join makes it very very fast. And wrapping
it in a non-destructive function makes it acceptably fast. So there
are ways to make it go fast.

My bright idea is: don't worry, be happy :)

P

Reply | Threaded
Open this post in threaded view
|

Re: [postgis-users] GIST index speed

Mark Cave-Ayland-4
Paul Ramsey wrote:

> As performance problems go, it's not the worst case scenario.
> Re-writing the query as a join makes it very very fast. And wrapping
> it in a non-destructive function makes it acceptably fast. So there
> are ways to make it go fast.

Just for completeness, here is the EXPLAIN I get from your re-written
join query:


postgis=# explain analyze select count(*) from geography a join
geography b on (b.the_geom &&
b.centroid) where a.id = 69495;
                                                         QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------
  Aggregate  (cost=14298.01..14298.02 rows=1 width=0) (actual
time=294.601..294.602 rows=1 loops=1)
    ->  Nested Loop  (cost=0.00..14298.01 rows=1 width=0) (actual
time=56.222..257.332 rows=32880 loops=1)
          ->  Seq Scan on geography a  (cost=0.00..7149.00 rows=1
width=0) (actual time=56.186..56.363 rows=1 loops=1)
                Filter: (id = 69495::numeric)
          ->  Seq Scan on geography b  (cost=0.00..7149.00 rows=1
width=0) (actual time=0.020..128.780 rows=32880 loops=1)
                Filter: (b.the_geom && b.centroid)
  Total runtime: 294.693 ms
(7 rows)


I'm afraid I don't have enough planner-fu to know why this takes the low
cost route...

 > My bright idea is: don't worry, be happy :)

I think that may just have to be the case ;)


ATB,

Mark.

--
Mark Cave-Ayland
Sirius Corporation - The Open Source Experts
http://www.siriusit.co.uk
T: +44 870 608 0063

Reply | Threaded
Open this post in threaded view
|

Re: [postgis-users] GIST index speed

Tom Lane
In reply to this post by Mark Cave-Ayland-4
Mark Cave-Ayland <[hidden email]> writes:
> ... The question is: what can we do about this, especially as this is a very
> common case within PostGIS? According to the thread on -hackers, Tom
> suggested it may be possible to get PostgreSQL to automatically de-TOAST
> index scan keys. Unfortunately while this would solve the problem, it
> requires some non-trivial development work (i.e. it isn't exactly clear
> how to do it), and wouldn't help existing users.

I think I might have scared you off a bit too much there.  My impression
of this problem is that it should be just a few lines of code to fix;
I'm just not instantly sure of where to put those lines.

                        regards, tom lane

Reply | Threaded
Open this post in threaded view
|

Re: [postgis-users] GIST index speed

Tom Lane
In reply to this post by Mark Cave-Ayland-4
Mark Cave-Ayland <[hidden email]> writes:
> postgis=# explain analyze select count(*) from geography a join
> geography b on (b.the_geom &&
> b.centroid) where a.id = 69495;

Is that query really meaningful?  You seem to be forming the
cartesian product of a subset of a with an unrelated subset of b.

                        regards, tom lane

Reply | Threaded
Open this post in threaded view
|

Re: [postgis-users] GIST index speed

Obe, Regina     DND\MIS-3
Mark Cave-Ayland <[hidden email]> writes:
>> postgis=# explain analyze select count(*) from geography a join
>> geography b on (b.the_geom &&
>> b.centroid) where a.id = 69495;

>Is that query really meaningful?  You seem to be forming the
>cartesian product of a subset of a with an unrelated subset of b.

> regards, tom lane

Yap that looks like a typo

Mark did you mean -

explain analyze select count(*) from geography a join
        geography b on (b.the_geom && a.centroid) where a.id = 69495;

Hope that helps,
Regina
-----------------------------------------
The substance of this message, including any attachments, may be
confidential, legally privileged and/or exempt from disclosure
pursuant to Massachusetts law. It is intended
solely for the addressee. If you received this in error, please
contact the sender and delete the material from any computer.


Reply | Threaded
Open this post in threaded view
|

Re: [postgis-users] GIST index speed

Tom Lane
In reply to this post by Tom Lane
I wrote:
> I think I might have scared you off a bit too much there.  My impression
> of this problem is that it should be just a few lines of code to fix;
> I'm just not instantly sure of where to put those lines.

After looking around a bit, I thought probably the best place to do the
deed is in ExecIndexEvalRuntimeKeys().  The attached patch is a bit
larger than I'd anticipated because it seems best to look up the
possible toastability of the datatype just once per query, instead of
every time through ExecIndexEvalRuntimeKeys().

The patch passes core and contrib regression tests in CVS HEAD, but
I've not tried it further back.  (I can say that the patch applies
successfully to 8.3 and 8.2 branches, but not 8.1; I didn't look at
what it might take to make it go in 8.1 or before.)

I don't have any test cases that might show performance benefits.
I'd be willing to apply the patch to HEAD on my own authority, but
to get it into existing release branches, I think the PostGIS crowd
will need to make a case to pgsql-hackers that there are significant
performance benefits here.  Hence, please test ...

                        regards, tom lane


4201.1213330380.2@sss.pgh.pa.us (6K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [postgis-users] GIST index speed

Mark Cave-Ayland-4
In reply to this post by Obe, Regina DND\MIS-3
Obe, Regina wrote:

> Yap that looks like a typo
>
> Mark did you mean -
>
> explain analyze select count(*) from geography a join
> geography b on (b.the_geom && a.centroid) where a.id = 69495;
>
> Hope that helps,
> Regina

Thanks guys.

Yeah, it was just me experimenting with trying to simplify the query down
even further in both forms. So it is likely that the results of this
particular query are just meaningless ;)


ATB,

Mark.

--
Mark Cave-Ayland
Sirius Corporation - The Open Source Experts
http://www.siriusit.co.uk
T: +44 870 608 0063



Reply | Threaded
Open this post in threaded view
|

Re: [postgis-users] GIST index speed

Mark Cave-Ayland-4
In reply to this post by Tom Lane
Tom Lane wrote:

> After looking around a bit, I thought probably the best place to do the
> deed is in ExecIndexEvalRuntimeKeys().  The attached patch is a bit
> larger than I'd anticipated because it seems best to look up the
> possible toastability of the datatype just once per query, instead of
> every time through ExecIndexEvalRuntimeKeys().

Great! My first question was going to be along the lines of "would someone
of my experience be able to handle this?", but obviously you beat me to
it. It looks like a relatively straightforward small and non-invasive
patch which is good.

> The patch passes core and contrib regression tests in CVS HEAD, but
> I've not tried it further back.  (I can say that the patch applies
> successfully to 8.3 and 8.2 branches, but not 8.1; I didn't look at
> what it might take to make it go in 8.1 or before.)

Okay. I'm personally not too worried about 8.1, but inclusion within 8.2
and 8.3 would definitely help out a lot of people with large geometries.

> I don't have any test cases that might show performance benefits.
> I'd be willing to apply the patch to HEAD on my own authority, but
> to get it into existing release branches, I think the PostGIS crowd
> will need to make a case to pgsql-hackers that there are significant
> performance benefits here.  Hence, please test ...

(goes away and plays for a bit)

Hmmm there is still something strange going on; I can see some performance
benefit to the patch, but nothing near to the level of the mcatest()
function I was using before.

Here are the results using vanilla PostgreSQL 8.3.3 for Steve's original
query without your included patch:


postgis=# explain analyze select id,name from geography where type='Z' and
centroid && (select the_geom from geography where id=69495);
                                                                    QUERY
PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------
 Index Scan using geography_centroid_index on geography
(cost=7092.00..7100.28 rows=1 width=14) (actual time=51.911..3761.878
rows=29687 loops=1)
   Index Cond: (centroid && $0)
   Filter: ((centroid && $0) AND ((type)::text = 'Z'::text))
   InitPlan
     ->  Seq Scan on geography  (cost=0.00..7092.00 rows=1 width=4503)
(actual time=22.314..42.087 rows=1 loops=1)
           Filter: (id = 69495::numeric)
 Total runtime: 3797.354 ms
(7 rows)


postgis=# explain analyze select id,name from geography where type='Z' and
centroid && (select mcatest(the_geom) from geography where id=69495);
                                                                    QUERY
PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------
 Index Scan using geography_centroid_index on geography
(cost=7092.00..7100.28 rows=1 width=14) (actual time=58.853..271.775
rows=29687 loops=1)
   Index Cond: (centroid && $0)
   Filter: ((centroid && $0) AND ((type)::text = 'Z'::text))
   InitPlan
     ->  Seq Scan on geography  (cost=0.00..7092.00 rows=1 width=4503)
(actual time=24.640..58.501 rows=1 loops=1)
           Filter: (id = 69495::numeric)
 Total runtime: 317.961 ms
(7 rows)


And here are the results with your attached patch applied (note: I did
receive some warnings about hunk offsets during application, but the patch
did appear to apply successfully):


postgis=# explain analyze select id,name from geography where type='Z' and
centroid && (select the_geom from geography where id=69495);
                                                                    QUERY
PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------
 Index Scan using geography_centroid_index on geography
(cost=7092.00..7100.28 rows=1 width=14) (actual time=51.433..1993.498
rows=29687 loops=1)
   Index Cond: (centroid && $0)
   Filter: ((centroid && $0) AND ((type)::text = 'Z'::text))
   InitPlan
     ->  Seq Scan on geography  (cost=0.00..7092.00 rows=1 width=4503)
(actual time=30.813..50.979 rows=1 loops=1)
           Filter: (id = 69495::numeric)
 Total runtime: 2031.378 ms
(7 rows)

postgis=# explain analyze select id,name from geography where type='Z' and
centroid && (select mcatest(the_geom) from geography where id=69495);
                                                                    QUERY
PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------
 Index Scan using geography_centroid_index on geography
(cost=7092.00..7100.28 rows=1 width=14) (actual time=57.051..266.321
rows=29687 loops=1)
   Index Cond: (centroid && $0)
   Filter: ((centroid && $0) AND ((type)::text = 'Z'::text))
   InitPlan
     ->  Seq Scan on geography  (cost=0.00..7092.00 rows=1 width=4503)
(actual time=23.738..56.669 rows=1 loops=1)
           Filter: (id = 69495::numeric)
 Total runtime: 318.374 ms
(7 rows)


So the good news is that the patch has shaved nearly 50% off the overall
query time. But in comparison to my simple wrapper function that de-TOASTs
the geometry, it is still 6 times slower for an identical query plan even
with your patch included.

This seems to indicate that something else must still be at play here: can
you think of any other ways in which these two queries are still
different? Given the simplicity of the patch, I can't see that much of
this would be influenced by the overhead of the patch itself.


Many thanks,

Mark.

--
Mark Cave-Ayland
Sirius Corporation - The Open Source Experts
http://www.siriusit.co.uk
T: +44 870 608 0063



Reply | Threaded
Open this post in threaded view
|

Re: [postgis-users] GIST index speed

Paul Ramsey
On Mon, Jun 16, 2008 at 12:59 PM, Mark Cave-Ayland
<[hidden email]> wrote:

> So the good news is that the patch has shaved nearly 50% off the overall
> query time. But in comparison to my simple wrapper function that de-TOASTs
> the geometry, it is still 6 times slower for an identical query plan even
> with your patch included.

Coincidentally (?) 50% is the same speed-up I got my removing RECHECK
from the index for this test case.

Reply | Threaded
Open this post in threaded view
|

Re: [postgis-users] GIST index speed

Tom Lane
In reply to this post by Mark Cave-Ayland-4
"Mark Cave-Ayland" <[hidden email]> writes:
> So the good news is that the patch has shaved nearly 50% off the overall
> query time. But in comparison to my simple wrapper function that de-TOASTs
> the geometry, it is still 6 times slower for an identical query plan even
> with your patch included.

Huh, that's disappointing.  I see where the extra time must be going:

>  Index Scan using geography_centroid_index on geography
> (cost=7092.00..7100.28 rows=1 width=14) (actual time=51.911..3761.878
> rows=29687 loops=1)
>    Index Cond: (centroid && $0)
>    Filter: ((centroid && $0) AND ((type)::text = 'Z'::text))

Since this is a lossy index, the && condition has to be rechecked on
each candidate row identified by the index (note the Filter condition).
My patch eliminates repeat detoastings inside the index machinery, but
does nothing for the Filter condition.  Apparently the number of
candidate matches is large enough that about half of the detoastings
were occurring there.  (Can you get it to use a bitmap indexscan by
setting enable_indexscan off?  It'd be interesting to see just how many
rows the index is returning.)

So apparently we need a more general solution.  Not sure what offhand.

                        regards, tom lane

Reply | Threaded
Open this post in threaded view
|

Re: [postgis-users] GIST index speed

Mark Cave-Ayland-4
Tom Lane wrote:

> Since this is a lossy index, the && condition has to be rechecked on
> each candidate row identified by the index (note the Filter condition).
> My patch eliminates repeat detoastings inside the index machinery, but
> does nothing for the Filter condition.  Apparently the number of
> candidate matches is large enough that about half of the detoastings
> were occurring there.  (Can you get it to use a bitmap indexscan by
> setting enable_indexscan off?  It'd be interesting to see just how many
> rows the index is returning.)

This seems to agree with what Paul has noticed; we've long been aware that
the RECHECK has been contributing to heavily increased query times, but
this is the first time it's been nailed down to a particular cause. Here's
the relevant session output:

postgis=# set enable_indexscan='f';
SET
postgis=# explain analyze select id,name from geography where type='Z' and
centroid && (select the_geom from geography where id=69495);
                                                              QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on geography  (cost=7096.26..7100.28 rows=1 width=14)
(actual time=89.458..1949.395 rows=29687 loops=1)
   Filter: ((centroid && $0) AND ((type)::text = 'Z'::text))
   InitPlan
     ->  Seq Scan on geography  (cost=0.00..7092.00 rows=1 width=4503)
(actual time=26.520..70.221 rows=1 loops=1)
           Filter: (id = 69495::numeric)
   ->  Bitmap Index Scan on geography_centroid_index  (cost=0.00..4.26
rows=1 width=0) (actual time=87.842..87.842 rows=32880 loops=1)
         Index Cond: (centroid && $0)
 Total runtime: 1985.376 ms
(8 rows)

postgis=# set enable_bitmapscan = 'f';
SET
postgis=# explain analyze select id,name from geography where type='Z' and
centroid && (select the_geom from geography where id=69495);
                                                    QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
 Seq Scan on geography  (cost=7092.00..14266.20 rows=1 width=14) (actual
time=66.554..1819.057 rows=29687 loops=1)
   Filter: ((centroid && $0) AND ((type)::text = 'Z'::text))
   InitPlan
     ->  Seq Scan on geography  (cost=0.00..7092.00 rows=1 width=4503)
(actual time=27.779..66.281 rows=1 loops=1)
           Filter: (id = 69495::numeric)
 Total runtime: 1857.119 ms
(6 rows)

postgis=# select count(*) from geography;
 count
-------
 32880
(1 row)


It would seem that the sequential scan is actually very slightly faster,
and in fact the index is returning every one of the 32880 rows and passing
them through the filter.

> So apparently we need a more general solution.  Not sure what offhand.

With some grepping of the source, it's fairly easy to see that if the
operator has been marked as RECHECK then the same condition is simply
added to the qualification list.

So it almost seems we need some sort of logic at scan level, perhaps
something  along the lines of: if a TOASTed datum is referenced within a
qualification higher up in the plan tree, de-TOAST the datum just before
the tuple is returned as part of the scan. This should help both the
sequential scan and the index scan in the cases above.


ATB,

Mark.

--
Mark Cave-Ayland
Sirius Corporation - The Open Source Experts
http://www.siriusit.co.uk
T: +44 870 608 0063



Reply | Threaded
Open this post in threaded view
|

Re: [postgis-users] GIST index speed

Tom Lane
"Mark Cave-Ayland" <[hidden email]> writes:

> postgis=# set enable_indexscan='f';
> SET
> postgis=# explain analyze select id,name from geography where type='Z' and
> centroid && (select the_geom from geography where id=69495);
>                                                               QUERY PLAN
> ---------------------------------------------------------------------------------------------------------------------------------------
>  Bitmap Heap Scan on geography  (cost=7096.26..7100.28 rows=1 width=14)
> (actual time=89.458..1949.395 rows=29687 loops=1)
>    Filter: ((centroid && $0) AND ((type)::text = 'Z'::text))
>    InitPlan
>      ->  Seq Scan on geography  (cost=0.00..7092.00 rows=1 width=4503)
> (actual time=26.520..70.221 rows=1 loops=1)
>            Filter: (id = 69495::numeric)
>    ->  Bitmap Index Scan on geography_centroid_index  (cost=0.00..4.26
> rows=1 width=0) (actual time=87.842..87.842 rows=32880 loops=1)
>          Index Cond: (centroid && $0)
>  Total runtime: 1985.376 ms
> (8 rows)

Hm, this is with that patch in place, right?  Because it's showing only
87 msec spent inside the indexscan proper, which wouldn't square with
our theories if there were multiple detoastings going on in there.
Can you show the same case without the patch?

> and in fact the index is returning every one of the 32880 rows and passing
> them through the filter.

Ugh.  Is that to be expected given the particular data involved here,
or does it suggest there's some larger problem with indexing of &&
queries?

>> So apparently we need a more general solution.  Not sure what offhand.

> So it almost seems we need some sort of logic at scan level, perhaps
> something  along the lines of: if a TOASTed datum is referenced within a
> qualification higher up in the plan tree, de-TOAST the datum just before
> the tuple is returned as part of the scan.

Getting that right would be tricky though.  For example, if the datum
has to pass through a Sort node before it gets used, early detoasting
would be counterproductive because it'd increase the volume of data
to be sorted.

I wonder if it'd be sane for the TOAST code to keep a small lookaside
cache of recently-detoasted values ...

                        regards, tom lane

Reply | Threaded
Open this post in threaded view
|

Re: [postgis-users] GIST index speed

Tom Lane
I wrote:
> I wonder if it'd be sane for the TOAST code to keep a small lookaside
> cache of recently-detoasted values ...

I put up a design proposal for that on pgsql-hackers:
http://archives.postgresql.org/pgsql-hackers/2008-06/msg00709.php
It seems do-able as new development for 8.4, but of course it'd be
much too invasive to be considered for back-patching.  I don't currently
have any ideas about a back-patchable fix that would alleviate the
performance problem for index filter conditions.  If anyone's got bright
ideas, please contribute to the -hackers thread.

My previous patch might be worth pursuing in any case, on the grounds
that 50% improvement is better than nothing ...

                        regards, tom lane

Reply | Threaded
Open this post in threaded view
|

Re: [postgis-users] GIST index speed

Mark Cave-Ayland-4
In reply to this post by Tom Lane
Tom Lane wrote:

> Hm, this is with that patch in place, right?  Because it's showing only
> 87 msec spent inside the indexscan proper, which wouldn't square with
> our theories if there were multiple detoastings going on in there.
> Can you show the same case without the patch?

Yes, that's correct. Here are the same results without the patch in place:

(Note I've also added an extra case at the bottom to show that the
de-TOASTing also benefits plain sequential scans)


postgis=# set enable_indexscan='f';
SET
postgis=# explain analyze select id,name from geography where type='Z' and
postgis-# centroid && (select the_geom from geography where id=69495);
                                                                 QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------
  Bitmap Heap Scan on geography  (cost=7096.26..7100.28 rows=1 width=14)
(actual time=1772.346..3610.121 rows=29687 loops=1)
    Filter: ((centroid && $0) AND ((type)::text = 'Z'::text))
    InitPlan
      ->  Seq Scan on geography  (cost=0.00..7092.00 rows=1 width=4503)
(actual time=23.373..56.344 rows=1 loops=1)
            Filter: (id = 69495::numeric)
    ->  Bitmap Index Scan on geography_centroid_index  (cost=0.00..4.26
rows=1 width=0) (actual time=1770.802..1770.802 rows=32880 loops=1)
          Index Cond: (centroid && $0)
  Total runtime: 3646.019 ms
(8 rows)

postgis=# set enable_bitmapscan = 'f';
SET
postgis=# explain analyze select id,name from geography where type='Z' and
postgis-# centroid && (select the_geom from geography where id=69495);
                                                     QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
  Seq Scan on geography  (cost=7092.00..14266.20 rows=1 width=14)
(actual time=53.867..1852.810 rows=29687 loops=1)
    Filter: ((centroid && $0) AND ((type)::text = 'Z'::text))
    InitPlan
      ->  Seq Scan on geography  (cost=0.00..7092.00 rows=1 width=4503)
(actual time=25.730..53.595 rows=1 loops=1)
            Filter: (id = 69495::numeric)
  Total runtime: 1889.969 ms
(6 rows)

postgis=# explain analyze select id,name from geography where type='Z' and
centroid && (select mcatest(the_geom) from geography where id=69495);
                                                     QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
  Seq Scan on geography  (cost=7092.00..14266.20 rows=1 width=14)
(actual time=54.452..161.947 rows=29687 loops=1)
    Filter: ((centroid && $0) AND ((type)::text = 'Z'::text))
    InitPlan
      ->  Seq Scan on geography  (cost=0.00..7092.00 rows=1 width=4503)
(actual time=26.126..54.133 rows=1 loops=1)
            Filter: (id = 69495::numeric)
  Total runtime: 209.119 ms
(6 rows)


> Ugh.  Is that to be expected given the particular data involved here,
> or does it suggest there's some larger problem with indexing of &&
> queries?

Yeah that's fine with this dataset - it appears to be the type field
which is the main filter for this query.

> I wonder if it'd be sane for the TOAST code to keep a small lookaside
> cache of recently-detoasted values ...

Sounds like it could be a plan. I suspect that the caching will be the
easy bit, whereas as managing the entry lifetimes will be hard.


ATB,

Mark.

--
Mark Cave-Ayland
Sirius Corporation - The Open Source Experts
http://www.siriusit.co.uk
T: +44 870 608 0063

Reply | Threaded
Open this post in threaded view
|

Re: [postgis-users] GIST index speed

Mark Cave-Ayland-4
In reply to this post by Tom Lane
Tom Lane wrote:

> I put up a design proposal for that on pgsql-hackers:
> http://archives.postgresql.org/pgsql-hackers/2008-06/msg00709.php
> It seems do-able as new development for 8.4, but of course it'd be
> much too invasive to be considered for back-patching.  I don't currently
> have any ideas about a back-patchable fix that would alleviate the
> performance problem for index filter conditions.  If anyone's got bright
> ideas, please contribute to the -hackers thread.

Looks good. I see you're attempting to use MemoryContexts to influence
the lifetime of the cache entries. As long as cache entries aren't
removed completely at the end of a context, then it should work well.

While we're at it, here's something else for the PostGIS wishlist. At
the moment, we perform a lot of the geometry processing using the
external GEOS library. This is a similar problem to TOAST in that the
conversion between the PostGIS geometry type and the GEOS geometry type
is expensive on large geometries; so if we could find some way to cache
the conversion results we could reap performance benefits of several
orders of magnitude.

I'm wondering if it would be possible add an extra field to Datum
(similar to flinfo->fn_extra for functions) which is simply a
general-purpose pointer. We could then use it during query execution to
store a cached representation of the geometry conversion for the
lifetime of the Datum.

> My previous patch might be worth pursuing in any case, on the grounds
> that 50% improvement is better than nothing ...

I still think that it is a valid patch for 8.3 and back-branches in that
it brings the index scan overhead down to the same level as a sequential
scan; and I think a lot of people with larger objects in their database
will see the benefits of this. This can then be revisited (if) the TOAST
cache can get implemented for 8.4.


ATB,

Mark.

--
Mark Cave-Ayland
Sirius Corporation - The Open Source Experts
http://www.siriusit.co.uk
T: +44 870 608 0063

Reply | Threaded
Open this post in threaded view
|

Re: [postgis-users] GIST index speed

Tom Lane
Mark Cave-Ayland <[hidden email]> writes:
> I'm wondering if it would be possible add an extra field to Datum

Datum?  No.  Datum has to be a scalar type --- turning it into a
struct would break an impossibly large amount of code, and the
efficiency implications aren't pleasant either.

However, it does seem like a mechanism that's able to handle caching
of detoasting operations might be able to solve your problem too,
if it's got a reasonably flexible notion of what detoasting means.
I'll try to keep your issue in mind while working on that.

Did you see the alternative design sketch at
http://archives.postgresql.org/pgsql-hackers/2008-06/msg00777.php
?  I'm trying to decide which way to pursue.  The second proposal
would have a lot less management overhead, but would not be able
to cache detoast work across queries, which is something that might
be critical for your case.  Or not --- I'm not very clear on the
use pattern you foresee.  Datum certainly wouldn't have a cross-query
lifespan either.

                        regards, tom lane

Reply | Threaded
Open this post in threaded view
|

Re: [postgis-users] GIST index speed

Mark Cave-Ayland-4
Tom Lane wrote:

> Datum?  No.  Datum has to be a scalar type --- turning it into a
> struct would break an impossibly large amount of code, and the
> efficiency implications aren't pleasant either.
>
> However, it does seem like a mechanism that's able to handle caching
> of detoasting operations might be able to solve your problem too,
> if it's got a reasonably flexible notion of what detoasting means.
> I'll try to keep your issue in mind while working on that.

Okay. The reason I was thinking about Datum was because I was thinking
about trying to cache the results of the PostGIS -> GEOS transformation
for non-TOASTed as well as TOASTed objects. So effectively we'd need to
keep both the PostgreSQL geometry type and the GEOS-converted PostgreSQL
geometry type around where we can access them. With your suggestion, I'm
guessing that we would only be able to cache the PostGIS -> GEOS
transformation for TOASTed objects. Maybe that would be enough, although
it's one of those things that would be difficult to test without an
actual implementation :(

> Did you see the alternative design sketch at
> http://archives.postgresql.org/pgsql-hackers/2008-06/msg00777.php
> ?  I'm trying to decide which way to pursue.  The second proposal
> would have a lot less management overhead, but would not be able
> to cache detoast work across queries, which is something that might
> be critical for your case.  Or not --- I'm not very clear on the
> use pattern you foresee.  Datum certainly wouldn't have a cross-query
> lifespan either.

Yes, I did take a look at it, although it's beginning to get outside of
my sphere of knowledge. Since geometries can get quite big, the most
common query pattern is accessing TOASTed geometries within a correlated
subquery, or as part of an (inner) JOIN using the && operator against
two columns containing TOASTed geometries in different tables.

Note that because geometries contain floating point numbers and are
multi-dimensional, the only real way to perform the join is using a
Nested Loop. Most of the slow queries I see are of this form; so it may
be that a cache simply for the duration of a single query would be
sufficient for the majority of cases.


ATB,

Mark.

--
Mark Cave-Ayland
Sirius Corporation - The Open Source Experts
http://www.siriusit.co.uk
T: +44 870 608 0063

Reply | Threaded
Open this post in threaded view
|

Re: [postgis-users] GIST index speed

Tom Lane
Mark Cave-Ayland <[hidden email]> writes:
> Okay. The reason I was thinking about Datum was because I was thinking
> about trying to cache the results of the PostGIS -> GEOS transformation
> for non-TOASTed as well as TOASTed objects. So effectively we'd need to
> keep both the PostgreSQL geometry type and the GEOS-converted PostgreSQL
> geometry type around where we can access them. With your suggestion, I'm
> guessing that we would only be able to cache the PostGIS -> GEOS
> transformation for TOASTed objects. Maybe that would be enough, although
> it's one of those things that would be difficult to test without an
> actual implementation :(

Yeah.  I don't really see any way to cache stuff for datums that aren't
toasted out-of-line, because there's no unique identifier assigned to
them that you could use for a cache lookup key.  On the other hand,
if the geometry isn't big enough to get toasted, it can't be all that
expensive to convert, so maybe such a solution is Good Enough.

Seems like you might also be able to solve it internally to PostGIS,
if you were to add some sort of reasonably unique identifier to the
internal representation of a geometry datum --- md5 of the rest of
the contents, say.  Then you could use that value as a cache key.

> Note that because geometries contain floating point numbers and are
> multi-dimensional, the only real way to perform the join is using a
> Nested Loop. Most of the slow queries I see are of this form; so it may
> be that a cache simply for the duration of a single query would be
> sufficient for the majority of cases.

Hmm.  What would happen with the TupleTableSlot implementation is that
a geometry coming from the outer side of the nestloop would get
detoasted only once, while those on the inner side would get detoasted
on each visit.  A backend-wide cache would do better, but only if it
were big enough to hold all the detoasted values from the inner relation
--- otherwise the values would fall out of cache before being visited
again, and you'd be no better off.

                        regards, tom lane

12