FAQ

[PostgreSQL-Hackers] Qual evaluation cost estimates for GIN indexes

Tom Lane
Feb 16, 2012 at 11:15 pm
I looked into the complaint here of poor estimation for GIN indexscans:
http://archives.postgresql.org/pgsql-performance/2012-02/msg00028.php
At first glance it sounds like a mistake in selectivity estimation,
but it isn't: the rowcount estimates are pretty nearly dead on.
The problem is in the planner's estimate of the cost of executing the
@@ operator. We have pg_proc.procost set to 1 for ts_match_vq, but
actually it's a good deal more expensive than that. Some
experimentation suggests that @@ might be about 500 times as expensive
as a simple integer comparison. I don't propose pushing its procost
up that much, but surely at least 10 would be appropriate, maybe even
100.

However ... if you just alter pg_proc.procost in Marc's example, the
planner *still* picks a seqscan, even though its estimate of the seqscan
cost surely does go up. The reason is that its estimate of the GIN
indexscan cost goes up just as much, since we charge one qual eval cost
per returned tuple in gincostestimate. It is easy to tell from the
actual runtimes that that is not what's happening in a GIN indexscan;
we are not re-executing the @@ operator for every tuple. But the
planner's cost model doesn't know that.

There are a couple of issues that would have to be addressed to make
this better:

1. If we shouldn't charge procost per row, what should we charge?
It's probably reasonable to assume that the primitive GIN-index-entry
comparison operations have cost equal to one cpu_operator_cost
regardless of what's assigned to the user-visible operators, but I'm
not convinced that that's sufficient to model complicated operators.
It might be okay to charge that much per index entry visited rather
than driving it off the number of heap tuples returned. The code in
gincostestimate goes to considerable lengths to estimate the number of
index pages fetched, and it seems like it might be able to derive the
number of index entries visited too, but it's not trying to account for
any CPU costs at the moment.

2. What about lossy operators, or lossy bitmap scans? If either of
those things happen, we *will* re-execute the @@ operator at visited
tuples, so discounting its high cost would be a mistake. But the
planner has no information about either effect, since we moved all
support for lossiness to runtime.

I think it was point #2 that led us to not consider these issues before.
But now that we've seen actual cases where the planner makes a poor
decision because it's not modeling this effect, I think we ought to try
to do something about it.

I haven't got time to do anything about this for 9.2, and I bet you
don't either, but it ought to be on the TODO list to try to improve
this.

BTW, an entirely different line of thought is "why on earth is @@ so
frickin expensive, when it's comparing already-processed tsvectors
with only a few entries to an already-processed tsquery with only one
entry??". This test case suggests to me that there's something
unnecessarily slow in there, and a bit of micro-optimization effort
might be well repaid.

regards, tom lane
reply

Search Discussions

7 responses

  • Tom Lane at Feb 16, 2012 at 11:31 pm

    I wrote:
    BTW, an entirely different line of thought is "why on earth is @@ so
    frickin expensive, when it's comparing already-processed tsvectors
    with only a few entries to an already-processed tsquery with only one
    entry??". This test case suggests to me that there's something
    unnecessarily slow in there, and a bit of micro-optimization effort
    might be well repaid.
    Oh, scratch that: a bit of oprofiling shows that while the tsvectors
    aren't all that long, they are long enough to get compressed, and most
    of the runtime is going into pglz_decompress not @@ itself. So this
    goes back to the known issue that the planner ought to try to account
    for detoasting costs.

    regards, tom lane
  • Robert Haas at Feb 17, 2012 at 2:21 am

    On Thu, Feb 16, 2012 at 6:30 PM, Tom Lane wrote:
    I wrote:
    BTW, an entirely different line of thought is "why on earth is @@ so
    frickin expensive, when it's comparing already-processed tsvectors
    with only a few entries to an already-processed tsquery with only one
    entry??".  This test case suggests to me that there's something
    unnecessarily slow in there, and a bit of micro-optimization effort
    might be well repaid.
    Oh, scratch that: a bit of oprofiling shows that while the tsvectors
    aren't all that long, they are long enough to get compressed, and most
    of the runtime is going into pglz_decompress not @@ itself.  So this
    goes back to the known issue that the planner ought to try to account
    for detoasting costs.
    This issue of detoasting costs comes up a lot, specifically in
    reference to @@. I wonder if we shouldn't try to apply some quick and
    dirty hack in time for 9.2, like maybe random_page_cost for every row
    or every attribute we think will require detoasting. That's obviously
    going to be an underestimate in many if not most cases, but it would
    probably still be an improvement over assuming that detoasting is
    free.

    --
    Robert Haas
    EnterpriseDB: http://www.enterprisedb.com
    The Enterprise PostgreSQL Company
  • Tom Lane at Feb 17, 2012 at 3:10 am

    Robert Haas writes:
    This issue of detoasting costs comes up a lot, specifically in
    reference to @@. I wonder if we shouldn't try to apply some quick and
    dirty hack in time for 9.2, like maybe random_page_cost for every row
    or every attribute we think will require detoasting. That's obviously
    going to be an underestimate in many if not most cases, but it would
    probably still be an improvement over assuming that detoasting is
    free.
    Well, you can't theorize without data, to misquote Sherlock. We'd need
    to have some stats on which to base "we think this will require
    detoasting". I guess we could teach ANALYZE to compute and store
    fractions "percent of entries in this column that are compressed"
    and "percent that are stored out-of-line", and then hope that those
    percentages apply to the subset of entries that a given query will
    visit, and thereby derive a number of operations to multiply by whatever
    we think the cost-per-detoast-operation is.

    It's probably all do-able, but it seems way too late to be thinking
    about this for 9.2. We've already got a ton of new stuff that needs
    to be polished and tuned...

    regards, tom lane
  • Jesper Krogh at Feb 17, 2012 at 6:10 am
    Hi.

    First, thanks for looking at this. Except from GIN indexes and
    full-text-search being really good in our applications, this also
    points to those excact places where it can be improved.
    On 2012-02-17 00:15, Tom Lane wrote:
    I looked into the complaint here of poor estimation for GIN indexscans:
    http://archives.postgresql.org/pgsql-performance/2012-02/msg00028.php
    I think this is the excact same issue:
    http://archives.postgresql.org/pgsql-hackers/2011-11/msg01754.php
    At first glance it sounds like a mistake in selectivity estimation,
    but it isn't: the rowcount estimates are pretty nearly dead on.
    The problem is in the planner's estimate of the cost of executing the
    @@ operator. We have pg_proc.procost set to 1 for ts_match_vq, but
    actually it's a good deal more expensive than that. Some
    experimentation suggests that @@ might be about 500 times as expensive
    as a simple integer comparison. I don't propose pushing its procost
    up that much, but surely at least 10 would be appropriate, maybe even
    100.

    However ... if you just alter pg_proc.procost in Marc's example, the
    planner *still* picks a seqscan, even though its estimate of the seqscan
    cost surely does go up. The reason is that its estimate of the GIN
    indexscan cost goes up just as much, since we charge one qual eval cost
    per returned tuple in gincostestimate. It is easy to tell from the
    actual runtimes that that is not what's happening in a GIN indexscan;
    we are not re-executing the @@ operator for every tuple. But the
    planner's cost model doesn't know that.
    There is something about lossy vs. non-lossy, if the index-result
    is lossy, then it would "need" to execute the @@ operator
    on each tuple and de-toast the toasted stuff and go all the way.

    If it isn't then at least count() on a gin-index should be able to
    utillize an index-only scan now?

    I've had a significant amout of struggle over the years in this
    corner and the patch that went in for gincostestimate brought
    a huge set of problems to the ground, but not all.

    Other related threads:
    http://archives.postgresql.org/pgsql-performance/2010-05/msg00031.php
    (ts_match_vq cost in discussion)
    http://archives.postgresql.org/pgsql-performance/2010-05/msg00266.php

    I dont think I have ever seen the actual run-time of any @@ query
    to be faster going through the seq-scan than going through the index. Not
    even if it is pulling near all the tuples out.

    (test-case that tries to go in that corner).
    http://archives.postgresql.org/pgsql-performance/2009-10/msg00393.php

    And I think is it due to a coulple of "real-world" things:
    1) The tsvector-column is typically toasted.
    2) The selected columns are typically in the main table.
    3) The gin-index search + pulling main table is in
    fact a measuable cheaper operation than pulling main+toast
    uncompressing toast and applying ts_match_vq even in the most
    favourable case for the seqscan.

    Another real-world thing is that since the tsvector column is in toast
    and isn't read when performing a bitmap-heap-scan, in addition
    to the decompress-cost is it almost never hot in memory either,
    causing its actuall runtime to be even worse.

    Same problems hit a index-scan on another key where filtering
    on a @@ operator, but I think I got around most of them by bumping
    both cost of @@ and limit in the query to 10K instead of the 200 actually
    wanted.

    I do think I have been digging sufficiently in this corner and can
    fairly easy test and craft test-examples that will demonstrate
    the challenges. (a few is attached in above links).

    Thanks for digging in this corner. Let me know if i can help, allthough
    my actual coding skills are spare (at best).

    --
    Jesper
  • Marc Mamin at Feb 20, 2012 at 9:19 am

    I looked into the complaint here of poor estimation for GIN
    indexscans:
    http://archives.postgresql.org/pgsql-performance/2012-02/msg00028.php
    At first glance it sounds like a mistake in selectivity estimation,
    but it isn't: the rowcount estimates are pretty nearly dead on.
    The problem is in the planner's estimate of the cost of executing the
    @@ operator. We have pg_proc.procost set to 1 for ts_match_vq, but
    actually it's a good deal more expensive than that. Some
    experimentation suggests that @@ might be about 500 times as expensive
    as a simple integer comparison. I don't propose pushing its procost
    up that much, but surely at least 10 would be appropriate, maybe even
    100.

    However ... if you just alter pg_proc.procost in Marc's example, the
    planner *still* picks a seqscan, even though its estimate of the
    seqscan
    cost surely does go up. The reason is that its estimate of the GIN
    indexscan cost goes up just as much, since we charge one qual eval cost
    per returned tuple in gincostestimate. It is easy to tell from the
    actual runtimes that that is not what's happening in a GIN indexscan;
    we are not re-executing the @@ operator for every tuple. But the
    planner's cost model doesn't know that.
    Hello,

    many thanks for your feedback.

    I've repeated my test with a table using plain storage, which halved the
    query time.
    This confirms that detoasting is the major issue for cost estimation,
    but even with plain storage the table scan remains about 30% slower
    compared to the index scan.

    I've also looked for complex tsqueries where the planner would make a
    better choice when the statistics are available
    but found none. In some cases I got an identical plan, in other an
    inversion of the plans (with NOT operator(s)).

    In all cases where the plans differed, the planner chose the worse one,
    with severe time differences.
    So a naive 'empirical' question:

    In case of an inverted index in non lossy situation, shouldn't the
    planner also "invert" its cost assumptions?

    best regards,

    Marc Mamin


    toast impact:

    query: select id from <table> where v @@ 'fooblablabla'::tsquery

    toasted table, analyzed: 813 ms (table scan)
    http://explain.depesz.com/s/EoP

    plain storage, analyzed: 404 ms (table scan)
    http://explain.depesz.com/s/iGX

    without analyze: 280 ms (index scan)
    http://explain.depesz.com/s/5aGL

    other queries

    v @@ '(lexeme1 | lexeme4 ) &! (lexeme2 | lexeme3)'::tsquery
    http://explain.depesz.com/s/BC7 (index scan im both cases)

    plan switch !
    v @@ '! fooblablabla'::tsquery

    plain storage, analyzed: 2280 ms (index scan !)
    http://explain.depesz.com/s/gCt

    without analyze: 760 ms (table scan !)
    http://explain.depesz.com/s/5aGL


    There are a couple of issues that would have to be addressed to make
    this better:

    1. If we shouldn't charge procost per row, what should we charge?
    It's probably reasonable to assume that the primitive GIN-index-entry
    comparison operations have cost equal to one cpu_operator_cost
    regardless of what's assigned to the user-visible operators, but I'm
    not convinced that that's sufficient to model complicated operators.
    It might be okay to charge that much per index entry visited rather
    than driving it off the number of heap tuples returned. The code in
    gincostestimate goes to considerable lengths to estimate the number of
    index pages fetched, and it seems like it might be able to derive the
    number of index entries visited too, but it's not trying to account for
    any CPU costs at the moment.

    2. What about lossy operators, or lossy bitmap scans? If either of
    those things happen, we *will* re-execute the @@ operator at visited
    tuples, so discounting its high cost would be a mistake. But the
    planner has no information about either effect, since we moved all
    support for lossiness to runtime.

    I think it was point #2 that led us to not consider these issues
    before.
    But now that we've seen actual cases where the planner makes a poor
    decision because it's not modeling this effect, I think we ought to try
    to do something about it.

    I haven't got time to do anything about this for 9.2, and I bet you
    don't either, but it ought to be on the TODO list to try to improve
    this.

    BTW, an entirely different line of thought is "why on earth is @@ so
    frickin expensive, when it's comparing already-processed tsvectors
    with only a few entries to an already-processed tsquery with only one
    entry??". This test case suggests to me that there's something
    unnecessarily slow in there, and a bit of micro-optimization effort
    might be well repaid.

    regards, tom lane
  • Ktm at Feb 20, 2012 at 2:25 pm

    On Mon, Feb 20, 2012 at 10:18:31AM +0100, Marc Mamin wrote:
    I looked into the complaint here of poor estimation for GIN
    indexscans:
    http://archives.postgresql.org/pgsql-performance/2012-02/msg00028.php
    At first glance it sounds like a mistake in selectivity estimation,
    but it isn't: the rowcount estimates are pretty nearly dead on.
    The problem is in the planner's estimate of the cost of executing the
    @@ operator. We have pg_proc.procost set to 1 for ts_match_vq, but
    actually it's a good deal more expensive than that. Some
    experimentation suggests that @@ might be about 500 times as expensive
    as a simple integer comparison. I don't propose pushing its procost
    up that much, but surely at least 10 would be appropriate, maybe even
    100.

    However ... if you just alter pg_proc.procost in Marc's example, the
    planner *still* picks a seqscan, even though its estimate of the
    seqscan
    cost surely does go up. The reason is that its estimate of the GIN
    indexscan cost goes up just as much, since we charge one qual eval cost
    per returned tuple in gincostestimate. It is easy to tell from the
    actual runtimes that that is not what's happening in a GIN indexscan;
    we are not re-executing the @@ operator for every tuple. But the
    planner's cost model doesn't know that.
    Hello,

    many thanks for your feedback.

    I've repeated my test with a table using plain storage, which halved the
    query time.
    This confirms that detoasting is the major issue for cost estimation,
    but even with plain storage the table scan remains about 30% slower
    compared to the index scan.
    Hi Marc,

    Do you happen to know in which function, the extra time for the toast
    storage is spent -- zlib compression? I saw a mention of the LZ4 compression
    algorithm that is BSD licensed as a Google summer of code project:

    http://code.google.com/p/lz4/

    that compresses at almost 7X than zlib (-1) and decompresses at 6X.

    Regards,
    Ken
  • Marc Mamin at Feb 20, 2012 at 2:32 pm

    Hi Marc,

    Do you happen to know in which function, the extra time for the toast
    storage is spent -- zlib compression? I saw a mention of the LZ4
    compression
    algorithm that is BSD licensed as a Google summer of code project:

    http://code.google.com/p/lz4/

    that compresses at almost 7X than zlib (-1) and decompresses at 6X.

    Regards,
    Ken
    Hi,

    No,

    and my concern is more about cost estimation for ts_queries / gin
    indexes as for the detoasting issue.

    regards,

    Marc Mamin

Related Discussions

Discussion Navigation
viewthread | post