Content-Type: multipart/mixed; boundary="------------yx1Aa69Av0MQbY4VZMcR97bg"
Message-ID: <05838ca5-1c78-af81-34c1-19cae2516b61@postgrespro.ru>
Date: Wed, 28 Dec 2022 09:19:27 +0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.6.0
Subject: Re: POC, WIP: OR-clause support for indexes
Content-Language: en-US
To: Teodor Sigaev <teodor@sigaev.ru>,
 Pgsql Hackers <pgsql-hackers@postgresql.org>
References: <567ED6CA.2040504@sigaev.ru>
Cc: "a.rybakina" <a.rybakina@postgrespro.ru>
From: Andrey Lepikhov <a.lepikhov@postgrespro.ru>
Organization: Postgres Professional
In-Reply-To: <567ED6CA.2040504@sigaev.ru>
Archived-At: 
 <https://www.postgresql.org/message-id/05838ca5-1c78-af81-34c1-19cae2516b61%40postgrespro.ru>
Precedence: bulk

This is a multi-part message in MIME format.
--------------yx1Aa69Av0MQbY4VZMcR97bg
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit

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

--------------yx1Aa69Av0MQbY4VZMcR97bg
Content-Type: application/sql; name="demo.sql"
Content-Disposition: attachment; filename="demo.sql"
Content-Transfer-Encoding: base64

RFJPUCBUQUJMRSBJRiBFWElTVFMgdHN0OwpDUkVBVEUgVEFCTEUgdHN0IEFTIFNFTEVDVCB4
ICUgMTAwMDAgaWQsICdhYmN4eHh4eHh4eHh4eHgnOjp0ZXh0IHkKICBGUk9NIGdlbmVyYXRl
X3NlcmllcygxLDFFNSkgQVMgeDsKQ1JFQVRFIElOREVYIE9OIHRzdChpZCk7CgpFWFBMQUlO
IEFOQUxZWkUKU0VMRUNUIGNvdW50KCopIEZST00gdHN0IFdIRVJFIGlkID0gNSBPUiBpZCA9
IDUwIE9SIGlkID0gNTAwIE9SIGlkID0gNTAwMAogIE9SIGlkID0gMSBPUiBpZCA9IDEwIE9S
IGlkID0gMTAwIE9SIGlkID0gMTAwMCBPUiBpZCA9IDEwMDAwIE9SIGlkID4gMjAwMDA7CgpF
WFBMQUlOIEFOQUxZWkUKU0VMRUNUIGNvdW50KCopIEZST00gdHN0IFdIRVJFIGlkID0gNSBP
UiBpZCA9IDUwIE9SIGlkID0gNTAwIE9SIGlkID0gNTAwMAogIE9SIGlkID0gMSBPUiBpZCA9
IDEwIE9SIGlkID0gMTAwIE9SIGlkID0gMTAwMCBPUiBpZCA9IDEwMDAwOwoKRVhQTEFJTiBB
TkFMWVpFClNFTEVDVCBjb3VudCgqKSBGUk9NIHRzdCBXSEVSRSBpZCBJTiAoNSw1MCw1MDAs
NTAwMCwxLDEwLDEwMCwxMDAwLDEwMDAwKTsK

--------------yx1Aa69Av0MQbY4VZMcR97bg--