Extend more usecase for planning time partition pruning and init partition pruning.

On Sun, Jan 24, 2021 at 6:34 PM Andy Fan <zhihui.fan1213@gmail.com> wrote:

Hi:

I recently found a use case like this. SELECT * FROM p, q WHERE
p.partkey =
q.colx AND (q.colx = $1 OR q.colx = $2); Then we can't do either planning
time
partition prune or init partition prune. Even though we have run-time
partition pruning work at last, it is too late in some cases since we have
to init all the plan nodes in advance. In my case, there are 10+
partitioned relation in one query and the execution time is short, so the
init plan a lot of plan nodes cares a lot.

The attached patches fix this issue. It just get the "p.partkey = q.colx"
case in root->eq_classes or rel->joinlist (outer join), and then check if
there
is some baserestrictinfo in another relation which can be used for
partition
pruning. To make the things easier, both partkey and colx must be Var
expression in implementation.

- v1-0001-Make-some-static-functions-as-extern-and-extend-C.patch

Just some existing refactoring and extending ChangeVarNodes to be able
to change var->attno.

- v1-0002-Build-some-implied-pruning-quals-to-extend-the-us.patch

Do the real job.

Thought?

--
Best Regards
Andy Fan (https://www.aliyun.com/)

Some results from this patch.

create table p (a int, b int, c character varying(8)) partition by list(c);
create table p1 partition of p for values in ('000001');
create table p2 partition of p for values in ('000002');
create table p3 partition of p for values in ('000003');
create table q (a int, c character varying(8), b int) partition by list(c);
create table q1 partition of q for values in ('000001');
create table q2 partition of q for values in ('000002');
create table q3 partition of q for values in ('000003');

Before the patch:
postgres=# explain (costs off) select * from p inner join q on p.c = q.c
and q.c > '000002';
QUERY PLAN
----------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Append
-> Seq Scan on p1 p_1
-> Seq Scan on p2 p_2
-> Seq Scan on p3 p_3
-> Hash
-> Seq Scan on q3 q
Filter: ((c)::text > '000002'::text)
(9 rows)

After the patch:

QUERY PLAN
----------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Seq Scan on p3 p
-> Hash
-> Seq Scan on q3 q
Filter: ((c)::text > '000002'::text)
(6 rows)

Before the patch:
postgres=# explain (costs off) select * from p inner join q on p.c = q.c
and (q.c = '000002' or q.c = '000001');
QUERY PLAN
--------------------------------------------------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Append
-> Seq Scan on p1 p_1
-> Seq Scan on p2 p_2
-> Seq Scan on p3 p_3
-> Hash
-> Append
-> Seq Scan on q1 q_1
Filter: (((c)::text = '000002'::text) OR ((c)::text =
'000001'::text))
-> Seq Scan on q2 q_2
Filter: (((c)::text = '000002'::text) OR ((c)::text =
'000001'::text))
(12 rows)

After the patch:
QUERY PLAN
--------------------------------------------------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Append
-> Seq Scan on p1 p_1
-> Seq Scan on p2 p_2
-> Hash
-> Append
-> Seq Scan on q1 q_1
Filter: (((c)::text = '000002'::text) OR ((c)::text =
'000001'::text))
-> Seq Scan on q2 q_2
Filter: (((c)::text = '000002'::text) OR ((c)::text =
'000001'::text))
(11 rows)

Before the patch:
postgres=# explain (costs off) select * from p left join q on p.c = q.c
where (q.c = '000002' or q.c = '000001');
QUERY PLAN
--------------------------------------------------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Append
-> Seq Scan on p1 p_1
-> Seq Scan on p2 p_2
-> Seq Scan on p3 p_3
-> Hash
-> Append
-> Seq Scan on q1 q_1
Filter: (((c)::text = '000002'::text) OR ((c)::text =
'000001'::text))
-> Seq Scan on q2 q_2
Filter: (((c)::text = '000002'::text) OR ((c)::text =
'000001'::text))
(12 rows)

After the patch:
QUERY PLAN
--------------------------------------------------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Append
-> Seq Scan on p1 p_1
-> Seq Scan on p2 p_2
-> Hash
-> Append
-> Seq Scan on q1 q_1
Filter: (((c)::text = '000002'::text) OR ((c)::text =
'000001'::text))
-> Seq Scan on q2 q_2
Filter: (((c)::text = '000002'::text) OR ((c)::text =
'000001'::text))
(11 rows)

--
Best Regards
Andy Fan (https://www.aliyun.com/)

On Mon, Jan 25, 2021 at 10:21 AM Andy Fan <zhihui.fan1213@gmail.com> wrote:

On Sun, Jan 24, 2021 at 6:34 PM Andy Fan <zhihui.fan1213@gmail.com> wrote:

Hi:

I recently found a use case like this. SELECT * FROM p, q WHERE
p.partkey =
q.colx AND (q.colx = $1 OR q.colx = $2); Then we can't do either
planning time
partition prune or init partition prune. Even though we have run-time
partition pruning work at last, it is too late in some cases since we
have
to init all the plan nodes in advance. In my case, there are 10+
partitioned relation in one query and the execution time is short, so the
init plan a lot of plan nodes cares a lot.

The attached patches fix this issue. It just get the "p.partkey = q.colx"
case in root->eq_classes or rel->joinlist (outer join), and then check if
there
is some baserestrictinfo in another relation which can be used for
partition
pruning. To make the things easier, both partkey and colx must be Var
expression in implementation.

- v1-0001-Make-some-static-functions-as-extern-and-extend-C.patch

Just some existing refactoring and extending ChangeVarNodes to be able
to change var->attno.

- v1-0002-Build-some-implied-pruning-quals-to-extend-the-us.patch

Do the real job.

Thought?

--
Best Regards
Andy Fan (https://www.aliyun.com/)

Some results from this patch.

create table p (a int, b int, c character varying(8)) partition by list(c);
create table p1 partition of p for values in ('000001');
create table p2 partition of p for values in ('000002');
create table p3 partition of p for values in ('000003');
create table q (a int, c character varying(8), b int) partition by list(c);
create table q1 partition of q for values in ('000001');
create table q2 partition of q for values in ('000002');
create table q3 partition of q for values in ('000003');

Before the patch:
postgres=# explain (costs off) select * from p inner join q on p.c = q.c
and q.c > '000002';
QUERY PLAN
----------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Append
-> Seq Scan on p1 p_1
-> Seq Scan on p2 p_2
-> Seq Scan on p3 p_3
-> Hash
-> Seq Scan on q3 q
Filter: ((c)::text > '000002'::text)
(9 rows)

After the patch:

QUERY PLAN
----------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Seq Scan on p3 p
-> Hash
-> Seq Scan on q3 q
Filter: ((c)::text > '000002'::text)
(6 rows)

Before the patch:
postgres=# explain (costs off) select * from p inner join q on p.c = q.c
and (q.c = '000002' or q.c = '000001');
QUERY PLAN

--------------------------------------------------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Append
-> Seq Scan on p1 p_1
-> Seq Scan on p2 p_2
-> Seq Scan on p3 p_3
-> Hash
-> Append
-> Seq Scan on q1 q_1
Filter: (((c)::text = '000002'::text) OR ((c)::text =
'000001'::text))
-> Seq Scan on q2 q_2
Filter: (((c)::text = '000002'::text) OR ((c)::text =
'000001'::text))
(12 rows)

After the patch:
QUERY PLAN

--------------------------------------------------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Append
-> Seq Scan on p1 p_1
-> Seq Scan on p2 p_2
-> Hash
-> Append
-> Seq Scan on q1 q_1
Filter: (((c)::text = '000002'::text) OR ((c)::text =
'000001'::text))
-> Seq Scan on q2 q_2
Filter: (((c)::text = '000002'::text) OR ((c)::text =
'000001'::text))
(11 rows)

Before the patch:
postgres=# explain (costs off) select * from p left join q on p.c = q.c
where (q.c = '000002' or q.c = '000001');
QUERY PLAN

--------------------------------------------------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Append
-> Seq Scan on p1 p_1
-> Seq Scan on p2 p_2
-> Seq Scan on p3 p_3
-> Hash
-> Append
-> Seq Scan on q1 q_1
Filter: (((c)::text = '000002'::text) OR ((c)::text =
'000001'::text))
-> Seq Scan on q2 q_2
Filter: (((c)::text = '000002'::text) OR ((c)::text =
'000001'::text))
(12 rows)

After the patch:
QUERY PLAN

--------------------------------------------------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Append
-> Seq Scan on p1 p_1
-> Seq Scan on p2 p_2
-> Hash
-> Append
-> Seq Scan on q1 q_1
Filter: (((c)::text = '000002'::text) OR ((c)::text =
'000001'::text))
-> Seq Scan on q2 q_2
Filter: (((c)::text = '000002'::text) OR ((c)::text =
'000001'::text))
(11 rows)

--
Best Regards
Andy Fan (https://www.aliyun.com/)

Here is a performance test regarding this patch. In the following simple
case,
we can get 3x faster than before.

create table p (a int, b int, c int) partition by list(c);
select 'create table p_'||i||' partition of p for values in (' || i || ');'
from generate_series(1, 100)i; \gexec
insert into p select i, i, i from generate_series(1, 100)i;
create table m as select * from p;
analyze m;
analyze p;

test sql: select * from m, p where m.c = p.c and m.c in (3, 10);

With this patch: 1.1ms
Without this patch: 3.4ms

I'm happy with the result and the implementation, I have add this into
commitfest https://commitfest.postgresql.org/32/2975/

Thanks.

--
Best Regards
Andy Fan (https://www.aliyun.com/)

On Mon, Feb 8, 2021 at 3:43 PM Andy Fan <zhihui.fan1213@gmail.com> wrote:

On Mon, Jan 25, 2021 at 10:21 AM Andy Fan <zhihui.fan1213@gmail.com>
wrote:

On Sun, Jan 24, 2021 at 6:34 PM Andy Fan <zhihui.fan1213@gmail.com>
wrote:

Hi:

I recently found a use case like this. SELECT * FROM p, q WHERE
p.partkey =
q.colx AND (q.colx = $1 OR q.colx = $2); Then we can't do either
planning time
partition prune or init partition prune. Even though we have run-time
partition pruning work at last, it is too late in some cases since we
have
to init all the plan nodes in advance. In my case, there are 10+
partitioned relation in one query and the execution time is short, so
the
init plan a lot of plan nodes cares a lot.

The attached patches fix this issue. It just get the "p.partkey = q.colx"
case in root->eq_classes or rel->joinlist (outer join), and then check
if there
is some baserestrictinfo in another relation which can be used for
partition
pruning. To make the things easier, both partkey and colx must be Var
expression in implementation.

- v1-0001-Make-some-static-functions-as-extern-and-extend-C.patch

Just some existing refactoring and extending ChangeVarNodes to be able
to change var->attno.

- v1-0002-Build-some-implied-pruning-quals-to-extend-the-us.patch

Do the real job.

Thought?

--
Best Regards
Andy Fan (https://www.aliyun.com/)

Some results from this patch.

create table p (a int, b int, c character varying(8)) partition by
list(c);
create table p1 partition of p for values in ('000001');
create table p2 partition of p for values in ('000002');
create table p3 partition of p for values in ('000003');
create table q (a int, c character varying(8), b int) partition by
list(c);
create table q1 partition of q for values in ('000001');
create table q2 partition of q for values in ('000002');
create table q3 partition of q for values in ('000003');

Before the patch:
postgres=# explain (costs off) select * from p inner join q on p.c = q.c
and q.c > '000002';
QUERY PLAN
----------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Append
-> Seq Scan on p1 p_1
-> Seq Scan on p2 p_2
-> Seq Scan on p3 p_3
-> Hash
-> Seq Scan on q3 q
Filter: ((c)::text > '000002'::text)
(9 rows)

After the patch:

QUERY PLAN
----------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Seq Scan on p3 p
-> Hash
-> Seq Scan on q3 q
Filter: ((c)::text > '000002'::text)
(6 rows)

Before the patch:
postgres=# explain (costs off) select * from p inner join q on p.c = q.c
and (q.c = '000002' or q.c = '000001');
QUERY PLAN

--------------------------------------------------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Append
-> Seq Scan on p1 p_1
-> Seq Scan on p2 p_2
-> Seq Scan on p3 p_3
-> Hash
-> Append
-> Seq Scan on q1 q_1
Filter: (((c)::text = '000002'::text) OR ((c)::text
= '000001'::text))
-> Seq Scan on q2 q_2
Filter: (((c)::text = '000002'::text) OR ((c)::text
= '000001'::text))
(12 rows)

After the patch:
QUERY PLAN

--------------------------------------------------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Append
-> Seq Scan on p1 p_1
-> Seq Scan on p2 p_2
-> Hash
-> Append
-> Seq Scan on q1 q_1
Filter: (((c)::text = '000002'::text) OR ((c)::text
= '000001'::text))
-> Seq Scan on q2 q_2
Filter: (((c)::text = '000002'::text) OR ((c)::text
= '000001'::text))
(11 rows)

Before the patch:
postgres=# explain (costs off) select * from p left join q on p.c = q.c
where (q.c = '000002' or q.c = '000001');
QUERY PLAN

--------------------------------------------------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Append
-> Seq Scan on p1 p_1
-> Seq Scan on p2 p_2
-> Seq Scan on p3 p_3
-> Hash
-> Append
-> Seq Scan on q1 q_1
Filter: (((c)::text = '000002'::text) OR ((c)::text
= '000001'::text))
-> Seq Scan on q2 q_2
Filter: (((c)::text = '000002'::text) OR ((c)::text
= '000001'::text))
(12 rows)

After the patch:
QUERY PLAN

--------------------------------------------------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Append
-> Seq Scan on p1 p_1
-> Seq Scan on p2 p_2
-> Hash
-> Append
-> Seq Scan on q1 q_1
Filter: (((c)::text = '000002'::text) OR ((c)::text
= '000001'::text))
-> Seq Scan on q2 q_2
Filter: (((c)::text = '000002'::text) OR ((c)::text
= '000001'::text))
(11 rows)

--
Best Regards
Andy Fan (https://www.aliyun.com/)

Here is a performance test regarding this patch. In the following simple
case,
we can get 3x faster than before.

create table p (a int, b int, c int) partition by list(c);
select 'create table p_'||i||' partition of p for values in (' || i ||
');' from generate_series(1, 100)i; \gexec
insert into p select i, i, i from generate_series(1, 100)i;
create table m as select * from p;
analyze m;
analyze p;

test sql: select * from m, p where m.c = p.c and m.c in (3, 10);

With this patch: 1.1ms
Without this patch: 3.4ms

I'm happy with the result and the implementation, I have add this into
commitfest https://commitfest.postgresql.org/32/2975/

Thanks.

--
Best Regards
Andy Fan (https://www.aliyun.com/)

Rebase to the current latest commit 678d0e239b.

--
Best Regards
Andy Fan (https://www.aliyun.com/)

On Fri, Feb 19, 2021 at 6:03 PM Andy Fan <zhihui.fan1213@gmail.com> wrote:

On Mon, Feb 8, 2021 at 3:43 PM Andy Fan <zhihui.fan1213@gmail.com> wrote:

On Mon, Jan 25, 2021 at 10:21 AM Andy Fan <zhihui.fan1213@gmail.com>
wrote:

On Sun, Jan 24, 2021 at 6:34 PM Andy Fan <zhihui.fan1213@gmail.com>
wrote:

Hi:

I recently found a use case like this. SELECT * FROM p, q WHERE
p.partkey =
q.colx AND (q.colx = $1 OR q.colx = $2); Then we can't do either
planning time
partition prune or init partition prune. Even though we have run-time
partition pruning work at last, it is too late in some cases since we
have
to init all the plan nodes in advance. In my case, there are 10+
partitioned relation in one query and the execution time is short, so
the
init plan a lot of plan nodes cares a lot.

The attached patches fix this issue. It just get the "p.partkey =
q.colx"
case in root->eq_classes or rel->joinlist (outer join), and then check
if there
is some baserestrictinfo in another relation which can be used for
partition
pruning. To make the things easier, both partkey and colx must be Var
expression in implementation.

- v1-0001-Make-some-static-functions-as-extern-and-extend-C.patch

Just some existing refactoring and extending ChangeVarNodes to be able
to change var->attno.

- v1-0002-Build-some-implied-pruning-quals-to-extend-the-us.patch

Do the real job.

Thought?

--
Best Regards
Andy Fan (https://www.aliyun.com/)

Some results from this patch.

create table p (a int, b int, c character varying(8)) partition by
list(c);
create table p1 partition of p for values in ('000001');
create table p2 partition of p for values in ('000002');
create table p3 partition of p for values in ('000003');
create table q (a int, c character varying(8), b int) partition by
list(c);
create table q1 partition of q for values in ('000001');
create table q2 partition of q for values in ('000002');
create table q3 partition of q for values in ('000003');

Before the patch:
postgres=# explain (costs off) select * from p inner join q on p.c = q.c
and q.c > '000002';
QUERY PLAN
----------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Append
-> Seq Scan on p1 p_1
-> Seq Scan on p2 p_2
-> Seq Scan on p3 p_3
-> Hash
-> Seq Scan on q3 q
Filter: ((c)::text > '000002'::text)
(9 rows)

After the patch:

QUERY PLAN
----------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Seq Scan on p3 p
-> Hash
-> Seq Scan on q3 q
Filter: ((c)::text > '000002'::text)
(6 rows)

Before the patch:
postgres=# explain (costs off) select * from p inner join q on p.c = q.c
and (q.c = '000002' or q.c = '000001');
QUERY PLAN

--------------------------------------------------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Append
-> Seq Scan on p1 p_1
-> Seq Scan on p2 p_2
-> Seq Scan on p3 p_3
-> Hash
-> Append
-> Seq Scan on q1 q_1
Filter: (((c)::text = '000002'::text) OR ((c)::text
= '000001'::text))
-> Seq Scan on q2 q_2
Filter: (((c)::text = '000002'::text) OR ((c)::text
= '000001'::text))
(12 rows)

After the patch:
QUERY PLAN

--------------------------------------------------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Append
-> Seq Scan on p1 p_1
-> Seq Scan on p2 p_2
-> Hash
-> Append
-> Seq Scan on q1 q_1
Filter: (((c)::text = '000002'::text) OR ((c)::text
= '000001'::text))
-> Seq Scan on q2 q_2
Filter: (((c)::text = '000002'::text) OR ((c)::text
= '000001'::text))
(11 rows)

Before the patch:
postgres=# explain (costs off) select * from p left join q on p.c = q.c
where (q.c = '000002' or q.c = '000001');
QUERY PLAN

--------------------------------------------------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Append
-> Seq Scan on p1 p_1
-> Seq Scan on p2 p_2
-> Seq Scan on p3 p_3
-> Hash
-> Append
-> Seq Scan on q1 q_1
Filter: (((c)::text = '000002'::text) OR ((c)::text
= '000001'::text))
-> Seq Scan on q2 q_2
Filter: (((c)::text = '000002'::text) OR ((c)::text
= '000001'::text))
(12 rows)

After the patch:
QUERY PLAN

--------------------------------------------------------------------------------------------
Hash Join
Hash Cond: ((p.c)::text = (q.c)::text)
-> Append
-> Seq Scan on p1 p_1
-> Seq Scan on p2 p_2
-> Hash
-> Append
-> Seq Scan on q1 q_1
Filter: (((c)::text = '000002'::text) OR ((c)::text
= '000001'::text))
-> Seq Scan on q2 q_2
Filter: (((c)::text = '000002'::text) OR ((c)::text
= '000001'::text))
(11 rows)

--
Best Regards
Andy Fan (https://www.aliyun.com/)

Here is a performance test regarding this patch. In the following simple
case,
we can get 3x faster than before.

create table p (a int, b int, c int) partition by list(c);
select 'create table p_'||i||' partition of p for values in (' || i ||
');' from generate_series(1, 100)i; \gexec
insert into p select i, i, i from generate_series(1, 100)i;
create table m as select * from p;
analyze m;
analyze p;

test sql: select * from m, p where m.c = p.c and m.c in (3, 10);

With this patch: 1.1ms
Without this patch: 3.4ms

I'm happy with the result and the implementation, I have add this into
commitfest https://commitfest.postgresql.org/32/2975/

Thanks.

--
Best Regards
Andy Fan (https://www.aliyun.com/)

Rebase to the current latest commit 678d0e239b.

Rebase to the latest commit ea1268f630 .

--
Best Regards
Andy Fan (https://www.aliyun.com/)

Hi Andy,

On Sun, Jan 24, 2021 at 7:34 PM Andy Fan <zhihui.fan1213@gmail.com> wrote:

I recently found a use case like this. SELECT * FROM p, q WHERE p.partkey =
q.colx AND (q.colx = $1 OR q.colx = $2); Then we can't do either planning time
partition prune or init partition prune. Even though we have run-time
partition pruning work at last, it is too late in some cases since we have
to init all the plan nodes in advance. In my case, there are 10+
partitioned relation in one query and the execution time is short, so the
init plan a lot of plan nodes cares a lot.

The attached patches fix this issue. It just get the "p.partkey = q.colx"
case in root->eq_classes or rel->joinlist (outer join), and then check if there
is some baserestrictinfo in another relation which can be used for partition
pruning. To make the things easier, both partkey and colx must be Var
expression in implementation.

- v1-0001-Make-some-static-functions-as-extern-and-extend-C.patch

Just some existing refactoring and extending ChangeVarNodes to be able
to change var->attno.

- v1-0002-Build-some-implied-pruning-quals-to-extend-the-us.patch

IIUC, your proposal is to transpose the "q.b in (1, 2)" in the
following query as "p.a in (1, 2)" and pass it down as a pruning qual
for p:

select * from p, q where p.a = q.b and q.b in (1, 2);

or "(q.b = 1 or q.b = 2)" in the following query as "(p.a = 1 or p.a = 2)":

select * from p, q where p.a = q.b and (q.b = 1 or q.b = 2);

While that transposition sounds *roughly* valid, I have some questions
about the approach:

* If the transposed quals are assumed valid to use for partition
pruning, could they also not be used by, say, the surviving
partitions' index scan paths? So, perhaps, it doesn't seem right that
partprune.c builds the clauses on-the-fly for pruning and dump them
once done.

* On that last part, I wonder if partprune.c isn't the wrong place to
determine that "q.b in (1, 2)" and "p.a in (1, 2)" are in fact
equivalent. That sort of thing is normally done in the phase of
planning when distribute_qual_to_rels() runs and any equivalences
found stored in PlannerInfo.eq_classes. Have you investigated why the
process_ machinery doesn't support working with ScalarArrayOpExpr and
BoolExpr to begin with?

* Or maybe have you considered generalizing what
build_implied_pruning_quals() does so that other places like
indxpath.c can use the facility?

--
Amit Langote
EDB: http://www.enterprisedb.com

Hi Amit:
Thanks for your review!

On Thu, Mar 4, 2021 at 5:07 PM Amit Langote <amitlangote09@gmail.com> wrote:

Hi Andy,

On Sun, Jan 24, 2021 at 7:34 PM Andy Fan <zhihui.fan1213@gmail.com> wrote:

I recently found a use case like this. SELECT * FROM p, q WHERE

p.partkey =

q.colx AND (q.colx = $1 OR q.colx = $2); Then we can't do either

planning time

partition prune or init partition prune. Even though we have run-time
partition pruning work at last, it is too late in some cases since we

have

to init all the plan nodes in advance. In my case, there are 10+
partitioned relation in one query and the execution time is short, so

the

init plan a lot of plan nodes cares a lot.

The attached patches fix this issue. It just get the "p.partkey = q.colx"
case in root->eq_classes or rel->joinlist (outer join), and then check

if there

is some baserestrictinfo in another relation which can be used for

partition

pruning. To make the things easier, both partkey and colx must be Var
expression in implementation.

- v1-0001-Make-some-static-functions-as-extern-and-extend-C.patch

Just some existing refactoring and extending ChangeVarNodes to be able
to change var->attno.

- v1-0002-Build-some-implied-pruning-quals-to-extend-the-us.patch

IIUC, your proposal is to transpose the "q.b in (1, 2)" in the
following query as "p.a in (1, 2)" and pass it down as a pruning qual
for p:

select * from p, q where p.a = q.b and q.b in (1, 2);

or "(q.b = 1 or q.b = 2)" in the following query as "(p.a = 1 or p.a = 2)":

select * from p, q where p.a = q.b and (q.b = 1 or q.b = 2);

Yes, you understand me correctly.

While that transposition sounds *roughly* valid, I have some questions
about the approach:

* If the transposed quals are assumed valid to use for partition
pruning, could they also not be used by, say, the surviving
partitions' index scan paths? So, perhaps, it doesn't seem right that
partprune.c builds the clauses on-the-fly for pruning and dump them
once done.

* On that last part, I wonder if partprune.c isn't the wrong place to
determine that "q.b in (1, 2)" and "p.a in (1, 2)" are in fact
equivalent. That sort of thing is normally done in the phase of
planning when distribute_qual_to_rels() runs and any equivalences
found stored in PlannerInfo.eq_classes. Have you investigated why the
process_ machinery doesn't support working with ScalarArrayOpExpr and
BoolExpr to begin with?

* Or maybe have you considered generalizing what
build_implied_pruning_quals() does so that other places like
indxpath.c can use the facility?

Actually at the beginning of this work, I do think I should put the implied
quals to baserestictinfo in the distribute_qual_for_rels stage. That
probably
can fix all the issues you reported. However that probably more complex
than what I did with more risks and I have a very limited timeline to handle
the real custom issue, so I choose this strategy. But it is the time to
re-think
the baserestrictinfo way now. I will spend some time in this direction,
Thank you
for this kind of push-up:) I just checked this stuff on Oracle, Oracle
does use
this strategy.

SQL> explain plan for select * from t1, t2 where t1.a = t2.a and t1.a > 2;

Explained.

SQL> select * from table(dbms_xplan.display);

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Plan hash value: 1838229974

---------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
---------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 52 | 4 (0)| 00:00:01 |
|* 1 | HASH JOIN | | 1 | 52 | 4 (0)| 00:00:01 |
|* 2 | TABLE ACCESS FULL| T1 | 1 | 26 | 2 (0)| 00:00:01 |
|* 3 | TABLE ACCESS FULL| T2 | 1 | 26 | 2 (0)| 00:00:01 |
---------------------------------------------------------------------------

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------

1 - access("T1"."A"="T2"."A")

* 2 - filter("T1"."A">2) 3 - filter("T2"."A">2)*

17 rows selected.

postgres=# explain (costs off) select * from t1, t2 where t1.a = t2.a and
t1.a > 2;
QUERY PLAN
-------------------------------
Merge Join
Merge Cond: (t1.a = t2.a)
-> Sort
Sort Key: t1.a
-> Seq Scan on t1
Filter: (a > 2)
-> Sort
Sort Key: t2.a
-> Seq Scan on t2
(9 rows)

--
Best Regards
Andy Fan (https://www.aliyun.com/)

On Thu, 4 Mar 2021 at 22:07, Amit Langote <amitlangote09@gmail.com> wrote:

* Or maybe have you considered generalizing what
build_implied_pruning_quals() does so that other places like
indxpath.c can use the facility?

I agree with doing it another way. There's plenty of other queries
which we could produce a better plan for if EquivalenceClass knew
about things like IN conditions and >=, >, < and <= btree ops.

It seems wrong to code anything in this regard that's specific to
partition pruning.

Please see [1]/messages/by-id/CAKJS1f9fPdLKM6=SUZAGwucH3otbsPk6k0YT8-A1HgjFapL-zQ@mail.gmail.com for an idea. IIRC, the implementation was not well
received and there were concerns about having to evaluate additional
needless quals. That part I think can be coded around. The trick will
be to know when and when not to use additional quals.

The show stopper for me was having a more efficient way to find if a
given Expr exists in an EquivalenceClass. This is why I didn't take
the idea further, at the time. My implementation in that patch
required lots of looping to find if a given Expr had an existing
EquivalenceMember, to which there was a danger of that becoming slow
for complex queries.

I'm unsure right now if it would be possible to build standard
EquivalenceMembers and EquivalenceFilters in the same pass. I think
it might require 2 passes since you only can use IN and range type
quals for Exprs that actually have a EquivalenceMember. So you need to
wait until you're certain there's some equality OpExpr before adding
EquivalenceFilters. (Pass 1 can perhaps remember if anything looks
interesting and then skip pass 2 if there's not...??)

EquivalenceClass might be slightly faster now since we have
RelOptInfo.eclass_indexes. However, I've not checked to see if the
indexes will be ready in time for when you'd be building the
additional filters. I'm guessing that they wouldn't be since you'd
still be building the EquivalenceClasses at that time. Certainly,
process_equivalence() could do much faster lookups of Exprs if there
was some global index for all EquivalenceMembers. However,
equalfuncs.c only gives us true or false if two nodes are equal().
We'd need to either have a -1, 0, +1 value or be able to hash nodes
and put things into a hash table. Else we're stuck trawling through
lists comparing each item 1-by-1. That's pretty slow. Especially with
complex queries.

Both Andres and I have previously suggested ways to improve Node
searching. My idea is likely easier to implement, as it just changed
equalfuncs.c to add a function that returns -1, 0, +1 so we could use
a binary search tree to index Nodes. Andres' idea [2]/messages/by-id/20190828234136.fk2ndqtld3onfrrp@alap3.anarazel.de is likely the
better of the two. Please have a look at that. It'll allow us to
easily build a function to hash nodes and put them in a hash table.

To get [1]/messages/by-id/CAKJS1f9fPdLKM6=SUZAGwucH3otbsPk6k0YT8-A1HgjFapL-zQ@mail.gmail.com, the implementation will need to be pretty smart. There's
concern about the idea. See [3]/messages/by-id/30810.1449335261@sss.pgh.pa.us. You'll need to ensure you're not
adding too much planner overhead and also not slowing down execution
for cases by adding additional qual evals that are redundant.

It's going to take some effort to make everyone happy here.

David

[1]: /messages/by-id/CAKJS1f9fPdLKM6=SUZAGwucH3otbsPk6k0YT8-A1HgjFapL-zQ@mail.gmail.com
[2]: /messages/by-id/20190828234136.fk2ndqtld3onfrrp@alap3.anarazel.de
[3]: /messages/by-id/30810.1449335261@sss.pgh.pa.us

Hi David:

On Mon, Mar 8, 2021 at 9:34 AM David Rowley <dgrowleyml@gmail.com> wrote:

On Thu, 4 Mar 2021 at 22:07, Amit Langote <amitlangote09@gmail.com> wrote:

* Or maybe have you considered generalizing what
build_implied_pruning_quals() does so that other places like
indxpath.c can use the facility?

I agree with doing it another way. There's plenty of other queries
which we could produce a better plan for if EquivalenceClass knew
about things like IN conditions and >=, >, < and <= btree ops.

It seems wrong to code anything in this regard that's specific to
partition pruning.

Please see [1] for an idea. IIRC, the implementation was not well
received and there were concerns about having to evaluate additional
needless quals. That part I think can be coded around. The trick will
be to know when and when not to use additional quals.

The show stopper for me was having a more efficient way to find if a
given Expr exists in an EquivalenceClass. This is why I didn't take
the idea further, at the time. My implementation in that patch
required lots of looping to find if a given Expr had an existing
EquivalenceMember, to which there was a danger of that becoming slow
for complex queries.

I'm unsure right now if it would be possible to build standard
EquivalenceMembers and EquivalenceFilters in the same pass. I think
it might require 2 passes since you only can use IN and range type
quals for Exprs that actually have a EquivalenceMember. So you need to
wait until you're certain there's some equality OpExpr before adding
EquivalenceFilters. (Pass 1 can perhaps remember if anything looks
interesting and then skip pass 2 if there's not...??)

EquivalenceClass might be slightly faster now since we have
RelOptInfo.eclass_indexes. However, I've not checked to see if the
indexes will be ready in time for when you'd be building the
additional filters. I'm guessing that they wouldn't be since you'd
still be building the EquivalenceClasses at that time. Certainly,
process_equivalence() could do much faster lookups of Exprs if there
was some global index for all EquivalenceMembers. However,
equalfuncs.c only gives us true or false if two nodes are equal().
We'd need to either have a -1, 0, +1 value or be able to hash nodes
and put things into a hash table. Else we're stuck trawling through
lists comparing each item 1-by-1. That's pretty slow. Especially with
complex queries.

Both Andres and I have previously suggested ways to improve Node
searching. My idea is likely easier to implement, as it just changed
equalfuncs.c to add a function that returns -1, 0, +1 so we could use
a binary search tree to index Nodes. Andres' idea [2] is likely the
better of the two. Please have a look at that. It'll allow us to
easily build a function to hash nodes and put them in a hash table.

To get [1], the implementation will need to be pretty smart. There's
concern about the idea. See [3]. You'll need to ensure you're not
adding too much planner overhead and also not slowing down execution
for cases by adding additional qual evals that are redundant.

It's going to take some effort to make everyone happy here.

I truly understand what you are saying here, and believe that needs some
more hard work to do. I am not sure I am prepared to do that at current
stage. So I will give up this idea now and continue to work with this
when time is permitted. I have marked the commitfest entry as "Returned
with
Feedback". Thanks for the detailed information!

David

[1]
/messages/by-id/CAKJS1f9fPdLKM6=SUZAGwucH3otbsPk6k0YT8-A1HgjFapL-zQ@mail.gmail.com
[2]
/messages/by-id/20190828234136.fk2ndqtld3onfrrp@alap3.anarazel.de
[3]
/messages/by-id/30810.1449335261@sss.pgh.pa.us

--
Best Regards
Andy Fan (https://www.aliyun.com/)