Super PathKeys (Allowing sort order through precision loss functions)

On Tue, 30 Oct 2018 at 07:58, David Rowley <david.rowley@2ndquadrant.com>
wrote:

I've started working on something I've ended up calling "Super
PathKeys". The idea here is to increase the likelihood of a Path with
PathKeys being used for a purpose that requires a less strict sort
order due to ordering being required from the return value of some
precision loss function.

Anything left anchored would benefit, so SUBSTR(), TRIM() etc

Main use for this would be where the partition condition is a function, so
we can still order by partitions easily.

--
Simon Riggs http://www.2ndQuadrant.com/
<http://www.2ndquadrant.com/&gt;
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

David Rowley <david.rowley@2ndquadrant.com> writes:

I've started working on something I've ended up calling "Super
PathKeys". The idea here is to increase the likelihood of a Path with
PathKeys being used for a purpose that requires a less strict sort
order due to ordering being required from the return value of some
precision loss function.

I'm a little confused by the terminology here, or why this has anything
at all to do with a new sort of pathkey. It seems like the idea you're
driving at is to be able to mark a function as being order-preserving,
in the sense that if one input is known sorted then the output will
also be sorted (by the same or a related opclass). You probably need
some additional constraints, like any other inputs being constants,
before that really works. But given that, I don't see why you need a
new kind of pathkey: you just have a new way to conclude that some
path is sorted by the pathkey you already want.

Maybe if I read the patch it'd be clearer why you want to describe it
that way, but I'm too lazy to do that right now. One thing I would
say though is that a pg_proc column identifying the interesting input
parameter is insufficient; you'd need to *explicitly* say which opclass(es)
the sorting behavior guarantee applies for.

-- Test a more complex case where the superkey can be matched to
multiple pathkeys
explain (costs off) select date_trunc('year', ts), date_trunc('month',
ts), a, count(*) from tstbl group by 1,2,3 order by 1,2,3;
QUERY PLAN
-----------------------------------------------------------------------------
GroupAggregate
Group Key: date_trunc('year'::text, ts), date_trunc('month'::text, ts), a
-> Index Only Scan using tstbl_ts_a_idx on tstbl
(3 rows)

[ squint... ] Does that really work? If so, how? It would need a whole
lot more knowledge about the behavior of date_trunc than I think could
possibly be reasonable to encode in a general mechanism.

regards, tom lane

On 31 October 2018 at 08:52, Tom Lane <tgl@sss.pgh.pa.us> wrote:

David Rowley <david.rowley@2ndquadrant.com> writes:

I've started working on something I've ended up calling "Super
PathKeys". The idea here is to increase the likelihood of a Path with
PathKeys being used for a purpose that requires a less strict sort
order due to ordering being required from the return value of some
precision loss function.

I'm a little confused by the terminology here, or why this has anything
at all to do with a new sort of pathkey. It seems like the idea you're
driving at is to be able to mark a function as being order-preserving,
in the sense that if one input is known sorted then the output will
also be sorted (by the same or a related opclass). You probably need
some additional constraints, like any other inputs being constants,
before that really works. But given that, I don't see why you need a
new kind of pathkey: you just have a new way to conclude that some
path is sorted by the pathkey you already want.

Thanks for chipping in on this.

The additional pathkeys are not required to make it work, they're just
required to make it work efficiently. The fact that we could to the
trouble of making pathkeys canonical so we can perform pointer
comparison rather than using equals() says to me that I'd better not
do anything to slow this down too much. Doing it without the superkey
idea seems to require quite a bit of analysis during
pathkeys_contained_in() as we'd need to check for superkeys then,
instead of when we're building the pathkey in the first place. As
for the code that I did add to pathkeys_contained_in(), I doubt it's
measurably slower for the normal case.

The other fields being Const part I did miss. That will also be a
requirement. I just failed to consider that date_trunc() could be used
with a variable 1st arg.

Maybe if I read the patch it'd be clearer why you want to describe it
that way, but I'm too lazy to do that right now. One thing I would
say though is that a pg_proc column identifying the interesting input
parameter is insufficient; you'd need to *explicitly* say which opclass(es)
the sorting behavior guarantee applies for.

-- Test a more complex case where the superkey can be matched to
multiple pathkeys
explain (costs off) select date_trunc('year', ts), date_trunc('month',
ts), a, count(*) from tstbl group by 1,2,3 order by 1,2,3;
QUERY PLAN
-----------------------------------------------------------------------------
GroupAggregate
Group Key: date_trunc('year'::text, ts), date_trunc('month'::text, ts), a
-> Index Only Scan using tstbl_ts_a_idx on tstbl
(3 rows)

[ squint... ] Does that really work? If so, how? It would need a whole
lot more knowledge about the behavior of date_trunc than I think could
possibly be reasonable to encode in a general mechanism.

I'm not entirely certain we can always consume multiple matching keys
or if it has to be one for one. However, I get an empty diff from each
of the following two query pairs.

select date_trunc('month'::text,date),date_Trunc('year', date) from dt
order by dt;
select date_trunc('month'::text,date),date_Trunc('year', date) from dt
order by 1,2;

and

select date_trunc('year'::text,date),date_Trunc('month', date) from dt
order by dt;
select date_trunc('year'::text,date),date_Trunc('month', date) from dt
order by 1,2;

with setup:

create table dt (date date);
insert into dt select d from generate_series('2018-01-01',
'2018-12-31', '1 day'::interval) d;

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

Hi,

On 10/30/2018 11:41 PM, David Rowley wrote:

On 31 October 2018 at 08:52, Tom Lane <tgl@sss.pgh.pa.us> wrote:

David Rowley <david.rowley@2ndquadrant.com> writes:

I've started working on something I've ended up calling "Super
PathKeys". The idea here is to increase the likelihood of a Path with
PathKeys being used for a purpose that requires a less strict sort
order due to ordering being required from the return value of some
precision loss function.

I'm a little confused by the terminology here, or why this has anything
at all to do with a new sort of pathkey. It seems like the idea you're
driving at is to be able to mark a function as being order-preserving,
in the sense that if one input is known sorted then the output will
also be sorted (by the same or a related opclass). You probably need
some additional constraints, like any other inputs being constants,
before that really works. But given that, I don't see why you need a
new kind of pathkey: you just have a new way to conclude that some
path is sorted by the pathkey you already want.

Thanks for chipping in on this.

The additional pathkeys are not required to make it work, they're just
required to make it work efficiently. The fact that we could to the
trouble of making pathkeys canonical so we can perform pointer
comparison rather than using equals() says to me that I'd better not
do anything to slow this down too much. Doing it without the superkey
idea seems to require quite a bit of analysis during
pathkeys_contained_in() as we'd need to check for superkeys then,
instead of when we're building the pathkey in the first place. As
for the code that I did add to pathkeys_contained_in(), I doubt it's
measurably slower for the normal case.

The other fields being Const part I did miss. That will also be a
requirement. I just failed to consider that date_trunc() could be used
with a variable 1st arg.

Maybe if I read the patch it'd be clearer why you want to describe it
that way, but I'm too lazy to do that right now. One thing I would
say though is that a pg_proc column identifying the interesting input
parameter is insufficient; you'd need to *explicitly* say which opclass(es)
the sorting behavior guarantee applies for.

The other thing likely affecting this is locale / collation. Probably
not for date_trunc, but certainly for things like substr()/trim(),
mentioned by Simon upthread.

In some languages the rules are pretty complex, and there's no chance
it'll survive arbitrary substr() applied to the string. For example, in
Czech we mostly sort character-by-character, but "ch" is an exception
sorted in between "h" and "i".

So essentially "hhhh <= hchh <= hihh". Obviously, substr($1,0,3) cuts
the "ch" in half, changing the ordering:

create table x (y text collate "cs_CZ");
insert into x values ('hhhh'), ('hchh'), ('hihh');

test=# select y from x order by 1;
y
------
hhhh
hchh
hihh
(3 rows)

test=# select substr(y,0,3) from x order by 1;
substr
--------
hc
hh
hi
(3 rows)

I'm preeeeeeetty sure other languages have even funnier rules ...

-- Test a more complex case where the superkey can be matched to
multiple pathkeys
explain (costs off) select date_trunc('year', ts), date_trunc('month',
ts), a, count(*) from tstbl group by 1,2,3 order by 1,2,3;
QUERY PLAN
-----------------------------------------------------------------------------
GroupAggregate
Group Key: date_trunc('year'::text, ts), date_trunc('month'::text, ts), a
-> Index Only Scan using tstbl_ts_a_idx on tstbl
(3 rows)

[ squint... ] Does that really work? If so, how? It would need a whole
lot more knowledge about the behavior of date_trunc than I think could
possibly be reasonable to encode in a general mechanism.

I'm not entirely certain we can always consume multiple matching keys
or if it has to be one for one. However, I get an empty diff from each
of the following two query pairs.

select date_trunc('month'::text,date),date_Trunc('year', date) from dt
order by dt;
select date_trunc('month'::text,date),date_Trunc('year', date) from dt
order by 1,2;

and

select date_trunc('year'::text,date),date_Trunc('month', date) from dt
order by dt;
select date_trunc('year'::text,date),date_Trunc('month', date) from dt
order by 1,2;

with setup:

create table dt (date date);
insert into dt select d from generate_series('2018-01-01',
'2018-12-31', '1 day'::interval) d;

I'm mildly suspicious of this data set, because it's essentially
perfectly sorted/deterministic, and the Sort node won't have to do
anything. So perhaps it just works by chance.

Consider this instead:

create table dt (ts timestamp, x text);

insert into dt select * from (select d, (case when random() < 0.5 then
'month' else 'hour' end) from generate_series('2018-01-01'::timestamp,
'2018-12-31'::timestamp, '1 hour'::interval) d) as foo order by random();

test=# explain select date_trunc(x, ts) from dt order by 1;
QUERY PLAN
-------------------------------------------------------------
Sort (cost=729.18..751.02 rows=8737 width=8)
Sort Key: (date_trunc(x, ts))
-> Seq Scan on dt (cost=0.00..157.21 rows=8737 width=8)
(3 rows)

test=# select date_trunc(x, ts) from dt order by 1;

date_trunc
---------------------
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
... seems ok ...

test=# explain select date_trunc(x, ts) from dt order by ts;
QUERY PLAN
--------------------------------------------------------------
Sort (cost=729.18..751.02 rows=8737 width=16)
Sort Key: ts
-> Seq Scan on dt (cost=0.00..157.21 rows=8737 width=16)
(3 rows)

test=# select date_trunc(x, ts) from dt order by ts;

date_trunc
---------------------
2018-01-01 00:00:00
2018-01-01 01:00:00
2018-01-01 02:00:00
2018-01-01 00:00:00
2018-01-01 04:00:00
2018-01-01 05:00:00
2018-01-01 06:00:00
2018-01-01 07:00:00
2018-01-01 08:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 13:00:00
2018-01-01 14:00:00
2018-01-01 00:00:00
2018-01-01 16:00:00
2018-01-01 17:00:00
2018-01-01 18:00:00
2018-01-01 19:00:00
2018-01-01 20:00:00
2018-01-01 21:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-02 00:00:00
2018-01-01 00:00:00
2018-01-02 02:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-02 05:00:00
2018-01-02 06:00:00
2018-01-02 07:00:00
2018-01-02 08:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-02 13:00:00
... kaboooooom! ...

I suspect this runs into the date_trunc() precision parameter being
variable, which is something Tom mentioned as a potential issue.

The already-mentioned substr/trim are another example of this issue. Not
only must the parameters be constant (or generally using the same value
for all rows), but it may work for some values and fail for others.

For example substr($1,0,$2) might work, but substr($1,10,$2) likely not.
Similarly for trim().

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

On 31 October 2018 at 14:23, Tomas Vondra <tomas.vondra@2ndquadrant.com> wrote:

The other thing likely affecting this is locale / collation. Probably
not for date_trunc, but certainly for things like substr()/trim(),
mentioned by Simon upthread.

In some languages the rules are pretty complex, and there's no chance
it'll survive arbitrary substr() applied to the string. For example, in
Czech we mostly sort character-by-character, but "ch" is an exception
sorted in between "h" and "i".

So essentially "hhhh <= hchh <= hihh". Obviously, substr($1,0,3) cuts
the "ch" in half, changing the ordering:

create table x (y text collate "cs_CZ");
insert into x values ('hhhh'), ('hchh'), ('hihh');

test=# select y from x order by 1;
y
------
hhhh
hchh
hihh
(3 rows)

test=# select substr(y,0,3) from x order by 1;
substr
--------
hc
hh
hi
(3 rows)

I'm preeeeeeetty sure other languages have even funnier rules ...

That's pretty interesting, but as mentioned in my initial email...
More careful thought would be needed for other numerical types and
text types, I imagine, though I've not thought much about that.

I don't really think trim() or substr() would ever work for the reason
that they don't always operate on a prefix of the string. What you've
mentioned seems to rule out LEFT().

I'm mildly suspicious of this data set, because it's essentially
perfectly sorted/deterministic, and the Sort node won't have to do
anything. So perhaps it just works by chance.

Consider this instead:

create table dt (ts timestamp, x text);

insert into dt select * from (select d, (case when random() < 0.5 then
'month' else 'hour' end) from generate_series('2018-01-01'::timestamp,
'2018-12-31'::timestamp, '1 hour'::interval) d) as foo order by random();

[...]

2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-02 13:00:00
... kaboooooom! ...

Yeah. This is an issue. Thanks for the test case. However, I
acknowledged that in my reply to Tom. I did overlook it, which was
completely down to lack of imagination on my part. I'd never
considered using date_trunc() without a const 1st argument before. It
seems simple enough to disable the optimisation in that case. I've
attached a patch which does that. Maybe that'll help us look beyond
this and focus on any other reasons why this is not possible.

It's also true that this diminishes the usefulness of the idea, but
part of the reason I've posting the idea so early after having thought
about it is precisely to see if this is going to float or sink.
Maybe we'll decide the scope of usefulness is so small that it's not
worth it, or that each function has such different requirements that
we can't reasonably make it work by adding a few columns to pg_proc.
I'm personally more interested in the cases that can work. I
understand there is no shortage of cases where it can't.

Giving that we require const arguments away from the orderkey, perhaps
it could be made to work for simple arithmetic OpExprs. I'm not sure
if the use cases are actually there for that sort of thing and I've
seen WHERE indexcol+0 = <n> used many times to disable the use of
indexes, so making pathkeys see through those might be more annoying
than useful... But it's a thought...

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

On 10/31/2018 04:32 AM, David Rowley wrote:

On 31 October 2018 at 14:23, Tomas Vondra <tomas.vondra@2ndquadrant.com> wrote:

The other thing likely affecting this is locale / collation. Probably
not for date_trunc, but certainly for things like substr()/trim(),
mentioned by Simon upthread.

In some languages the rules are pretty complex, and there's no chance
it'll survive arbitrary substr() applied to the string. For example, in
Czech we mostly sort character-by-character, but "ch" is an exception
sorted in between "h" and "i".

So essentially "hhhh <= hchh <= hihh". Obviously, substr($1,0,3) cuts
the "ch" in half, changing the ordering:

create table x (y text collate "cs_CZ");
insert into x values ('hhhh'), ('hchh'), ('hihh');

test=# select y from x order by 1;
y
------
hhhh
hchh
hihh
(3 rows)

test=# select substr(y,0,3) from x order by 1;
substr
--------
hc
hh
hi
(3 rows)

I'm preeeeeeetty sure other languages have even funnier rules ...

That's pretty interesting, but as mentioned in my initial email...
More careful thought would be needed for other numerical types and
text types, I imagine, though I've not thought much about that.

I don't really think trim() or substr() would ever work for the reason
that they don't always operate on a prefix of the string. What you've
mentioned seems to rule out LEFT().

Sure, but it wasn't very clear to me what the "more careful thought"
would mean.

I think a direct consequence of Tom's point about opclasses is that
storing this information in pg_proc is not going to fly - you would need
a separate catalog for that, to allow mapping the function to multiple
opclasses (possibly with different features?). But OK, that's doable.

But what if you also need to do that for collations? Firstly, it would
it add another degree of freedom, essentially making it (proc, opclass,
collation, ... metadata ...) so there would be many such combinations. I
can't really imagine defining that manually, but maybe it can be
simplified. But more importantly - the list of collations is kinda
dynamic, and AFAIK the collation rules may change depending on the
glibc/icu versions. So, that seems pretty tricky. It's certainly not a
just a SMOP.

I'm mildly suspicious of this data set, because it's essentially
perfectly sorted/deterministic, and the Sort node won't have to do
anything. So perhaps it just works by chance.

Consider this instead:

create table dt (ts timestamp, x text);

insert into dt select * from (select d, (case when random() < 0.5 then
'month' else 'hour' end) from generate_series('2018-01-01'::timestamp,
'2018-12-31'::timestamp, '1 hour'::interval) d) as foo order by random();

[...]

2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-01 00:00:00
2018-01-02 13:00:00
... kaboooooom! ...

Yeah. This is an issue. Thanks for the test case. However, I
acknowledged that in my reply to Tom. I did overlook it, which was
completely down to lack of imagination on my part. I'd never
considered using date_trunc() without a const 1st argument before. It
seems simple enough to disable the optimisation in that case. I've
attached a patch which does that. Maybe that'll help us look beyond
this and focus on any other reasons why this is not possible.

Ah, sorry - I've missed this bit in your response. In my defense, it's
been quite late over here, and my caffeine level got a tad too low.

Anyway, the question is how strong would the requirement need to be, and
how would that affect applicability of this optimization in other cases.
I agree it's probably not an issue for date_trunc() - I don't recall
ever using it with non-constant first parameter. I wonder if there are
other functions where that's not the case - although, that's not really
an argument against this optimization.

It's also true that this diminishes the usefulness of the idea, but
part of the reason I've posting the idea so early after having thought
about it is precisely to see if this is going to float or sink.

Sure. And pgsql-hackers are very good in sinking ideas ;-)

Maybe we'll decide the scope of usefulness is so small that it's not
worth it, or that each function has such different requirements that
we can't reasonably make it work by adding a few columns to pg_proc.
I'm personally more interested in the cases that can work. I
understand there is no shortage of cases where it can't.

I think it can't be made just by adding a couple of columns to pg_proc,
as explained above. A separate catalog mapping procs to opclasses (and
maybe collations) may be needed. For cases where it depends on the
actual parameter values (like substr/trim/ltrim) an extra function might
be needed (something like the selectivity functions for data types).

Giving that we require const arguments away from the orderkey, perhaps
it could be made to work for simple arithmetic OpExprs. I'm not sure
if the use cases are actually there for that sort of thing and I've
seen WHERE indexcol+0 = <n> used many times to disable the use of
indexes, so making pathkeys see through those might be more annoying
than useful... But it's a thought...

Well, that really depends on the definition of the "+" operator, which
is pretty much just a function. So I don't see why would that simplify
the situation?

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

On Wed, Oct 31, 2018 at 9:19 AM Tomas Vondra
<tomas.vondra@2ndquadrant.com> wrote:

I think it can't be made just by adding a couple of columns to pg_proc,
as explained above. A separate catalog mapping procs to opclasses (and
maybe collations) may be needed. For cases where it depends on the
actual parameter values (like substr/trim/ltrim) an extra function might
be needed (something like the selectivity functions for data types).

This kinda reminds me of commit
8f9fe6edce358f7904e0db119416b4d1080a83aa. We needed a way to provide
the planner with knowledge about the behavior of specific functions.
In that case, the specific need was to be able to tell the planner
that a certain function call could be omitted or strength-reduced, and
we did that by having the planner call a function that encoded the
necessary knowledge. Here, we want to evaluate a function call and
see whether it is order preserving, which could depend on a whole
bunch of stuff that isn't easily parameterized by catalog entries, but
could be figured out by a C function written for that purpose. I'm
not really sure how that would work in this case, or whether it's a
good idea, but I thought I'd mention it just in case it's helpful.

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

Robert Haas <robertmhaas@gmail.com> writes:

This kinda reminds me of commit
8f9fe6edce358f7904e0db119416b4d1080a83aa. We needed a way to provide
the planner with knowledge about the behavior of specific functions.
In that case, the specific need was to be able to tell the planner
that a certain function call could be omitted or strength-reduced, and
we did that by having the planner call a function that encoded the
necessary knowledge. Here, we want to evaluate a function call and
see whether it is order preserving, which could depend on a whole
bunch of stuff that isn't easily parameterized by catalog entries, but
could be figured out by a C function written for that purpose.

+1. If we're otherwise going to need multiple pg_proc columns, this
is a better answer just from the standpoint of avoiding pg_proc bloat:
we'd only need to add one OID column. And I concur with your point
that we're going to have a really hard time parameterizing the mechanism
adequately if there isn't dedicated per-function code.

regards, tom lane

On 1 November 2018 at 05:40, Robert Haas <robertmhaas@gmail.com> wrote:

This kinda reminds me of commit
8f9fe6edce358f7904e0db119416b4d1080a83aa. We needed a way to provide
the planner with knowledge about the behavior of specific functions.
In that case, the specific need was to be able to tell the planner
that a certain function call could be omitted or strength-reduced, and
we did that by having the planner call a function that encoded the
necessary knowledge. Here, we want to evaluate a function call and
see whether it is order preserving, which could depend on a whole
bunch of stuff that isn't easily parameterized by catalog entries, but
could be figured out by a C function written for that purpose. I'm
not really sure how that would work in this case, or whether it's a
good idea, but I thought I'd mention it just in case it's helpful.

Agreed. That's a good idea. Thanks.

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

On Oct 30, 2018, at 9:08 AM, Simon Riggs <simon@2ndquadrant.com> wrote:

On Tue, 30 Oct 2018 at 07:58, David Rowley <david.rowley@2ndquadrant.com> wrote:

I've started working on something I've ended up calling "Super
PathKeys". The idea here is to increase the likelihood of a Path with
PathKeys being used for a purpose that requires a less strict sort
order due to ordering being required from the return value of some
precision loss function.

Anything left anchored would benefit, so SUBSTR(), TRIM() etc

Main use for this would be where the partition condition is a function, so we can still order by partitions easily.

This would also be very helpful in many BI cases; it’s very common to aggregate based on year, year/month, year/quarter, etc.

The other thing that would be extremely useful would be pushing predicats through this, so you could do things like

WHERE date_trunc(‘year’, timestamp_field) = 2018

On 10/31/2018 10:07 PM, David Rowley wrote:

On 1 November 2018 at 05:40, Robert Haas <robertmhaas@gmail.com> wrote:

This kinda reminds me of commit
8f9fe6edce358f7904e0db119416b4d1080a83aa. We needed a way to provide
the planner with knowledge about the behavior of specific functions.
In that case, the specific need was to be able to tell the planner
that a certain function call could be omitted or strength-reduced, and
we did that by having the planner call a function that encoded the
necessary knowledge. Here, we want to evaluate a function call and
see whether it is order preserving, which could depend on a whole
bunch of stuff that isn't easily parameterized by catalog entries, but
could be figured out by a C function written for that purpose. I'm
not really sure how that would work in this case, or whether it's a
good idea, but I thought I'd mention it just in case it's helpful.

Agreed. That's a good idea. Thanks.

FWIW this is mostly what I had in mind when referring to the selectivity
estimation functions for operators, although I now realize it might not
have been explained very clearly.

Anyway, I agree this seems like a much better way than trying to store
all the potentially relevant meta-data in catalogs.

I still have trouble imagining what exactly would the function do to
determine if the optimization can be applied to substr() and similar
collation-dependent cases.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

On 1 November 2018 at 12:11, Tomas Vondra <tomas.vondra@2ndquadrant.com> wrote:

I still have trouble imagining what exactly would the function do to
determine if the optimization can be applied to substr() and similar
collation-dependent cases.

I guess the function would have to check for a Const offset of 0, and
a collection, perhaps of "C" for the 1st arg. In any case, I wouldn't
want this idea to be hung up on the fact we can't determine how to
make substr() work correctly with it.

I'm most interested in date_trunc() and friends. A first cut
implementation would not have to implement functions for everything
that's possible to implement.

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

Hi,

On 2018-11-01 12:19:32 +1300, David Rowley wrote:

On 1 November 2018 at 12:11, Tomas Vondra <tomas.vondra@2ndquadrant.com> wrote:

I still have trouble imagining what exactly would the function do to
determine if the optimization can be applied to substr() and similar
collation-dependent cases.

I guess the function would have to check for a Const offset of 0, and
a collection, perhaps of "C" for the 1st arg. In any case, I wouldn't
want this idea to be hung up on the fact we can't determine how to
make substr() work correctly with it.

I'm most interested in date_trunc() and friends. A first cut
implementation would not have to implement functions for everything
that's possible to implement.

FWIW, I kind of wonder if we built proper infrastructure to allow to
make such inferrences from function calls, whether it could also be made
to support the transformation of LIKEs into indexable <= >= clauses.

Greetings,

Andres Freund

On 1 November 2018 at 12:24, Andres Freund <andres@anarazel.de> wrote:

FWIW, I kind of wonder if we built proper infrastructure to allow to
make such inferrences from function calls, whether it could also be made
to support the transformation of LIKEs into indexable <= >= clauses.

Perhaps, but I doubt it would be the same function to do both. Surely
I need something that accepts details about the function call as
arguments and returns an Expr * of the argument that we can derive the
order of the return value from, or NULL. I think the transformation
you need might be more along the lines of returning a List * of quals
that can substitute an OpExpr containing a function call. I'm not that
clear on how we'd know the new quals were better than the existing
ones. For example extract('year', dt) = 2018 could be transformed to
dt >= '2018-01-01' AND dt < '2019-01-01', but how would we know that
was better. There might be an index on extract('year', dt).

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

On 11/01/2018 02:40 AM, David Rowley wrote:

On 1 November 2018 at 12:24, Andres Freund <andres@anarazel.de> wrote:

FWIW, I kind of wonder if we built proper infrastructure to allow to
make such inferrences from function calls, whether it could also be made
to support the transformation of LIKEs into indexable <= >= clauses.

Perhaps, but I doubt it would be the same function to do both. Surely
I need something that accepts details about the function call as
arguments and returns an Expr * of the argument that we can derive the
order of the return value from, or NULL. I think the transformation
you need might be more along the lines of returning a List * of quals
that can substitute an OpExpr containing a function call. I'm not that
clear on how we'd know the new quals were better than the existing
ones. For example extract('year', dt) = 2018 could be transformed to
dt >= '2018-01-01' AND dt < '2019-01-01', but how would we know that
was better. There might be an index on extract('year', dt).

IMHO there is only a handful of "useful" transformations of this kind,
depending on the operator class of an index. So when building index
paths and checking which quals may be used as index conditions, we'd do
try transforming incompatible quals and leave the rest up to the
existing create_index_path machinery (which already makes the decision
about which quals to use for index search etc.)

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services