Re: [HACKERS] Surjective functional indexes

[Konstantin Knizhnik]

On 09/28/2017 10:10 PM, Robert Haas wrote:

On Wed, Sep 13, 2017 at 7:00 AM, Simon Riggs  wrote:

If we do have an option it won't be using fancy mathematical
terminology at all, it would be described in terms of its function,
e.g. recheck_on_update

+1.


I have nothing against renaming "projection" option to "recheck_on_update" or 
whatever else is suggested.
Just let me know the best version. From my point of view "recheck_on_update" is too verbose and still not self-explained (to understand the meaning of this option it is necessary to uunderstand how heap_update works). "projection"/"non-injective"/... are 
more declarative notions, explaining the characteristic of the index, while "recheck_on_update"  is more procedural notion, explaining behavior of heap_update.





Yes, I'd rather not have an option at all, just some simple code with
useful effect, like we have in many other places.

I think the question we need to be able to answer is: What is the
probability that an update that would otherwise be non-HOT can be made
into a HOT update by performing a recheck to see whether the value has
changed?  It doesn't seem easy to figure that out from any of the
statistics we have available today or could easily get, because it
depends not only on the behavior of the expression which appears in
the index definition but also on the application behavior.  For
example, consider a JSON blob representing a bank account.
b->'balance' is likely to change most of the time, but
b->'account_holder_name' only rarely.  That's going to be hard for an
automated system to determine.

We should clearly check as many of the other criteria for a HOT update
as possible before performing a recheck of this type, so that it only
gets performed when it might help.  For example, if column a is
indexed and b->'foo' is indexed, there's no point in checking whether
b->'foo' has changed if we know that a has changed.  I don't know
whether it would be feasible to postpone deciding whether to do a
recheck until after we've figured out whether the page seems to
contain enough free space to allow a HOT update.

Turning non-HOT updates into HOT updates is really good, so it seems
likely that the rechecks will often be worthwhile.  If we avoid a HOT
update in 25% of cases, that's probably easily worth the CPU overhead
of a recheck assuming the function isn't something ridiculously
expensive to compute; the extra CPU cost will be repaid by reduced
bloat.  However, if we avoid a HOT update only one time in a million,
it's probably not worth the cost of recomputing the expression the
other 999,999 times.  I wonder where the crossover point is -- it
seems like something that could be figured out by benchmarking.

While I agree that it would be nice to have this be a completely
automatic determination, I am not sure that will be practical.  I
oppose overloading some other marker (like function_cost>1) for
this; that's too magical.


I almost agree with you.
Just few remarks: indexes are rarely created for frequently changed attributes, 
like b->'balance'.
So in case of proper database schema design it is possible to expect that most 
of updates are hot updates: do not actually affect any index.
But certainly different attributes may have different probability of been 
updated.
Unfortunately we do not know before check which attribute of JSON field (or any 
other fields used in indexed expression) is changed.

--
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company



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

Re: [HACKERS] Surjective functional indexes

[Oleg Bartunov]

On Thu, May 25, 2017 at 7:30 PM, Konstantin Knizhnik
 wrote:
> Right now Postgres determines whether update operation touch index or not
> based only on set of the affected columns.
> But in case of functional indexes such policy quite frequently leads to
> unnecessary index updates.
> For example, functional index are widely use for indexing JSON data:
> info->>'name'.
>
> JSON data may contain multiple attributes and only few of them may be
> affected by update.
> Moreover, index is used to build for immutable attributes (like "id",
> "isbn", "name",...).
>
> Functions like (info->>'name') are named "surjective" ni mathematics.
> I have strong feeling that most of functional indexes are based on
> surjective functions.
> For such indexes current Postgresql index update policy is very inefficient.
> It cause disabling of hot updates
> and so leads to significant degrade of performance.
>
> Without this patch Postgres is slower than Mongo on YCSB benchmark with (50%
> update,50 % select)  workload.
> And after applying this patch Postgres beats Mongo at all workloads.

I confirm that the patch helps for workload A of YCSB, but actually
just extends #clients, where postgres outperforms mongodb (see
attached picture).  If we increase #clients > 100 postgres quickly
degrades not only for workload A, but even for workload B (5%
updates), while mongodb and mysql behave much-much better, but this is
another problem, we will discuss in different thread.

>
> My proposal is to check value of function for functional indexes instead of
> just comparing set of effected attributes.
> Obviously, for some complex functions it may  have negative effect on update
> speed.
> This is why I have added "surjective" option to index. By default it is
> switched on for all functional indexes (based on my assumption
> that most functions used in functional indexes are surjective). But it is
> possible to explicitly disable it and make decision weather index
> needs to be updated or not only based on set of effected attributes.
>
>
> --
> Konstantin Knizhnik
> Postgres Professional: http://www.postgrespro.com
> The Russian Postgres Company
>
>
>
> --
> Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers
>


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

Re: [HACKERS] Surjective functional indexes

[Robert Haas]

On Wed, Sep 13, 2017 at 7:00 AM, Simon Riggs  wrote:
> If we do have an option it won't be using fancy mathematical
> terminology at all, it would be described in terms of its function,
> e.g. recheck_on_update

+1.

> Yes, I'd rather not have an option at all, just some simple code with
> useful effect, like we have in many other places.

I think the question we need to be able to answer is: What is the
probability that an update that would otherwise be non-HOT can be made
into a HOT update by performing a recheck to see whether the value has
changed?  It doesn't seem easy to figure that out from any of the
statistics we have available today or could easily get, because it
depends not only on the behavior of the expression which appears in
the index definition but also on the application behavior.  For
example, consider a JSON blob representing a bank account.
b->'balance' is likely to change most of the time, but
b->'account_holder_name' only rarely.  That's going to be hard for an
automated system to determine.

We should clearly check as many of the other criteria for a HOT update
as possible before performing a recheck of this type, so that it only
gets performed when it might help.  For example, if column a is
indexed and b->'foo' is indexed, there's no point in checking whether
b->'foo' has changed if we know that a has changed.  I don't know
whether it would be feasible to postpone deciding whether to do a
recheck until after we've figured out whether the page seems to
contain enough free space to allow a HOT update.

Turning non-HOT updates into HOT updates is really good, so it seems
likely that the rechecks will often be worthwhile.  If we avoid a HOT
update in 25% of cases, that's probably easily worth the CPU overhead
of a recheck assuming the function isn't something ridiculously
expensive to compute; the extra CPU cost will be repaid by reduced
bloat.  However, if we avoid a HOT update only one time in a million,
it's probably not worth the cost of recomputing the expression the
other 999,999 times.  I wonder where the crossover point is -- it
seems like something that could be figured out by benchmarking.

While I agree that it would be nice to have this be a completely
automatic determination, I am not sure that will be practical.  I
oppose overloading some other marker (like function_cost>1) for
this; that's too magical.

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


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

Re: [HACKERS] Surjective functional indexes

[Simon Riggs]

On 15 September 2017 at 16:34, Konstantin Knizhnik
 wrote:

> Attached please find yet another version of the patch.

Thanks. I'm reviewing it.

-- 
Simon Riggshttp://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


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

Re: [HACKERS] Surjective functional indexes

[Konstantin Knizhnik]

On 14.09.2017 18:53, Simon Riggs wrote:

It's not going to work, as already mentioned above. Those stats are at
table level and very little to do with this particular index.

But you've not commented on the design I mention that can work: index relcache.


Concerning your idea to check cost of index function: it certainly makes
sense.
The only problems: I do not understand now how to calculate this cost.
It can be easily calculated by optimizer when it is building query execution
plan.
But inside BuildIndexInfo I have just reference to Relation and have no idea
how
I can propagate here information about index expression cost from optimizer.

We could copy at create index, if we took that route. Or we can look
up the cost for the index expression and cache it.


Anyway, this is just jumping around because we still have a parameter
and the idea was to remove the parameter entirely by autotuning, which
I think is both useful and possible, just as HOT itself is autotuned.



Attached please find yet another version of the patch.
I have to significantly rewrite it,  because my first attempts to add 
auto-tune were not correct.

New patch does it in correct way (I hope) and more efficiently.
I moved auto-tune code from BuildIndexInfo, which is called many times, 
including heap_update (so at least once per update tuple).
to RelationGetIndexAttrBitmap which is called only when cached 
RelationData is filled by backend.
The problem with my original implementation of auto-tune was that 
switching off "projection" property of index, it doesn't update 
attribute masks,

calculated by RelationGetIndexAttrBitmap.

I have also added check for maximal cost of indexed expression.
So now decision whether to apply projection index optimization (compare 
old and new values of indexed expression)

is based  on three sources:
 1. Calculated hot update statistic: we compare number of hot updates 
which are performed
because projection index check shows that index expression is not 
changed with total
number of updates affecting attributes used in projection indexes. 
If it is smaller than

some threshold (10%), then index is considered as non-projective.
 2. Calculated cost of index expression: if it is higher than some 
threshold (1000) then
extra comparison of index expression values is expected to be too 
expensive.
 3. "projection" index option explicitly set by user. This setting 
overrides 1) and 2)




--
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 83ee7d3..52189ac 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -294,8 +294,33 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] 
 The optional WITH clause specifies storage
 parameters for the index.  Each index method has its own set of allowed
-storage parameters.  The B-tree, hash, GiST and SP-GiST index methods all
-accept this parameter:
+storage parameters. All indexes accept the following parameter:
+   
+
+   
+   
+projection
+
+ 
+   Functional index is based on on projection function: function which extract subset of its argument.
+   In mathematic such functions are called non-injective. For injective function if any attribute used in the indexed
+   expression is changed, then value of index expression is also changed. So to check that index is affected by the
+   update, it is enough to check the set of changed fields. By default this parameters is assigned true value and function is considered
+   as non-injective.
+   In this case change of any of indexed key doesn't mean that value of the function is changed. For example, for
+   the expression expression(bookinfo-'isbn') defined
+   for column of JSON type is changed only when ISBN is changed, which rarely happen. The same is true for most
+   functional indexes. For non-injective functions, Postgres compares values of indexed expression for old and updated tuple and updates
+   index only when function results are different. It allows to eliminate index update and use HOT update.
+   But there are extra evaluations of the functions. So if function is expensive or probability that change of indexed column will not effect
+   the function value is small, then marking index as projection may increase update speed.
+
+
+   
+   
+
+   
+ The B-tree, hash, GiST and SP-GiST index methods all accept this parameter:

 

diff --git a/src/backend/access/common/reloptions.c b/src/backend/access/common/reloptions.c
index ec10762..b73165f 100644
--- a/src/backend/access/common/reloptions.c
+++ b/src/backend/access/common/reloptions.c
@@ -130,6 +130,15 @@ static relopt_bool boolRelOpts[] =
 	},
 	{
 		{
+			"projection",
+			"Evaluate functional index expression on update to check if its values is 

Re: [HACKERS] Surjective functional indexes

[Konstantin Knizhnik]

On 14.09.2017 18:53, Simon Riggs wrote:



This works by looking at overall stats, and only looks at the overall
HOT %, so its too heavyweight and coarse.

I suggested storing stat info on the relcache and was expecting you
would look at how often the expression evaluates to new == old. If we
evaluate new against old many times, then if the success rate is low
we should stop attempting the comparison. (<10%?)

Another idea:
If we don't make a check when we should have done then we will get a
non-HOT update, so we waste time extra time difference between a HOT
and non-HOT update. If we check and fail we waste time take to perform
check. So the question is how expensive the check is against how
expensive a non-HOT update is. Could we simply say we don't bother to
check functions that have a cost higher than 1? So if the user
doesn't want to perform the check they can just increase the cost of
the function above the check threshold?


Attached pleased find one more patch which calculates hot update check hit
rate more precisely: I have to extended PgStat_StatTabEntry with two new
fields:
hot_update_hits and hot_update_misses.

It's not going to work, as already mentioned above. Those stats are at
table level and very little to do with this particular index.

But you've not commented on the design I mention that can work: index relcache.

Sorry, I do not completely agree with you.
Yes, certainly whether functional index is projective or not is property 
of the index, not of the table.
But the decision whether hot update is applicable or not is made for the 
whole table - for all indexes.
If a value of just one indexed expressions is changed then we can not 
use hot update and have to update all indexes.


Assume that we have table with "bookinfo" field of type JSONB.
And we create several functional indexes on this column: 
(bookinfo->'isbn'), (bookinfo->'title'), (bookinfo->'author'), 
(bookinfo->'rating').
Probability that indexed expression is changed is case of updating 
"bookinfo" field my be different for all this three indexes.
But there is completely no sense to check if 'isbn' is changed or not, 
if we already detect that most updates cause change of 'rating' 
attribute and
so comparing old and new values of (bookinfo->'rating') is just waste of 
time. In this case we should not also compare (bookinfo->'isbn') and
other indexed expressions because for already rejected possibility of 
hot update.


So despite to the fact that this information depends on particular 
index, it affects behavior of the whole table and it is reasonable (and 
simpler) to collect it in table's statistic.



Concerning your idea to check cost of index function: it certainly makes
sense.
The only problems: I do not understand now how to calculate this cost.
It can be easily calculated by optimizer when it is building query execution
plan.
But inside BuildIndexInfo I have just reference to Relation and have no idea
how
I can propagate here information about index expression cost from optimizer.

We could copy at create index, if we took that route. Or we can look
up the cost for the index expression and cache it.


Anyway, this is just jumping around because we still have a parameter
and the idea was to remove the parameter entirely by autotuning, which
I think is both useful and possible, just as HOT itself is autotuned.



Hot update in almost all cases is preferable to normal update, causing 
update of indexes.
There are can be some scenarios when hot updates reduce speed of some 
queries,

but it is very difficult to predict such cases user level.

But usually nature of index is well known by DBA or programmer. In 
almost all cases it is clear for person creating functional index 
whether it will perform projection or not
and whether comparing old/new expression value makes sense or is just 
waste of time. We can guess it from autotune, but such decision may be 
wrong (just because of application
business logic). Postgres indexes already have a lot of options. And I 
think that "projection" option (or whatever we name it) is also needed.



--
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company



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

Re: [HACKERS] Surjective functional indexes

[Simon Riggs]

On 14 September 2017 at 16:37, Konstantin Knizhnik
 wrote:
>
>
> On 14.09.2017 13:19, Simon Riggs wrote:

>> This works by looking at overall stats, and only looks at the overall
>> HOT %, so its too heavyweight and coarse.
>>
>> I suggested storing stat info on the relcache and was expecting you
>> would look at how often the expression evaluates to new == old. If we
>> evaluate new against old many times, then if the success rate is low
>> we should stop attempting the comparison. (<10%?)
>>
>> Another idea:
>> If we don't make a check when we should have done then we will get a
>> non-HOT update, so we waste time extra time difference between a HOT
>> and non-HOT update. If we check and fail we waste time take to perform
>> check. So the question is how expensive the check is against how
>> expensive a non-HOT update is. Could we simply say we don't bother to
>> check functions that have a cost higher than 1? So if the user
>> doesn't want to perform the check they can just increase the cost of
>> the function above the check threshold?
>>
> Attached pleased find one more patch which calculates hot update check hit
> rate more precisely: I have to extended PgStat_StatTabEntry with two new
> fields:
> hot_update_hits and hot_update_misses.

It's not going to work, as already mentioned above. Those stats are at
table level and very little to do with this particular index.

But you've not commented on the design I mention that can work: index relcache.

> Concerning your idea to check cost of index function: it certainly makes
> sense.
> The only problems: I do not understand now how to calculate this cost.
> It can be easily calculated by optimizer when it is building query execution
> plan.
> But inside BuildIndexInfo I have just reference to Relation and have no idea
> how
> I can propagate here information about index expression cost from optimizer.

We could copy at create index, if we took that route. Or we can look
up the cost for the index expression and cache it.


Anyway, this is just jumping around because we still have a parameter
and the idea was to remove the parameter entirely by autotuning, which
I think is both useful and possible, just as HOT itself is autotuned.

-- 
Simon Riggshttp://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


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

Re: [HACKERS] Surjective functional indexes

[Konstantin Knizhnik]

On 14.09.2017 13:19, Simon Riggs wrote:

On 14 September 2017 at 10:42, Konstantin Knizhnik
 wrote:


On 13.09.2017 14:00, Simon Riggs wrote:

On 13 September 2017 at 11:30, Konstantin Knizhnik
 wrote:


The only reason of all this discussion about terms is that I need to
choose
name for correspondent index option.
Simon think that we do not need this option at all. In this case we
should
not worry about right term.
  From my point of view, "projection" is quite clear notion and not only
for
mathematics. It is also widely used in IT and especially in DBMSes.

If we do have an option it won't be using fancy mathematical
terminology at all, it would be described in terms of its function,
e.g. recheck_on_update

Yes, I'd rather not have an option at all, just some simple code with
useful effect, like we have in many other places.


Attached please find new version of projection functional index optimization
patch.
I have implemented very simple autotune strategy: now I use table statistic
to compare total number of updates with number of hot updates.
If fraction of hot updates is relatively small, then there is no sense to
spend time performing extra evaluation of index expression and comparing its
old and new values.
Right now the formula is the following:

#define MIN_UPDATES_THRESHOLD 10
#define HOT_RATIO_THRESHOLD   2

 if (stat->tuples_updated > MIN_UPDATES_THRESHOLD
 && stat->tuples_updated >
stat->tuples_hot_updated*HOT_RATIO_THRESHOLD)
 {
 /* If percent of hot updates is small, then disable projection
index function
  * optimization to eliminate overhead of extra index expression
evaluations.
  */
 ii->ii_Projection = false;
 }

This threshold values are pulled out of a hat: I am not sure if this
heuristic is right.
I will be please to get feedback if such approach to autotune is promising.

Hmm, not really, but thanks for trying.

This works by looking at overall stats, and only looks at the overall
HOT %, so its too heavyweight and coarse.

I suggested storing stat info on the relcache and was expecting you
would look at how often the expression evaluates to new == old. If we
evaluate new against old many times, then if the success rate is low
we should stop attempting the comparison. (<10%?)

Another idea:
If we don't make a check when we should have done then we will get a
non-HOT update, so we waste time extra time difference between a HOT
and non-HOT update. If we check and fail we waste time take to perform
check. So the question is how expensive the check is against how
expensive a non-HOT update is. Could we simply say we don't bother to
check functions that have a cost higher than 1? So if the user
doesn't want to perform the check they can just increase the cost of
the function above the check threshold?

Attached pleased find one more patch which calculates hot update check 
hit rate more precisely: I have to extended PgStat_StatTabEntry with two 
new fields:

hot_update_hits and hot_update_misses.

Concerning your idea to check cost of index function: it certainly makes 
sense.

The only problems: I do not understand now how to calculate this cost.
It can be easily calculated by optimizer when it is building query 
execution plan.
But inside BuildIndexInfo I have just reference to Relation and have no 
idea how

I can propagate here information about index expression cost from optimizer.


--
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 83ee7d3..52189ac 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -294,8 +294,33 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] 
 The optional WITH clause specifies storage
 parameters for the index.  Each index method has its own set of allowed
-storage parameters.  The B-tree, hash, GiST and SP-GiST index methods all
-accept this parameter:
+storage parameters. All indexes accept the following parameter:
+   
+
+   
+   
+projection
+
+ 
+   Functional index is based on on projection function: function which extract subset of its argument.
+   In mathematic such functions are called non-injective. For injective function if any attribute used in the indexed
+   expression is changed, then value of index expression is also changed. So to check that index is affected by the
+   update, it is enough to check the set of changed fields. By default this parameters is assigned true value and function is considered
+   as non-injective.
+   In this case change of any of indexed key doesn't mean that value of the function is changed. For example, for
+   the expression expression(bookinfo-'isbn') defined
+   for column of JSON type is changed only when 

Re: [HACKERS] Surjective functional indexes

[Simon Riggs]

On 14 September 2017 at 10:42, Konstantin Knizhnik
 wrote:
>
>
> On 13.09.2017 14:00, Simon Riggs wrote:
>>
>> On 13 September 2017 at 11:30, Konstantin Knizhnik
>>  wrote:
>>
>>> The only reason of all this discussion about terms is that I need to
>>> choose
>>> name for correspondent index option.
>>> Simon think that we do not need this option at all. In this case we
>>> should
>>> not worry about right term.
>>>  From my point of view, "projection" is quite clear notion and not only
>>> for
>>> mathematics. It is also widely used in IT and especially in DBMSes.
>>
>> If we do have an option it won't be using fancy mathematical
>> terminology at all, it would be described in terms of its function,
>> e.g. recheck_on_update
>>
>> Yes, I'd rather not have an option at all, just some simple code with
>> useful effect, like we have in many other places.
>>
> Attached please find new version of projection functional index optimization
> patch.
> I have implemented very simple autotune strategy: now I use table statistic
> to compare total number of updates with number of hot updates.
> If fraction of hot updates is relatively small, then there is no sense to
> spend time performing extra evaluation of index expression and comparing its
> old and new values.
> Right now the formula is the following:
>
> #define MIN_UPDATES_THRESHOLD 10
> #define HOT_RATIO_THRESHOLD   2
>
> if (stat->tuples_updated > MIN_UPDATES_THRESHOLD
> && stat->tuples_updated >
> stat->tuples_hot_updated*HOT_RATIO_THRESHOLD)
> {
> /* If percent of hot updates is small, then disable projection
> index function
>  * optimization to eliminate overhead of extra index expression
> evaluations.
>  */
> ii->ii_Projection = false;
> }
>
> This threshold values are pulled out of a hat: I am not sure if this
> heuristic is right.
> I will be please to get feedback if such approach to autotune is promising.

Hmm, not really, but thanks for trying.

This works by looking at overall stats, and only looks at the overall
HOT %, so its too heavyweight and coarse.

I suggested storing stat info on the relcache and was expecting you
would look at how often the expression evaluates to new == old. If we
evaluate new against old many times, then if the success rate is low
we should stop attempting the comparison. (<10%?)

Another idea:
If we don't make a check when we should have done then we will get a
non-HOT update, so we waste time extra time difference between a HOT
and non-HOT update. If we check and fail we waste time take to perform
check. So the question is how expensive the check is against how
expensive a non-HOT update is. Could we simply say we don't bother to
check functions that have a cost higher than 1? So if the user
doesn't want to perform the check they can just increase the cost of
the function above the check threshold?

-- 
Simon Riggshttp://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


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

Re: [HACKERS] Surjective functional indexes

[Konstantin Knizhnik]

On 13.09.2017 14:00, Simon Riggs wrote:

On 13 September 2017 at 11:30, Konstantin Knizhnik
 wrote:


The only reason of all this discussion about terms is that I need to choose
name for correspondent index option.
Simon think that we do not need this option at all. In this case we should
not worry about right term.
 From my point of view, "projection" is quite clear notion and not only for
mathematics. It is also widely used in IT and especially in DBMSes.

If we do have an option it won't be using fancy mathematical
terminology at all, it would be described in terms of its function,
e.g. recheck_on_update

Yes, I'd rather not have an option at all, just some simple code with
useful effect, like we have in many other places.

Attached please find new version of projection functional index 
optimization patch.
I have implemented very simple autotune strategy: now I use table 
statistic to compare total number of updates with number of hot updates.
If fraction of hot updates is relatively small, then there is no sense 
to spend time performing extra evaluation of index expression and 
comparing its old and new values.

Right now the formula is the following:

#define MIN_UPDATES_THRESHOLD 10
#define HOT_RATIO_THRESHOLD   2

if (stat->tuples_updated > MIN_UPDATES_THRESHOLD
&& stat->tuples_updated > 
stat->tuples_hot_updated*HOT_RATIO_THRESHOLD)

{
/* If percent of hot updates is small, then disable 
projection index function
 * optimization to eliminate overhead of extra index 
expression evaluations.

 */
ii->ii_Projection = false;
}

This threshold values are pulled out of a hat: I am not sure if this 
heuristic is right.

I will be please to get feedback if such approach to autotune is promising.

--
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 83ee7d3..52189ac 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -294,8 +294,33 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] 
 The optional WITH clause specifies storage
 parameters for the index.  Each index method has its own set of allowed
-storage parameters.  The B-tree, hash, GiST and SP-GiST index methods all
-accept this parameter:
+storage parameters. All indexes accept the following parameter:
+   
+
+   
+   
+projection
+
+ 
+   Functional index is based on on projection function: function which extract subset of its argument.
+   In mathematic such functions are called non-injective. For injective function if any attribute used in the indexed
+   expression is changed, then value of index expression is also changed. So to check that index is affected by the
+   update, it is enough to check the set of changed fields. By default this parameters is assigned true value and function is considered
+   as non-injective.
+   In this case change of any of indexed key doesn't mean that value of the function is changed. For example, for
+   the expression expression(bookinfo-'isbn') defined
+   for column of JSON type is changed only when ISBN is changed, which rarely happen. The same is true for most
+   functional indexes. For non-injective functions, Postgres compares values of indexed expression for old and updated tuple and updates
+   index only when function results are different. It allows to eliminate index update and use HOT update.
+   But there are extra evaluations of the functions. So if function is expensive or probability that change of indexed column will not effect
+   the function value is small, then marking index as projection may increase update speed.
+
+
+   
+   
+
+   
+ The B-tree, hash, GiST and SP-GiST index methods all accept this parameter:

 

diff --git a/src/backend/access/common/reloptions.c b/src/backend/access/common/reloptions.c
index ec10762..b73165f 100644
--- a/src/backend/access/common/reloptions.c
+++ b/src/backend/access/common/reloptions.c
@@ -130,6 +130,15 @@ static relopt_bool boolRelOpts[] =
 	},
 	{
 		{
+			"projection",
+			"Evaluate functional index expression on update to check if its values is changed",
+			RELOPT_KIND_INDEX,
+			AccessExclusiveLock
+		},
+		true
+	},
+	{
+		{
 			"security_barrier",
 			"View acts as a row security barrier",
 			RELOPT_KIND_VIEW,
@@ -1301,7 +1310,7 @@ fillRelOptions(void *rdopts, Size basesize,
 break;
 			}
 		}
-		if (validate && !found)
+		if (validate && !found && options[i].gen->kinds != RELOPT_KIND_INDEX)
 			elog(ERROR, "reloption \"%s\" not found in parse table",
  options[i].gen->name);
 	}
diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index e29c5ad..05e372f 100644
--- a/src/backend/access/heap/heapam.c
+++ 

Re: [HACKERS] Surjective functional indexes

[Konstantin Knizhnik]

On 13.09.2017 14:00, Simon Riggs wrote:

On 13 September 2017 at 11:30, Konstantin Knizhnik
 wrote:


The only reason of all this discussion about terms is that I need to choose
name for correspondent index option.
Simon think that we do not need this option at all. In this case we should
not worry about right term.
 From my point of view, "projection" is quite clear notion and not only for
mathematics. It is also widely used in IT and especially in DBMSes.

If we do have an option it won't be using fancy mathematical
terminology at all, it would be described in terms of its function,
e.g. recheck_on_update

Yes, I'd rather not have an option at all, just some simple code with
useful effect, like we have in many other places.


Yehhh,
After more thinking I found out that my idea to use table/index 
statistic (particularity number of distinct values) to determine 
projection functions  was wrong.
Consider case column bookinfo of jsonb type and index expression 
(bookinfo->'ISBN').
Both can be considered as unique. But it is an obvious example of 
projection function, which value is  not changed if we update other 
information related with this book.


So this approach doesn't work. Looks like the only thing we can do to 
autotune is to collect own statistic: how frequently changing 
attribute(s) doesn't affect result of the function.
By default we can considered function as projection and perform 
comparison of old/new function results.
If after some number of comparisons  fraction of hits (when value of 
function is not changed) is smaller than some threshold (0.5?, 0.9?,...) 
then we can mark index as non-projective
and eliminate this checks in future. But it will require extending index 
statistic. Do we really need/want it?


Despite to the possibility to implement autotune, I still think that we 
should have manual switch, doesn't mater how it is named.


--
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company



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

Re: [HACKERS] Surjective functional indexes

[Simon Riggs]

On 13 September 2017 at 11:30, Konstantin Knizhnik
 wrote:

> The only reason of all this discussion about terms is that I need to choose
> name for correspondent index option.
> Simon think that we do not need this option at all. In this case we should
> not worry about right term.
> From my point of view, "projection" is quite clear notion and not only for
> mathematics. It is also widely used in IT and especially in DBMSes.

If we do have an option it won't be using fancy mathematical
terminology at all, it would be described in terms of its function,
e.g. recheck_on_update

Yes, I'd rather not have an option at all, just some simple code with
useful effect, like we have in many other places.

-- 
Simon Riggshttp://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


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

Re: [HACKERS] Surjective functional indexes

[Konstantin Knizhnik]

On 13.09.2017 13:14, Christoph Berg wrote:

Re: Konstantin Knizhnik 2017-09-13 
<2393c4b3-2ec4-dc68-4ea9-670597b56...@postgrespro.ru>


On 13.09.2017 10:51, Christoph Berg wrote:

Re: Konstantin Knizhnik 2017-09-01 


+   Functional index is based on on projection function: function which 
extract subset of its argument.
+   In mathematic such functions are called non-injective. For injective 
function if any attribute used in the indexed
+   expression is changed, then value of index expression is also changed.

This is Just Wrong. I still think what you are doing here doesn't have
anything to do with the function being injective or not.

Sorry, can you please explain what is wrong?

I don't get why you are reasoning about "projection" ->
"non-injective" -> "injective". Can't you try to explain what this
functionality is about without abusing math terms that just mean
something else in the rest of the world?


I tried to explain it in my previous e-mail. In most cases (it is just 
my filling, may be it is wrong), functional indexes are built for some 
complex types, like JSON, arrays, structs,...
and index expression extracts some components of this compound value. It 
means that even if underlying column is changes, there is good chance 
that value of index function is not changed. So there is no need to 
update index and we can use HOT. It allows to several time increase 
performance.


The only reason of all this discussion about terms is that I need to 
choose name for correspondent index option.
Simon think that we do not need this option at all. In this case we 
should not worry about right term.
From my point of view, "projection" is quite clear notion and not only 
for mathematics. It is also widely used in IT and especially in DBMSes.


--

Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company



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

Re: [HACKERS] Surjective functional indexes

[Christoph Berg]

Re: Konstantin Knizhnik 2017-09-13 
<2393c4b3-2ec4-dc68-4ea9-670597b56...@postgrespro.ru>
> 
> 
> On 13.09.2017 10:51, Christoph Berg wrote:
> > Re: Konstantin Knizhnik 2017-09-01 
> > 
> > > +   Functional index is based on on projection function: function 
> > > which extract subset of its argument.
> > > +   In mathematic such functions are called non-injective. For 
> > > injective function if any attribute used in the indexed
> > > +   expression is changed, then value of index expression is also 
> > > changed.
> > This is Just Wrong. I still think what you are doing here doesn't have
> > anything to do with the function being injective or not.
> 
> Sorry, can you please explain what is wrong?

I don't get why you are reasoning about "projection" ->
"non-injective" -> "injective". Can't you try to explain what this
functionality is about without abusing math terms that just mean
something else in the rest of the world?

Christoph


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

Re: [HACKERS] Surjective functional indexes

[Konstantin Knizhnik]

On 13.09.2017 10:51, Christoph Berg wrote:

Re: Konstantin Knizhnik 2017-09-01 


+   Functional index is based on on projection function: function which 
extract subset of its argument.
+   In mathematic such functions are called non-injective. For injective 
function if any attribute used in the indexed
+   expression is changed, then value of index expression is also changed.

This is Just Wrong. I still think what you are doing here doesn't have
anything to do with the function being injective or not.


Sorry, can you please explain what is wrong?
The problem I am trying to solve comes from particular use case: 
functional index on part of JSON column.
Usually such index is built for persistent attributes, which are rarely 
changed, like ISBN...
Right now any update of JSON column disables hot update. Even if such 
update doesn't really affect index.
So instead of disabling HOT juts based on mask of modified attributes, I 
suggest to compare old and new value of index expression.


Such behavior can significantly (several times) increase performance. 
But only for "projection" functions.
There was long discussion in this thread about right notion for this 
function (subjective,  non-injective,  projection).

But I think criteria is quite obvious.

Simon propose eliminate "projection" property and use autotune to 
determine optimal behavior.
I still think that such option will be useful, but we can really use 
statistic to compare number of unique values for index function and for 
it's argument(s).
If them are similar, then most likely the function is injective, so it 
produce different result for different attributes.
Then there is no sense to spend extra CPU time, calculating old and new 
values of the function.

This is what I am going to implement now.

So I will be please if you more precisely explain your concerns and 
suggestions (if you have one).


--
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company



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

Re: [HACKERS] Surjective functional indexes

[Christoph Berg]

Re: Konstantin Knizhnik 2017-09-01 

> +   Functional index is based on on projection function: function which 
> extract subset of its argument.
> +   In mathematic such functions are called non-injective. For injective 
> function if any attribute used in the indexed
> +   expression is changed, then value of index expression is also changed.

This is Just Wrong. I still think what you are doing here doesn't have
anything to do with the function being injective or not.

Christoph


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

Re: [HACKERS] Surjective functional indexes

[Konstantin Knizhnik]

On 12.09.2017 19:28, Simon Riggs wrote:

On 1 September 2017 at 09:47, Konstantin Knizhnik
 wrote:

On 01.09.2017 09:25, Simon Riggs wrote:

On 1 September 2017 at 05:40, Thomas Munro
 wrote:

On Fri, Jun 9, 2017 at 8:08 PM, Konstantin Knizhnik
 wrote:

Attached please find rebased version of the patch.
Now "projection" attribute is used instead of surjective/injective.

Hi Konstantin,

This still applies but it doesn't compile after commits 2cd70845 and
c6293249.  You need to change this:

Form_pg_attribute att = RelationGetDescr(indexDesc)->attrs[i];

... to this:

Form_pg_attribute att = TupleDescAttr(RelationGetDescr(indexDesc),
i);

Thanks!

Does the patch work fully with that change? If so, I will review.


Attached please find rebased version of the patch.
Yes, I checked that it works after this fix.
Thank you in advance for review.

Thanks for the patch. Overall looks sound and I consider that we are
working towards commit for this.

The idea is that we default "projection = on", and can turn it off in
case the test is expensive. Why bother to have the option? (No docs at
all then!) Why not just evaluate the test and autotune whether to make
the test again in the future? That way we can avoid having an option
completely. I am imagining collecting values on the relcache entry for
the index.


Autotune is definitely good thing. But I do not think that excludes 
having explicit parameter for manual tuning.
For some functional indexes DBA or programmer knows for sure that it 
doesn't perform projection.
For example if it translates or changes encoding of original key. It 
seems to me that we should make it possible to

declare this index as non-projective and do not rely on autotune.

Also I have some doubts concerning using autotune in this case. First of 
all it is very hard to estimate complexity of test.
How can we measure it? Calculate average execution time? It can vary for 
different systems and greatly depends on system load...
Somehow calculate cost of indexed expression? It may be also not always 
produce expected result.


Moreover, in some cases test may be not expensive, but still useless, if 
index expression specifies one-to-one mapping (for example function 
reversing key).
Autotone will never be able to reliable determine that indexed 
expression is projection or not.


It seems to be more precise to compare statistic for source column and 
index expression.
If them are similar, then most likely index expression is not a 
projection...

I will think more about it.


To implement autotuning we would need to instrument the execution. We
could then display the collected value via EXPLAIN, so we could just
then use EXPLAIN in your tests rather than implementing a special
debug mode just for testing. We could also pass that information thru
to stats as well.



--
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company



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

Re: [HACKERS] Surjective functional indexes

[Simon Riggs]

On 1 September 2017 at 09:47, Konstantin Knizhnik
 wrote:
>
> On 01.09.2017 09:25, Simon Riggs wrote:
>>
>> On 1 September 2017 at 05:40, Thomas Munro
>>  wrote:
>>>
>>> On Fri, Jun 9, 2017 at 8:08 PM, Konstantin Knizhnik
>>>  wrote:

 Attached please find rebased version of the patch.
 Now "projection" attribute is used instead of surjective/injective.
>>>
>>> Hi Konstantin,
>>>
>>> This still applies but it doesn't compile after commits 2cd70845 and
>>> c6293249.  You need to change this:
>>>
>>>Form_pg_attribute att = RelationGetDescr(indexDesc)->attrs[i];
>>>
>>> ... to this:
>>>
>>>Form_pg_attribute att = TupleDescAttr(RelationGetDescr(indexDesc),
>>> i);
>>>
>>> Thanks!
>>
>> Does the patch work fully with that change? If so, I will review.
>>
> Attached please find rebased version of the patch.
> Yes, I checked that it works after this fix.
> Thank you in advance for review.

Thanks for the patch. Overall looks sound and I consider that we are
working towards commit for this.

The idea is that we default "projection = on", and can turn it off in
case the test is expensive. Why bother to have the option? (No docs at
all then!) Why not just evaluate the test and autotune whether to make
the test again in the future? That way we can avoid having an option
completely. I am imagining collecting values on the relcache entry for
the index.

To implement autotuning we would need to instrument the execution. We
could then display the collected value via EXPLAIN, so we could just
then use EXPLAIN in your tests rather than implementing a special
debug mode just for testing. We could also pass that information thru
to stats as well.

-- 
Simon Riggshttp://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


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

Re: [HACKERS] Surjective functional indexes

[Konstantin Knizhnik]

On 01.09.2017 09:25, Simon Riggs wrote:

On 1 September 2017 at 05:40, Thomas Munro
 wrote:

On Fri, Jun 9, 2017 at 8:08 PM, Konstantin Knizhnik
 wrote:

Attached please find rebased version of the patch.
Now "projection" attribute is used instead of surjective/injective.

Hi Konstantin,

This still applies but it doesn't compile after commits 2cd70845 and
c6293249.  You need to change this:

   Form_pg_attribute att = RelationGetDescr(indexDesc)->attrs[i];

... to this:

   Form_pg_attribute att = TupleDescAttr(RelationGetDescr(indexDesc), i);

Thanks!

Does the patch work fully with that change? If so, I will review.


Attached please find rebased version of the patch.
Yes, I checked that it works after this fix.
Thank you in advance for review.

--
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 83ee7d3..52189ac 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -294,8 +294,33 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] 
 The optional WITH clause specifies storage
 parameters for the index.  Each index method has its own set of allowed
-storage parameters.  The B-tree, hash, GiST and SP-GiST index methods all
-accept this parameter:
+storage parameters. All indexes accept the following parameter:
+   
+
+   
+   
+projection
+
+ 
+   Functional index is based on on projection function: function which extract subset of its argument.
+   In mathematic such functions are called non-injective. For injective function if any attribute used in the indexed
+   expression is changed, then value of index expression is also changed. So to check that index is affected by the
+   update, it is enough to check the set of changed fields. By default this parameters is assigned true value and function is considered
+   as non-injective.
+   In this case change of any of indexed key doesn't mean that value of the function is changed. For example, for
+   the expression expression(bookinfo-'isbn') defined
+   for column of JSON type is changed only when ISBN is changed, which rarely happen. The same is true for most
+   functional indexes. For non-injective functions, Postgres compares values of indexed expression for old and updated tuple and updates
+   index only when function results are different. It allows to eliminate index update and use HOT update.
+   But there are extra evaluations of the functions. So if function is expensive or probability that change of indexed column will not effect
+   the function value is small, then marking index as projection may increase update speed.
+
+
+   
+   
+
+   
+ The B-tree, hash, GiST and SP-GiST index methods all accept this parameter:

 

diff --git a/src/backend/access/common/reloptions.c b/src/backend/access/common/reloptions.c
index ec10762..b73165f 100644
--- a/src/backend/access/common/reloptions.c
+++ b/src/backend/access/common/reloptions.c
@@ -130,6 +130,15 @@ static relopt_bool boolRelOpts[] =
 	},
 	{
 		{
+			"projection",
+			"Evaluate functional index expression on update to check if its values is changed",
+			RELOPT_KIND_INDEX,
+			AccessExclusiveLock
+		},
+		true
+	},
+	{
+		{
 			"security_barrier",
 			"View acts as a row security barrier",
 			RELOPT_KIND_VIEW,
@@ -1301,7 +1310,7 @@ fillRelOptions(void *rdopts, Size basesize,
 break;
 			}
 		}
-		if (validate && !found)
+		if (validate && !found && options[i].gen->kinds != RELOPT_KIND_INDEX)
 			elog(ERROR, "reloption \"%s\" not found in parse table",
  options[i].gen->name);
 	}
diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index e29c5ad..05e372f 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -56,6 +56,7 @@
 #include "access/xlogutils.h"
 #include "catalog/catalog.h"
 #include "catalog/namespace.h"
+#include "catalog/index.h"
 #include "miscadmin.h"
 #include "pgstat.h"
 #include "port/atomics.h"
@@ -74,7 +75,9 @@
 #include "utils/snapmgr.h"
 #include "utils/syscache.h"
 #include "utils/tqual.h"
-
+#include "utils/memutils.h"
+#include "nodes/execnodes.h"
+#include "executor/executor.h"
 
 /* GUC variable */
 bool		synchronize_seqscans = true;
@@ -126,6 +129,7 @@ static bool ConditionalMultiXactIdWait(MultiXactId multi, MultiXactStatus status
 static XLogRecPtr log_heap_new_cid(Relation relation, HeapTuple tup);
 static HeapTuple ExtractReplicaIdentity(Relation rel, HeapTuple tup, bool key_modified,
 	   bool *copy);
+static bool ProjectionIsNotChanged(Relation relation, HeapTuple oldtup, HeapTuple newtup);
 
 
 /*
@@ -3547,8 +3551,6 @@ heap_update(Relation relation, ItemPointer otid, HeapTuple newtup,
 	key_attrs = 

Re: [HACKERS] Surjective functional indexes

[Simon Riggs]

On 1 September 2017 at 05:40, Thomas Munro
 wrote:
> On Fri, Jun 9, 2017 at 8:08 PM, Konstantin Knizhnik
>  wrote:
>> Attached please find rebased version of the patch.
>> Now "projection" attribute is used instead of surjective/injective.
>
> Hi Konstantin,
>
> This still applies but it doesn't compile after commits 2cd70845 and
> c6293249.  You need to change this:
>
>   Form_pg_attribute att = RelationGetDescr(indexDesc)->attrs[i];
>
> ... to this:
>
>   Form_pg_attribute att = TupleDescAttr(RelationGetDescr(indexDesc), i);
>
> Thanks!

Does the patch work fully with that change? If so, I will review.

-- 
Simon Riggshttp://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


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

Re: [HACKERS] Surjective functional indexes

[Thomas Munro]

On Fri, Jun 9, 2017 at 8:08 PM, Konstantin Knizhnik
 wrote:
> Attached please find rebased version of the patch.
> Now "projection" attribute is used instead of surjective/injective.

Hi Konstantin,

This still applies but it doesn't compile after commits 2cd70845 and
c6293249.  You need to change this:

  Form_pg_attribute att = RelationGetDescr(indexDesc)->attrs[i];

... to this:

  Form_pg_attribute att = TupleDescAttr(RelationGetDescr(indexDesc), i);

Thanks!

-- 
Thomas Munro
http://www.enterprisedb.com


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

Re: [HACKERS] Surjective functional indexes

[Konstantin Knizhnik]

Attached please find rebased version of the patch.
Now "projection" attribute is used instead of surjective/injective.

--
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 83ee7d3..b221c18 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -294,8 +294,33 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] 
 The optional WITH clause specifies storage
 parameters for the index.  Each index method has its own set of allowed
-storage parameters.  The B-tree, hash, GiST and SP-GiST index methods all
-accept this parameter:
+storage parameters. All indexes accept the following parameter:
+   
+
+   
+   
+projection
+
+ 
+   Functional index is based on on projection function: function which extract subset of its argument. 
+   In mathematic such functions are called non-injective. For injective function if any attribute used in the indexed 
+   expression is changed, then value of index expression is also changed. So to check that index is affected by the 
+   update, it is enough to check the set of changed fields. By default this parameters is assigned true value and function is considered 
+   as non-injective.
+   In this case change of any of indexed key doesn't mean that value of the function is changed. For example, for 
+   the expression expression(bookinfo-'isbn') defined
+   for column of JSON type is changed only when ISBN is changed, which rarely happen. The same is true for most
+   functional indexes. For non-injective functions, Postgres compares values of indexed expression for old and updated tuple and updates
+   index only when function results are different. It allows to eliminate index update and use HOT update.
+   But there are extra evaluations of the functions. So if function is expensive or probability that change of indexed column will not effect 
+   the function value is small, then marking index as projection may increase update speed.
+
+
+   
+   
+
+   
+ The B-tree, hash, GiST and SP-GiST index methods all accept this parameter:

 

diff --git a/src/backend/access/common/reloptions.c b/src/backend/access/common/reloptions.c
index 6d1f22f..509c647 100644
--- a/src/backend/access/common/reloptions.c
+++ b/src/backend/access/common/reloptions.c
@@ -130,6 +130,15 @@ static relopt_bool boolRelOpts[] =
 	},
 	{
 		{
+			"projection",
+			"Evaluate functional index expression on update to check if its values is changed",
+			RELOPT_KIND_INDEX,
+			AccessExclusiveLock
+		},
+		true
+	},
+	{
+		{
 			"security_barrier",
 			"View acts as a row security barrier",
 			RELOPT_KIND_VIEW,
@@ -1301,7 +1310,7 @@ fillRelOptions(void *rdopts, Size basesize,
 break;
 			}
 		}
-		if (validate && !found)
+		if (validate && !found && options[i].gen->kinds != RELOPT_KIND_INDEX)
 			elog(ERROR, "reloption \"%s\" not found in parse table",
  options[i].gen->name);
 	}
diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index e890e08..2be99ab 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -56,6 +56,7 @@
 #include "access/xlogutils.h"
 #include "catalog/catalog.h"
 #include "catalog/namespace.h"
+#include "catalog/index.h"
 #include "miscadmin.h"
 #include "pgstat.h"
 #include "storage/bufmgr.h"
@@ -73,7 +74,9 @@
 #include "utils/snapmgr.h"
 #include "utils/syscache.h"
 #include "utils/tqual.h"
-
+#include "utils/memutils.h"
+#include "nodes/execnodes.h"
+#include "executor/executor.h"
 
 /* GUC variable */
 bool		synchronize_seqscans = true;
@@ -124,6 +127,7 @@ static bool ConditionalMultiXactIdWait(MultiXactId multi, MultiXactStatus status
 static XLogRecPtr log_heap_new_cid(Relation relation, HeapTuple tup);
 static HeapTuple ExtractReplicaIdentity(Relation rel, HeapTuple tup, bool key_modified,
 	   bool *copy);
+static bool ProjectionIsNotChanged(Relation relation, HeapTuple oldtup, HeapTuple newtup);
 
 
 /*
@@ -3533,8 +3537,6 @@ heap_update(Relation relation, ItemPointer otid, HeapTuple newtup,
 	key_attrs = RelationGetIndexAttrBitmap(relation, INDEX_ATTR_BITMAP_KEY);
 	id_attrs = RelationGetIndexAttrBitmap(relation,
 		  INDEX_ATTR_BITMAP_IDENTITY_KEY);
-
-
 	block = ItemPointerGetBlockNumber(otid);
 	buffer = ReadBuffer(relation, block);
 	page = BufferGetPage(buffer);
@@ -4161,8 +4163,12 @@ l2:
 		 * changed. If the page was already full, we may have skipped checking
 		 * for index columns. If so, HOT update is possible.
 		 */
-		if (hot_attrs_checked && !bms_overlap(modified_attrs, hot_attrs))
+		if (hot_attrs_checked 
+			&& !bms_overlap(modified_attrs, hot_attrs) 
+			&& (!relation->rd_projection || ProjectionIsNotChanged(relation, , newtup)))
+		{
 			use_hot_update = true;
+		}
 	}
 	else
 	{
@@ -4199,6 

Re: [HACKERS] Surjective functional indexes

[Christoph Berg]

Re: Konstantin Knizhnik 2017-05-30 

> 
> 
> On 29.05.2017 20:21, Christoph Berg wrote:
> > 
> > I think the term you were looking for is "projection".
> > 
> > https://en.wikipedia.org/wiki/Projection_(set_theory)
> 
> I have already renamed parameter from "surjective" to "injective".
> But I am ok to do do one more renaming to "projection" if it will be
> considered as better alternative.
> From my point of view, "projection" seems to be clearer for people without
> mathematical background,
> but IMHO this term is overloaded in DBMS context.

With mathematical background, I don't see how your indexes would
exploit surjective or injective properties of the function used. What
you are using is that ->> projects a json value to one of its
components, i.e. the projection/function result does not depend on the
other attributes contained.

> The irony is that in Wikipedia "projection" is explained using
> "surjection" term:)

For the equivalence classes part, which isn't really connected to your
application.

Christoph


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

Re: [HACKERS] Surjective functional indexes

[Konstantin Knizhnik]

On 29.05.2017 20:21, Christoph Berg wrote:


I think the term you were looking for is "projection".

https://en.wikipedia.org/wiki/Projection_(set_theory)


I have already renamed parameter from "surjective" to "injective".
But I am ok to do do one more renaming to "projection" if it will be 
considered as better alternative.
From my point of view, "projection" seems to be clearer for people 
without mathematical background,
but IMHO this term is overloaded in DBMS context. The irony is that in 
Wikipedia "projection" is explained using "surjection" term:)




Christoph


--
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company



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

Re: [HACKERS] Surjective functional indexes

[Sven R. Kunze]

On 29.05.2017 21:25, Sven R. Kunze wrote:

[...] non-surjective functions.

non-injective of course


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

Re: [HACKERS] Surjective functional indexes

[Sven R. Kunze]

On 29.05.2017 19:21, Christoph Berg wrote:

I think the term you were looking for is "projection".
https://en.wikipedia.org/wiki/Projection_(set_theory)


Maybe, I am seeing too much of a connection here but recently Raymond 
Hettinger held a very interesting talk [1] at PyCon 2017.


For those without the time or bandwidth to watch: it describes the 
history of the modern dict in Python in several steps.


1) avoiding having a database scheme with columns and rows and indexes
2) introducing hashing with bucket lists
3...6) several improvements
7) in the end looks like a database table with indexes again ;)

If you have the time, just go ahead and watch the 30 min video. He can 
explain things definitely better than me.



In order to draw the line back on-topic, if I am not completely 
mistaken, his talks basically shows that over time even datastructures 
with different APIs such as dicts (hashes, maps, sets, etc.) internally 
converge towards a relational-database-y design because of performance 
and resources reasons.



Thus let me think that also in the on-topic case, we might best be 
supporting the much narrow use-case of "Projection" (a term also used in 
relation database theory btw. ;-) ) instead of non-surjective functions.



Cheers,
Sven


[1] https://www.youtube.com/watch?v=npw4s1QTmPg


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

Re: [HACKERS] Surjective functional indexes

[Christoph Berg]

Re: Konstantin Knizhnik 2017-05-29 <592bbd90.3060...@postgrespro.ru>
> On 05/27/2017 09:50 PM, Peter Eisentraut wrote:
> > On 5/25/17 12:30, Konstantin Knizhnik wrote:
> > > Functions like (info->>'name') are named "surjective" ni mathematics.
> > A surjective function is one where each value in the output type can be
> > obtained by some input value.  That's not what you are after here.  The
> > behavior you are describing is a not-injective function.
> > 
> > I think you are right that in practice most functions are not injective.
> >   But I think there is still quite some difference between a function
> > like the one you showed that selects a component from a composite data
> > structure and, for example, round(), where in practice any update is
> > likely to change the result of the function.
> > 
> Thank you, I will rename "surjective" parameter to "injective" with "false" 
> as default value.

I think the term you were looking for is "projection".

https://en.wikipedia.org/wiki/Projection_(set_theory)

Christoph


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

Re: [HACKERS] Surjective functional indexes

[Konstantin Knizhnik]

On 05/27/2017 09:50 PM, Peter Eisentraut wrote:

On 5/25/17 12:30, Konstantin Knizhnik wrote:

Functions like (info->>'name') are named "surjective" ni mathematics.

A surjective function is one where each value in the output type can be
obtained by some input value.  That's not what you are after here.  The
behavior you are describing is a not-injective function.

I think you are right that in practice most functions are not injective.
  But I think there is still quite some difference between a function
like the one you showed that selects a component from a composite data
structure and, for example, round(), where in practice any update is
likely to change the result of the function.


Thank you, I will rename "surjective" parameter to "injective" with "false" as 
default value.
Concerning "round" and other similar functions - obviously there are use cases 
when such functions are used for
functional indexes. This is why I want to allow user to make a choice and this 
is the reason of introducing this parameter.
The question is the default value of this parameter: should we by default 
preserve original Postgres behavior:
check only affected set of keys or should we pay extra cost for calculating 
value of the function (even if we managed to store
calculated value of the indexes expression for new tuple, we still have to 
calculate it for old tuple, so function will be calculated
at least twice more times).

--
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company



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

Re: [HACKERS] Surjective functional indexes

[Peter Eisentraut]

On 5/25/17 12:30, Konstantin Knizhnik wrote:
> Functions like (info->>'name') are named "surjective" ni mathematics.

A surjective function is one where each value in the output type can be
obtained by some input value.  That's not what you are after here.  The
behavior you are describing is a not-injective function.

I think you are right that in practice most functions are not injective.
 But I think there is still quite some difference between a function
like the one you showed that selects a component from a composite data
structure and, for example, round(), where in practice any update is
likely to change the result of the function.

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



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

Re: [HACKERS] Surjective functional indexes

[Konstantin Knizhnik]

On 25.05.2017 19:37, Tom Lane wrote:

Konstantin Knizhnik  writes:

My proposal is to check value of function for functional indexes instead
of just comparing set of effected attributes.
Obviously, for some complex functions it may  have negative effect on
update speed.
This is why I have added "surjective" option to index.

This seems overcomplicated.  We would have to compute the function
value at some point anyway.  Can't we refactor to do that earlier?

regards, tom lane



Check for affected indexes/applicability of HOT update and update of 
indexes themselves is done in two completely different parts of code.
And if we find out that values of indexed expressions are not changed, 
then we can use HOT update and indexes should not be updated
(so calculated value of function is not needed). And it is expected to 
be most frequent case.


Certainly, if value of indexed expression is changed, then we can avoid 
redundant calculation of function by storing result of calculations 
somewhere.
But it will greatly complicate all logic of updating indexes. Please 
notice, that if we have several functional indexes and only one of them 
is actually changed,
then in any case we can not use HOT and have to update all indexes. So 
we do not need to evaluate values of all indexed expressions. We just 
need to find first
changed one. So we should somehow keep track values of which expression 
are calculated and which not.


One more argument. Originally Postgres evaluates index expression only 
once (when inserting new version of tuple to the index).
Now (with this patch) Postgres has to evaluate expression three times in 
the worst case: calculate the value of expression for old and new tuples 
to make a decision bout hot update,
and the evaluate it once again when performing index update itself. Even 
if I managed to store somewhere calculated value of the expression, we 
still have to perform
twice more evaluations than before. This is why for expensive functions 
or for functions defined for frequently updated attributes (in case of 
JSON) such policy should be disabled.
And for non-expensive functions extra overhead is negligible. Also there 
is completely no overhead if indexed expression is not actually changed. 
And it is expected to be most frequent case.


At least at the particular example with YCSB benchmark, our first try 
was just to disable index update by commenting correspondent check of 
updated fields mask.
Obviously there are no extra function calculations in this case. Then I 
have implemented this patch. And performance is almost the same.
This is why I think that simplicity and modularity of code is more 
important here than elimination of redundant function calculation.



--
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company



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

Re: [HACKERS] Surjective functional indexes

[Andres Freund]

On 2017-05-25 12:37:40 -0400, Tom Lane wrote:
> Konstantin Knizhnik  writes:
> > My proposal is to check value of function for functional indexes instead 
> > of just comparing set of effected attributes.
> > Obviously, for some complex functions it may  have negative effect on 
> > update speed.
> > This is why I have added "surjective" option to index.
> 
> This seems overcomplicated.  We would have to compute the function
> value at some point anyway.  Can't we refactor to do that earlier?

Yea, that'd be good. Especially if we were to compute the expressions
for all indexes in one go - doing that in other places (e.g. aggregate
transition values) yielded a good amount of speedup.  It'd be even
larger if we get JITing of expressions.  It seems feasible to do so for
at least the nodeModifyTable case.

I wonder if there's a chance to use such logic alsofor HOT update
considerations, but that seems harder to do without larger layering
violations.

- Andres


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

Re: [HACKERS] Surjective functional indexes

[Tom Lane]

Konstantin Knizhnik  writes:
> My proposal is to check value of function for functional indexes instead 
> of just comparing set of effected attributes.
> Obviously, for some complex functions it may  have negative effect on 
> update speed.
> This is why I have added "surjective" option to index.

This seems overcomplicated.  We would have to compute the function
value at some point anyway.  Can't we refactor to do that earlier?

regards, tom lane


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

[HACKERS] Surjective functional indexes

[Konstantin Knizhnik]

Right now Postgres determines whether update operation touch index or 
not based only on set of the affected columns.
But in case of functional indexes such policy quite frequently leads to 
unnecessary index updates.
For example, functional index are widely use for indexing JSON data: 
info->>'name'.


JSON data may contain multiple attributes and only few of them may be 
affected by update.
Moreover, index is used to build for immutable attributes (like "id", 
"isbn", "name",...).


Functions like (info->>'name') are named "surjective" ni mathematics.
I have strong feeling that most of functional indexes are based on 
surjective functions.
For such indexes current Postgresql index update policy is very 
inefficient.  It cause disabling of hot updates

and so leads to significant degrade of performance.

Without this patch Postgres is slower than Mongo on YCSB benchmark with 
(50% update,50 % select)  workload.

And after applying this patch Postgres beats Mongo at all workloads.

My proposal is to check value of function for functional indexes instead 
of just comparing set of effected attributes.
Obviously, for some complex functions it may  have negative effect on 
update speed.
This is why I have added "surjective" option to index. By default it is 
switched on for all functional indexes (based on my assumption
that most functions used in functional indexes are surjective). But it 
is possible to explicitly disable it and make decision weather index

needs to be updated or not only based on set of effected attributes.


--
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

diff --git a/src/backend/access/common/reloptions.c b/src/backend/access/common/reloptions.c
index 6d1f22f..37fc407 100644
--- a/src/backend/access/common/reloptions.c
+++ b/src/backend/access/common/reloptions.c
@@ -130,6 +130,15 @@ static relopt_bool boolRelOpts[] =
 	},
 	{
 		{
+			"surjective",
+			"Reevaluate functional index expression on update to check if its values is changed",
+			RELOPT_KIND_INDEX,
+			AccessExclusiveLock
+		},
+		true
+	},
+	{
+		{
 			"security_barrier",
 			"View acts as a row security barrier",
 			RELOPT_KIND_VIEW,
@@ -1301,7 +1310,7 @@ fillRelOptions(void *rdopts, Size basesize,
 break;
 			}
 		}
-		if (validate && !found)
+		if (validate && !found && options[i].gen->kinds != RELOPT_KIND_INDEX)
 			elog(ERROR, "reloption \"%s\" not found in parse table",
  options[i].gen->name);
 	}
diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index e890e08..3525e3c 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -56,6 +56,7 @@
 #include "access/xlogutils.h"
 #include "catalog/catalog.h"
 #include "catalog/namespace.h"
+#include "catalog/index.h"
 #include "miscadmin.h"
 #include "pgstat.h"
 #include "storage/bufmgr.h"
@@ -73,7 +74,9 @@
 #include "utils/snapmgr.h"
 #include "utils/syscache.h"
 #include "utils/tqual.h"
-
+#include "utils/memutils.h"
+#include "nodes/execnodes.h"
+#include "executor/executor.h"
 
 /* GUC variable */
 bool		synchronize_seqscans = true;
@@ -4199,6 +4202,7 @@ l2:
 
 	if (use_hot_update)
 	{
+		elog(DEBUG1, "Use hot update");
 		/* Mark the old tuple as HOT-updated */
 		HeapTupleSetHotUpdated();
 		/* And mark the new tuple as heap-only */
@@ -4436,6 +4440,73 @@ HeapDetermineModifiedColumns(Relation relation, Bitmapset *interesting_cols,
 attnum - FirstLowInvalidHeapAttributeNumber);
 	}
 
+	if (hot_result && relation->rd_surjective)
+	{
+		ListCell   *l;
+		List	   *indexoidlist = RelationGetIndexList(relation);
+		EState *estate = CreateExecutorState();
+		ExprContext*econtext = GetPerTupleExprContext(estate);
+		TupleTableSlot *slot = MakeSingleTupleTableSlot(RelationGetDescr(relation));
+		Datum	   	old_values[INDEX_MAX_KEYS];
+		bool		old_isnull[INDEX_MAX_KEYS];
+		Datum	   	new_values[INDEX_MAX_KEYS];
+		bool		new_isnull[INDEX_MAX_KEYS];
+
+		econtext->ecxt_scantuple = slot;
+
+		foreach(l, indexoidlist)
+		{
+			Oid		indexOid = lfirst_oid(l);
+			RelationindexDesc = index_open(indexOid, AccessShareLock);
+			IndexInfo  *indexInfo = BuildIndexInfo(indexDesc);
+			int i;
+
+			if (indexInfo->ii_Expressions && indexInfo->ii_Surjective)
+			{
+ResetExprContext(econtext);
+ExecStoreTuple(oldtup, slot, InvalidBuffer, false);
+FormIndexDatum(indexInfo,
+			   slot,
+			   estate,
+			   old_values,
+			   old_isnull);
+
+ExecStoreTuple(newtup, slot, InvalidBuffer, false);
+FormIndexDatum(indexInfo,
+			   slot,
+			   estate,
+			   new_values,
+			   new_isnull);
+
+for (i = 0; i < indexInfo->ii_NumIndexAttrs; i++)
+{
+	if (old_isnull[i] != new_isnull[i])
+	{
+		hot_result = false;
+		break;
+	}
+	else if (!old_isnull[i])
+	{
+		Form_pg_attribute att = RelationGetDescr(indexDesc)->attrs[i];
+		if