Обсуждение: PassDownLimitBound for ForeignScan/CustomScan

Hello,

The attached patch adds an optional callback to support special optimization
if ForeignScan/CustomScan are located under the Limit node in plan-tree.

Our sort node wisely switches the behavior when we can preliminary know
exact number of rows to be produced, because all the Sort node has to
return is the top-k rows when it is located under the Limit node.
It is much lightweight workloads than sorting of entire input rows when
nrows is not small.

In my case, this information is very useful because GPU can complete its
sorting operations mostly on L1-grade memory if we can preliminary know
the top-k value is enough small and fits to size of the fast memory.

Probably, it is also valuable for Fujita-san's case because this information
allows to attach "LIMIT k" clause on the remote query of postgres_fdw.
It will reduce amount of the network traffic and remote CPU consumption
once we got support of sort pushdown.

One thing we need to pay attention is cost estimation on the planner stage.
In the existing code, only create_ordered_paths() and create_merge_append_path()
considers the limit clause for cost estimation of sorting. They use the
'limit_tuples' of PlannerInfo; we can reference the structure when extension
adds ForeignPath/CustomPath, so I think we don't need a special enhancement
on the planner stage.

Thanks,
--
NEC Business Creation Division / PG-Strom Project
KaiGai Kohei <kaigai@ak.jp.nec.com>

> On Mon, Aug 29, 2016 at 7:25 AM, Kouhei Kaigai <kaigai@ak.jp.nec.com> wrote:
> 
> 
>     Hello,
> 
>     The attached patch adds an optional callback to support special optimization
>     if ForeignScan/CustomScan are located under the Limit node in plan-tree.
> 
>     Our sort node wisely switches the behavior when we can preliminary know
>     exact number of rows to be produced, because all the Sort node has to
>     return is the top-k rows when it is located under the Limit node.
>     It is much lightweight workloads than sorting of entire input rows when
>     nrows is not small.
> 
>     In my case, this information is very useful because GPU can complete its
>     sorting operations mostly on L1-grade memory if we can preliminary know
>     the top-k value is enough small and fits to size of the fast memory.
> 
>     Probably, it is also valuable for Fujita-san's case because this information
>     allows to attach "LIMIT k" clause on the remote query of postgres_fdw.
>     It will reduce amount of the network traffic and remote CPU consumption
>     once we got support of sort pushdown.
> 
> 
> 
>     One thing we need to pay attention is cost estimation on the planner stage.
>     In the existing code, only create_ordered_paths() and
> create_merge_append_path()
>     considers the limit clause for cost estimation of sorting. They use the
>     'limit_tuples' of PlannerInfo; we can reference the structure when extension
>     adds ForeignPath/CustomPath, so I think we don't need a special enhancement
>     on the planner stage.
>
Thanks for your comments.

> I believe this hook is gets called at execution time.
> So to push LIMIT clause like you said above we should use "limit_tuples" at the time
> of planning and then use this hook to optimize at runtime, right?
>
Yes. For more correctness, a valid "limit_tuples" of PlannerInfo is set only when
LIMIT clause takes constant values; it is true for most of use case.
Then, the hook I added shall be called at execution time for more exact optimization.

If FDW/CSP cannot accept uncertain number of rows to generate on planning time,
it is not a duty to provide its own path which is optimized for small number of
LIMIT clause.

> Apart from that, attached patch applies cleanly on latest sources and found no issues
> with make or with regressions.
> 
> However this patch is an infrastructure for any possible optimization when
> foreign/customscan is under LIMIT.
> 
> So look good to me.
> 
> I quickly tried adding a hook support in postgres_fdw, and it gets called correctly
> when we have foreignscan with LIMIT (limit being evaluated on local server).
> 
> So code wise no issue. Also add this hook details in documentation.
>
OK, I'll try to write up some detailed documentation stuff; not only API specification.

Best regards,

> 
> Thanks
> 
> 
> 
>     Thanks,
>     --
>     NEC Business Creation Division / PG-Strom Project
>     KaiGai Kohei <kaigai@ak.jp.nec.com>
> 
> 
> 
>     --
>     Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
>     To make changes to your subscription:
>     http://www.postgresql.org/mailpref/pgsql-hackers
> <http://www.postgresql.org/mailpref/pgsql-hackers>
> 
> 
> 
> 
> 
> 
> --
> 
> Jeevan B Chalke
> Principal Software Engineer, Product Development
> EnterpriseDB Corporation
> The Enterprise PostgreSQL Company
> 

> -----Original Message-----
> From: pgsql-hackers-owner@postgresql.org
> [mailto:pgsql-hackers-owner@postgresql.org] On Behalf Of Kouhei Kaigai
> Sent: Monday, September 05, 2016 12:58 PM
> To: Jeevan Chalke
> Cc: pgsql-hackers@postgresql.org; Etsuro Fujita
> Subject: Re: [HACKERS] PassDownLimitBound for ForeignScan/CustomScan
> 
> > On Mon, Aug 29, 2016 at 7:25 AM, Kouhei Kaigai <kaigai@ak.jp.nec.com> wrote:
> >
> >
> >     Hello,
> >
> >     The attached patch adds an optional callback to support special optimization
> >     if ForeignScan/CustomScan are located under the Limit node in plan-tree.
> >
> >     Our sort node wisely switches the behavior when we can preliminary know
> >     exact number of rows to be produced, because all the Sort node has to
> >     return is the top-k rows when it is located under the Limit node.
> >     It is much lightweight workloads than sorting of entire input rows when
> >     nrows is not small.
> >
> >     In my case, this information is very useful because GPU can complete its
> >     sorting operations mostly on L1-grade memory if we can preliminary know
> >     the top-k value is enough small and fits to size of the fast memory.
> >
> >     Probably, it is also valuable for Fujita-san's case because this information
> >     allows to attach "LIMIT k" clause on the remote query of postgres_fdw.
> >     It will reduce amount of the network traffic and remote CPU consumption
> >     once we got support of sort pushdown.
> >
> >
> >
> >     One thing we need to pay attention is cost estimation on the planner stage.
> >     In the existing code, only create_ordered_paths() and
> > create_merge_append_path()
> >     considers the limit clause for cost estimation of sorting. They use the
> >     'limit_tuples' of PlannerInfo; we can reference the structure when extension
> >     adds ForeignPath/CustomPath, so I think we don't need a special enhancement
> >     on the planner stage.
> >
> Thanks for your comments.
> 
> > I believe this hook is gets called at execution time.
> > So to push LIMIT clause like you said above we should use "limit_tuples" at the time
> > of planning and then use this hook to optimize at runtime, right?
> >
> Yes. For more correctness, a valid "limit_tuples" of PlannerInfo is set only when
> LIMIT clause takes constant values; it is true for most of use case.
> Then, the hook I added shall be called at execution time for more exact optimization.
> 
> If FDW/CSP cannot accept uncertain number of rows to generate on planning time,
> it is not a duty to provide its own path which is optimized for small number of
> LIMIT clause.
> 
> > Apart from that, attached patch applies cleanly on latest sources and found no issues
> > with make or with regressions.
> >
> > However this patch is an infrastructure for any possible optimization when
> > foreign/customscan is under LIMIT.
> >
> > So look good to me.
> >
> > I quickly tried adding a hook support in postgres_fdw, and it gets called correctly
> > when we have foreignscan with LIMIT (limit being evaluated on local server).
> >
> > So code wise no issue. Also add this hook details in documentation.
> >
> OK, I'll try to write up some detailed documentation stuff; not only API specification.
>
The v2 patch attached. It introduces the role of this hook and how extension
utilizes the LIMIT clause for its further optimization on planning and
execution time.

Thanks,
--
NEC Business Creation Division / PG-Strom Project
KaiGai Kohei <kaigai@ak.jp.nec.com>

Sorry for my late.

The attached patch fixed the wording problems on SGML part.

Best regards,
--
NEC Business Creation Division / PG-Strom Project
KaiGai Kohei <kaigai@ak.jp.nec.com>

> -----Original Message-----
> From: Jeevan Chalke [mailto:jeevan.chalke@enterprisedb.com]
> Sent: Tuesday, September 06, 2016 11:22 PM
> To: Kaigai Kouhei(海外 浩平)
> Cc: pgsql-hackers@postgresql.org; Etsuro Fujita
> Subject: Re: [HACKERS] PassDownLimitBound for ForeignScan/CustomScan
> 
> Hi,
> 
> Changes look good to me.
> 
> However there are couple of minor issues need to be fixed.
> 
> 1.
> "under" repeated on second line. Please remove.
> +    if and when <structname>CustomScanState</> is located under
> +    under <structname>LimitState</>; which implies the underlying node is not
> 
> 2.
> Typo: dicsussion => discussion
> Please fix.
> 
> Apart from this I see no issues.
> 
> 
> Thanks
> 
> 
> --
> 
> Jeevan B Chalke
> Principal Software Engineer, Product Development
> EnterpriseDB Corporation
> The Enterprise PostgreSQL Company
> 

On Tue, Sep 13, 2016 at 3:48 AM, Kouhei Kaigai <kaigai@ak.jp.nec.com> wrote:
> Sorry for my late.
>
> The attached patch fixed the wording problems on SGML part.

I agree that we should have some way for foreign data wrappers and
custom scans and perhaps also other executor nodes to find out whether
there's a known limit to the number of tuples that they might need to
produce, but I wonder if we should be doing something more general
than this.  For example, suppose we add a new PlanState member "long
numTuples" where 0 means that the number of tuples that will be needed
is unknown (so that most node types need not initialize it), a
positive value is an upper bound on the number of tuples that will be
fetched, and -1 means that it is known for certain that we will need
all of the tuples.  This might be relevant to the executor batching
stuff that Andres has been working on, because you could for example
set ps->numTuples == 1 on the inner side of a semi-join, warning the
executor node that it shouldn't bother trying to batch anything.

On a more practical level, I notice that you haven't adapted
postgres_fdw or file_fdw to benefit from this new callback.  It seems
like postgres_fdw could benefit, because it could fetch only the
required number of tuples if that happens to be a smaller number than
the configured fetch_size.

Andres, anyone, thoughts?

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas@gmail.com> writes:
> I agree that we should have some way for foreign data wrappers and
> custom scans and perhaps also other executor nodes to find out whether
> there's a known limit to the number of tuples that they might need to
> produce, but I wonder if we should be doing something more general
> than this.

I had the same feeling that this could stand to be considered more
generally, but had not had time to consider it in detail.  The bound
passdown from Limit to Sort was never anything but a quick-and-dirty
private hack, and I'm not very comfortable with just exposing it to the
whole world without reconsidering the design.

> On a more practical level, I notice that you haven't adapted
> postgres_fdw or file_fdw to benefit from this new callback.  It seems
> like postgres_fdw could benefit, because it could fetch only the
> required number of tuples if that happens to be a smaller number than
> the configured fetch_size.

I think we should insist on that, either in the base patch or a followup
patch, because you never know if a hook is actually convenient to use
until you try.
        regards, tom lane

> On Tue, Sep 13, 2016 at 3:48 AM, Kouhei Kaigai <kaigai@ak.jp.nec.com> wrote:
> > Sorry for my late.
> >
> > The attached patch fixed the wording problems on SGML part.
> 
> I agree that we should have some way for foreign data wrappers and
> custom scans and perhaps also other executor nodes to find out whether
> there's a known limit to the number of tuples that they might need to
> produce, but I wonder if we should be doing something more general
> than this.  For example, suppose we add a new PlanState member "long
> numTuples" where 0 means that the number of tuples that will be needed
> is unknown (so that most node types need not initialize it), a
> positive value is an upper bound on the number of tuples that will be
> fetched, and -1 means that it is known for certain that we will need
> all of the tuples.  This might be relevant to the executor batching
> stuff that Andres has been working on, because you could for example
> set ps->numTuples == 1 on the inner side of a semi-join, warning the
> executor node that it shouldn't bother trying to batch anything.
>
I also think the generic approach is a preferable direction.

In the current implementation calls recompute_limits() on the first
invocation of ExecLimit and ExecReScanLimit. Do we expect the
ps->numTuples will be also passed down to the child nodes on the same
timing?
I also think this new executor contract shall be considered as a hint
(but not a requirement) for the child nodes, because it allows the
parent nodes to re-distribute the upper limit regardless of the type
of the child nodes as long as the parent node can work correctly and
has benefit even if the child node returns a part of tuples. It makes
the decision whether the upper limit should be passed down much simple.
The child node "can" ignore the hint but can utilize for more optimization.

> On a more practical level, I notice that you haven't adapted
> postgres_fdw or file_fdw to benefit from this new callback.  It seems
> like postgres_fdw could benefit, because it could fetch only the
> required number of tuples if that happens to be a smaller number than
> the configured fetch_size.
>
It is because of just my time pressure around the patch submission days.
I'll try to enhance postgres_fdw as a usage of this run-time optimization.

Thanks,
--
NEC Business Creation Division / PG-Strom Project
KaiGai Kohei <kaigai@ak.jp.nec.com>

On Tue, Sep 13, 2016 at 9:07 PM, Kouhei Kaigai <kaigai@ak.jp.nec.com> wrote:
> In the current implementation calls recompute_limits() on the first
> invocation of ExecLimit and ExecReScanLimit. Do we expect the
> ps->numTuples will be also passed down to the child nodes on the same
> timing?

Sure, unless we find some reason why that's not good.

> I also think this new executor contract shall be considered as a hint
> (but not a requirement) for the child nodes, because it allows the
> parent nodes to re-distribute the upper limit regardless of the type
> of the child nodes as long as the parent node can work correctly and
> has benefit even if the child node returns a part of tuples. It makes
> the decision whether the upper limit should be passed down much simple.
> The child node "can" ignore the hint but can utilize for more optimization.

+1.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Tue, Sep 13, 2016 at 9:07 PM, Kouhei Kaigai <kaigai@ak.jp.nec.com> wrote:
> It is because of just my time pressure around the patch submission days.
> I'll try to enhance postgres_fdw as a usage of this run-time optimization.

Time has (pretty much) expired for this CommitFest.  In any case, this
will amount to a whole new patch, not just a rework of the current
one.  So I'm going to mark this "Rejected" in the CommitFest, and I
suggest you start a new thread for the proposed approach if you get a
chance to work on it.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company