Re: [HACKERS] Surjective functional indexes
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
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
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
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
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 ch
Re: [HACKERS] Surjective functional indexes
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
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
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 ISBN is changed, which rarely happen. The same is true f
Re: [HACKERS] Surjective functional indexes
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
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 +++ b/src/backend/access/heap/
Re: [HACKERS] Surjective functional indexes
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
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
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
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
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
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
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
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
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 = RelationGetIndexAttrBitmap(relation, INDEX_ATTR_BITMAP_KEY); id_attrs = RelationGetInd
Re: [HACKERS] Surjective functional indexes
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
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
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, &oldtup, newtup))) + { use_hot_update = true; + } } else { @@ -4
Re: [HACKERS] Surjective functional indexes
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
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
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
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
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
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
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
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
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
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
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(&oldtup); /* 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]; +