Horton

Re: POC, WIP: OR-clause support for indexes

Andrei Lepikhov <a.lepikhov@postgrespro.ru>

View thread
From: Andrey Lepikhov <a.lepikhov@postgrespro.ru>
To: Teodor Sigaev <teodor@sigaev.ru>, Pgsql Hackers <pgsql-hackers@postgresql.org>
Cc: "a.rybakina" <a.rybakina@postgrespro.ru>
Date: 2022-12-28T04:19:27Z
Lists: pgsql-hackers

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

  1. Make group_similar_or_args() reorder clause list as little as possible

  2. Allow usage of match_orclause_to_indexcol() for joins

  3. Skip not SOAP-supported indexes while transforming an OR clause into SAOP

  4. Remove the wrong assertion from match_orclause_to_indexcol()

  5. Teach bitmap path generation about transforming OR-clauses to SAOP's

  6. Transform OR-clauses to SAOP's during index matching

  7. Fix the value of or_to_any_transform_limit in postgresql.conf.sample

  8. Transform OR clauses to ANY expression

  9. MergeAttributes code deduplication

  10. SEARCH and CYCLE clauses

  11. Improve estimation of OR clauses using extended statistics.

  12. Teach btree to handle ScalarArrayOpExpr quals natively.

  13. Revise collation derivation method and expression-tree representation.

  14. Instead of trying to force WHERE clauses into CNF or DNF normal form,

Attachments

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