Horton

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

Peter Geoghegan <pg@bowt.ie>

View thread
From: Peter Geoghegan <pg@bowt.ie>
To: Alena Rybakina <lena.ribackina@yandex.ru>
Cc: Marcos Pegoraro <marcos@f10.com.br>, Alena Rybakina <a.rybakina@postgrespro.ru>, Andrey Lepikhov <a.lepikhov@postgrespro.ru>, pgsql-hackers@postgresql.org, teodor@sigaev.ru
Date: 2023-07-25T23:47:41Z
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,

On Thu, Jun 29, 2023 at 2:32 AM Alena Rybakina <lena.ribackina@yandex.ru> wrote:
> Hi! I'm sorry I didn't answer you right away, I was too busy with work.

Same for me, this time. I was busy working on my patch, which I
finally posted yesterday.

> To be honest, I didn't think about the fact that my optimization can help eliminate duplicates before reading the data before.

I'm not surprised that you didn't specifically think of that, because
it's very subtle.

> I am still only in the process of familiarizing myself with the thread [1] (reference from your letter), but I have already seen that there are problems related, for example, to when "or" expressions refer to the parent element.

I didn't intend to imply that you might have the same problem here. I
just meant that OR optimizations can have problems with duplicate
elimination, in general. I suspect that your patch doesn't have that
problem, because you are performing a transformation of one kind of OR
into another kind of OR.

> I think, I would face the similar problems if I complicate the current code, for example, so that not only or expressions standing on the same level are written in any, but also on different ones without violating the logic of the priority of executing operators.

I can't say that I am particularly experienced in this general area --
I have never tried to formally reason about how two different
statements are equivalent. It just hasn't been something that I've
needed to have a totally rigorous understanding of up until now. But
my recent patch changes that. Now I need to study this area to make
sure that I have a truly rigorous understanding.

Jeff Davis suggested that I read "Logic and Databases", by C.J. Date.
So now I have some homework to do.

> Unfortunately, when I tried to make a transformation at the stage of index formation, I encountered too incorrect an assessment of the selectivity of relation, which affected the incorrect calculation of the cost and cardinality.

It's not surprising that a weird shift in the plan chosen by the
optimizer is seen with some random test case, as a result of this
added transformation. Even changes that are 100% strictly better (e.g.
changes in a selectivity estimation function that is somehow
guaranteed to be more accurate in all cases) might do that. Here is a
recent example of that with another patch, involving a bitmap OR:

https://postgr.es/m/CAH2-WznCDK9n2tZ6j_-iLN563_ePuC3NzP6VSVTL6jHzs6nRuQ@mail.gmail.com

This example was *not* a regression, if you go by conventional
measures. It was merely a less robust plan than the bitmap OR plan,
because it didn't pass down both columns as index quals.

BTW, there are various restrictions on the sort order of SAOPs that
you might want to try to familiarize yourself with. I describe them
(perhaps not very clearly) here:

https://postgr.es/m/CAH2-Wz=ksvN_sjcnD1+Bt-WtifRA5ok48aDYnq3pkKhxgMQpcw@mail.gmail.com

Currently, the optimizer doesn't recognize multi-column indexes with
SAOPs on every column as having a valid sort order, except on the
first column. It seems possible that that has consequences for your
patch. (I'm really only guessing, though; don't trust anything that I
say about the optimizer too much.)

--
Peter Geoghegan