New feature: accumulative functions.

On Sep 25, 2011, at 9:19, pasman pasmański <pasman.p@gmail.com> wrote:

Hi.

I propose to add "accumulative" flag to a function definition. This
flag would be set for function f(x) which is accumulative and
immutable.

This flag allows to use an index on x for clauses containing f(x):

where f(x) = const
where f(x) > const

and so on.

We can term it a Schrodinger function :)

I don't understand how it can have mutable state (accumulator) and still be called immutable.

Can explain further and give an example (or better yet, real life) use-case?

David J.

=?ISO-8859-2?Q?pasman_pasma=F1ski?= <pasman.p@gmail.com> writes:

I propose to add "accumulative" flag to a function definition. This
flag would be set for function f(x) which is accumulative and
immutable.

Maybe you'd better define what you mean by "accumulative" ...

This flag allows to use an index on x for clauses containing f(x):
where f(x) = const
where f(x) > const

... because it's sure not clear how you would get that to work.

regards, tom lane

pasman pasmański <pasman.p@gmail.com> Sunday 25 of September 2011 15:19:28

Hi.

I propose to add "accumulative" flag to a function definition. This
flag would be set for function f(x) which is accumulative and
immutable.

This flag allows to use an index on x for clauses containing f(x):

where f(x) = const

I think for this index designe will require that f(x) will be stored,
additional behaviour of fucntion are not required, is quite enaugh that it
will be function.

where f(x) > const

and so on.

By this assume that "accumulative" function is
(weakly) increasing or decreasing

f such that x < y => f(x) <= f(y)
?

I only may deduce it for idea that search will be faster on index.

Regards,
Radosław Smogura
http://softperience.eu/

My english is not perfect, by accumulative i think about monotonically
increasing function.

It works that for clause WHERE f(x)=const:
1. Read root page of index_on_x and get x1 ... Xn
2. Calculate f(x1) ... f(xn) for this page
3. When f(x1)<=const<= f(xn) then x1 <= searched x <= xn and we can
test smaller range (xlower, xgreater).
4. Otherwise no rows satisfy condition.

Step 3 we repeat for current index's page and subpages until xlower =
searched x = xgreater

2011/9/25, Tom Lane <tgl@sss.pgh.pa.us>:

=?ISO-8859-2?Q?pasman_pasma=F1ski?= <pasman.p@gmail.com> writes:

I propose to add "accumulative" flag to a function definition. This
flag would be set for function f(x) which is accumulative and
immutable.

Maybe you'd better define what you mean by "accumulative" ...

This flag allows to use an index on x for clauses containing f(x):
where f(x) = const
where f(x) > const

... because it's sure not clear how you would get that to work.

regards, tom lane

--
------------
pasman

=?ISO-8859-2?Q?pasman_pasma=F1ski?= <pasman.p@gmail.com> writes:

My english is not perfect, by accumulative i think about monotonically
increasing function.

Oh, I see how that would work. I can't get real excited about it
though. The use-case seems a bit narrow, and the amount of complexity
added to the btree search mechanism (thereby slowing down all btree
searches) would be significant. Furthermore, unless f() is pretty cheap
to evaluate, you'd end up preferring an index on f(x) anyway, because
that can be searched without any new evaluations of f().

regards, tom lane

This feature give profits for increasing muliti-arg functions. Example:

WHERE f(x,param) = const

it may be impossible to create functional indexes for all params.

2011/9/25, Pavel Stehule <pavel.stehule@gmail.com>:

Hello

what is a real use case?

Regards

Pavel

2011/9/25 pasman pasmański <pasman.p@gmail.com>:

My english is not perfect, by accumulative i think about monotonically
increasing function.

It works that for clause WHERE f(x)=const:
1. Read root page of index_on_x and get x1 ... Xn
2. Calculate f(x1) ... f(xn) for this page
3. When f(x1)<=const<= f(xn) then x1 <= searched x <= xn and we can
test smaller range (xlower, xgreater).
4. Otherwise no rows satisfy condition.

Step 3 we repeat for current index's page and subpages until xlower =
searched x = xgreater

2011/9/25, Tom Lane <tgl@sss.pgh.pa.us>:

=?ISO-8859-2?Q?pasman_pasma=F1ski?= <pasman.p@gmail.com> writes:

I propose to add "accumulative" flag to a function definition. This
flag would be set for function f(x) which is accumulative and
immutable.

Maybe you'd better define what you mean by "accumulative" ...

This flag allows to use an index on  x for clauses containing f(x):
where f(x) = const
where f(x) > const

... because it's sure not clear how you would get that to work.

                      regards, tom lane

--
------------
pasman

--
Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general

--
------------
pasman

I think, it should be new node in executor. Planner select classic
index scan or new functional index scan.

2011/9/25, Tom Lane <tgl@sss.pgh.pa.us>:

=?ISO-8859-2?Q?pasman_pasma=F1ski?= <pasman.p@gmail.com> writes:

My english is not perfect, by accumulative i think about monotonically
increasing function.

Oh, I see how that would work. I can't get real excited about it
though. The use-case seems a bit narrow, and the amount of complexity
added to the btree search mechanism (thereby slowing down all btree
searches) would be significant. Furthermore, unless f() is pretty cheap
to evaluate, you'd end up preferring an index on f(x) anyway, because
that can be searched without any new evaluations of f().

regards, tom lane

--
------------
pasman

2011/9/25 pasman pasmański <pasman.p@gmail.com>:

This feature give profits for increasing muliti-arg functions. Example:

WHERE f(x,param) = const

it may be impossible to create functional indexes for all params.

Sorry, I asked on real use case. Do you know some one?

Pavel

I found second use case. Look at expression:

where left(str,n)='value'

function left(str,n) increase monotonically for str and n. With this
feature it can use index on str.

Classic index needs recreating.

2011/9/25, Pavel Stehule <pavel.stehule@gmail.com>:

Hello

what is a real use case?

Regards

Pavel

2011/9/25 pasman pasmański <pasman.p@gmail.com>:

My english is not perfect, by accumulative i think about monotonically
increasing function.

It works that for clause WHERE f(x)=const:
1. Read root page of index_on_x and get x1 ... Xn
2. Calculate f(x1) ... f(xn) for this page
3. When f(x1)<=const<= f(xn) then x1 <= searched x <= xn and we can
test smaller range (xlower, xgreater).
4. Otherwise no rows satisfy condition.

Step 3 we repeat for current index's page and subpages until xlower =
searched x = xgreater

2011/9/25, Tom Lane <tgl@sss.pgh.pa.us>:

=?ISO-8859-2?Q?pasman_pasma=F1ski?= <pasman.p@gmail.com> writes:

I propose to add "accumulative" flag to a function definition. This
flag would be set for function f(x) which is accumulative and
immutable.

Maybe you'd better define what you mean by "accumulative" ...

This flag allows to use an index on  x for clauses containing f(x):
where f(x) = const
where f(x) > const

... because it's sure not clear how you would get that to work.

                      regards, tom lane

--
------------
pasman

--
Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general

--
------------
pasman

... When n changes of course.

Sorry for top posting, phone not allows to move cite.

2011/9/25, pasman pasmański <pasman.p@gmail.com>:

I found second use case. Look at expression:

where left(str,n)='value'

function left(str,n) increase monotonically for str and n. With this
feature it can use index on str.

Classic index needs recreating.

2011/9/25, Pavel Stehule <pavel.stehule@gmail.com>:

Hello

what is a real use case?

Regards

Pavel

2011/9/25 pasman pasmański <pasman.p@gmail.com>:

My english is not perfect, by accumulative i think about monotonically
increasing function.

It works that for clause WHERE f(x)=const:
1. Read root page of index_on_x and get x1 ... Xn
2. Calculate f(x1) ... f(xn) for this page
3. When f(x1)<=const<= f(xn) then x1 <= searched x <= xn and we can
test smaller range (xlower, xgreater).
4. Otherwise no rows satisfy condition.

Step 3 we repeat for current index's page and subpages until xlower =
searched x = xgreater

2011/9/25, Tom Lane <tgl@sss.pgh.pa.us>:

=?ISO-8859-2?Q?pasman_pasma=F1ski?= <pasman.p@gmail.com> writes:

I propose to add "accumulative" flag to a function definition. This
flag would be set for function f(x) which is accumulative and
immutable.

Maybe you'd better define what you mean by "accumulative" ...

This flag allows to use an index on  x for clauses containing f(x):
where f(x) = const
where f(x) > const

... because it's sure not clear how you would get that to work.

                      regards, tom lane

--
------------
pasman

--
Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general

--
------------
pasman

--
------------
pasman

2011/9/25 pasman pasmański <pasman.p@gmail.com>:

I found second use case. Look at expression:

where left(str,n)='value'

function left(str,n) increase monotonically for str and n. With this
feature it can use index on str.

Classic index needs recreating.

these use cases are just theory - for example - this case should be
solved with immutable functions

I can use a functional index left(str, const) and use a query

where left(str, const) = left('value', const) and left(str, n) = 'value'

There are a theoretical cases, but these cases should be solved via
special data type and GiST index

Pavel

=?ISO-8859-2?Q?pasman_pasma=F1ski?= <pasman.p@gmail.com> writes:

I found second use case. Look at expression:
where left(str,n)='value'

function left(str,n) increase monotonically for str and n. With this
feature it can use index on str.

Can't get excited about that, because that only works in C locale,
and in C locale you can already get the same result with
WHERE str LIKE '...%'

Also, I think you just moved the goalposts quite a bit by introducing
multiple-argument functions into the proposed feature. That's going
to add even more complexity, for instance there would need to be a way
to specify which argument(s) the function was monotonic in. The C
versus not-C locale aspect also shows that for textual arguments,
it might matter which locale you're talking about.

In short, this is looking awfully complicated, and I gauge the probable
level of interest by the fact that you're the first person to ask for it
in more than a dozen years of Postgres development.

regards, tom lane

See that setting flag on function need less work than create new gist
operator. Of course if postgresql's developers do biggest work before.

2011/9/25, Pavel Stehule <pavel.stehule@gmail.com>:

2011/9/25 pasman pasmański <pasman.p@gmail.com>:

I found second use case. Look at expression:

where left(str,n)='value'

function left(str,n) increase monotonically for str and n. With this
feature it can use index on str.

Classic index needs recreating.

these use cases are just theory - for example - this case should be
solved with immutable functions

I can use a functional index left(str, const) and use a query

where left(str, const) = left('value', const) and left(str, n) = 'value'

There are a theoretical cases, but these cases should be solved via
special data type and GiST index

Pavel

2011/9/25, Pavel Stehule <pavel.stehule@gmail.com>:

Hello

what is a real use case?

Regards

Pavel

2011/9/25 pasman pasmański <pasman.p@gmail.com>:

My english is not perfect, by accumulative i think about monotonically
increasing function.

It works that for clause WHERE f(x)=const:
1. Read root page of index_on_x and get x1 ... Xn
2. Calculate f(x1) ... f(xn) for this page
3. When f(x1)<=const<= f(xn) then x1 <= searched x <= xn and we can
test smaller range (xlower, xgreater).
4. Otherwise no rows satisfy condition.

Step 3 we repeat for current index's page and subpages until xlower =
searched x = xgreater

2011/9/25, Tom Lane <tgl@sss.pgh.pa.us>:

=?ISO-8859-2?Q?pasman_pasma=F1ski?= <pasman.p@gmail.com> writes:

I propose to add "accumulative" flag to a function definition. This
flag would be set for function f(x) which is accumulative and
immutable.

Maybe you'd better define what you mean by "accumulative" ...

This flag allows to use an index on  x for clauses containing f(x):
where f(x) = const
where f(x) > const

... because it's sure not clear how you would get that to work.

                      regards, tom lane

--
------------
pasman

--
Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general

--
------------
pasman

--
------------
pasman

Yes, i wrote this for pleasure and discusion, not for solve a real problem :).

2011/9/25, Tom Lane <tgl@sss.pgh.pa.us>:

=?ISO-8859-2?Q?pasman_pasma=F1ski?= <pasman.p@gmail.com> writes:

I found second use case. Look at expression:
where left(str,n)='value'

function left(str,n) increase monotonically for str and n. With this
feature it can use index on str.

Can't get excited about that, because that only works in C locale,
and in C locale you can already get the same result with
WHERE str LIKE '...%'

Also, I think you just moved the goalposts quite a bit by introducing
multiple-argument functions into the proposed feature. That's going
to add even more complexity, for instance there would need to be a way
to specify which argument(s) the function was monotonic in. The C
versus not-C locale aspect also shows that for textual arguments,
it might matter which locale you're talking about.

In short, this is looking awfully complicated, and I gauge the probable
level of interest by the fact that you're the first person to ask for it
in more than a dozen years of Postgres development.

regards, tom lane

--
------------
pasman

2011/9/25 pasman pasmański <pasman.p@gmail.com>:

See that setting flag on function need less work than create new gist
operator. Of course if postgresql's developers do biggest work before.

any feature in pg should to have a general usage - with real use cases
and real performance advantages.

I am not sure, if monotonically functions should be useful - this
request is relative strong. This feature should be interesting, but
should be a source of bugs if somebody use it wrong. Some similar
searching is possible with multidimensional indexes.

note: a searching is one task - second task is design of estimations.

Pavel

For single argument strict increasing function f(x), estimation is
simple: it is f(estimation of x).

2011/9/25, Pavel Stehule <pavel.stehule@gmail.com>:

2011/9/25 pasman pasmański <pasman.p@gmail.com>:

See that setting flag on function need less work than create new gist
operator. Of course if postgresql's developers do biggest work before.

any feature in pg should to have a general usage - with real use cases
and real performance advantages.

I am not sure, if monotonically functions should be useful - this
request is relative strong. This feature should be interesting, but
should be a source of bugs if somebody use it wrong. Some similar
searching is possible with multidimensional indexes.

note: a searching is one task - second task is design of estimations.

Pavel

2011/9/25, Pavel Stehule <pavel.stehule@gmail.com>:

2011/9/25 pasman pasmański <pasman.p@gmail.com>:

I found second use case. Look at expression:

where left(str,n)='value'

function left(str,n) increase monotonically for str and n. With this
feature it can use index on str.

Classic index needs recreating.

these use cases are just theory - for example - this case should be
solved with immutable functions

I can use a functional index left(str, const) and use a query

where left(str, const) = left('value', const) and left(str, n) = 'value'

There are a theoretical cases, but these cases should be solved via
special data type and GiST index

Pavel

2011/9/25, Pavel Stehule <pavel.stehule@gmail.com>:

Hello

what is a real use case?

Regards

Pavel

2011/9/25 pasman pasmański <pasman.p@gmail.com>:

My english is not perfect, by accumulative i think about monotonically
increasing function.

It works that for clause WHERE f(x)=const:
1. Read root page of index_on_x and get x1 ... Xn
2. Calculate f(x1) ... f(xn) for this page
3. When f(x1)<=const<= f(xn) then x1 <= searched x <= xn and we can
test smaller range (xlower, xgreater).
4. Otherwise no rows satisfy condition.

Step 3 we repeat for current index's page and subpages until xlower =
searched x = xgreater

2011/9/25, Tom Lane <tgl@sss.pgh.pa.us>:

=?ISO-8859-2?Q?pasman_pasma=F1ski?= <pasman.p@gmail.com> writes:

I propose to add "accumulative" flag to a function definition. This
flag would be set for function f(x) which is accumulative and
immutable.

Maybe you'd better define what you mean by "accumulative" ...

This flag allows to use an index on  x for clauses containing f(x):
where f(x) = const
where f(x) > const

... because it's sure not clear how you would get that to work.

                      regards, tom lane

--
------------
pasman

--
Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general

--
------------
pasman

--
------------
pasman

--
------------
pasman

I write small summary.

Feature details: additional flags for monotonical functions. Learn
planner to use them. New node in execution plan - functional index
scan.

Pro: single btree index may be used in many expressions containing
only monotonnical functions.

Contra: big developement effort. No new functionalities - functional
or gist index does the same work. Not for all encodings. Unknown
performance advantages.

------------
pasman

In article <CAFj8pRDx6JLmneV30kWNrcwzGLOSqyK-qN7T4_N37L9UPd2M=Q@mail.gmail.com>,
Pavel Stehule <pavel.stehule@gmail.com> writes:

2011/9/25 pasman pasmański <pasman.p@gmail.com>:

I found second use case. Look at expression:

where left(str,n)='value'

function left(str,n) increase monotonically for str and n. With this
feature it can use index on str.

Classic index needs recreating.

these use cases are just theory - for example - this case should be
solved with immutable functions

I can use a functional index left(str, const) and use a query

where left(str, const) = left('value', const) and left(str, n) = 'value'

There are a theoretical cases, but these cases should be solved via
special data type and GiST index

If I don't misunderstand you, this data type is called 'prefix_range',
available at PgFoundry.

2011/9/25 pasman pasmański <pasman.p@gmail.com>:

My english is not perfect, by accumulative i think about monotonically
increasing function.

It works that for clause WHERE f(x)=const:
1. Read root page of index_on_x and get x1 ... Xn
2. Calculate f(x1) ... f(xn) for this page
3. When f(x1)<=const<= f(xn) then x1 <= searched x <= xn and we can
test smaller range (xlower, xgreater).
4. Otherwise no rows satisfy condition.

I can't get very excited about this feature for index scans. However,
I think there's another, more interesting use case: sorting

I frequently write queries like:
SELECT date_trunc('month', somedate), sum(foo)
GROUP BY date_trunc('month', somedate);

Currently the planner doesn't realize that instead of
GroupAggregate+Sort, it can use the already existing sorted index on
just (somedate). Alternatively I would need to create a separate
date_trunc functional index for daily, weekly and monthly aggregates
for EACH meaningful time zone.

This would be a planner-only change and nothing the executor needs to know of.

Now obviously HashAggregate helps a lot with these kinds of queries,
but there are still cases where GroupAggregate would be a win -- for
instance, queries with a LIMIT.

Regards,
Marti