Patch for removng unused targets

Hi!

Attached patch removes unused targets which are used only for order by when
data already comes in right order. It introduces resorderbyonly flag of
TargetEntry which indicated that entry is used only for ORDER BY clause. If
data comes in right order then such entries are removed in grouping_planner
function.

This is my first patch on planner. Probably, I did it in wrong way. But I
think it is worthwhile optimization and you could give me direction to
rework patch.

Actually we meet need of this optimization when ranking full-text search in
GIN index (it isn't published yet, will post prototype soon). But there is
some synthetic example illustrating benefit from patch.

CREATE OR REPLACE FUNCTION slow_func(x float8, y float8) RETURNS float8 AS
$$
BEGIN
PERFORM pg_sleep(0.01);
RETURN x + y;
END;
$$ IMMUTABLE LANGUAGE plpgsql;

CREATE TABLE test AS (SELECT random() AS x, random() AS y FROM
generate_series(1,1000));
CREATE INDEX test_idx ON test(slow_func(x,y));

Without patch:

test=# EXPLAIN (ANALYZE, VERBOSE) SELECT * FROM test ORDER BY
slow_func(x,y) LIMIT 10;
QUERY PLAN

--------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.00..3.09 rows=10 width=16) (actual time=11.344..103.443
rows=10 loops=1)
Output: x, y, (slow_func(x, y))
-> Index Scan using test_idx on public.test (cost=0.00..309.25
rows=1000 width=16) (actual time=11.341..103.422 rows=10 loops=1)
Output: x, y, slow_func(x, y)
Total runtime: 103.524 ms
(5 rows)

With patch:

test=# EXPLAIN (ANALYZE, VERBOSE) SELECT * FROM test ORDER BY
slow_func(x,y) LIMIT 10;
QUERY PLAN

-----------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.00..3.09 rows=10 width=16) (actual time=0.062..0.093
rows=10 loops=1)
Output: x, y
-> Index Scan using test_idx on public.test (cost=0.00..309.25
rows=1000 width=16) (actual time=0.058..0.085 rows=10 loops=1)
Output: x, y
Total runtime: 0.164 ms
(5 rows)

------
With best regards,
Alexander Korotkov.

Sorry for the delay. I've reviewed the patch. It was applied successfully, and
it worked well for tests I did including the example you showed. I think it's
worth the work, but I'm not sure you go about it in the right way. (I feel the
patch decreases code readability more than it gives an advantage.) If you move
forward in this way, I think the following need to be considered at least:

* The following functions need to be changed to have the resorderbyonly flag:

_equalTargetEntry()

_readTargetEntry()

_outTargetEntry()

* Can we remove the attributes in the coded way safely?

/*

* Plan come out in the right order, we can remove attributes which

* are used only for ORDER BY clause because there is no need to

* calculate them.

*/

The implicit relationship between the TargetEntry's resno and the list size
(the resno is not larger than the list size if I understand it aright) might
break. Is that OK?

(I would like to think a more simple approach to this optimization.)

Thanks,

Best regards,

Etsuro Fujita

From: pgsql-hackers-owner(at)postgresql(dot)org
[mailto:pgsql-hackers-owner(at)postgresql(dot)org] On Behalf Of Alexander Korotkov
Sent: Tuesday, October 02, 2012 4:46 PM
To: pgsql-hackers; Tom Lane
Subject: [HACKERS] Patch for removng unused targets

Hi!

Attached patch removes unused targets which are used only for order by when data
already comes in right order. It introduces resorderbyonly flag of TargetEntry
which indicated that entry is used only for ORDER BY clause. If data comes in
right order then such entries are removed in grouping_planner function.

This is my first patch on planner. Probably, I did it in wrong way. But I think
it is worthwhile optimization and you could give me direction to rework patch.

Actually we meet need of this optimization when ranking full-text search in GIN
index (it isn't published yet, will post prototype soon). But there is some
synthetic example illustrating benefit from patch.

CREATE OR REPLACE FUNCTION slow_func(x float8, y float8) RETURNS float8 AS $$

BEGIN

PERFORM pg_sleep(0.01);

RETURN x + y;

END;

$$ IMMUTABLE LANGUAGE plpgsql;

CREATE TABLE test AS (SELECT random() AS x, random() AS y FROM
generate_series(1,1000));

CREATE INDEX test_idx ON test(slow_func(x,y));

Without patch:

test=# EXPLAIN (ANALYZE, VERBOSE) SELECT * FROM test ORDER BY slow_func(x,y)
LIMIT 10;

QUERY PLAN

--------------------------------------------------------------------------------
------------------------------------------------------

Limit (cost=0.00..3.09 rows=10 width=16) (actual time=11.344..103.443 rows=10
loops=1)

Output: x, y, (slow_func(x, y))

-> Index Scan using test_idx on public.test (cost=0.00..309.25 rows=1000
width=16) (actual time=11.341..103.422 rows=10 loops=1)

Output: x, y, slow_func(x, y)

Total runtime: 103.524 ms

(5 rows)

With patch:

test=# EXPLAIN (ANALYZE, VERBOSE) SELECT * FROM test ORDER BY slow_func(x,y)
LIMIT 10;

QUERY PLAN

--------------------------------------------------------------------------------
---------------------------------------------------

Limit (cost=0.00..3.09 rows=10 width=16) (actual time=0.062..0.093 rows=10
loops=1)

Output: x, y

-> Index Scan using test_idx on public.test (cost=0.00..309.25 rows=1000
width=16) (actual time=0.058..0.085 rows=10 loops=1)

Output: x, y

Total runtime: 0.164 ms

(5 rows)

------
With best regards,
Alexander Korotkov.

"Etsuro Fujita" <fujita(dot)etsuro(at)lab(dot)ntt(dot)co(dot)jp> writes:
> Sorry for the delay. I've reviewed the patch. It was applied
> successfully, and it worked well for tests I did including the example
> you showed. I think it's worth the work, but I'm not sure you go
> about it in the right way. (I feel the patch decreases code
> readability more than it gives an advantage.)

One thought here is that I don't particularly like adding a field like
"resorderbyonly" to TargetEntry in the first place. That makes this
optimization the business of the parser, which it should not be; and
furthermore makes it incumbent on the rewriter, as well as anything else
that manipulates parsetrees, to maintain the flag correctly while
rearranging queries. It would be better if this were strictly the
business of the planner.

But having said that, I'm wondering (without having read the patch)
why you need anything more than the existing "resjunk" field.

regards, tom lane

> From: Tom Lane [mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us]

> "Etsuro Fujita" <fujita(dot)etsuro(at)lab(dot)ntt(dot)co(dot)jp> writes:
> > Sorry for the delay. I've reviewed the patch. It was applied
> > successfully, and it worked well for tests I did including the example
> > you showed. I think it's worth the work, but I'm not sure you go
> > about it in the right way. (I feel the patch decreases code
> > readability more than it gives an advantage.)
>
> One thought here is that I don't particularly like adding a field like
> "resorderbyonly" to TargetEntry in the first place. That makes this
> optimization the business of the parser, which it should not be; and
> furthermore makes it incumbent on the rewriter, as well as anything else
> that manipulates parsetrees, to maintain the flag correctly while
> rearranging queries. It would be better if this were strictly the
> business of the planner.

Okay. I would like to investigate a planner-based approach that would not
require the resorderbyonly field.

Thanks,

Best regards,
Etsuro Fujita

On Mon, Dec 3, 2012 at 8:31 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> "Etsuro Fujita" <fujita(dot)etsuro(at)lab(dot)ntt(dot)co(dot)jp> writes:
> > Sorry for the delay. I've reviewed the patch. It was applied
> > successfully, and it worked well for tests I did including the example
> > you showed. I think it's worth the work, but I'm not sure you go
> > about it in the right way. (I feel the patch decreases code
> > readability more than it gives an advantage.)
>
> One thought here is that I don't particularly like adding a field like
> "resorderbyonly" to TargetEntry in the first place. That makes this
> optimization the business of the parser, which it should not be; and
> furthermore makes it incumbent on the rewriter, as well as anything else
> that manipulates parsetrees, to maintain the flag correctly while
> rearranging queries. It would be better if this were strictly the
> business of the planner.
>
> But having said that, I'm wondering (without having read the patch)
> why you need anything more than the existing "resjunk" field.
>

Actually, I don't know all the cases when "resjunk" flag is set. Is it
reliable to decide target to be used only for "ORDER BY" if it's "resjunk"
and neither system or used in grouping? If it's so or there are some other
cases which are easy to determine then I'll remove "resorderbyonly" flag.

------
With best regards,
Alexander Korotkov.

Alexander Korotkov <aekorotkov(at)gmail(dot)com> writes:
> On Mon, Dec 3, 2012 at 8:31 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> But having said that, I'm wondering (without having read the patch)
>> why you need anything more than the existing "resjunk" field.

> Actually, I don't know all the cases when "resjunk" flag is set. Is it
> reliable to decide target to be used only for "ORDER BY" if it's "resjunk"
> and neither system or used in grouping? If it's so or there are some other
> cases which are easy to determine then I'll remove "resorderbyonly" flag.

resjunk means that the target is not supposed to be output by the query.
Since it's there at all, it's presumably referenced by ORDER BY or GROUP
BY or DISTINCT ON, but the meaning of the flag doesn't depend on that.

What you would need to do is verify that the target is resjunk and not
used in any clause besides ORDER BY. I have not read your patch, but
I rather imagine that what you've got now is that the parser checks this
and sets the new flag for consumption far downstream. Why not just make
the same check in the planner?

A more invasive, but possibly cleaner in the long run, approach is to
strip all resjunk targets from the query's tlist at the start of
planning and only put them back if needed.

BTW, when I looked at this a couple years ago, it seemed like the major
problem was that the planner assumes that all plans for the query should
emit the same tlist, and thus that tlist eval cost isn't a
distinguishing factor. Breaking that assumption seemed to require
rather significant refactoring. I never found the time to try to
actually do it.

regards, tom lane

On Tue, Dec 4, 2012 at 11:52 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Alexander Korotkov <aekorotkov(at)gmail(dot)com> writes:
> > On Mon, Dec 3, 2012 at 8:31 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> >> But having said that, I'm wondering (without having read the patch)
> >> why you need anything more than the existing "resjunk" field.
>
> > Actually, I don't know all the cases when "resjunk" flag is set. Is it
> > reliable to decide target to be used only for "ORDER BY" if it's
> "resjunk"
> > and neither system or used in grouping? If it's so or there are some
> other
> > cases which are easy to determine then I'll remove "resorderbyonly" flag.
>
> resjunk means that the target is not supposed to be output by the query.
> Since it's there at all, it's presumably referenced by ORDER BY or GROUP
> BY or DISTINCT ON, but the meaning of the flag doesn't depend on that.
>
> What you would need to do is verify that the target is resjunk and not
> used in any clause besides ORDER BY. I have not read your patch, but
> I rather imagine that what you've got now is that the parser checks this
> and sets the new flag for consumption far downstream. Why not just make
> the same check in the planner?
>
> A more invasive, but possibly cleaner in the long run, approach is to
> strip all resjunk targets from the query's tlist at the start of
> planning and only put them back if needed.
>
> BTW, when I looked at this a couple years ago, it seemed like the major
> problem was that the planner assumes that all plans for the query should
> emit the same tlist, and thus that tlist eval cost isn't a
> distinguishing factor. Breaking that assumption seemed to require
> rather significant refactoring. I never found the time to try to
> actually do it.
>

May be there is some way to not remove items from tlist, but evade actual
calculation?

------
With best regards,
Alexander Korotkov.

On 12/05/2012 04:15 AM, Alexander Korotkov wrote:
> On Tue, Dec 4, 2012 at 11:52 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us
> <mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us>> wrote:
>
> Alexander Korotkov <aekorotkov(at)gmail(dot)com
> <mailto:aekorotkov(at)gmail(dot)com>> writes:
> > On Mon, Dec 3, 2012 at 8:31 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us
> <mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us>> wrote:
> >> But having said that, I'm wondering (without having read the patch)
> >> why you need anything more than the existing "resjunk" field.
>
> > Actually, I don't know all the cases when "resjunk" flag is set.
> Is it
> > reliable to decide target to be used only for "ORDER BY" if it's
> "resjunk"
> > and neither system or used in grouping? If it's so or there are
> some other
> > cases which are easy to determine then I'll remove
> "resorderbyonly" flag.
>
> resjunk means that the target is not supposed to be output by the
> query.
> Since it's there at all, it's presumably referenced by ORDER BY or
> GROUP
> BY or DISTINCT ON, but the meaning of the flag doesn't depend on that.
>
> What you would need to do is verify that the target is resjunk and not
> used in any clause besides ORDER BY. I have not read your patch, but
> I rather imagine that what you've got now is that the parser
> checks this
> and sets the new flag for consumption far downstream. Why not
> just make
> the same check in the planner?
>
> A more invasive, but possibly cleaner in the long run, approach is to
> strip all resjunk targets from the query's tlist at the start of
> planning and only put them back if needed.
>
> BTW, when I looked at this a couple years ago, it seemed like the
> major
> problem was that the planner assumes that all plans for the query
> should
> emit the same tlist, and thus that tlist eval cost isn't a
> distinguishing factor. Breaking that assumption seemed to require
> rather significant refactoring. I never found the time to try to
> actually do it.
>
>
> May be there is some way to not remove items from tlist, but evade
> actual calculation?

Did you make any headway on this? Is there work in a state that's likely
to be committable for 9.3, or is it perhaps best to defer this to
post-9.3 pending further work and review?

https://commitfest.postgresql.org/action/patch_view?id=980

--
Craig Ringer http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

I'd like to rework on this optimization and submit a patch at the next CF. Is
that okay?

Thanks,

Best regards,

Etsuro Fujita

From: Craig Ringer [mailto:craig(at)2ndQuadrant(dot)com]
Sent: Friday, January 18, 2013 8:30 PM
To: Alexander Korotkov
Cc: Tom Lane; Etsuro Fujita; pgsql-hackers
Subject: Re: [HACKERS] Patch for removng unused targets

On 12/05/2012 04:15 AM, Alexander Korotkov wrote:

On Tue, Dec 4, 2012 at 11:52 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

Alexander Korotkov <aekorotkov(at)gmail(dot)com> writes:
> On Mon, Dec 3, 2012 at 8:31 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

>> But having said that, I'm wondering (without having read the patch)
>> why you need anything more than the existing "resjunk" field.

> Actually, I don't know all the cases when "resjunk" flag is set. Is it
> reliable to decide target to be used only for "ORDER BY" if it's "resjunk"
> and neither system or used in grouping? If it's so or there are some other
> cases which are easy to determine then I'll remove "resorderbyonly" flag.

resjunk means that the target is not supposed to be output by the query.
Since it's there at all, it's presumably referenced by ORDER BY or GROUP
BY or DISTINCT ON, but the meaning of the flag doesn't depend on that.

What you would need to do is verify that the target is resjunk and not
used in any clause besides ORDER BY. I have not read your patch, but
I rather imagine that what you've got now is that the parser checks this
and sets the new flag for consumption far downstream. Why not just make
the same check in the planner?

A more invasive, but possibly cleaner in the long run, approach is to
strip all resjunk targets from the query's tlist at the start of
planning and only put them back if needed.

BTW, when I looked at this a couple years ago, it seemed like the major
problem was that the planner assumes that all plans for the query should
emit the same tlist, and thus that tlist eval cost isn't a
distinguishing factor. Breaking that assumption seemed to require
rather significant refactoring. I never found the time to try to
actually do it.

May be there is some way to not remove items from tlist, but evade actual
calculation?

Did you make any headway on this? Is there work in a state that's likely to be
committable for 9.3, or is it perhaps best to defer this to post-9.3 pending
further work and review?

https://commitfest.postgresql.org/action/patch_view?id=980

--
Craig Ringer http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On 01/22/2013 01:24 PM, Etsuro Fujita wrote:
>
> I'd like to rework on this optimization and submit a patch at the next
> CF. Is that okay?
>
That sounds very sensible to me, given how busy CF2013-01 is and the
remaining time before 9.3.

--
Craig Ringer http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

> From: Tom Lane [mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us]

> Alexander Korotkov <aekorotkov(at)gmail(dot)com> writes:
> > On Mon, Dec 3, 2012 at 8:31 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> >> But having said that, I'm wondering (without having read the patch)
> >> why you need anything more than the existing "resjunk" field.
>
> > Actually, I don't know all the cases when "resjunk" flag is set. Is it
> > reliable to decide target to be used only for "ORDER BY" if it's "resjunk"
> > and neither system or used in grouping? If it's so or there are some other
> > cases which are easy to determine then I'll remove "resorderbyonly" flag.
>
> resjunk means that the target is not supposed to be output by the query.
> Since it's there at all, it's presumably referenced by ORDER BY or GROUP
> BY or DISTINCT ON, but the meaning of the flag doesn't depend on that.
>
> What you would need to do is verify that the target is resjunk and not
> used in any clause besides ORDER BY. I have not read your patch, but
> I rather imagine that what you've got now is that the parser checks this
> and sets the new flag for consumption far downstream. Why not just make
> the same check in the planner?

I've created a patch using this approach. Please find attached the patch.

> A more invasive, but possibly cleaner in the long run, approach is to
> strip all resjunk targets from the query's tlist at the start of
> planning and only put them back if needed.
>
> BTW, when I looked at this a couple years ago, it seemed like the major
> problem was that the planner assumes that all plans for the query should
> emit the same tlist, and thus that tlist eval cost isn't a
> distinguishing factor. Breaking that assumption seemed to require
> rather significant refactoring. I never found the time to try to
> actually do it.

Such an approach would improve code readability, but I'm not sure it's worth the
work for this optimization, though I think I'm missing something.

Thanks,

Best regards,
Etsuro Fujita

Hi Alexander,

I wrote:
> > From: Tom Lane [mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us]

> > resjunk means that the target is not supposed to be output by the query.
> > Since it's there at all, it's presumably referenced by ORDER BY or GROUP
> > BY or DISTINCT ON, but the meaning of the flag doesn't depend on that.

> > What you would need to do is verify that the target is resjunk and not
> > used in any clause besides ORDER BY. I have not read your patch, but
> > I rather imagine that what you've got now is that the parser checks this
> > and sets the new flag for consumption far downstream. Why not just make
> > the same check in the planner?

> I've created a patch using this approach.

I've rebased the above patch against the latest head. Could you review the
patch? If you have no objection, I'd like to mark the patch "ready for
committer".

Thanks,

Best regards,
Etsuro Fujita

Hi Alexander,

I wrote:
> > > From: Tom Lane [mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us]
>
> > > resjunk means that the target is not supposed to be output by the query.
> > > Since it's there at all, it's presumably referenced by ORDER BY or GROUP
> > > BY or DISTINCT ON, but the meaning of the flag doesn't depend on that.
>
> > > What you would need to do is verify that the target is resjunk and not
> > > used in any clause besides ORDER BY. I have not read your patch, but
> > > I rather imagine that what you've got now is that the parser checks this
> > > and sets the new flag for consumption far downstream. Why not just make
> > > the same check in the planner?
>
> > I've created a patch using this approach.
>
> I've rebased the above patch against the latest head. Could you review the
> patch? If you have no objection, I'd like to mark the patch "ready for
> committer".

Sorry, I've had a cleanup of the patch. Please find attached the patch.

Thanks,

Best regards,
Etsuro Fujita

Hi Etsuro!

On Tue, Jun 18, 2013 at 4:15 PM, Etsuro Fujita
<fujita(dot)etsuro(at)lab(dot)ntt(dot)co(dot)jp>wrote:

> Hi Alexander,
>
> I wrote:
> > > > From: Tom Lane [mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us]
> >
> > > > resjunk means that the target is not supposed to be output by the
> query.
> > > > Since it's there at all, it's presumably referenced by ORDER BY or
> GROUP
> > > > BY or DISTINCT ON, but the meaning of the flag doesn't depend on
> that.
> >
> > > > What you would need to do is verify that the target is resjunk and
> not
> > > > used in any clause besides ORDER BY. I have not read your patch, but
> > > > I rather imagine that what you've got now is that the parser checks
> this
> > > > and sets the new flag for consumption far downstream. Why not just
> make
> > > > the same check in the planner?
> >
> > > I've created a patch using this approach.
> >
> > I've rebased the above patch against the latest head. Could you review
> the
> > patch? If you have no objection, I'd like to mark the patch "ready for
> > committer".
>
> Sorry, I've had a cleanup of the patch. Please find attached the patch.

I've checked the attached patch. It looks good for me. No objection to mark
it "ready for committer".

------
With best regards,
Alexander Korotkov.

Hi Alexander,

Thank you for the check! I marked the patch "ready for committer".

Best regards,

Etsuro Fujita

From: Alexander Korotkov [mailto:aekorotkov(at)gmail(dot)com]
Sent: Wednesday, June 19, 2013 1:26 AM
To: Etsuro Fujita
Cc: Tom Lane; pgsql-hackers
Subject: Re: [HACKERS] Patch for removng unused targets

Hi Etsuro!

On Tue, Jun 18, 2013 at 4:15 PM, Etsuro Fujita <fujita(dot)etsuro(at)lab(dot)ntt(dot)co(dot)jp>
wrote:

Hi Alexander,

I wrote:
> > > From: Tom Lane [mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us]
>
> > > resjunk means that the target is not supposed to be output by the query.
> > > Since it's there at all, it's presumably referenced by ORDER BY or GROUP
> > > BY or DISTINCT ON, but the meaning of the flag doesn't depend on that.
>
> > > What you would need to do is verify that the target is resjunk and not
> > > used in any clause besides ORDER BY. I have not read your patch, but
> > > I rather imagine that what you've got now is that the parser checks this
> > > and sets the new flag for consumption far downstream. Why not just make
> > > the same check in the planner?
>
> > I've created a patch using this approach.
>
> I've rebased the above patch against the latest head. Could you review the
> patch? If you have no objection, I'd like to mark the patch "ready for
> committer".

Sorry, I've had a cleanup of the patch. Please find attached the patch.

I've checked the attached patch. It looks good for me. No objection to mark it
"ready for committer".

------
With best regards,
Alexander Korotkov.

On Tue, Jun 18, 2013 at 5:15 AM, Etsuro Fujita
<fujita(dot)etsuro(at)lab(dot)ntt(dot)co(dot)jp>wrote:

> Hi Alexander,
>
> I wrote:
> > > > From: Tom Lane [mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us]
> >
> > > > resjunk means that the target is not supposed to be output by the
> query.
> > > > Since it's there at all, it's presumably referenced by ORDER BY or
> GROUP
> > > > BY or DISTINCT ON, but the meaning of the flag doesn't depend on
> that.
> >
> > > > What you would need to do is verify that the target is resjunk and
> not
> > > > used in any clause besides ORDER BY. I have not read your patch, but
> > > > I rather imagine that what you've got now is that the parser checks
> this
> > > > and sets the new flag for consumption far downstream. Why not just
> make
> > > > the same check in the planner?
> >
> > > I've created a patch using this approach.
> >
> > I've rebased the above patch against the latest head. Could you review
> the
> > patch? If you have no objection, I'd like to mark the patch "ready for
> > committer".
>
> Sorry, I've had a cleanup of the patch. Please find attached the patch.
>

Don't forget about window functions!

test=# EXPLAIN (ANALYZE, VERBOSE) SELECT *, count(*) over (partition by
slow_func(x,y)) FROM test ORDER BY slow_func(x,y) LIMIT
10; QUERY
PLAN
-------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.28..3.52 rows=10 width=16) (actual time=20.860..113.764
rows=10 loops=1)
Output: x, y, (count(*) OVER (?))
-> WindowAgg (cost=0.28..324.27 rows=1000 width=16) (actual
time=20.858..113.747 rows=10 loops=1)
Output: x, y, count(*) OVER (?)
-> Index Scan using test_idx on public.test (cost=0.28..59.27
rows=1000 width=16) (actual time=10.563..113.530 rows=11 loops=1)
Output: slow_func(x, y), x, y
Total runtime: 117.889 ms
(7 rows)

And I don't think it's a good idea to rely on the parse tree to see if we
can remove those unused columns from the target list, because there should
be a lot of optimization that has been done through grouping_planner, and
the parse tree is not necessarily representing the corresponding elements
at this point. I think it'd be better to see path keys to find out the
list of elements that may be removed, rather than SortClause, which would
be a more generalized approach.

Thanks,
--
Hitoshi Harada

Hi Harada-san,

Thank you for the review.

I think that the parse tree has enough information to do this optimization and
that the easiest way to do it is to use the information, though I might not have
understand your comments correctly. So, I would like to fix the bug by simply
modifying the removability check in adjust_targetlist() so that the resjunk
column is not used in GROUP BY, DISTINCT ON and *window PARTITION/ORDER BY*,
besides ORDER BY. No? I am open to any comments.

Thanks,

Best regards,

Etsuro Fujita

From: Hitoshi Harada [mailto:umi(dot)tanuki(at)gmail(dot)com]
Sent: Wednesday, June 19, 2013 2:57 PM
To: Etsuro Fujita
Cc: Tom Lane; Alexander Korotkov; pgsql-hackers
Subject: Re: [HACKERS] Patch for removng unused targets

On Tue, Jun 18, 2013 at 5:15 AM, Etsuro Fujita <fujita(dot)etsuro(at)lab(dot)ntt(dot)co(dot)jp>
wrote:

Hi Alexander,

I wrote:
> > > From: Tom Lane [mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us]
>
> > > resjunk means that the target is not supposed to be output by the query.
> > > Since it's there at all, it's presumably referenced by ORDER BY or GROUP
> > > BY or DISTINCT ON, but the meaning of the flag doesn't depend on that.
>
> > > What you would need to do is verify that the target is resjunk and not
> > > used in any clause besides ORDER BY. I have not read your patch, but
> > > I rather imagine that what you've got now is that the parser checks this
> > > and sets the new flag for consumption far downstream. Why not just make
> > > the same check in the planner?
>
> > I've created a patch using this approach.
>
> I've rebased the above patch against the latest head. Could you review the
> patch? If you have no objection, I'd like to mark the patch "ready for
> committer".

Sorry, I've had a cleanup of the patch. Please find attached the patch.

Don't forget about window functions!

test=# EXPLAIN (ANALYZE, VERBOSE) SELECT *, count(*) over (partition by
slow_func(x,y)) FROM test ORDER BY slow_func(x,y) LIMIT 10;
QUERY PLAN
--------------------------------------------------------------------------------
----------------------------------------------------------- Limit
(cost=0.28..3.52 rows=10 width=16) (actual time=20.860..113.764 rows=10 loops=1)
Output: x, y, (count(*) OVER (?))
-> WindowAgg (cost=0.28..324.27 rows=1000 width=16) (actual
time=20.858..113.747 rows=10 loops=1)
Output: x, y, count(*) OVER (?)
-> Index Scan using test_idx on public.test (cost=0.28..59.27
rows=1000 width=16) (actual time=10.563..113.530 rows=11 loops=1)
Output: slow_func(x, y), x, y
Total runtime: 117.889 ms
(7 rows)

And I don't think it's a good idea to rely on the parse tree to see if we can
remove those unused columns from the target list, because there should be a lot
of optimization that has been done through grouping_planner, and the parse tree
is not necessarily representing the corresponding elements at this point. I
think it'd be better to see path keys to find out the list of elements that may
be removed, rather than SortClause, which would be a more generalized approach.

Thanks,

--
Hitoshi Harada

On Wed, Jun 19, 2013 at 4:49 AM, Etsuro Fujita
<fujita(dot)etsuro(at)lab(dot)ntt(dot)co(dot)jp>wrote:

> Hi Harada-san,****
>
> ** **
>
> Thank you for the review.****
>
> ** **
>
> I think that the parse tree has enough information to do this optimization
> and that the easiest way to do it is to use the information, though I might
> not have understand your comments correctly. So, I would like to fix the
> bug by simply modifying the removability check in adjust_targetlist() so
> that the resjunk column is not used in GROUP BY, DISTINCT ON and *window
> PARTITION/ORDER BY*, besides ORDER BY. No? I am open to any comments.***
> *
>
>
>

I guess the patch works fine, but what I'm saying is it might be limited to
small use cases. Another instance of this that I can think of is ORDER BY
clause of window specifications, which you may want to remove from the
target list as well, in addition to ORDER BY of query. It will just not be
removed by this approach, simply because it is looking at only
parse->sortClause. Certainly you can add more rules to the new function to
look at the window specification, but then I'm not sure what we are
missing. So, as it stands it doesn't have critical issue, but more
generalized approach would be desirable. That said, I don't have strong
objection to the current patch, and just posting one thought to see if
others may have the same opinion.

Thanks,
--
Hitoshi Harada

> From: Hitoshi Harada [mailto:umi(dot)tanuki(at)gmail(dot)com]

> I guess the patch works fine, but what I'm saying is it might be limited to
> small use cases. Another instance of this that I can think of is ORDER BY
clause
> of window specifications, which you may want to remove from the target list
> as well, in addition to ORDER BY of query. It will just not be removed by
this
> approach, simply because it is looking at only parse->sortClause. Certainly
> you can add more rules to the new function to look at the window
specification,
> but then I'm not sure what we are missing.

Yeah, I thought the extension to the window ORDER BY case, too. But I'm not
sure it's worth complicating the code, considering that the objective of this
optimization is to improve full-text search related things if I understand
correctly, though general solutions would be desirable as you mentioned.

> So, as it stands it doesn't have
> critical issue, but more generalized approach would be desirable. That said,
> I don't have strong objection to the current patch, and just posting one
thought
> to see if others may have the same opinion.

OK. I'll also wait for others' comments. For review, an updated version of the
patch is attached, which fixed the bug using the approach that directly uses the
clause information in the parse tree.

Thanks,

Best regards,
Etsuro Fujit

On Thu, Jun 20, 2013 at 12:19 AM, Etsuro Fujita <fujita(dot)etsuro(at)lab(dot)ntt(dot)co(dot)jp
> wrote:

> > From: Hitoshi Harada [mailto:umi(dot)tanuki(at)gmail(dot)com]
>
> > I guess the patch works fine, but what I'm saying is it might be limited
> to
> > small use cases. Another instance of this that I can think of is ORDER
> BY
> clause
> > of window specifications, which you may want to remove from the target
> list
> > as well, in addition to ORDER BY of query. It will just not be removed
> by
> this
> > approach, simply because it is looking at only parse->sortClause.
> Certainly
> > you can add more rules to the new function to look at the window
> specification,
> > but then I'm not sure what we are missing.
>
> Yeah, I thought the extension to the window ORDER BY case, too. But I'm
> not
> sure it's worth complicating the code, considering that the objective of
> this
> optimization is to improve full-text search related things if I understand
> correctly, though general solutions would be desirable as you mentioned.
>
>
Ah, I see the use case now. Makes sense.

> > So, as it stands it doesn't have
> > critical issue, but more generalized approach would be desirable. That
> said,
> > I don't have strong objection to the current patch, and just posting one
> thought
> > to see if others may have the same opinion.
>
> OK. I'll also wait for others' comments. For review, an updated version
> of the
> patch is attached, which fixed the bug using the approach that directly
> uses the
> clause information in the parse tree.
>
>
>
I tried several ways but I couldn't find big problems. Small typo:
s/rejunk/resjunk/

I defer to commiter.

Thanks,
--
Hitoshi Harada

> From: Hitoshi Harada [mailto:umi(dot)tanuki(at)gmail(dot)com]

> I tried several ways but I couldn't find big problems. Small typo:
> s/rejunk/resjunk/

Thank you for the review. Attached is an updated version of the patch.

Thanks,

Best regards,
Etsuro Fujita

Etsuro Fujita escribió:
> > From: Hitoshi Harada [mailto:umi(dot)tanuki(at)gmail(dot)com]
>
> > I tried several ways but I couldn't find big problems. Small typo:
> > s/rejunk/resjunk/
>
> Thank you for the review. Attached is an updated version of the patch.

Thanks. I gave this a look, and made it some trivial adjustments.
Attached is the edited version. I think this needs some more (succint)
code comments:

. why do we want to remove these entries
. why can't we do it in the DISTINCT case
. why don't we remove the cases we don't remove, within adjust_targetlist().

--
Álvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

> From: Alvaro Herrera [mailto:alvherre(at)2ndquadrant(dot)com]

> Etsuro Fujita escribió:
> > > From: Hitoshi Harada [mailto:umi(dot)tanuki(at)gmail(dot)com]
> >
> > > I tried several ways but I couldn't find big problems. Small typo:
> > > s/rejunk/resjunk/
> >
> > Thank you for the review. Attached is an updated version of the patch.
>
> Thanks. I gave this a look, and made it some trivial adjustments.
> Attached is the edited version. I think this needs some more (succint) code
> comments:
>
> . why do we want to remove these entries . why can't we do it in the DISTINCT
> case . why don't we remove the cases we don't remove, within
adjust_targetlist().

Thank you for the adjustments and comments! In addition to adding comments to
the function, I've improved the code in the function a little bit. Please find
attached an updated version of the patch.

Sorry for the late response. (I was busy with another job lately...)

Best regards,
Etsuro Fujita

Everyone,

This patch has been marked "ready for committer" since July 2nd. Can
someone please commit it, and let us close out this CF?

Thanks!

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

On 07/29/2013 03:23 PM, Josh Berkus wrote:
> Everyone,
>
> This patch has been marked "ready for committer" since July 2nd. Can
> someone please commit it, and let us close out this CF?

Hello? Hello? Is there a committer in the house?

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

Josh Berkus escribió:
> On 07/29/2013 03:23 PM, Josh Berkus wrote:
> > Everyone,
> >
> > This patch has been marked "ready for committer" since July 2nd. Can
> > someone please commit it, and let us close out this CF?
>
> Hello? Hello? Is there a committer in the house?

Uhm, I had written a reply but I think it was lost in the shuffle. I
said that "ready for committer" doesn't mean that the patch is ready to
commit, it means that a committer needs to review it. I did give it a
quick review, but I think, as we said elsewhere, that it's best that Tom
commits it.

--
Álvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

Alvaro Herrera <alvherre(at)2ndquadrant(dot)com> writes:
> Josh Berkus escribi:
>> Hello? Hello? Is there a committer in the house?

> Uhm, I had written a reply but I think it was lost in the shuffle. I
> said that "ready for committer" doesn't mean that the patch is ready to
> commit, it means that a committer needs to review it. I did give it a
> quick review, but I think, as we said elsewhere, that it's best that Tom
> commits it.

I should be able to get to it later this week. I've been pretty
distracted with moving all my stuff onto a new server, but it's mostly
up and running now. (If you pay close attention to Received: headers
you'll realize that sss.pgh.pa.us is now a different machine than it was
48 hours ago.)

regards, tom lane

"Etsuro Fujita" <fujita(dot)etsuro(at)lab(dot)ntt(dot)co(dot)jp> writes:
> Thank you for the adjustments and comments! In addition to adding comments to
> the function, I've improved the code in the function a little bit. Please find
> attached an updated version of the patch.

I started looking at this patch (finally). I'm not terribly satisfied
with it, because it addresses only a very small part of what we really
need to do in this area, and I'm afraid we might end up throwing it away
in toto once we make the larger changes needed. I carped about this
a bit back in <15642(dot)1354650764(at)sss(dot)pgh(dot)pa(dot)us>, but to try to fill in
some background, consider a query like

select expensive_function(x) from t;

where, since the DBA is smart, t has an index on expensive_function(x).
Ideally we'd just scan the index and return values out of it, without
recomputing the expensive_function(). The planner is physically able
to produce such a plan, but only in very limited cases, and an even
bigger problem is that its cost accounting doesn't recognize the potential
savings from not evaluating expensive_function(x); therefore, even if it
can generate the right plan, it might discard it in favor of a plan that
doesn't use the index. This patch has got that same problem: it makes
a useful improvement in the finished plan if that plan is of the right
form, but it does nothing to push the planner to produce that form in
the first place.

Basically these problems stem from the assumption that we can treat all
scan/join paths as producing the same "flat" tlist (containing only Vars)
and only worry about tlist evaluation at the top level. I think the fix
will have to involve recognizing that certain paths can produce some
expressions more cheaply than others can, and explicitly including those
expressions in the returned tlists in such cases. That's going to be a
pretty invasive change. (Of course, the executor already works that way,
but the planner has never included such considerations at the Path stage.)

Now, the connection to the patch at hand is that if the query is

select x,y,z from t order by expensive_function(x);

this patch will successfully suppress calculation of the expensive
function, *if* we were lucky enough to make the right choice of plan
without considering the cost of the function. It's perfectly capable
of making the wrong choice though. This will lead to bug reports about
"the planner chooses a dumb plan, even though it knows the right plan is
cheaper when I force it to choose that one". I think it's possible to
revise the patch so that we do take the cost savings into account, at
least at the point in grouping_planner where it chooses between the
cheapest_path and the sorted_path returned by query_planner. (I'm not
sure if there are cases where query_planner would discard the best choice
at an earlier stage, but that seems possible in join queries.) But this
won't do anything for cases where the expensive function appears in the
SELECT list.

So as I said, I'm worried that this will be mostly bogus once we address
the larger problem. With the larger fix in place, the expensive_function
value could come out of the indexscan, and then the resjunk expression
would be nothing more than a Var referencing it, and hence hardly worth
suppressing.

Having said all that, there is one situation where this type of approach
might still be useful even after such a fix, and that's KNNGist-style
queries:

select a,b,c from t order by col <-> constant limit 10;

In a KNNGist search, there's no provision for the index AM to return the
actual value of the ORDER BY expression, and in fact it's theoretically
possible that that value is never even explicitly computed inside the
index AM. So we couldn't suppress the useless evaluation of <-> by dint
of requiring the physical scan to return that value as a Var.

Reading between the lines of the original submission at
<CAPpHfdtG5qoHoD+w=Tz3wC3fZ=b8i21=V5xandBFM=DTo-Yg=Q(at)mail(dot)gmail(dot)com>,
I gather that it's the KNNGist-style case that worries you, so maybe
it's worth applying this type of patch anyway. I'd want to rejigger
it to be aware of the cost implications though, at least for
grouping_planner's choices.

Comments?

regards, tom lane

> Reading between the lines of the original submission at
> <CAPpHfdtG5qoHoD+w=Tz3wC3fZ=b8i21=V5xandBFM=DTo-Yg=Q(at)mail(dot)gmail(dot)com>,
> I gather that it's the KNNGist-style case that worries you, so maybe
> it's worth applying this type of patch anyway. I'd want to rejigger
> it to be aware of the cost implications though, at least for
> grouping_planner's choices.

Hmm. Can we optimize for the KNN case, without causing the issues which
you warned about earlier in your post? I'm really wary of any
"optimization" which operates completely outside of the cost model; the
ones we have (abort-early plans, for example) are already among our
primary sources of bad plan issues.

>
> Comments?

So, Returned With Feedback, or move it to September?

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

Josh Berkus <josh(at)agliodbs(dot)com> writes:
>> Reading between the lines of the original submission at
>> <CAPpHfdtG5qoHoD+w=Tz3wC3fZ=b8i21=V5xandBFM=DTo-Yg=Q(at)mail(dot)gmail(dot)com>,
>> I gather that it's the KNNGist-style case that worries you, so maybe
>> it's worth applying this type of patch anyway. I'd want to rejigger
>> it to be aware of the cost implications though, at least for
>> grouping_planner's choices.

> Hmm. Can we optimize for the KNN case, without causing the issues which
> you warned about earlier in your post?

Those are pre-existing issues, not something that would be made any worse
by this patch. The main thing I think is really wrong with the patch
as it stands is that the cost savings from suppressing the ORDER BY
expressions should enter into the cheapest_path-vs-sorted_path decision,
which it doesn't, in fact the total cost the plan is labeled with isn't
corrected either. (Not that that matters for the current level of plan,
but it could matter at an outer level if this is a subquery.) I think
that is fixable but am just wondering whether to bother.

> So, Returned With Feedback, or move it to September?

The patch is certainly not getting committed as-is (at least not by me),
so it would likely be fair to mark it RWF so we can close the commitfest.
I'll still work on a revised version after the fest if people think that
improving the KNN-search case is worth a patch that's a bit larger than
this one currently is.

regards, tom lane

On 08/02/2013 03:45 PM, Tom Lane wrote:

>> So, Returned With Feedback, or move it to September?
>
> The patch is certainly not getting committed as-is (at least not by me),
> so it would likely be fair to mark it RWF so we can close the commitfest.
> I'll still work on a revised version after the fest if people think that
> improving the KNN-search case is worth a patch that's a bit larger than
> this one currently is.

Ok, marking it "returned with feedback".

Thanks!

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

> From: Tom Lane [mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us]

> Having said all that, there is one situation where this type of approach might
> still be useful even after such a fix, and that's KNNGist-style
> queries:
>
> select a,b,c from t order by col <-> constant limit 10;
>
> In a KNNGist search, there's no provision for the index AM to return the
actual
> value of the ORDER BY expression, and in fact it's theoretically possible that
> that value is never even explicitly computed inside the index AM. So we
couldn't
> suppress the useless evaluation of <-> by dint of requiring the physical scan
> to return that value as a Var.
>
> Reading between the lines of the original submission at
> <CAPpHfdtG5qoHoD+w=Tz3wC3fZ=b8i21=V5xandBFM=DTo-Yg=Q(at)mail(dot)gmail(dot)com>,
> I gather that it's the KNNGist-style case that worries you, so maybe it's
worth
> applying this type of patch anyway. I'd want to rejigger it to be aware of
> the cost implications though, at least for grouping_planner's choices.

+1 for improving KNNGist-style queries.

Sorry for the late response.

Thanks,

Best regards,
Etsuro Fujita