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

Hi, Robert!

Thank you so much for your very valuable review. It took some time to
address all the points. Hopefully I didn't miss anything.

On Fri, Oct 4, 2024 at 4:34 PM Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> On Mon, Sep 23, 2024 at 7:11 AM Alexander Korotkov <aekorotkov(at)gmail(dot)com>
wrote:
> > Makes sense. Please, check the attached patch freeing the consts list
> > while returning NULL from match_orclause_to_indexcol().
>
> Some review comments:
>
> I agree with the comments already given to the effect that the patch
> looks much better now. I was initially surprised to see this happening
> in match_clause_to_indexcol() but after studying it I think it looks
> like the right place. I think it makes sense to think about moving
> forward with this, although it would be nice to get Tom's take if we
> can.

Thank you. And surely, Tom's feedback is very welcome.

> I see that the patch makes no update to the header comment for
> match_clause_to_indexcol() nor to the comment just above the cascade
> of if-statements. I think both need to be updated.
>
> More generally, many of the comments in this patch seem to just
> explain what the code does, and I'd like to reiterate my usual
> complaint: as far as possible, comments should explain WHY the code
> does what it does. Certainly, in some cases there's nothing to be said
> about that e.g. /* Lookup for operator to fetch necessary information
> for the SAOP node */ isn't really saying anything non-obvious but it's
> reasonable to have the comment here anyway. However, when there is
> something more interesting to be said, then we should do that rather
> than just reiterate what the reader who knows C can anyway see. For
> instance, the lengthy comment beginning with "Iterate over OR
> entries." could either be shorter and recapitulate less of the code
> that follows, or it could say something more interesting about why
> we're doing it like that.

I've integrated comments by Andrei [1], edit them and added some from
myself. Hopefully that's better now.

> + /* We allow constant to be Const or Param */
> + if (!IsA(constExpr, Const) && !IsA(constExpr, Param))
> + break;
>
> This restriction is a lot tighter than the one mentioned in the header
> comment of match_clause_to_indexcol ("Our definition of const is
> exceedingly liberal"). If there's a reason for that, the comments
> should talk about it. If there isn't, it's better to be consistent.

Yes, actually I think the restriction could be less tight. It should be
possible to use the same definition of const as
match_opclause_to_indexcol() antd others. The 0003 patch demonstrates
that. But it appears that match_join_clauses_to_index() needs changes.
So, generally I think this area needs more research. This is why, I would
prefer to deal just with Const and Param as 0001 and 0002 currently do, but
consider something like 0003 later.

> + /*
> + * Check operator is present in the opfamily, expression collation
> + * matches index collation. Also, there must be an array type in
> + * order to construct an array later.
> + */
> + if (!IndexCollMatchesExprColl(index->indexcollations[indexcol],
> inputcollid) ||
> + !op_in_opfamily(matchOpno, index->opfamily[indexcol]) ||
> + !OidIsValid(arraytype))
> + break;
>
> I spent some time wondering whether this was safe. The
> IndexCollMatchesExprColl() guarantees that either the input collation
> is equal to the index collation, or the index collation is 0. If the
> index collation is 0 then that I *think* that guarantees that the
> indexed type is non-collatable, but this could be a cross-type
> comparison, and it's possible that the other type is collatable. In
> that case, I don't think anything would prevent us from merging a
> bunch of OR clauses with different collations into a single SAOP. I
> don't really see how that could be a problem, because if the index is
> of a non-collatable type, then presumably the operator doesn't care
> about what the collation is, so it should all be fine, I guess? But
> I'm not very confident about that conclusion.

Generally, we have the same requirements as match_opclause_to_indexcol()
for the first OR argument. And we require rest arguments to have same
input collations. Looks pretty safe for me.

> I'm unclear what the current thinking is about the performance of this
> patch, both as to planning and as to execution. Do we believe that
> this transformation is a categorical win at execution-time? In theory,
> OR format alllows for short-circuit execution, but because of the
> Const-or-Param restriction above, I don't think that's mostly a
> non-issue. But maybe not completely, because I can see from the
> regression test changes that it's possible for us to apply this
> transformation when the Param is set by an InitPlan or SubPlan. If we
> have something like WHERE tenthous = 1 OR tenthous =
> (very_expensive_computation() + 1), maybe the patch could lose,
> because we'll have to do the very expensive calculation to evaluate
> the SAOP, and the OR could stop as soon as we establish that tenthous
> != 1. If we only did the transformation when the Param is an external
> parameter, then we wouldn't have this issue. Maybe this isn't worth
> worrying about; I'm not sure. Are there any other cases where the
> transformation can produce something that executes more slowly?

I didn't manage to find issues with expressions like WHERE tenthous = 1 OR
tenthous => (very_expensive_computation() + 1), because master also need to
evaluate very_expensive_computation() in order to do index scan or bitmap
scan. And patch doesn't do anything to sequential scan. However, I
managed to find an issue with more complex expression. See the example
below.

create or replace function slowfunc() returns int as $$
begin
PERFORM pg_sleep(1.0);
RETURN 1;
end;
$$ stable language plpgsql cost 10000000;
create table t (i int not null, j int not null);
insert into t (select i, i from generate_series(1,10) i,
generate_series(1,1000));
create index t_i_j on t (i, j);

*master*
# explain select count(*) from t where i = 1 and (j = 1 or j = (select
slowfunc()));
QUERY PLAN
-----------------------------------------------------------------------------
Aggregate (cost=25031.27..25031.28 rows=1 width=8)
InitPlan 1
-> Result (cost=0.00..25000.01 rows=1 width=4)
-> Index Only Scan using t_i_j on t (cost=0.29..30.79 rows=190 width=0)
Index Cond: (i = 1)
Filter: ((j = 1) OR (j = (InitPlan 1).col1))
(6 rows)

# select count(*) from t where i = 1 and (j = 1 or j = (select slowfunc()));
count
-------
1000
(1 row)

Time: 2.923 ms

*patched*

# explain select count(*) from t where i = 1 and (j = 1 or j = (select
slowfunc()));
QUERY PLAN
---------------------------------------------------------------------------
Aggregate (cost=25012.61..25012.62 rows=1 width=8)
InitPlan 1
-> Result (cost=0.00..25000.01 rows=1 width=4)
-> Index Only Scan using t_i_j on t (cost=0.29..12.60 rows=1 width=0)
Index Cond: ((i = 1) AND (j = ANY (ARRAY[1, (InitPlan 1).col1])))
(5 rows)

# select count(*) from t where i = 1 and (j = 1 or j = (select slowfunc()));
count
-------
1000
(1 row)

Time: 1006.147 ms (00:01.006)

But, I don't think this is a new issue. We generally trying to use as many
clauses as possible in index scan. We don't do any cost analysis about
that. See the following example.

*master*
# explain analyze select * from t where i = 0 and j = (select slowfunc());
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------
Index Only Scan using t_i_j on t (cost=25000.29..25004.31 rows=1 width=8)
(actual time=1001.234..1001.235 rows=0 loops=1)
Index Cond: ((i = 0) AND (j = (InitPlan 1).col1))
Heap Fetches: 0
InitPlan 1
-> Result (cost=0.00..25000.01 rows=1 width=4) (actual
time=1001.120..1001.121 rows=1 loops=1)
Planning Time: 0.240 ms
Execution Time: 1001.290 ms
(7 rows)

# set enable_indexscan = off;
# set enable_bitmapscan = off;

# explain analyze select * from t where i = 0 and j = (select slowfunc());
QUERY PLAN
---------------------------------------------------------------------------------------------------
Seq Scan on t (cost=25000.01..25195.01 rows=1 width=8) (actual
time=0.806..0.807 rows=0 loops=1)
Filter: ((i = 0) AND (j = (InitPlan 1).col1))
Rows Removed by Filter: 10000
InitPlan 1
-> Result (cost=0.00..25000.01 rows=1 width=4) (never executed)
Planning Time: 0.165 ms
Execution Time: 0.843 ms
(7 rows)

Thus, I think patch just follows our general logic to push as many clauses
as possible to the index, and doesn't make situation any worse. There are
cases when this logic cause the slowdown, by I think they are rather rare.
It's required that one of OR argument to be always true, or one of AND
arguments to be always false, while another argument to be expensive to
calculate. I think this happens very rarely in practice, otherwise we will
hear more (any?) complaints about that from users. Also, notice we now can
evaluate stable function at planning time for selectivity estimation
disregarding its high cost.

# explain analyze select * from t where i = 0 and j = slowfunc();
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------
Index Only Scan using t_i_j on t (cost=25000.28..25004.30 rows=1 width=8)
(actual time=1001.220..1001.220 rows=0 loops=1)
Index Cond: ((i = 0) AND (j = slowfunc()))
Heap Fetches: 0
Planning Time: 1000.994 ms
Execution Time: 1001.284 ms
(5 rows)

Therefore, I don't see a particular problem in the path. But if you insist
there is a problem, we can restrict patch to work only with external params.

> As far as planning time is concerned, I don't think this is going to
> be too bad, because most of the work only needs to be done if there
> are OR-clauses, and my intuition is that the optimization will often
> apply in such cases, so it seems alright. But I wonder how much
> testing has been done of adversarial cases, e.g. lots of non-indexable
> clause in the query; or lots of OR clauses in the query but all of
> them turn out on inspection to be non-indexable. My expectation would
> be that there's no real problem here, but it would be good to verify
> that experimentally.

I made some experiments in this field. The sample table contains 64
columns, first 32 of them are indexed.

\o script.sql
\pset tuples_only
select 'create table t (' || string_agg(format('a%s int not null default
0', i), ', ') || ');' from generate_series(1, 64) i;
select 'create index t_a1_to_a50_idx on t (' || string_agg(format('a%s',
i), ', ') || ');' from generate_series(1, 32) i;

First query contains 6400 OR arguments, 100 per each column.

\o q1.sql
select 'explain analyze select * from t where ' || string_agg(format('a%s =
%s', (i - 1) / 100 + 1, i), ' OR ') || ';' from generate_series(1, 6400) i;

Second query also contains 6400 OR arguments, but 200 per each indexed
column.

\o q2.sql
select 'explain analyze select * from t where ' || string_agg(format('a%s =
%s', (i - 1) / 200 + 1, i), ' OR ') || ';' from generate_series(1, 6400) i;

Third query also contains 6400 OR arguments, but 200 per each non-indexed
column.

\o q3.sql
select 'explain analyze select * from t where ' || string_agg(format('a%s =
%s', (i - 1) / 200 + 32, i), ' OR ') || ';' from generate_series(1, 6400) i;

\pset tuples_only off
\o
\i script.sql
\i q1.sql
\i q2.sql
\i q3.sql

The results for planning time are following.

| master | patch
---------- | ------ | ------
Q1 (run 1) | 14.450 | 12.190
Q1 (run 2) | 13.158 | 11.778
Q1 (run 3) | 11.220 | 12.457
Q2 (run 1) | 15.365 | 13.584
Q2 (run 2) | 15.804 | 14.185
Q2 (run 3) | 16.205 | 13.488
Q3 (run 1) | 9.481 | 12.729
Q3 (run 2) | 10.907 | 13.662
Q3 (run 3) | 11.783 | 12.021

The planning of Q1 and Q2 is somewhat faster with the patch. I think the
reason for this is shortcut condition in make_bitmap_paths_for_or_group(),
which make us select jointlist without making splitlist. So, we generally
produce simpler bitmap scan plans. The Q3 is somewhat slower with the
patch, because it contains no index-matching clauses,
thus group_similar_or_args() appears to be a waste of cycles. This
generally looks acceptable for me.

Additionally the attached patchset contains changes I promised in response
to Jian He comments, in particular:
1. Fast-path exit form make_bitmap_paths_for_or_group() when joint path is
found and no extra clauses present.
2. Fast-path exit from group_similar_or_args() when not even single clause
is matching index.
3. Fix exit iteration over indexes after first success with
match_index_to_operand() in group_similar_or_args().

Also, in this revision I fixed buggy modification of all_clauses list
with list_delete() in generate_bitmap_or_paths(). Instead, new copy of
list is created.

This is all for now. The feedback is welcome.

Links.
1.
https://www.postgresql.org/message-id/5d7a66e7-b256-41a7-905a-728c7ae54bce%40gmail.com
2.
https://www.postgresql.org/message-id/CAPpHfdsB2e20Y4jThsonD3%2BsmwwisYWJbJN_mpGjm%3DJiT7OQaQ%40mail.gmail.com
3.
https://www.postgresql.org/message-id/CAPpHfdunXXFT%3Djk%2B3ojXQWo0wZ1Rk%3DrpmAp%2BfjcistCWcH7KqA%40mail.gmail.com

------
Regards,
Alexander Korotkov
Supabase