Horton

Thread

Commits

  1. Improve GIN cost estimation

  1. Hung Nguyen <hungnq1989@gmail.com> — 2022-07-02T12:15:55Z

    Hellom

<https://dba.stackexchange.com/posts/314015/timeline>

I've just upgraded my postgres instance from v11 to v14. There was an
interesting problem because we have a trigram index on order_id column.

This new feature makes our simple join query on that column very slow. For
example:

SELECT count(*) from order_rows o1 join order o2 on o1.order_id = o2.order_id

To solve this problem the existing trigram index must be dropped and we
cannot use ILIKE queries on this column. I just wonder if there is any way
to tell postgres what index (in this case btree index) to use when doing
the join operations?

[Postgres 14] Allow GiST/GIN pg_trgm indexes to do equality lookups (Julien
Rouhaud)

I'm not sure if this is really a bug, but its' super weird if the query
planner favors the trigram index over the b-tree index for joining is not
optimal to me. Thank you so much.

References

   - https://www.postgresql.org/docs/current/release-14.html
   - https://www.postgresql.org/docs/11/pgtrgm.html

  2. Re:

    Tom Lane <tgl@sss.pgh.pa.us> — 2022-07-02T13:45:31Z

    Hung Nguyen <hungnq1989@gmail.com> writes:
> I'm not sure if this is really a bug, but its' super weird if the query
> planner favors the trigram index over the b-tree index for joining is not
> optimal to me. Thank you so much.

I agree that sounds bad, but you've provided a conclusion with no
supporting evidence, making it impossible to investigate.  A
self-contained test case that behaves this way would be ideal.
Otherwise, please see

https://wiki.postgresql.org/wiki/Slow_Query_Questions

and provide the info suggested therein.

			regards, tom lane

  3. Re: your mail

    Julien Rouhaud <rjuju123@gmail.com> — 2022-07-02T13:49:16Z

    Hi,

On Sat, Jul 02, 2022 at 03:15:55PM +0300, Hung Nguyen wrote:
> Hellom
>
> <https://dba.stackexchange.com/posts/314015/timeline>
>
> I've just upgraded my postgres instance from v11 to v14. There was an
> interesting problem because we have a trigram index on order_id column.
>
> This new feature makes our simple join query on that column very slow. For
> example:
>
> SELECT count(*) from order_rows o1 join order o2 on o1.order_id = o2.order_id

Oh, that's surprising.  It's not clear to me why any index would be used with
such a query, especially if it's not compatible with index only scans.  Is that
some simplification of some query or really one that exhibit the problem?

>
> To solve this problem the existing trigram index must be dropped and we
> cannot use ILIKE queries on this column. I just wonder if there is any way
> to tell postgres what index (in this case btree index) to use when doing
> the join operations?

There's no such capability builtin.  However, trigram indexes should be way
more expensive that btree indexes in general, so the planner should be able to
make the correct decision, there must be something else going on.
>
> [Postgres 14] Allow GiST/GIN pg_trgm indexes to do equality lookups (Julien
> Rouhaud)
>
> I'm not sure if this is really a bug, but its' super weird if the query
> planner favors the trigram index over the b-tree index for joining is not
> optimal to me. Thank you so much.

Can you provide the full definition for both order and order_rows, and EXPLAIN
(ANALYZE, TIMING, BUFFERS) for the problematic query, with and without the trgm
index being used?  Doing a "SET enable_bitmapscan = 0;" should be enough for
that.  Do you have any usual settings configured, like enable_* or others?

  4. Re:

    Ronan Dunklau <ronan.dunklau@aiven.io> — 2022-07-06T08:53:52Z

    I've taken a look at this, and can expose a minimal test case reproducing what 
I believe is the same problem, see the attached test.sql file for this.

The test case is a bit extreme, by setting random_page_cost so low, but the 
same thing can happen with default values of random_page_cost given a 
significantly high number of loops.

Running the attached test case, I get the following:

                                                          QUERY PLAN                                                           
-------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.01..711.84 rows=20000 width=13) (actual 
time=0.240..6521.129 rows=20000 loops=1)
   Buffers: shared hit=445110
   ->  Seq Scan on t2  (cost=0.00..307.00 rows=20000 width=9) (actual 
time=0.007..2.297 rows=20000 loops=1)
         Buffers: shared hit=107
   ->  Bitmap Heap Scan on t1  (cost=0.01..0.02 rows=1 width=4) (actual 
time=0.325..0.325 rows=1 loops=20000)
         Recheck Cond: (id = t2.t1_id)
         Rows Removed by Index Recheck: 0
         Heap Blocks: exact=20013
         Buffers: shared hit=445003
         ->  Bitmap Index Scan on t1_gin_index  (cost=0.00..0.01 rows=1 
width=0) (actual time=0.324..0.324 rows=1 loops=20000)
               Index Cond: (id = t2.t1_id)
               Buffers: shared hit=424990
 Planning:
   Buffers: shared hit=79
 Planning Time: 0.325 ms
 Execution Time: 6522.759 ms

If I drop the gin index, the btree index is used:

                                                           QUERY PLAN                                                           
--------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.29..1249.56 rows=20000 width=13) (actual 
time=0.018..16.570 rows=20000 loops=1)
   Buffers: shared hit=4607
   ->  Seq Scan on t2  (cost=0.00..307.00 rows=20000 width=9) (actual 
time=0.007..1.717 rows=20000 loops=1)
         Buffers: shared hit=107
   ->  Memoize  (cost=0.29..0.31 rows=1 width=4) (actual time=0.000..0.000 
rows=1 loops=20000)
         Cache Key: t2.t1_id
         Cache Mode: logical
         Hits: 18500  Misses: 1500  Evictions: 0  Overflows: 0  Memory Usage: 
154kB
         Buffers: shared hit=4500
         ->  Index Only Scan using t1_pkey on t1  (cost=0.28..0.30 rows=1 
width=4) (actual time=0.002..0.002 rows=1 loops=1500)
               Index Cond: (id = t2.t1_id)
               Heap Fetches: 1500
               Buffers: shared hit=4500
 Planning:
   Buffers: shared hit=10
 Planning Time: 0.198 ms
 Execution Time: 17.683 ms

Looking into it, it looks like we are not charging a cpu "descent" cost for 
the entry tree of the gin index, which we do for the btree index. In general, 
it does not pose a problem since IO costs are far greater than cpu costs. But 
when the index scan is inside a nestloop, we account for cache effect and 
amortize the cost of IO over the number of outer scans, which reduces its 
relative importance significantly. In that case, the index scan on the gin 
index appears much cheaper, as the constant cpu cost is not taken into 
account. 

I'm not sure how we should account for the cost of the descent, but  I believe 
it should be more than free. Perhaps we could devise a similar strategy using 
the estimated numEntryPages ?

-- 
Ronan Dunklau

  5. Re: index cost estimation

    Tom Lane <tgl@sss.pgh.pa.us> — 2022-07-06T14:41:29Z

    Ronan Dunklau <ronan.dunklau@aiven.io> writes:
> Looking into it, it looks like we are not charging a cpu "descent" cost for 
> the entry tree of the gin index, which we do for the btree index. In general, 
> it does not pose a problem since IO costs are far greater than cpu costs. But 
> when the index scan is inside a nestloop, we account for cache effect and 
> amortize the cost of IO over the number of outer scans, which reduces its 
> relative importance significantly. In that case, the index scan on the gin 
> index appears much cheaper, as the constant cpu cost is not taken into 
> account. 

Hm, so it'd seem this probably could happen when comparing *any*
non-btree index to a btree index, because I don't think we are
particularly careful with CPU cost estimation for any of the
other index types.  If we do something about this, we probably
have to look at all of them.

			regards, tom lane

  6. Re: index cost estimation

    Ronan Dunklau <ronan.dunklau@aiven.io> — 2022-07-06T14:52:09Z

    Le mercredi 6 juillet 2022, 16:41:29 CEST Tom Lane a écrit :
> Hm, so it'd seem this probably could happen when comparing *any*
> non-btree index to a btree index, because I don't think we are
> particularly careful with CPU cost estimation for any of the
> other index types.  If we do something about this, we probably
> have to look at all of them.

For gist and sp-gist, a descent cost is taken into account, by estimating the 
tree height so that particular effect is mitigated. Whether the cpu cost 
estimation is sensible regarding to btree is another topic, but at least the 
index cost doesn't vanish when inside a loop.

Hash, brin and bloom are quite different, so maybe another examination would be 
required but probably outside the scope of this bug report. 


-- 
Ronan Dunklau

  7. Re: index cost estimation

    Ronan Dunklau <ronan.dunklau@aiven.io> — 2022-07-06T15:42:28Z

    Le mercredi 6 juillet 2022, 16:52:09 CEST Ronan Dunklau a écrit :
> Le mercredi 6 juillet 2022, 16:41:29 CEST Tom Lane a écrit :
> > Hm, so it'd seem this probably could happen when comparing *any*
> > non-btree index to a btree index, because I don't think we are
> > particularly careful with CPU cost estimation for any of the
> > other index types.  If we do something about this, we probably
> > have to look at all of them.
> 
> For gist and sp-gist, a descent cost is taken into account, by estimating 
the
> tree height so that particular effect is mitigated. Whether the cpu cost
> estimation is sensible regarding to btree is another topic, but at least the
> index cost doesn't vanish when inside a loop.
> 
> Hash, brin and bloom are quite different, so maybe another examination would 
be
> required but probably outside the scope of this bug report.

Here is a patch tentatively addressing the problem. I'm not sure what I'm 
doing with the number of searched entries is right though.


-- 
Ronan Dunklau