Re: [PERFORM] GiST index performance
On Sat, 20 Mar 2010, Yeb Havinga wrote: The gist virtual pages would then match more the original blocksizes that were used in Guttman's R-tree paper (first google result, then figure 4.5). Since the nature/characteristics of the underlying datatypes and keys is not changed, it might be that with the disk pages getting larger, gist indexing has therefore become unexpectedly inefficient. Yes, that is certainly a factor. For example, the page size for bioseg which we use here is 130 entries, which is very excessive, and doesn't allow very deep trees. On the other hand, it means that a single disc seek performs quite a lot of work. But I am also not really into the core-gist code, but do have a motivation to dive into it (more than 200% performance increase in Mathew's test case). However I'd like to verify for community support before working on it. I'd also love to dive into the core gist code, but am rather daunted by it. I believe that there is something there that is taking more time than I can account for. The indexing algorithm itself is good. Matthew -- The problem with defending the purity of the English language is that English is about as pure as a cribhouse whore. We don't just borrow words; on occasion, English has pursued other languages down alleyways to beat them unconscious and rifle their pockets for new vocabulary. - James Nicoll -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Matthew Wakeling wrote: On Sat, 20 Mar 2010, Yeb Havinga wrote: The gist virtual pages would then match more the original blocksizes that were used in Guttman's R-tree paper (first google result, then figure 4.5). Since the nature/characteristics of the underlying datatypes and keys is not changed, it might be that with the disk pages getting larger, gist indexing has therefore become unexpectedly inefficient. Yes, that is certainly a factor. For example, the page size for bioseg which we use here is 130 entries, which is very excessive, and doesn't allow very deep trees. On the other hand, it means that a single disc seek performs quite a lot of work. Yeah, I only did in-memory fitting tests and wondered about increased io's. However I bet that even for bigger than ram db's, the benefit of having to fan out to less pages still outweighs the over-general non leaf nodes and might still result in less disk io's. I redid some earlier benchmarking with other datatypes with a 1kB block size and also multicolumn gist and the multicolumn variant had an ever greater benefit than the single column indexes, both equality and range scans. (Like execution times down to 20% of original). If gist is important to you, I really recommend doing a test with 1kB blocks. regards, Yeb Havinga -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Mon, 22 Mar 2010, Yeb Havinga wrote: Yes, that is certainly a factor. For example, the page size for bioseg which we use here is 130 entries, which is very excessive, and doesn't allow very deep trees. On the other hand, it means that a single disc seek performs quite a lot of work. Yeah, I only did in-memory fitting tests and wondered about increased io's. However I bet that even for bigger than ram db's, the benefit of having to fan out to less pages still outweighs the over-general non leaf nodes and might still result in less disk io's. I redid some earlier benchmarking with other datatypes with a 1kB block size and also multicolumn gist and the multicolumn variant had an ever greater benefit than the single column indexes, both equality and range scans. (Like execution times down to 20% of original). If gist is important to you, I really recommend doing a test with 1kB blocks. Purely from a disc seek count point of view, assuming an infinite CPU speed and infinite disc transfer rate, the larger the index pages the better. The number of seeks per fetch will be equivalent to the depth of the tree. If you take disc transfer rate into account, the break-even point is when you spend an equal time transferring as seeking, which places the page size around 500kB on a modern disc, assuming RAID stripe alignment doesn't make that into two seeks instead of one. However, for efficient CPU usage, the ideal page size for a tree index is much smaller - between two and ten entries, depending on the type of the data. There may be some mileage in reorganising indexes into a two-level system. That is, have an index format where the page size is 512kB or similar, but each page is internally a CPU-efficient tree itself. However, this is beyond the scope of the problem of speeding up gist. Matthew -- If you let your happiness depend upon how somebody else feels about you, now you have to control how somebody else feels about you. -- Abraham Hicks -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Fri, Mar 19, 2010 at 10:16 PM, Kenneth Marshall k...@rice.edu wrote:
Hi Yeb,
I have not looked at the gist code, but would it be possible to
make virtual pages that have a size that is 1/power-of-2 * blocksize.
Then the leaf node could be 1/8 or even 1/16 the size of the full
pagesize.
Hello Ken,
The gist virtual pages would then match more the original blocksizes that
were used in Guttman's R-tree paper (first google result, then figure 4.5).
Since the nature/characteristics of the underlying datatypes and keys is not
changed, it might be that with the disk pages getting larger, gist indexing
has therefore become unexpectedly inefficient.
But I am also not really into the core-gist code, but do have a motivation
to dive into it (more than 200% performance increase in Mathew's test case).
However I'd like to verify for community support before working on it.
Maybe Theodor or Oleg could say something about how easy or hard it is to
do?
regards,
Yeb Havinga
Regards,
Ken
On Fri, Mar 19, 2010 at 09:49:30PM +0100, Yeb Havinga wrote:
Yeb Havinga wrote:
Since the gistpagesize is derived from the database blocksize, it might
be
wise to set the blocksize low for this case, I'm going to play with this
a
bit more.
Ok, one last mail before it turns into spam: with a 1KB database
blocksize,
the query now runs in 30 seconds (original 70 on my machine, shared
buffers
240MB).
The per inner loop access time now 24 microsecs compared to on my machine
original 74 microsecs with 8KB size and 8 for the btree scan. Not a bad
speedup with such a simple parameter :-)
postgres=# EXPLAIN ANALYSE SELECT * FROM a, b WHERE a.a BETWEEN b.b AND
b.b
+ 2;
QUERY PLAN
---
Nested Loop (cost=0.00..4169159462.20 rows=09777668 width=8) (actual
time=0.184..29540.355 rows=297 loops=1)
- Seq Scan on b (cost=0.00..47037.62 rows=62 width=4) (actual
time=0.024..1783.484 rows=100 loops=1)
- Index Scan using a_a on a (cost=0.00..2224.78 rows=14 width=4)
(actual time=0.021..0.024 rows=3 loops=100)
Index Cond: ((a.a = b.b) AND (a.a = (b.b + 2)))
Total runtime: 30483.303 ms
(5 rows)
postgres=# select gist_stat('a_a');
gist_stat
---
Number of levels: 5 +
Number of pages: 47618 +
Number of leaf pages: 45454 +
Number of tuples: 1047617 +
Number of invalid tuples: 0 +
Number of leaf tuples: 100 +
Total size of tuples: 21523756 bytes+
Total size of leaf tuples: 20545448 bytes+
Total size of index: 48760832 bytes+
(1 row)
--
Sent via pgsql-performance mailing list (
pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Yeb Havinga wrote: Yeb Havinga wrote: Matthew Wakeling wrote: Matthew Wakeling wrote: A second quite distinct issue is the general performance of GiST indexes which is also mentioned in the old thread linked from Open Items. For that, we have a test case at http://archives.postgresql.org/pgsql-performance/2009-04/msg00276.php for btree_gist indexes. I have a similar example with the bioseg GiST index. I have completely reimplemented the same algorithms in Java for algorithm investigation and instrumentation purposes, and it runs about a hundred times faster than in Postgres. I think this is a problem, and I'm willing to do some investigation to try and solve it. I have not made any progress on this issue. I think Oleg and Teodor would be better placed working it out. All I can say is that I implemented the exact same indexing algorithm in Java, and it performed 100 times faster than Postgres. Now, Postgres has to do a lot of additional work, like mapping the index onto disc, locking pages, and abstracting to plugin user functions, so I would expect some difference - I'm not sure 100 times is reasonable though. I tried to do some profiling, but couldn't see any one section of code that was taking too much time. Not sure what I can further do. Looked in the code a bit more - only the index nodes are compressed at index creation, the consistent functions does not compress queries, so not pallocs there. However when running Mathews example from http://archives.postgresql.org/pgsql-performance/2009-04/msg00276.php with the gist index, the coverage shows in gistget.c: 100 palloc0 's of gistsearchstack at line 152 and 2010982 palloc's also of the gistsearchstack on line 342. Two pfrees are also hit a lot: line 195: 1010926 of a stackentry and line 293: 200056 times. My $0.02 cents is that the pain is here. My knowledge of gistget or the other sources in access/gist is zero, but couldn't it be possible to determine the maximum needed size of the stack and then allocate it at once and use a pop/push kind off api? Waisted some time today on a ghost chase... I though that removing the millions of pallocs would help, so I wrote an alternative of the gistsearchstack-stack to find out that it was not the index scanning itself that caused milltions of pallocs, but the scan being in the inner loop that was called 100 times. The actual scanning time was not changed significantly. The actual scanning time in my vm is for btree (actual time=0.006..0.008) and gist (actual time=0.071..0.074). An error in my searchstack alternative caused pages to be scanned twice, returing twice the amount of rows (6 instead of 3 each time). This resulted in a likewise increase of ms (actual time=0.075..0.150). Somewhere I hit something that causes ~= 0.070 ms twice. For a single index scan, 0.070ms startup time for gist vs 0.006 for btree doesn't seem like a big problem, but yeah when calling it a million times... regards, Yeb Havinga -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Yeb Havinga wrote: Matthew Wakeling wrote: A second quite distinct issue is the general performance of GiST indexes which is also mentioned in the old thread linked from Open Items. For that, we have a test case at http://archives.postgresql.org/pgsql-performance/2009-04/msg00276.php for btree_gist indexes. I have a similar example with the bioseg GiST index. I have completely reimplemented the same algorithms in Java for algorithm investigation and instrumentation purposes, and it runs about a hundred times faster than in Postgres. I think this is a problem, and I'm willing to do some investigation to try and solve it. More gist performance.. Some background: I've been involved in developing several datatypes that make use of gist indexes (we just published a paper on it, see http://arxiv.org/abs/1003.3370), that's the main reason I'm very much interested in possible improvements in gist index speed. One of the datatypes was 'very badly' indexable: non leaf pages were getting very general keys, so in the end we could see from the scanning times compared to sequential scans that the whole index was being scanned. One thing I remember was the idea that somehow it would be nice if the dept of the gist tree could be fiddled with: in that case keys of non leaf nodes would be more specific again. In the original Guttman R-tree paper there was mention of a parameter that determined the size of entries in nodes and thereby indirectly the depth of the tree. I missed that in the PostgreSQL gist api. One thing Gist scanning does very often is key comparisons. So another approach is to try to limit those and again this might be possible by increasing the depth / decrease number of entries per page. I just did a test where in gistfitpage the gistpagesize was divided by 5 and something similar in gistnospace. Scantime before adjustment: about 70 seconds. After adjustment: 45 seconds. With gist_stat from the gevel package confirmed that the depth was now 4 (original 3). Drawback: bigger index size because pages are not filled completely anymore. The explain shows (actual time=0.030..0.032) for the inner loop times, which is less then half of the original scan time. Since the gistpagesize is derived from the database blocksize, it might be wise to set the blocksize low for this case, I'm going to play with this a bit more. regards, Yeb Havinga -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Yeb Havinga wrote:
Since the gistpagesize is derived from the database blocksize, it
might be wise to set the blocksize low for this case, I'm going to
play with this a bit more.
Ok, one last mail before it turns into spam: with a 1KB database
blocksize, the query now runs in 30 seconds (original 70 on my machine,
shared buffers 240MB).
The per inner loop access time now 24 microsecs compared to on my
machine original 74 microsecs with 8KB size and 8 for the btree scan.
Not a bad speedup with such a simple parameter :-)
postgres=# EXPLAIN ANALYSE SELECT * FROM a, b WHERE a.a BETWEEN b.b AND
b.b + 2;
QUERY
PLAN
---
Nested Loop (cost=0.00..4169159462.20 rows=09777668 width=8)
(actual time=0.184..29540.355 rows=297 loops=1)
- Seq Scan on b (cost=0.00..47037.62 rows=62 width=4) (actual
time=0.024..1783.484 rows=100 loops=1)
- Index Scan using a_a on a (cost=0.00..2224.78 rows=14
width=4) (actual time=0.021..0.024 rows=3 loops=100)
Index Cond: ((a.a = b.b) AND (a.a = (b.b + 2)))
Total runtime: 30483.303 ms
(5 rows)
postgres=# select gist_stat('a_a');
gist_stat
---
Number of levels: 5 +
Number of pages: 47618 +
Number of leaf pages: 45454 +
Number of tuples: 1047617 +
Number of invalid tuples: 0 +
Number of leaf tuples: 100 +
Total size of tuples: 21523756 bytes+
Total size of leaf tuples: 20545448 bytes+
Total size of index: 48760832 bytes+
(1 row)
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Yeb Havinga wrote: Matthew Wakeling wrote: Matthew Wakeling wrote: A second quite distinct issue is the general performance of GiST indexes which is also mentioned in the old thread linked from Open Items. For that, we have a test case at http://archives.postgresql.org/pgsql-performance/2009-04/msg00276.php for btree_gist indexes. I have a similar example with the bioseg GiST index. I have completely reimplemented the same algorithms in Java for algorithm investigation and instrumentation purposes, and it runs about a hundred times faster than in Postgres. I think this is a problem, and I'm willing to do some investigation to try and solve it. I have not made any progress on this issue. I think Oleg and Teodor would be better placed working it out. All I can say is that I implemented the exact same indexing algorithm in Java, and it performed 100 times faster than Postgres. Now, Postgres has to do a lot of additional work, like mapping the index onto disc, locking pages, and abstracting to plugin user functions, so I would expect some difference - I'm not sure 100 times is reasonable though. I tried to do some profiling, but couldn't see any one section of code that was taking too much time. Not sure what I can further do. Hello Mathew and list, A lot of time spent in gistget.c code and a lot of functioncall5's to the gist's consistent function which is out of sight for gprof. Something different but related since also gist: we noticed before that gist indexes that use a compressed form for index entries suffer from repeated compress calls on query operands (see http://archives.postgresql.org/pgsql-hackers/2009-05/msg00078.php). The btree_gist int4 compress function calls the generic gbt_num_compress, which does a palloc. Maybe this palloc is allso hit al lot when scanning the index, because the constants that are queries with are repeatedly compressed and palloced. Looked in the code a bit more - only the index nodes are compressed at index creation, the consistent functions does not compress queries, so not pallocs there. However when running Mathews example from http://archives.postgresql.org/pgsql-performance/2009-04/msg00276.php with the gist index, the coverage shows in gistget.c: 100 palloc0 's of gistsearchstack at line 152 and 2010982 palloc's also of the gistsearchstack on line 342. Two pfrees are also hit a lot: line 195: 1010926 of a stackentry and line 293: 200056 times. My $0.02 cents is that the pain is here. My knowledge of gistget or the other sources in access/gist is zero, but couldn't it be possible to determine the maximum needed size of the stack and then allocate it at once and use a pop/push kind off api? regards, Yeb Havinga regards, Yeb Havinga -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Matthew Wakeling wrote: Matthew Wakeling wrote: A second quite distinct issue is the general performance of GiST indexes which is also mentioned in the old thread linked from Open Items. For that, we have a test case at http://archives.postgresql.org/pgsql-performance/2009-04/msg00276.php for btree_gist indexes. I have a similar example with the bioseg GiST index. I have completely reimplemented the same algorithms in Java for algorithm investigation and instrumentation purposes, and it runs about a hundred times faster than in Postgres. I think this is a problem, and I'm willing to do some investigation to try and solve it. I have not made any progress on this issue. I think Oleg and Teodor would be better placed working it out. All I can say is that I implemented the exact same indexing algorithm in Java, and it performed 100 times faster than Postgres. Now, Postgres has to do a lot of additional work, like mapping the index onto disc, locking pages, and abstracting to plugin user functions, so I would expect some difference - I'm not sure 100 times is reasonable though. I tried to do some profiling, but couldn't see any one section of code that was taking too much time. Not sure what I can further do. Hello Mathew and list, A lot of time spent in gistget.c code and a lot of functioncall5's to the gist's consistent function which is out of sight for gprof. Something different but related since also gist: we noticed before that gist indexes that use a compressed form for index entries suffer from repeated compress calls on query operands (see http://archives.postgresql.org/pgsql-hackers/2009-05/msg00078.php). The btree_gist int4 compress function calls the generic gbt_num_compress, which does a palloc. Maybe this palloc is allso hit al lot when scanning the index, because the constants that are queries with are repeatedly compressed and palloced. regards, Yeb Havinga -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Thu, 25 Feb 2010, Bruce Momjian wrote: Was there every any conclusion on this issue? Not really. Comments inline: Matthew Wakeling wrote: Revisiting the thread a month back or so, I'm still investigating performance problems with GiST indexes in Postgres. Looking at http://wiki.postgresql.org/wiki/PostgreSQL_8.4_Open_Items I'd like to clarify the contrib/seg issue. Contrib/seg is vulnerable to pathological behaviour which is fixed by my second patch, which can be viewed as complete. Contrib/cube, being multi-dimensional, is not affected to any significant degree, so should not need alteration. This issue is addressed by my patch, which AFAIK noone has reviewed. However, that patch was derived from a patch that I applied to bioseg, which is itself a derivative of seg. This patch works very well indeed, and gave an approximate 100 times speed improvement in the one test I ran. So you could say that the sister patch of the one I submitted is tried and tested in production. A second quite distinct issue is the general performance of GiST indexes which is also mentioned in the old thread linked from Open Items. For that, we have a test case at http://archives.postgresql.org/pgsql-performance/2009-04/msg00276.php for btree_gist indexes. I have a similar example with the bioseg GiST index. I have completely reimplemented the same algorithms in Java for algorithm investigation and instrumentation purposes, and it runs about a hundred times faster than in Postgres. I think this is a problem, and I'm willing to do some investigation to try and solve it. I have not made any progress on this issue. I think Oleg and Teodor would be better placed working it out. All I can say is that I implemented the exact same indexing algorithm in Java, and it performed 100 times faster than Postgres. Now, Postgres has to do a lot of additional work, like mapping the index onto disc, locking pages, and abstracting to plugin user functions, so I would expect some difference - I'm not sure 100 times is reasonable though. I tried to do some profiling, but couldn't see any one section of code that was taking too much time. Not sure what I can further do. Matthew -- Some people, when confronted with a problem, think I know, I'll use regular expressions. Now they have two problems. -- Jamie Zawinski -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Mon, Mar 15, 2010 at 11:58 AM, Matthew Wakeling matt...@flymine.org wrote: On Thu, 25 Feb 2010, Bruce Momjian wrote: Was there every any conclusion on this issue? Not really. Comments inline: Matthew Wakeling wrote: Revisiting the thread a month back or so, I'm still investigating performance problems with GiST indexes in Postgres. Looking at http://wiki.postgresql.org/wiki/PostgreSQL_8.4_Open_Items I'd like to clarify the contrib/seg issue. Contrib/seg is vulnerable to pathological behaviour which is fixed by my second patch, which can be viewed as complete. Contrib/cube, being multi-dimensional, is not affected to any significant degree, so should not need alteration. This issue is addressed by my patch, which AFAIK noone has reviewed. However, that patch was derived from a patch that I applied to bioseg, which is itself a derivative of seg. This patch works very well indeed, and gave an approximate 100 times speed improvement in the one test I ran. So you could say that the sister patch of the one I submitted is tried and tested in production. We rely fairly heavily on the commitfest app to track which patches need review; perhaps it would be good to add it here. https://commitfest.postgresql.org/action/commitfest_view/open I seem to recall thinking that this patch wasn't ready to apply for some reason, but I'm not sure why I thought that. ...Robert -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Thu, Feb 25, 2010 at 6:44 PM, Bruce Momjian br...@momjian.us wrote: Was this corrected? I don't see any commits to seg.c. I don't think this was ever reviewed. It seems like a good patch but I'd be skeptical of committing it now unless someone has the time to review it carefully. If not, let's add it to the next CF so we don't lose it again. ...Robert --- Matthew Wakeling wrote: On Thu, 7 May 2009, Oleg Bartunov wrote: Did you try Guttman quadratic split algorithm ? We also found linear split algorithm for Rtree. The existing (bugfixed) seg split algorithm is the Guttman quadratic split algorithm. Guttman did all his work on two-dimensional and above data, dismissing one-dimensional data as being handled adequately by B-trees, which is not true for segment overlaps. It turns out that the algorithm has a weakness with certain types of data, and one-dimensional data is almost certain to exercise that weakness. The greater the number of dimensions, the less the weakness is exercised. The problem is that the algorithm does not calculate a split pivot. Instead it finds two suitable entries, and adds the remaining entries to those two in turn. This can lead to the majority of the entries being added to just one side. In fact, I saw lots of cases where 367 entries were being split into two pages of 366 and one entry. Guttman's linear split algorithm has the same weakness. One thing I am seeing is a really big difference in performance between Postgres/GiST and a Java implementation I have written, using the same algorithms. Postgres takes three minutes to perform a set of index lookups while java takes six seconds. The old version of bioseg took an hour. I can't see anything in the GiST support code that could account for this. is the number of index lookups different, or just index lookup time is very big ? Same number of index lookups. Same algorithms. I have a set of 681879 segments, and I load them all into the index. I then query the index for overlaps for each one in turn. For some reason, GiST lookups seem to be slow, even if they are using a good algorithm. I have seen that problem with btree_gist on integers too. I can't see any reason for this is the GiST code - it all seems pretty tight to me. We probably need to do some profiling. Matthew -- I suppose some of you have done a Continuous Maths course. Yes? Continuous Maths? menacing stares from audience Whoah, it was like that, was it! -- Computer Science Lecturer -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance -- Bruce Momjian br...@momjian.us http://momjian.us EnterpriseDB http://enterprisedb.com PG East: http://www.enterprisedb.com/community/nav-pg-east-2010.do + If your life is a hard drive, Christ can be your backup. + -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Robert Haas wrote: On Thu, Feb 25, 2010 at 6:44 PM, Bruce Momjian br...@momjian.us wrote: Was this corrected? ?I don't see any commits to seg.c. I don't think this was ever reviewed. It seems like a good patch but I'd be skeptical of committing it now unless someone has the time to review it carefully. If not, let's add it to the next CF so we don't lose it again. I have asked Oleg and Teodor to work on it. -- Bruce Momjian br...@momjian.ushttp://momjian.us EnterpriseDB http://enterprisedb.com PG East: http://www.enterprisedb.com/community/nav-pg-east-2010.do -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Was there every any conclusion on this issue? --- Matthew Wakeling wrote: Revisiting the thread a month back or so, I'm still investigating performance problems with GiST indexes in Postgres. Looking at http://wiki.postgresql.org/wiki/PostgreSQL_8.4_Open_Items I'd like to clarify the contrib/seg issue. Contrib/seg is vulnerable to pathological behaviour which is fixed by my second patch, which can be viewed as complete. Contrib/cube, being multi-dimensional, is not affected to any significant degree, so should not need alteration. A second quite distinct issue is the general performance of GiST indexes which is also mentioned in the old thread linked from Open Items. For that, we have a test case at http://archives.postgresql.org/pgsql-performance/2009-04/msg00276.php for btree_gist indexes. I have a similar example with the bioseg GiST index. I have completely reimplemented the same algorithms in Java for algorithm investigation and instrumentation purposes, and it runs about a hundred times faster than in Postgres. I think this is a problem, and I'm willing to do some investigation to try and solve it. Do you have a recommendation for how to go about profiling Postgres, what profiler to use, etc? I'm running on Debian Linux x86_64. Matthew -- Jadzia: Don't forget the 34th rule of acquisition: Peace is good for business. Quark: That's the 35th. Jadzia: Oh yes, that's right. What's the 34th again? Quark: War is good for business. It's easy to get them mixed up. -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance -- Bruce Momjian br...@momjian.ushttp://momjian.us EnterpriseDB http://enterprisedb.com PG East: http://www.enterprisedb.com/community/nav-pg-east-2010.do + If your life is a hard drive, Christ can be your backup. + -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Was this corrected? I don't see any commits to seg.c. --- Matthew Wakeling wrote: On Thu, 7 May 2009, Oleg Bartunov wrote: Did you try Guttman quadratic split algorithm ? We also found linear split algorithm for Rtree. The existing (bugfixed) seg split algorithm is the Guttman quadratic split algorithm. Guttman did all his work on two-dimensional and above data, dismissing one-dimensional data as being handled adequately by B-trees, which is not true for segment overlaps. It turns out that the algorithm has a weakness with certain types of data, and one-dimensional data is almost certain to exercise that weakness. The greater the number of dimensions, the less the weakness is exercised. The problem is that the algorithm does not calculate a split pivot. Instead it finds two suitable entries, and adds the remaining entries to those two in turn. This can lead to the majority of the entries being added to just one side. In fact, I saw lots of cases where 367 entries were being split into two pages of 366 and one entry. Guttman's linear split algorithm has the same weakness. One thing I am seeing is a really big difference in performance between Postgres/GiST and a Java implementation I have written, using the same algorithms. Postgres takes three minutes to perform a set of index lookups while java takes six seconds. The old version of bioseg took an hour. I can't see anything in the GiST support code that could account for this. is the number of index lookups different, or just index lookup time is very big ? Same number of index lookups. Same algorithms. I have a set of 681879 segments, and I load them all into the index. I then query the index for overlaps for each one in turn. For some reason, GiST lookups seem to be slow, even if they are using a good algorithm. I have seen that problem with btree_gist on integers too. I can't see any reason for this is the GiST code - it all seems pretty tight to me. We probably need to do some profiling. Matthew -- I suppose some of you have done a Continuous Maths course. Yes? Continuous Maths? menacing stares from audience Whoah, it was like that, was it! -- Computer Science Lecturer -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance -- Bruce Momjian br...@momjian.ushttp://momjian.us EnterpriseDB http://enterprisedb.com PG East: http://www.enterprisedb.com/community/nav-pg-east-2010.do + If your life is a hard drive, Christ can be your backup. + -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Thu, 11 Jun 2009, Tom Lane wrote: Matthew Wakeling matt...@flymine.org writes: Oprofile scares me with the sheer number of options. You can ignore practically all of them; the defaults are pretty sane. The recipe I usually follow is: An excellent brain dump from Tom and lots of other good stuff in this thread. I just dumped a summary of all the profiling lore discussed onto http://wiki.postgresql.org/wiki/Profiling_with_OProfile as I don't know that I've ever seen a concise intro to this subject before. -- * Greg Smith gsm...@gregsmith.com http://www.gregsmith.com Baltimore, MD -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Fri, Jun 26, 2009 at 10:33 AM, Greg Smithgsm...@gregsmith.com wrote: On Thu, 11 Jun 2009, Tom Lane wrote: Matthew Wakeling matt...@flymine.org writes: Oprofile scares me with the sheer number of options. You can ignore practically all of them; the defaults are pretty sane. The recipe I usually follow is: An excellent brain dump from Tom and lots of other good stuff in this thread. I just dumped a summary of all the profiling lore discussed onto http://wiki.postgresql.org/wiki/Profiling_with_OProfile as I don't know that I've ever seen a concise intro to this subject before. Nice, thanks! ...Robert -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Tom Lane wrote: Matthew Wakeling matt...@flymine.org writes: I'm guessing my next step is to install a version of libc with debugging symbols? Yeah, if you want to find out what's happening in libc, that's what you need. Getting callgraph information from oprofile would also help. Although it won't directly tell what function in libc is being called, you would see where the calls are coming from, which is usually enough to guess what the libc function is. You can also get the oprofile data, including callgraph, into kcachegrind, which is *very* helpful. Here's a script I use: http://roberts.vorpus.org/~njs/op2calltree.py -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Matthew Wakeling wrote:
Okay, I don't know quite what's happening here. Tom, perhaps you could
advise. Running opannotate --source, I get this sort of stuff:
/*
* Total samples for file :
.../postgresql-8.4beta2/src/backend/access/gist/gistget.c
*
* 6880 0.2680
*/
and then:
:static int64
:gistnext(IndexScanDesc scan, TIDBitmap *tbm)
81 0.0032 :{ /* gistnext total: 420087 16.3649 */
:Pagep;
The gistnext total doesn't seem to correspond to the amount I get by
adding up all the individual lines in gistnest. Moreover, it is greater
than the total samples attributed to the whole file, and greater than
the samples assigned to all the lines where gistnext is called.
there's another alternative for profiling that you might try if you
can't get sensible results out of oprofile - cachegrind (which is part
of the valgrind toolset).
basically it runs the code in an emulated environment, but records every
access (reads/writes/CPU cycles/cache hits/misses/etc). it's *extremely*
good at finding hotspots, even when they are due to 'cache flushing'
behavior in your code (for example, trawling a linked list is touching a
bunch of pages and effectively blowing your CPU cache..)
there's an associated graphical tool called kcachegrind which takes the
dumped output and lets you drill down, even to the source code level
(with cycle count/percentage annotations on the source lines)
all you need to do is compile postgres with debug symbols (full
optimization ON, otherwise you end up reaching the wrong conclusions).
there's an example of running valgrind on postgres here:
http://blog.cleverelephant.ca/2008/08/valgrinding-postgis.html
for cachegrind, you basically need to use 'cachegrind' instead of
'valgrind', and don't disable optimization when you build..
smime.p7s
Description: S/MIME Cryptographic Signature
Re: [PERFORM] GiST index performance
On Wed, 10 Jun 2009, Tom Lane wrote: Also, no calls to anything including bioseg in the name are recorded, although they are definitely called as the GiST support functions for that data type. I have never had any success in getting gprof to profile functions that are in loadable libraries, which of course is exactly what you need to do here. That sucks. However, as another observation, no calls to gistfindnext are recorded in the profile either, and that's in the same source file as gistnext which is recorded. Could it have been inlined? Shouldn't inlining be switched off on a profiling build? ...the best bet is probably to make a test build of Postgres in which your functions are linked directly into the main postgres executable. I'll give that a try. Oprofile scares me with the sheer number of options. Matthew -- Prolog doesn't have enough parentheses. -- Computer Science Lecturer -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Matthew Wakeling matt...@flymine.org writes: That sucks. However, as another observation, no calls to gistfindnext are recorded in the profile either, and that's in the same source file as gistnext which is recorded. Could it have been inlined? Probably. Shouldn't inlining be switched off on a profiling build? Why? You generally want to profile the code's actual behavior, or as near as you can get to observing that. Defeating compiler optimizations doesn't sound like something that -pg should do on its own. If you really want it, there's a switch for it. Oprofile scares me with the sheer number of options. You can ignore practically all of them; the defaults are pretty sane. The recipe I usually follow is: Initial setup (only needed once per system boot): sudo opcontrol --init sudo opcontrol --setup --no-vmlinux (If you need detail about what the kernel is doing, you need kernel debug symbols and then specify them on the previous line) Start/stop profiling sudo opcontrol --start sudo opcontrol --reset ... exercise your debug-enabled program here ... sudo opcontrol --dump ; sudo opcontrol --shutdown The test case should run at least a minute or two to get numbers with reasonable accuracy. Analysis: opreport --long-filenames | more opreport -l image:/path/to/postgres | more if you really want detail: opannotate --source /path/to/postgres someplace regards, tom lane -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Thu, 11 Jun 2009, Tom Lane wrote: Oprofile scares me with the sheer number of options. You can ignore practically all of them; the defaults are pretty sane. Thanks, that was helpful. Here is the top of opreport --long-filenames: CPU: Core 2, speed 1998 MHz (estimated) Counted CPU_CLK_UNHALTED events (Clock cycles when not halted) with a unit mask of 0x00 (Unhalted core cycles) count 10 CPU_CLK_UNHALT...| samples| %| -- 5114464 61.5404 /lib/libc-2.9.so 1576829 18.9734 /changeable/pgsql_8.4_profiling/bin/postgres CPU_CLK_UNHALT...| samples| %| -- 1572346 99.7157 /changeable/pgsql_8.4_profiling/bin/postgres 4482 0.2842 [vdso] (tgid:13593 range:0x7fff8dbff000-0x7fff8dc0) 1 6.3e-05 [vdso] (tgid:13193 range:0x7fff8dbff000-0x7fff8dc0) 409534 4.9278 /no-vmlinux 309990 3.7300 /changeable/pgsql_8.4_profiling/lib/btree_gist.so 203684 2.4509 /changeable/pgsql_8.4_profiling/lib/bioseg.so So it seems that btree_gist and bioseg are not using that much CPU at all, compared to core postgres code. In fact, the majority of time seems to be spent in libc. Unfortunately my libc doesn't have any debugging symbols. Anyway, running opannotate seems to make it clear that time *is* spent in the gistnext function, but almost all of that is in children of the function. Lots of time is actually spent in fmgr_oldstyle though. Here is the top of opreport -l: CPU: Core 2, speed 1998 MHz (estimated) Counted CPU_CLK_UNHALTED events (Clock cycles when not halted) with a unit mask of 0x00 (Unhalted core cycles) count 10 samples %image name app name symbol name 5114464 61.5404 libc-2.9.so libc-2.9.so (no symbols) 4962155.9708 postgres postgres gistnext 4095344.9278 no-vmlinux no-vmlinux (no symbols) 4040374.8616 postgres postgres fmgr_oldstyle 1700792.0465 btree_gist.sobtree_gist.so gbt_int4_consistent 1600161.9254 postgres postgres gistdentryinit 1532661.8442 nvidia_drv.sonvidia_drv.so(no symbols) 1524631.8345 postgres postgres FunctionCall5 1493741.7974 postgres postgres FunctionCall1 1311121.5776 libxul.solibxul.so(no symbols) 1208711.4544 postgres postgres .plt 94506 1.1372 bioseg.sobioseg.so bioseg_gist_consistent I'm guessing my next step is to install a version of libc with debugging symbols? Matthew -- Some people, when confronted with a problem, think I know, I'll use regular expressions. Now they have two problems. -- Jamie Zawinski -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Matthew Wakeling matt...@flymine.org writes: So it seems that btree_gist and bioseg are not using that much CPU at all, compared to core postgres code. In fact, the majority of time seems to be spent in libc. Unfortunately my libc doesn't have any debugging symbols. hmm ... memcpy or qsort maybe? Anyway, running opannotate seems to make it clear that time *is* spent in the gistnext function, but almost all of that is in children of the function. Lots of time is actually spent in fmgr_oldstyle though. So it'd be worth converting your functions to V1 style. I'm guessing my next step is to install a version of libc with debugging symbols? Yeah, if you want to find out what's happening in libc, that's what you need. regards, tom lane -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Thu, 11 Jun 2009, Tom Lane wrote: So it'd be worth converting your functions to V1 style. Does that produce a significant reduction in overhead? (You'll probably say yes, that's the whole point). hmm ... memcpy or qsort maybe? Surprise: CPU: Core 2, speed 1998 MHz (estimated) Counted CPU_CLK_UNHALTED events (Clock cycles when not halted) with a unit mask of 0x00 (Unhalted core cycles) count 10 samples %image name app name symbol name 3005354 40.2868 libc-2.9.so libc-2.9.so __mcount_internal 1195592 16.0269 libc-2.9.so libc-2.9.so mcount 5499987.3727 postgres postgres gistnext 4204655.6363 postgres postgres fmgr_oldstyle 3763335.0447 no-vmlinux no-vmlinux (no symbols) 2109842.8282 postgres postgres FunctionCall5 1825092.4465 postgres postgres gistdentryinit 1743562.3372 btree_gist.sobtree_gist.so gbt_int4_consistent 1428291.9146 postgres postgres FunctionCall1 1298001.7400 postgres postgres .plt 1191801.5976 nvidia_drv.sonvidia_drv.so(no symbols) 96351 1.2916 libxul.solibxul.so(no symbols) 91726 1.2296 btree_gist.sobtree_gist.so gbt_num_consistent A quick grep in the postgres source for mcount reveals no hits. No idea what it does - there is no man page for it. Matthew -- I pause for breath to allow you to get over your shock that I really did cover all that in only five minutes...-- Computer Science Lecturer -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Thu, 11 Jun 2009, Matthew Wakeling wrote: A quick grep in the postgres source for mcount reveals no hits. No idea what it does - there is no man page for it. Ah - that's part of gprof. I'll recompile without --enable-profiling and try again. Duh. Matthew -- What goes up must come down. Ask any system administrator. -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Okay, I don't know quite what's happening here. Tom, perhaps you could
advise. Running opannotate --source, I get this sort of stuff:
/*
* Total samples for file :
.../postgresql-8.4beta2/src/backend/access/gist/gistget.c
*
* 6880 0.2680
*/
and then:
:static int64
:gistnext(IndexScanDesc scan, TIDBitmap *tbm)
81 0.0032 :{ /* gistnext total: 420087 16.3649 */
:Pagep;
The gistnext total doesn't seem to correspond to the amount I get by
adding up all the individual lines in gistnest. Moreover, it is greater
than the total samples attributed to the whole file, and greater than the
samples assigned to all the lines where gistnext is called.
However, yes it does seem like fmgr.c accounts for a large proportion of
samples. Also, I still seem to be getting mcount, even after recompiling
without --enable-profiling.
CPU: Core 2, speed 1998 MHz (estimated)
Counted CPU_CLK_UNHALTED events (Clock cycles when not halted) with a unit mask
of 0x00 (Unhalted core cycles) count 10
samples %image name app name symbol name
460213 17.9280 postgres postgres
fmgr_oldstyle
420087 16.3649 postgres postgres gistnext
2549759.9328 postgres postgres
FunctionCall5
2395729.3327 libc-2.9.so libc-2.9.so mcount
2199638.5689 libc-2.9.so libc-2.9.so
__mcount_internal
1256744.8957 no-vmlinux no-vmlinux (no symbols)
1171844.5650 postgres postgres
gistdentryinit
1069674.1670 btree_gist.sobtree_gist.so
gbt_int4_consistent
95677 3.7272 postgres postgres
FunctionCall1
75397 2.9372 bioseg.sobioseg.so
bioseg_gist_consistent
58832 2.2919 btree_gist.sobtree_gist.so
gbt_num_consistent
39128 1.5243 bioseg.sobioseg.so
bioseg_overlap
33874 1.3196 libxul.solibxul.so(no symbols)
32008 1.2469 bioseg.sobioseg.so
bioseg_gist_leaf_consistent
20890 0.8138 nvidia_drv.sonvidia_drv.so(no symbols)
19321 0.7527 bioseg.sobioseg.so
bioseg_gist_decompress
17365 0.6765 libmozjs.so.1d libmozjs.so.1d (no symbols)
Matthew
--
A good programmer is one who looks both ways before crossing a one-way street.
Considering the quality and quantity of one-way streets in Cambridge, it
should be no surprise that there are so many good programmers there.
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Matthew Wakeling matt...@flymine.org writes: The gistnext total doesn't seem to correspond to the amount I get by adding up all the individual lines in gistnest. Hmm, hadn't you determined that some other stuff was being inlined into gistnext? I'm not really sure how opannotate displays such cases, but this might be an artifact of that. However, yes it does seem like fmgr.c accounts for a large proportion of samples. Also, I still seem to be getting mcount, even after recompiling without --enable-profiling. You must still have some -pg code in there someplace. Maybe you didn't recompile bioseg.so, or even psql? Remember the libc counts you are looking at are for system-wide usage of libc. regards, tom lane -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Fri, 5 Jun 2009, Robert Haas wrote: On Thu, Jun 4, 2009 at 12:33 PM, Matthew Wakelingmatt...@flymine.org wrote: Do you have a recommendation for how to go about profiling Postgres, what profiler to use, etc? I'm running on Debian Linux x86_64. I mostly compile with --enable-profiling and use gprof. I know Tom Lane has had success with oprofile for quick and dirty measurements but I haven't quite figured out how to make all the bits work for that yet. Okay, I recompiled Postgres 8.4 beta 2 with profiling, installed btree_gist and bioseg, and did a large multi-column (btree_gist, bioseg) index search. EXPLAIN ANALYSE SELECT * FROM location l1, location l2 WHERE l1.objectid = l2.objectid AND bioseg_create(l1.intermine_start, l1.intermine_end) bioseg_create(l2.intermine_start, l2.intermine_end); QUERY PLAN --- Nested Loop (cost=0.01..9292374.77 rows=19468831 width=130) (actual time=0.337..24538315.569 rows=819811624 loops=1) - Seq Scan on location l1 (cost=0.00..90092.17 rows=4030117 width=65) (actual time=0.033..2561.142 rows=4030122 loops=1) - Index Scan using location_object_bioseg on location l2 (cost=0.01..1.58 rows=35 width=65) (actual time=0.467..5.990 rows=203 loops=4030122) Index Cond: ((l2.objectid = l1.objectid) AND (bioseg_create(l1.intermine_start, l1.intermine_end) bioseg_create(l2.intermine_start, l2.intermine_end))) Total runtime: 24613918.894 ms (5 rows) Here is the top of the profiling result: Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds secondscalls Ks/call Ks/call name 35.41 2087.04 2087.04 823841746 0.00 0.00 gistnext 15.36 2992.60 905.56 8560743382 0.00 0.00 fmgr_oldstyle 8.65 3502.37 509.77 3641723296 0.00 0.00 FunctionCall5 7.08 3919.87 417.50 3641723296 0.00 0.00 gistdentryinit 5.03 4216.59 296.72 6668 0.00 0.00 DirectFunctionCall1 3.84 4443.05 226.46 3641724371 0.00 0.00 FunctionCall1 2.32 4579.94 136.89 1362367466 0.00 0.00 hash_search_with_hash_value 1.89 4691.15 111.21 827892583 0.00 0.00 FunctionCall2 1.83 4799.27 108.12 FunctionCall6 1.77 4903.56 104.30 2799321398 0.00 0.00 LWLockAcquire 1.45 4989.2485.68 1043922430 0.00 0.00 PinBuffer 1.37 5070.1580.91 823844102 0.00 0.00 index_getnext 1.33 5148.2978.15 1647683886 0.00 0.00 slot_deform_tuple 0.95 5204.3656.07 738604164 0.00 0.00 heap_page_prune_opt The final cumulative time is 5894.06 seconds, which doesn't seem to match the query run time at all. Also, no calls to anything including bioseg in the name are recorded, although they are definitely called as the GiST support functions for that data type. Could someone give me a hand decyphering this result? It seems from this that the time is spent in the gistnext function (in src/backend/access/gist/gistget.c) and not its children. However, it's quite a large function containing several loops - is there a way to make the profiling result more specific? Matthew -- If you let your happiness depend upon how somebody else feels about you, now you have to control how somebody else feels about you. -- Abraham Hicks -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Matthew Wakeling matt...@flymine.org writes: The final cumulative time is 5894.06 seconds, which doesn't seem to match the query run time at all. Depending on the platform you're using, gprof might have the wrong idea about the kernel's tick rate, leading to its numbers being some multiple or fraction of the true elapsed time. I had that problem awhile back https://bugzilla.redhat.com/show_bug.cgi?id=151763 although I'd like to think it's fixed on all recent Linuxen. However, your bigger problem is here: Also, no calls to anything including bioseg in the name are recorded, although they are definitely called as the GiST support functions for that data type. I have never had any success in getting gprof to profile functions that are in loadable libraries, which of course is exactly what you need to do here. I have found hints on the web claiming that it's possible, but they don't work for me. gprof just ignores both the functions and the time spent in them. Personally I generally use oprofile these days, because it doesn't have that problem and also doesn't require any special build options. If you don't have that available to you, the best bet is probably to make a test build of Postgres in which your functions are linked directly into the main postgres executable. regards, tom lane -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Thu, Jun 4, 2009 at 12:33 PM, Matthew Wakelingmatt...@flymine.org wrote: Do you have a recommendation for how to go about profiling Postgres, what profiler to use, etc? I'm running on Debian Linux x86_64. I mostly compile with --enable-profiling and use gprof. I know Tom Lane has had success with oprofile for quick and dirty measurements but I haven't quite figured out how to make all the bits work for that yet. ...Robert -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
[PERFORM] GiST index performance
Revisiting the thread a month back or so, I'm still investigating performance problems with GiST indexes in Postgres. Looking at http://wiki.postgresql.org/wiki/PostgreSQL_8.4_Open_Items I'd like to clarify the contrib/seg issue. Contrib/seg is vulnerable to pathological behaviour which is fixed by my second patch, which can be viewed as complete. Contrib/cube, being multi-dimensional, is not affected to any significant degree, so should not need alteration. A second quite distinct issue is the general performance of GiST indexes which is also mentioned in the old thread linked from Open Items. For that, we have a test case at http://archives.postgresql.org/pgsql-performance/2009-04/msg00276.php for btree_gist indexes. I have a similar example with the bioseg GiST index. I have completely reimplemented the same algorithms in Java for algorithm investigation and instrumentation purposes, and it runs about a hundred times faster than in Postgres. I think this is a problem, and I'm willing to do some investigation to try and solve it. Do you have a recommendation for how to go about profiling Postgres, what profiler to use, etc? I'm running on Debian Linux x86_64. Matthew -- Jadzia: Don't forget the 34th rule of acquisition: Peace is good for business. Quark: That's the 35th. Jadzia: Oh yes, that's right. What's the 34th again? Quark: War is good for business. It's easy to get them mixed up. -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Wed, 6 May 2009, Tom Lane wrote: Matthew Wakeling matt...@flymine.org writes: Here is my patch ported over to the seg contrib package, attached. Apply it to seg.c and all should be well. A similar thing needs to be done to cube, but I haven't looked at that. Teodor, Oleg, do you intend to review/apply this patch? Tom, I just returned from trek around Annapurna and just learned about Matthew's experiments, Teodor is in holidays and will be available after May 11, then there are should be PGCon, so if it can wait, we could look on this after PGCon. Matthew, did you try various data ? From our experience we learned there are can be various corner cases. Regards, Oleg _ Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru), Sternberg Astronomical Institute, Moscow University, Russia Internet: o...@sai.msu.su, http://www.sai.msu.su/~megera/ phone: +007(495)939-16-83, +007(495)939-23-83 -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Thu, 7 May 2009, Oleg Bartunov wrote: Did you try Guttman quadratic split algorithm ? We also found linear split algorithm for Rtree. The existing (bugfixed) seg split algorithm is the Guttman quadratic split algorithm. Guttman did all his work on two-dimensional and above data, dismissing one-dimensional data as being handled adequately by B-trees, which is not true for segment overlaps. It turns out that the algorithm has a weakness with certain types of data, and one-dimensional data is almost certain to exercise that weakness. The greater the number of dimensions, the less the weakness is exercised. The problem is that the algorithm does not calculate a split pivot. Instead it finds two suitable entries, and adds the remaining entries to those two in turn. This can lead to the majority of the entries being added to just one side. In fact, I saw lots of cases where 367 entries were being split into two pages of 366 and one entry. Guttman's linear split algorithm has the same weakness. One thing I am seeing is a really big difference in performance between Postgres/GiST and a Java implementation I have written, using the same algorithms. Postgres takes three minutes to perform a set of index lookups while java takes six seconds. The old version of bioseg took an hour. I can't see anything in the GiST support code that could account for this. is the number of index lookups different, or just index lookup time is very big ? Same number of index lookups. Same algorithms. I have a set of 681879 segments, and I load them all into the index. I then query the index for overlaps for each one in turn. For some reason, GiST lookups seem to be slow, even if they are using a good algorithm. I have seen that problem with btree_gist on integers too. I can't see any reason for this is the GiST code - it all seems pretty tight to me. We probably need to do some profiling. Matthew -- I suppose some of you have done a Continuous Maths course. Yes? Continuous Maths? menacing stares from audience Whoah, it was like that, was it! -- Computer Science Lecturer -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Matthew Wakeling matt...@flymine.org writes: Here is my patch ported over to the seg contrib package, attached. Apply it to seg.c and all should be well. A similar thing needs to be done to cube, but I haven't looked at that. Teodor, Oleg, do you intend to review/apply this patch? regards, tom lane -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Tue, 21 Apr 2009, Matthew Wakeling wrote: Unfortunately, it seems there is another bug in the picksplit function. My patch fixes a bug that reveals this new bug. The whole picksplit algorithm is fundamentally broken, and needs to be rewritten completely, which is what I am doing. I have now rewritten the picksplit and penalty functions for the bioseg data type, and they perform much better. The index size is now 164MB, compared to 350MB or so originally, and 2400MB after my earlier bugfix. Execution time of one of our queries (basically a nested loop join over a sequential scan and an index lookup in this index type) has gone down from 45 minutes to two minutes. I have abandoned Guttman's poly time split algorithm. A fundamental flaw in the picksplit algorithm is that it would create two separate target sets, and incrementally add entries to whichever one would grow the least in range size. However, if the entries arrived in any sort of order, they would all be added to the one set, growing it by a small amount each time. This caused the picksplit algorithm to split a set of 367 entries into a set of 366 and a set of one a high proportion of the time. I have replaced the picksplit algorithm with a simple one. For each range element, find the midpoint of the range. Then find the mean of all the midpoints. All elements with a midpoint below the mean go in one set, and the others go in the second set. This usually splits the entries in a meaningful way. I have also changed the penalty function. Previously, the penalty was the amount that the range would have to expand. So, if a new element fitted inside the existing range, then the penalty is zero. I have changed it to create a tie-break between multiple index pages that the element would fit in without expanding the range - the element should be inserted into the index page with the smallest range. This prevents large elements from messing up the index by forcing a large index page range that sucks in all the elements in the whole area into a non-selective group. I may experiment with improving these functions further. The main problem with this index is the fact that I need to index ranges with a wide variety of widths, and I have a couple more strategies yet to help with that. I will post a patch when I have ported my bioseg code over to the seg data type. Matthew -- Riker: Our memory pathways have become accustomed to your sensory input. Data: I understand - I'm fond of you too, Commander. And you too Counsellor -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Wed, 22 Apr 2009, Matthew Wakeling wrote:
I will post a patch when I have ported my bioseg code over to the seg data
type.
Here is my patch ported over to the seg contrib package, attached. Apply
it to seg.c and all should be well. A similar thing needs to be done to
cube, but I haven't looked at that.
Matthew
--
An optimist sees the glass as half full, a pessimist as half empty,
and an engineer as having redundant storage capacity.--- seg.c 2006-09-10 18:36:51.0 +0100
+++ seg.c_new 2009-04-22 17:03:13.0 +0100
@@ -69,7 +69,6 @@
bool seg_right(SEG * a, SEG * b);
bool seg_over_right(SEG * a, SEG * b);
SEG *seg_union(SEG * a, SEG * b);
-SEG *seg_inter(SEG * a, SEG * b);
void rt_seg_size(SEG * a, float *sz);
float *seg_size(SEG * a);
@@ -269,14 +268,22 @@
gseg_penalty(GISTENTRY *origentry, GISTENTRY *newentry, float *result)
{
SEG*ud;
+SEG*origrange;
+SEG*newrange;
float tmp1,
tmp2;
- ud = seg_union((SEG *) DatumGetPointer(origentry-key),
- (SEG *) DatumGetPointer(newentry-key));
+origrange = (SEG *) DatumGetPointer(origentry-key);
+newrange = (SEG *) DatumGetPointer(newentry-key);
+ ud = seg_union(origrange, newrange);
rt_seg_size(ud, tmp1);
- rt_seg_size((SEG *) DatumGetPointer(origentry-key), tmp2);
- *result = tmp1 - tmp2;
+ rt_seg_size(origrange, tmp2);
+if (tmp1 == tmp2) {
+rt_seg_size(newrange, tmp1);
+*result = (tmp2 - tmp1) / tmp2;
+} else {
+*result = tmp1 - tmp2 + 1.0;
+}
#ifdef GIST_DEBUG
fprintf(stderr, penalty\n);
@@ -297,27 +304,16 @@
GIST_SPLITVEC *v)
{
OffsetNumber i,
- j;
SEG*datum_alpha,
- *datum_beta;
SEG*datum_l,
*datum_r;
- SEG*union_d,
- *union_dl,
- *union_dr;
- SEG*inter_d;
- boolfirsttime;
- float size_alpha,
- size_beta,
- size_union,
- size_inter;
- float size_waste,
- waste;
- float size_l,
- size_r;
+boolfirsttime;
+ float lowest,
+ highest,
+midpoint,
+split,
+midpointsum;
int nbytes;
- OffsetNumber seed_1 = 1,
- seed_2 = 2;
OffsetNumber *left,
*right;
OffsetNumber maxoff;
@@ -326,107 +322,64 @@
fprintf(stderr, picksplit\n);
#endif
- maxoff = entryvec-n - 2;
+ maxoff = entryvec-n - 1;
nbytes = (maxoff + 2) * sizeof(OffsetNumber);
v-spl_left = (OffsetNumber *) palloc(nbytes);
v-spl_right = (OffsetNumber *) palloc(nbytes);
+midpointsum = 0.0;
firsttime = true;
- waste = 0.0;
+lowest = 0.0;
+highest = 0.0;
- for (i = FirstOffsetNumber; i maxoff; i = OffsetNumberNext(i))
+ for (i = FirstOffsetNumber; i = maxoff; i = OffsetNumberNext(i))
{
datum_alpha = (SEG *) DatumGetPointer(entryvec-vector[i].key);
- for (j = OffsetNumberNext(i); j = maxoff; j =
OffsetNumberNext(j))
- {
- datum_beta = (SEG *)
DatumGetPointer(entryvec-vector[j].key);
-
- /* compute the wasted space by unioning these guys */
- /* size_waste = size_union - size_inter; */
- union_d = seg_union(datum_alpha, datum_beta);
- rt_seg_size(union_d, size_union);
- inter_d = seg_inter(datum_alpha, datum_beta);
- rt_seg_size(inter_d, size_inter);
- size_waste = size_union - size_inter;
-
- /*
-* are these a more promising split that what we've
already seen?
-*/
- if (size_waste waste || firsttime)
- {
- waste = size_waste;
- seed_1 = i;
- seed_2 = j;
- firsttime = false;
- }
- }
+midpoint = (datum_alpha-lower + datum_alpha-upper) / 2;
+midpointsum += midpoint;
+if (firsttime || (midpoint lowest))
+{
+lowest = midpoint;
+}
+if (firsttime || (midpoint highest))
+{
+
Re: [PERFORM] GiST index performance
On Mon, 20 Apr 2009, Teodor Sigaev wrote: Looks like contrib/cube has the same error. I don't see a similar code pattern elsewhere though. Oleg, Teodor, do you concur that this is a correct patch? Is it safe to back-patch (I think it should be)? Yeah, good catch, and it doesn't touch any already-on-disk data. Although release notes should mention advice about REINDEX seg and cube opclasses. Unfortunately, it seems there is another bug in the picksplit function. My patch fixes a bug that reveals this new bug. The whole picksplit algorithm is fundamentally broken, and needs to be rewritten completely, which is what I am doing. If you apply my patch, then index sizes will go up by a factor of ten or so, because the picksplit function tends to split the set of 367 ranges into one set of 366 and another set of 1, leading to a horribly unbalanced tree. Before the patch, the different branches of the tree were unselective, so new entries would just get stuffed in anywhere, leading to a much more balanced tree. I shall have a proper fix to this problem later today. Matthew -- It's one of those irregular verbs - I have an independent mind, You are an eccentric, He is round the twist. -- Bernard Woolly, Yes Prime Minister -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Fri, 17 Apr 2009, Matthew Wakeling wrote:
I have done a bit of investigation, and I think I might have found the
smoking gun I was looking for.
I have found a bug in the contrib package seg, which has been copied into
the bioseg data type as well. It causes the index to be created with
horribly bad unselective trees, so that when a search is performed many of
the branches of the tree need to be followed. This explanation does not
extend to btree_gist, so I will have to further investigate that. Apply
the following patch to contrib/seg/seg.c:
*** seg.c 2006-09-10 18:36:51.0 +0100
--- seg.c_new 2009-04-20 15:02:52.0 +0100
***
*** 426,432
else
{
datum_r = union_dr;
! size_r = size_alpha;
*right++ = i;
v-spl_nright++;
}
--- 426,432
else
{
datum_r = union_dr;
! size_r = size_beta;
*right++ = i;
v-spl_nright++;
}
Matthew
--
The early bird gets the worm. If you want something else for breakfast, get
up later.
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Matthew Wakeling matt...@flymine.org writes:
I have found a bug in the contrib package seg, which has been copied into
the bioseg data type as well. It causes the index to be created with
horribly bad unselective trees, so that when a search is performed many of
the branches of the tree need to be followed. This explanation does not
extend to btree_gist, so I will have to further investigate that. Apply
the following patch to contrib/seg/seg.c:
*** seg.c 2006-09-10 18:36:51.0 +0100
--- seg.c_new 2009-04-20 15:02:52.0 +0100
***
*** 426,432
else
{
datum_r = union_dr;
! size_r = size_alpha;
*right++ = i;
v-spl_nright++;
}
--- 426,432
else
{
datum_r = union_dr;
! size_r = size_beta;
*right++ = i;
v-spl_nright++;
}
Looks like contrib/cube has the same error. I don't see a similar code
pattern elsewhere though. Oleg, Teodor, do you concur that this is a
correct patch? Is it safe to back-patch (I think it should be)?
regards, tom lane
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Thu, 16 Apr 2009, Tom Lane wrote: Matthew, can you put together a self-contained test case with a similar slowdown? I have done a bit of investigation, and I think I might have found the smoking gun I was looking for. I just added a load of debug to the gist consistent function on the bioseg type, and did a single overlap lookup in the index. The index contains values ranging from 1 to 28,000,000 or so. The range I looked up was 23503297..23504738 (so a very small proportion). The index contains 375154 entries. The index returned 59 rows. The consistent method was called 54022 times - 5828 times for branch (internal) index entries, and 48194 times for leaf entries. Obviously this is a really bad index layout - scanning that many entries for such a small output. In fact, I saw lots of overlapping branch index entries, so the index isn't actually differentiating between the different branches of the tree very well. This indicates a failure of the picksplit or the penalty functions. I shall investigate this further next week. I shall also investigate whether this is the exact same problem that I had with the int4 gist system. Matthew -- So, given 'D' is undeclared too, with a default of zero, C++ is equal to D. mnw21, commenting on the Surely the value of C++ is zero, but C is now 1 response to No, C++ isn't equal to D. 'C' is undeclared [...] C++ should really be called 1 response to C++ -- shouldn't it be called D? -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
[PERFORM] GiST index performance
I have been doing some queries that are best answered with GiST indexes, however I have found that their performance is a little lacking. I thought I would do a direct comparison on a level playing field. Here are two EXPLAIN ANALYSE results for the same query, with two different indexes. The two indexes are identical except that one is btree and the other GiST. Here is the query: SELECT * FROM location l1, location l2, gene, primer WHERE l1.subjectid l2.subjectid AND l1.objectid = l2.objectid AND l1.subjectid = gene.id AND l2.subjectid = primer.id AND l2.intermine_start = l1.intermine_start AND l2.intermine_end = l1.intermine_start Here is the btree index: CREATE INDEX location_object_start ON location (objectid, intermine_start); QUERY PLAN -- Hash Join (cost=26213.16..135980894.76 rows=3155740824 width=484) (actual time=2799.260..14256.588 rows=2758 loops=1) Hash Cond: (l1.subjectid = gene.id) - Nested Loop (cost=0.00..4364485.01 rows=8891802645 width=324) (actual time=9.748..10418.807 rows=390695 loops=1) Join Filter: (l1.subjectid l2.subjectid) - Nested Loop (cost=0.00..446862.58 rows=572239 width=259) (actual time=9.720..4226.117 rows=211880 loops=1) - Seq Scan on primer (cost=0.00..15358.80 rows=211880 width=194) (actual time=9.678..579.877 rows=211880 loops=1) - Index Scan using location__key_all on location l2 (cost=0.00..2.00 rows=3 width=65) (actual time=0.004..0.007 rows=1 loops=211880) Index Cond: (l2.subjectid = primer.id) - Index Scan using location_object_start on location l1 (cost=0.00..3.85 rows=150 width=65) (actual time=0.005..0.012 rows=3 loops=211880) Index Cond: ((l1.objectid = l2.objectid) AND (l2.intermine_start = l1.intermine_start) AND (l2.intermine_end = l1.intermine_start)) - Hash (cost=20496.96..20496.96 rows=457296 width=160) (actual time=2788.698..2788.698 rows=457296 loops=1) - Seq Scan on gene (cost=0.00..20496.96 rows=457296 width=160) (actual time=0.038..1420.604 rows=457296 loops=1) Total runtime: 14263.846 ms (13 rows) Here is the GiST index: CREATE INDEX location_object_start_gist ON location USING gist (objectid, intermine_start); QUERY PLAN Hash Join (cost=26213.16..136159960.32 rows=3155740824 width=484) (actual time=2576.109..2300486.267 rows=2758 loops=1) Hash Cond: (l1.subjectid = gene.id) - Nested Loop (cost=0.00..4543550.56 rows=8891802645 width=324) (actual time=366.121..2296668.740 rows=390695 loops=1) Join Filter: (l1.subjectid l2.subjectid) - Nested Loop (cost=0.00..446862.58 rows=572239 width=259) (actual time=362.774..13423.443 rows=211880 loops=1) - Seq Scan on primer (cost=0.00..15358.80 rows=211880 width=194) (actual time=319.559..1296.907 rows=211880 loops=1) - Index Scan using location__key_all on location l2 (cost=0.00..2.00 rows=3 width=65) (actual time=0.041..0.045 rows=1 loops=211880) Index Cond: (l2.subjectid = primer.id) - Index Scan using location_object_start_gist on location l1 (cost=0.00..4.16 rows=150 width=65) (actual time=3.354..10.757 rows=3 loops=211880) Index Cond: ((l1.objectid = l2.objectid) AND (l2.intermine_start = l1.intermine_start) AND (l2.intermine_end = l1.intermine_start)) - Hash (cost=20496.96..20496.96 rows=457296 width=160) (actual time=2157.914..2157.914 rows=457296 loops=1) - Seq Scan on gene (cost=0.00..20496.96 rows=457296 width=160) (actual time=3.904..1206.907 rows=457296 loops=1) Total runtime: 2300510.674 ms (13 rows) The query plans are identical except in the type of index used, but there is a factor of a few hundred in execute time. Is this the kind of factor that would be expected, or is there something amiss? Is this seen as something that might be improved in the future? Matthew -- We have always been quite clear that Win95 and Win98 are not the systems to use if you are in a hostile security environment. We absolutely do recognize that the Internet is a hostile environment. Paul Leach pau...@microsoft.com -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Matthew Wakeling matt...@flymine.org wrote: I have been doing some queries that are best answered with GiST indexes For what definition of best answered? Since an index is only a performance tuning feature (unless declared UNIQUE), and should never alter the results (beyond possibly affecting row order if that is unspecified), how is an index which performs worse than an alternative the best answer? -Kevin -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Thu, 16 Apr 2009, Kevin Grittner wrote: Matthew Wakeling matt...@flymine.org wrote: I have been doing some queries that are best answered with GiST indexes For what definition of best answered? Since an index is only a performance tuning feature (unless declared UNIQUE), and should never alter the results (beyond possibly affecting row order if that is unspecified), how is an index which performs worse than an alternative the best answer? Don't be misled by my example using integers. I'm doing queries on the bioseg data type, and the only index type for that is GiST. There isn't a better alternative. Matthew -- Finger to spiritual emptiness underlying everything. -- How a foreign C manual referred to a pointer to void. -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Kevin Grittner kevin.gritt...@wicourts.gov writes: Matthew Wakeling matt...@flymine.org wrote: I have been doing some queries that are best answered with GiST indexes For what definition of best answered? Since an index is only a performance tuning feature (unless declared UNIQUE), and should never alter the results (beyond possibly affecting row order if that is unspecified), how is an index which performs worse than an alternative the best answer? The main point of GIST is to be able to index queries that simply are not indexable in btree. So I assume that Matthew is really worried about some queries that are not btree-indexable. One would fully expect btree to beat out GIST for btree-indexable cases. I think the significant point here is that it's winning by a factor of a couple hundred; that's pretty awful, and might point to some implementation problem. Matthew, can you put together a self-contained test case with a similar slowdown? Also, what are the physical sizes of the two indexes? I notice that the inner nestloop join gets slower too, when it's not changed at all --- that suggests that the overall I/O load is a lot worse, so maybe the reason the query is falling off a performance cliff is that the GIST index fails to fit in cache. regards, tom lane -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Thu, 16 Apr 2009, dforum wrote: there is other performance problem on this request. If you analyse query plan, you see that most of the time are lost during sequencial scan, and you have 2 seq scan. Nonsense. Sequential scans account for all of one or two seconds of processing in these queries, which are 14 seconds and 38 minutes respectively. Matthew -- Doctor: Are you okay? You appear to be injured. Neelix: Aaah! Doctor: It's okay, it looks superficial. Neelix: Am I going to die? Doctor: Not unless you are allergic to tomatoes. This appears to be a sauce some kind. -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
hello, there is other performance problem on this request. If you analyse query plan, you see that most of the time are lost during sequencial scan, and you have 2 seq scan. You have to create other indexes to match the request. Postgresq is totally dependant on index to reach is performance. Regarding gist or btree, I personnaly had better performance with btree. Regards david Matthew Wakeling a écrit : I have been doing some queries that are best answered with GiST indexes, however I have found that their performance is a little lacking. I thought I would do a direct comparison on a level playing field. Here are two EXPLAIN ANALYSE results for the same query, with two different indexes. The two indexes are identical except that one is btree and the other GiST. Here is the query: SELECT * FROM location l1, location l2, gene, primer WHERE l1.subjectid l2.subjectid AND l1.objectid = l2.objectid AND l1.subjectid = gene.id AND l2.subjectid = primer.id AND l2.intermine_start = l1.intermine_start AND l2.intermine_end = l1.intermine_start Here is the btree index: CREATE INDEX location_object_start ON location (objectid, intermine_start); QUERY PLAN -- Hash Join (cost=26213.16..135980894.76 rows=3155740824 width=484) (actual time=2799.260..14256.588 rows=2758 loops=1) Hash Cond: (l1.subjectid = gene.id) - Nested Loop (cost=0.00..4364485.01 rows=8891802645 width=324) (actual time=9.748..10418.807 rows=390695 loops=1) Join Filter: (l1.subjectid l2.subjectid) - Nested Loop (cost=0.00..446862.58 rows=572239 width=259) (actual time=9.720..4226.117 rows=211880 loops=1) - Seq Scan on primer (cost=0.00..15358.80 rows=211880 width=194) (actual time=9.678..579.877 rows=211880 loops=1) - Index Scan using location__key_all on location l2 (cost=0.00..2.00 rows=3 width=65) (actual time=0.004..0.007 rows=1 loops=211880) Index Cond: (l2.subjectid = primer.id) - Index Scan using location_object_start on location l1 (cost=0.00..3.85 rows=150 width=65) (actual time=0.005..0.012 rows=3 loops=211880) Index Cond: ((l1.objectid = l2.objectid) AND (l2.intermine_start = l1.intermine_start) AND (l2.intermine_end = l1.intermine_start)) - Hash (cost=20496.96..20496.96 rows=457296 width=160) (actual time=2788.698..2788.698 rows=457296 loops=1) - Seq Scan on gene (cost=0.00..20496.96 rows=457296 width=160) (actual time=0.038..1420.604 rows=457296 loops=1) Total runtime: 14263.846 ms (13 rows) Here is the GiST index: CREATE INDEX location_object_start_gist ON location USING gist (objectid, intermine_start); QUERY PLAN Hash Join (cost=26213.16..136159960.32 rows=3155740824 width=484) (actual time=2576.109..2300486.267 rows=2758 loops=1) Hash Cond: (l1.subjectid = gene.id) - Nested Loop (cost=0.00..4543550.56 rows=8891802645 width=324) (actual time=366.121..2296668.740 rows=390695 loops=1) Join Filter: (l1.subjectid l2.subjectid) - Nested Loop (cost=0.00..446862.58 rows=572239 width=259) (actual time=362.774..13423.443 rows=211880 loops=1) - Seq Scan on primer (cost=0.00..15358.80 rows=211880 width=194) (actual time=319.559..1296.907 rows=211880 loops=1) - Index Scan using location__key_all on location l2 (cost=0.00..2.00 rows=3 width=65) (actual time=0.041..0.045 rows=1 loops=211880) Index Cond: (l2.subjectid = primer.id) - Index Scan using location_object_start_gist on location l1 (cost=0.00..4.16 rows=150 width=65) (actual time=3.354..10.757 rows=3 loops=211880) Index Cond: ((l1.objectid = l2.objectid) AND (l2.intermine_start = l1.intermine_start) AND (l2.intermine_end = l1.intermine_start)) - Hash (cost=20496.96..20496.96 rows=457296 width=160) (actual time=2157.914..2157.914 rows=457296 loops=1) - Seq Scan on gene (cost=0.00..20496.96 rows=457296 width=160) (actual time=3.904..1206.907 rows=457296 loops=1) Total runtime: 2300510.674 ms (13 rows) The query plans are identical except in the type of index used, but there is a factor of a few hundred in execute time. Is this the kind of factor that would be expected, or is there something amiss? Is this seen as something that might be improved in the future? Matthew -- Sent via pgsql-performance mailing
Re: [PERFORM] GiST index performance
dforum dfor...@vieonet.com writes: If you analyse query plan, you see that most of the time are lost during sequencial scan, and you have 2 seq scan. I think you missed the loops count. - Index Scan using location_object_start_gist on location l1 (cost=0.00..4.16 rows=150 width=65) (actual time=3.354..10.757 rows=3 loops=211880) Index Cond: ((l1.objectid = l2.objectid) AND (l2.intermine_start = l1.intermine_start) AND (l2.intermine_end = l1.intermine_start)) This indexscan is accounting for 10.757 * 211880 msec, which is 99% of the runtime. regards, tom lane -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Thu, 16 Apr 2009, Tom Lane wrote: Matthew, can you put together a self-contained test case with a similar slowdown? It isn't the smoking gun I thought it would be, but: CREATE TABLE a AS SELECT a FROM generate_series(1,100) AS a(a); CREATE TABLE b AS SELECT b FROM generate_series(1,100) AS b(b); ANALYSE; CREATE INDEX a_a ON a (a); EXPLAIN ANALYSE SELECT * FROM a, b WHERE a.a BETWEEN b.b AND b.b + 2; DROP INDEX a_a; CREATE INDEX a_a ON a USING gist (a); EXPLAIN ANALYSE SELECT * FROM a, b WHERE a.a BETWEEN b.b AND b.b + 2; I see four seconds versus thirty seconds. The difference was much greater on my non-test-case - I wonder if multi-column indexing has something to do with it. Also, what are the physical sizes of the two indexes? relname | pg_size_pretty + location_object_start_gist | 193 MB location_object_start | 75 MB (2 rows) I notice that the inner nestloop join gets slower too, when it's not changed at all --- that suggests that the overall I/O load is a lot worse, so maybe the reason the query is falling off a performance cliff is that the GIST index fails to fit in cache. Memory in the machine is 16GB. Matthew -- [About NP-completeness] These are the problems that make efficient use of the Fairy Godmother.-- Computer Science Lecturer -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
Matthew Wakeling matt...@flymine.org writes: On Thu, 16 Apr 2009, Tom Lane wrote: Also, what are the physical sizes of the two indexes? location_object_start_gist | 193 MB location_object_start | 75 MB I notice that the inner nestloop join gets slower too, when it's not changed at all --- that suggests that the overall I/O load is a lot worse, so maybe the reason the query is falling off a performance cliff is that the GIST index fails to fit in cache. Memory in the machine is 16GB. Hmm, and what is shared_buffers set to? How big are the tables and other indexes used in the query? We still have to explain why the inner nestloop got slower, and it's hard to see that unless something stopped fitting in cache. regards, tom lane -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
Re: [PERFORM] GiST index performance
On Thu, 16 Apr 2009, Tom Lane wrote: Hmm, and what is shared_buffers set to? How big are the tables and other indexes used in the query? We still have to explain why the inner nestloop got slower, and it's hard to see that unless something stopped fitting in cache. I just noticed that someone has started running a big java program (6GB RAM so far) on that machine. Maybe it was running during the bad run. I'll see if I can re-run those two queries later on when the machine is idle. shared_buffers = 500MB Location table: 336 MB Gene table: 124 MB Primer table: 103 MB location__key_all index: 334 MB Matthew -- For those of you who are into writing programs that are as obscure and complicated as possible, there are opportunities for... real fun here -- Computer Science Lecturer -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
