Re: [Proposal] Table partition + join pushdown

Hello Kondo-san,

I briefly checked your patch. Let me put some comments about
its design and implementation, even though I have no arguments
towards its concept. :-)

* Construction of RelOptInfo

In your patch, try_hashjoin_pushdown() called by try_hashjoin_path()
constructs RelOptInfo of the join-rel between inner-rel and a subpath
of Append node. It is entirely wrong implementation.

I can understand we (may) have no RelOptInfo for the joinrel between
tbl_child_0 and other_table, when planner investigates a joinpath to
process join Append path with the other_table.

> HashJoin
> -> Append
> -> SeqScan on tbl_child_0
> -> SeqScan on tbl_child_1
> -> SeqScan on tbl_child_2
> -> SeqScan on tbl_child_3
> -> Hash
> -> SeqScan on other_table
>
How about these alternatives?

- calls make_join_rel() to the pair of tbl_child_X and other_table
by try_hashjoin_pushdown() or somewhere. make_join_rel() internally
construct a RelOptInfo for the supplied pair of relations, so
relevant RelOptInfo shall be properly constructed.
- make_join_rel() also calls add_paths_to_joinrel() towards all the
join logic, so it makes easier to support to push down other join
logic including nested-loop or custom-join.
- It may be an idea to add an extra argument to make_join_rel() to
inform expressions to be applied for tuple filtering on
construction of inner hash table.

* Why only SeqScan is supported

I think it is the role of Hash-node to filter out inner tuples
obviously unrelated to the join (if CHECK constraint of outer relation
gives information), because this join-pushdown may be able to support
multi-stacked pushdown.

For example, if planner considers a path to join this Append-path
with another relation, and join clause contains a reference to X?

> Append
> -> HashJoin
> -> SeqScan on tbl_child_0
> -> Hash ... Filter: hash_func(X) % 4 = 0
> -> SeqScan on other_table
> -> HashJoin
> -> SeqScan on tbl_child_1
> -> Hash ... Filter: hash_func(X) % 4 = 1
> -> SeqScan on other_table
> -> HashJoin
> -> SeqScan on tbl_child_2
> -> Hash ... Filter: hash_func(X) % 4 = 2
> -> SeqScan on other_table
> -> HashJoin
> -> SeqScan on tbl_child_3
> -> Hash ... Filter: hash_func(X) % 4 = 3
> -> SeqScan on other_table
>
It may be a good challenge to consider additional join pushdown,
even if subpaths of Append are HashJoin, not SeqScan, like:

Append
-> HashJoin
-> HashJoin
-> SeqScan on tbl_child_0
-> Hash ... Filter: hash_func(X) % 4 = 0
-> SeqScan on other_table
-> Hash ... Filter: hash_func(X) % 4 = 0
-> SeqScan on another_table
-> HashJoin
-> HashJoin
-> SeqScan on tbl_child_1
-> Hash ... Filter: hash_func(X) % 4 = 1
-> SeqScan on other_table
-> Hash ... Filter: hash_func(X) % 4 = 1
-> SeqScan on another_table
-> HashJoin
-> HashJoin
-> SeqScan on tbl_child_2
-> Hash ... Filter: hash_func(X) % 4 = 2
-> SeqScan on other_table
-> Hash ... Filter: hash_func(X) % 4 = 2
-> SeqScan on another_table
-> HashJoin
-> HashJoin
-> SeqScan on tbl_child_3
-> Hash ... Filter: hash_func(X) % 4 = 3
-> SeqScan on other_table
-> Hash ... Filter: hash_func(X) % 4 = 3
-> SeqScan on another_table

In this case, underlying nodes are not always SeqScan. So, only
Hash-node can have filter clauses.

* Way to handle expression nodes

All this patch supported is CHECK() constraint with equal operation
on INT4 data type. You can learn various useful infrastructure of
PostgreSQL. For example, ...
- expression_tree_mutator() is useful to make a copy of expression
node with small modification
- pull_varnos() is useful to check which relations are referenced
by the expression node.
- RestrictInfo->can_join is useful to check whether the clause is
binary operator, or not.

Anyway, reuse of existing infrastructure is the best way to make
a reliable infrastructure and to keep the implementation simple.

Thanks,
--
NEC Business Creation Division / PG-Strom Project
KaiGai Kohei <kaigai(at)ak(dot)jp(dot)nec(dot)com>

> -----Original Message-----
> From: pgsql-hackers-owner(at)postgresql(dot)org
> [mailto:pgsql-hackers-owner(at)postgresql(dot)org] On Behalf Of Taiki Kondo
> Sent: Thursday, August 13, 2015 6:30 PM
> To: pgsql-hackers(at)postgresql(dot)org
> Cc: Kaigai Kouhei(海外 浩平); Iwaasa Akio(岩浅 晃郎)
> Subject: [HACKERS] [Proposal] Table partition + join pushdown
>
> Hi all,
>
> I saw the email about the idea from KaiGai-san[1],
> and I worked to implement this idea.
>
> Now, I have implemented a part of this idea,
> so I want to propose this feature.
>
> Patch attached just shows my concept of this feature.
> It works fine for EXPLAIN, but it returns wrong result for other operations, sadly.
>
>
>
> Table partition + join pushdown
> ===============================
>
> Motivation
> ----------
> To make join logic working more effectively,
> it is important to make the size of relations smaller.
>
> Especially in Hash-join, it is meaningful to make the inner relation smaller,
> because smaller inner relation can be stored within smaller hash table.
> This means that memory usage can be reduced when joining with big tables.
>
>
> Design
> ------
> It was mentioned by the email from KaiGai-san.
> So I quote below here...
>
> ---- begin quotation ---
> Let's assume a table which is partitioned to four portions,
> and individual child relations have constraint by hash-value
> of its ID field.
>
> tbl_parent
> + tbl_child_0 ... CHECK(hash_func(id) % 4 = 0)
> + tbl_child_1 ... CHECK(hash_func(id) % 4 = 1)
> + tbl_child_2 ... CHECK(hash_func(id) % 4 = 2)
> + tbl_child_3 ... CHECK(hash_func(id) % 4 = 3)
>
> If someone tried to join another relation with tbl_parent
> using equivalence condition, like X = tbl_parent.ID, we
> know inner tuples that does not satisfies the condition
> hash_func(X) % 4 = 0
> shall be never joined to the tuples in tbl_child_0.
> So, we can omit to load these tuples to inner hash table
> preliminary, then it potentially allows to split the
> inner hash-table.
>
> Current typical plan structure is below:
>
> HashJoin
> -> Append
> -> SeqScan on tbl_child_0
> -> SeqScan on tbl_child_1
> -> SeqScan on tbl_child_2
> -> SeqScan on tbl_child_3
> -> Hash
> -> SeqScan on other_table
>
> It may be rewritable to:
>
> Append
> -> HashJoin
> -> SeqScan on tbl_child_0
> -> Hash ... Filter: hash_func(X) % 4 = 0
> -> SeqScan on other_table
> -> HashJoin
> -> SeqScan on tbl_child_1
> -> Hash ... Filter: hash_func(X) % 4 = 1
> -> SeqScan on other_table
> -> HashJoin
> -> SeqScan on tbl_child_2
> -> Hash ... Filter: hash_func(X) % 4 = 2
> -> SeqScan on other_table
> -> HashJoin
> -> SeqScan on tbl_child_3
> -> Hash ... Filter: hash_func(X) % 4 = 3
> -> SeqScan on other_table
> ---- end quotation ---
>
> In the quotation above, it was written that filter is set at Hash node.
> But I implemented that filter is set at SeqScan node under Hash node.
> In my opinion, filtering tuples is work of Scanner.
>
> Append
> -> HashJoin
> -> SeqScan on tbl_child_0
> -> Hash
> -> SeqScan on other_table ... Filter: hash_func(X) % 4 = 0
> -> HashJoin
> -> SeqScan on tbl_child_1
> -> Hash
> -> SeqScan on other_table ... Filter: hash_func(X) % 4 = 1
> -> HashJoin
> -> SeqScan on tbl_child_2
> -> Hash
> -> SeqScan on other_table ... Filter: hash_func(X) % 4 = 2
> -> HashJoin
> -> SeqScan on tbl_child_3
> -> Hash
> -> SeqScan on other_table ... Filter: hash_func(X) % 4 = 3
>
>
> API
> ---
> There are 3 new internal (static) functions to implement this feature.
> try_hashjoin_pushdown(), which is main function of this feature,
> is called from try_hashjoin_path(), and tries to push down HashPath
> under the AppendPath.
>
> To do so, this function does following operations.
>
> 1. Check if this Hash-join can be pushed down under AppendPath
> 2. To avoid an influence on other Path making operation,
> copy inner path's RelOptInfo and make new SeqScan path from it.
> At here, get CHECK() constraints from OUTER path, and convert its
> Var node according to join condition. And also convert Var nodes
> in join condition itself.
> 3. Create new HashPath nodes between each sub-paths of AppendPath and
> inner path made above.
> 4. When operations from 1 to 3 are done for each sub-paths,
> create new AppendPath which sub-paths are HashPath nodes made above.
>
> get_replaced_clause_constr() is called from try_hashjoin_pushdown(),
> and get_var_nodes_recurse() is called from get_replaced_cluase_constr().
> These 2 functions help above operations.
> (I may revise this part to use expression_tree_walker() and
> expression_tree_mutator().)
>
> In patch attached, it has the following limitations.
> o It only works for hash-join operation.
> (I want to support not only hash-join but also other logic.)
> o Join conditions must be "=" operator with int4 variables.
> o Inner path must be SeqScan.
> (I want to support other path-node.)
> o And now, planner may not choose this plan,
> because estimated costs are usually larger than original (non-pushdown) plan.
>
> And also 1 internal (static) function, get_relation_constraints() defined in
> plancat.c, is changed to global. This function will be called from
> get_replaced_clause_constr() to get CHECK() constraints.
>
>
> Usage
> -----
> To use this feature, create partition tables and small table to join,
> and run select operation with joining these tables.
>
> For your convenience, I attach DDL and DML script.
> And I also attach the result of EXPLAIN.
>
>
> Any comments are welcome. But, at first, I need your advices
> to correct this patch's behavior.
>
> At least, I think it has to expand array of RangeTblEntry and other arrays defined
> in PlannerInfo to register new RelOptInfos for new Path nodes mentioned above.
> Or, is it better choice to modify query parser to implement this feature more
> further?
>
>
> Remarks :
> [1]
> http://www.postgresql.org/message-id/9A28C8860F777E439AA12E8AEA7694F8010F672
> B(at)BPXM15GP(dot)gisp(dot)nec(dot)co(dot)jp
>
>
> Best regards,
> --
> Taiki Kondo
>
> NEC Solution Innovators, Ltd.