public inbox for [email protected]  

help / color / mirror / Atom feed

From: Andrey Lepikhov <[email protected]>
To: Teodor Sigaev <[email protected]>
To: Pgsql Hackers <[email protected]>
Cc: a.rybakina <[email protected]>
Subject: Re: POC, WIP: OR-clause support for indexes
Date: Wed, 28 Dec 2022 09:19:27 +0500
Message-ID: <[email protected]> (raw)
In-Reply-To: <[email protected]>
References: <[email protected]>

On 12/26/15 23:04, Teodor Sigaev wrote:
> I'd like to present OR-clause support for indexes. Although OR-clauses 
> could be supported by bitmapOR index scan it isn't very effective and 
> such scan lost any order existing in index. We (with Alexander Korotkov) 
> presented results on Vienna's conference this year. In short, it 
> provides performance improvement:
> 
> EXPLAIN ANALYZE
> SELECT count(*) FROM tst WHERE id = 5 OR id = 500 OR id = 5000;
> ...
> The problems on the way which I see for now:
> 1 Calculating cost. Right now it's just a simple transformation of costs 
> computed for BitmapOr path. I'd like to hope that's possible and so 
> index's estimation function could be non-touched. So, they could believe 
> that all clauses are implicitly-ANDed
> 2 I'd like to add such support to btree but it seems that it should be a 
> separated patch. Btree search algorithm doesn't use any kind of stack of 
> pages and algorithm to walk over btree doesn't clear for me for now.
> 3 I could miss some places which still assumes  implicitly-ANDed list of 
> clauses although regression tests passes fine.
I support such a cunning approach. But this specific case, you 
demonstrated above, could be optimized independently at an earlier 
stage. If to convert:

(F(A) = ConstStableExpr_1) OR (F(A) = ConstStableExpr_2)
to
F(A) IN (ConstStableExpr_1, ConstStableExpr_2)

it can be seen significant execution speedup. For example, using the 
demo.sql to estimate maximum positive effect we see about 40% of 
execution and 100% of planning speedup.

To avoid unnecessary overhead, induced by the optimization, such 
transformation may be made at the stage of planning (we have cardinality 
estimations and have pruned partitions) but before creation of a 
relation scan paths. So, we can avoid planning overhead and non-optimal 
BitmapOr in the case of many OR's possibly aggravated by many indexes on 
the relation.
For example, such operation can be executed in create_index_paths() 
before passing rel->indexlist.

-- 
Regards
Andrey Lepikhov
Postgres Professional


Attachments:

  [application/sql] demo.sql (567B, ../[email protected]/2-demo.sql)
  download

view thread (29+ messages)  latest in thread

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: [email protected]
  Cc: [email protected], [email protected], [email protected]
  Subject: Re: POC, WIP: OR-clause support for indexes
  In-Reply-To: <[email protected]>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox