Thread: New feature: accumulative functions.
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. -- ------------ pasman
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
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 > > > 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
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
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
>
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
=?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
>
>
> 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
>
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
Yes, accumulative functions may be used for sorting,groupping and
merge joins with limit.
Groupping looks simplest to implement, and comparable to performance
of functional index
.
2011/9/27, Marti Raudsepp <marti@juffo.org>:
> 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
>
--
------------
pasman
Thanks Marti for inspiration :). Monotonic functions allows to skip
some sorts in window expressions containing them:
select winfun1(...) over(order by x), winfun2(...) over(order by f(x)) from ...
2011/9/27, pasman pasmański <pasman.p@gmail.com>:
> Yes, accumulative functions may be used for sorting,groupping and
> merge joins with limit.
>
> Groupping looks simplest to implement, and comparable to performance
> of functional index
> .
>
> 2011/9/27, Marti Raudsepp <marti@juffo.org>:
>> 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
>>
>
>
> --
> ------------
> pasman
>
--
------------
pasman