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

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