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
Attachments:
surjective-index.patchtext/x-patch; name=surjective-index.patchDownload
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);
+ Relation indexDesc = 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 (!datumIsEqual(old_values[i], new_values[i], att->attbyval, att->attlen))
+ {
+ hot_result = false;
+ break;
+ }
+
+ }
+ }
+ }
+ index_close(indexDesc, AccessShareLock);
+ }
+ ExecDropSingleTupleTableSlot(slot);
+ FreeExecutorState(estate);
+ }
+
+ *satisfies_hot = hot_result;
+ *satisfies_key = key_result;
+ *satisfies_id = id_result;
+
return modified;
}
diff --git a/src/backend/catalog/index.c b/src/backend/catalog/index.c
index 2328b92..91217fa 100644
--- a/src/backend/catalog/index.c
+++ b/src/backend/catalog/index.c
@@ -26,6 +26,7 @@
#include "access/amapi.h"
#include "access/multixact.h"
#include "access/relscan.h"
+#include "access/reloptions.h"
#include "access/sysattr.h"
#include "access/transam.h"
#include "access/visibilitymap.h"
@@ -86,6 +87,13 @@ typedef struct
tups_inserted;
} v_i_state;
+/* options common to all indexes */
+typedef struct
+{
+ int32 vl_len_;
+ bool surjective;
+} index_options;
+
/* non-export function prototypes */
static bool relationHasPrimaryKey(Relation rel);
static TupleDesc ConstructTupleDescriptor(Relation heapRelation,
@@ -1676,6 +1684,40 @@ BuildIndexInfo(Relation index)
ii->ii_ExclusionStrats = NULL;
}
+ if (ii->ii_Expressions)
+ {
+ HeapTuple tuple;
+ Datum reloptions;
+ bool isnull;
+
+ ii->ii_Surjective = true; /* by default functional index is considered as surjective */
+
+ tuple = SearchSysCache1(RELOID, ObjectIdGetDatum(RelationGetRelid(index)));
+ if (!HeapTupleIsValid(tuple))
+ elog(ERROR, "cache lookup failed for relation %u", RelationGetRelid(index));
+
+ reloptions = SysCacheGetAttr(RELOID, tuple,
+ Anum_pg_class_reloptions, &isnull);
+ if (!isnull)
+ {
+ static const relopt_parse_elt tab[] = {
+ {"surjective", RELOPT_TYPE_BOOL, offsetof(index_options, surjective)}
+ };
+ int numoptions;
+ relopt_value *options = parseRelOptions(reloptions, false,
+ RELOPT_KIND_INDEX,
+ &numoptions);
+ if (numoptions != 0)
+ {
+ index_options optstruct;
+ fillRelOptions((void *)&optstruct, sizeof(bool), options, numoptions, false, tab, lengthof(tab));
+ ii->ii_Surjective = optstruct.surjective;
+ pfree(options);
+ }
+ }
+ ReleaseSysCache(tuple);
+ }
+
/* other info */
ii->ii_Unique = indexStruct->indisunique;
ii->ii_ReadyForInserts = IndexIsReady(indexStruct);
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index c2e8361..d3b75f6 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -4854,6 +4854,7 @@ RelationGetIndexAttrBitmap(Relation relation, IndexAttrBitmapKind attrKind)
List *newindexoidlist;
Oid relpkindex;
Oid relreplindex;
+ bool surjective = false;
ListCell *l;
MemoryContext oldcxt;
@@ -4963,9 +4964,15 @@ restart:
}
}
- /* Collect all attributes used in expressions, too */
- pull_varattnos((Node *) indexInfo->ii_Expressions, 1, &indexattrs);
-
+ if (indexInfo->ii_Expressions && indexInfo->ii_Surjective)
+ {
+ surjective = true;
+ }
+ else
+ {
+ /* Collect all attributes used in expressions, too */
+ pull_varattnos((Node *) indexInfo->ii_Expressions, 1, &indexattrs);
+ }
/* Collect all attributes in the index predicate, too */
pull_varattnos((Node *) indexInfo->ii_Predicate, 1, &indexattrs);
@@ -5010,6 +5017,8 @@ restart:
bms_free(relation->rd_idattr);
relation->rd_idattr = NULL;
+ relation->rd_surjective = surjective;
+
/*
* Now save copies of the bitmaps in the relcache entry. We intentionally
* set rd_indexattr last, because that's the one that signals validity of
diff --git a/src/bin/psql/tab-complete.c b/src/bin/psql/tab-complete.c
index 2abd087..f404888 100644
--- a/src/bin/psql/tab-complete.c
+++ b/src/bin/psql/tab-complete.c
@@ -1647,11 +1647,11 @@ psql_completion(const char *text, int start, int end)
COMPLETE_WITH_CONST("(");
/* ALTER INDEX <foo> SET|RESET ( */
else if (Matches5("ALTER", "INDEX", MatchAny, "RESET", "("))
- COMPLETE_WITH_LIST3("fillfactor", "fastupdate",
- "gin_pending_list_limit");
+ COMPLETE_WITH_LIST4("fillfactor", "fastupdate",
+ "gin_pending_list_limit", "surjective");
else if (Matches5("ALTER", "INDEX", MatchAny, "SET", "("))
- COMPLETE_WITH_LIST3("fillfactor =", "fastupdate =",
- "gin_pending_list_limit =");
+ COMPLETE_WITH_LIST4("fillfactor =", "fastupdate =",
+ "gin_pending_list_limit =", "surjective = ");
/* ALTER LANGUAGE <name> */
else if (Matches3("ALTER", "LANGUAGE", MatchAny))
diff --git a/src/include/access/reloptions.h b/src/include/access/reloptions.h
index 91b2cd7..1fba0f0 100644
--- a/src/include/access/reloptions.h
+++ b/src/include/access/reloptions.h
@@ -51,6 +51,7 @@ typedef enum relopt_kind
RELOPT_KIND_PARTITIONED = (1 << 11),
/* if you add a new kind, make sure you update "last_default" too */
RELOPT_KIND_LAST_DEFAULT = RELOPT_KIND_PARTITIONED,
+ RELOPT_KIND_INDEX = RELOPT_KIND_BTREE|RELOPT_KIND_HASH|RELOPT_KIND_GIN|RELOPT_KIND_SPGIST,
/* some compilers treat enums as signed ints, so we can't use 1 << 31 */
RELOPT_KIND_MAX = (1 << 30)
} relopt_kind;
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index d33392f..f67c9f0 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -147,6 +147,7 @@ typedef struct IndexInfo
bool ii_ReadyForInserts;
bool ii_Concurrent;
bool ii_BrokenHotChain;
+ bool ii_Surjective;
void *ii_AmCache;
MemoryContext ii_Context;
} IndexInfo;
diff --git a/src/include/utils/rel.h b/src/include/utils/rel.h
index 8476896..147ba89 100644
--- a/src/include/utils/rel.h
+++ b/src/include/utils/rel.h
@@ -125,6 +125,8 @@ typedef struct RelationData
List *rd_fkeylist; /* list of ForeignKeyCacheInfo (see below) */
bool rd_fkeyvalid; /* true if list has been computed */
+ bool rd_surjective; /* relation contains functional index with surjective function */
+
MemoryContext rd_partkeycxt; /* private memory cxt for the below */
struct PartitionKeyData *rd_partkey; /* partition key, or NULL */
MemoryContext rd_pdcxt; /* private context for partdesc */
diff --git a/src/test/regress/expected/func_index.out b/src/test/regress/expected/func_index.out
new file mode 100644
index 0000000..c57a46a
--- /dev/null
+++ b/src/test/regress/expected/func_index.out
@@ -0,0 +1,29 @@
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (surjective=false);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (surjective=true);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+DEBUG: Use hot update
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+DEBUG: Use hot update
+set client_min_messages=notice;
+drop table keyvalue;
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name'));
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+DEBUG: Use hot update
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+DEBUG: Use hot update
+set client_min_messages=notice;
+drop table keyvalue;
diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule
index 1f8f098..06fd9aa 100644
--- a/src/test/regress/parallel_schedule
+++ b/src/test/regress/parallel_schedule
@@ -79,7 +79,7 @@ ignore: random
# ----------
# Another group of parallel tests
# ----------
-test: select_into select_distinct select_distinct_on select_implicit select_having subselect union case join aggregates transactions random portals arrays btree_index hash_index update namespace prepared_xacts delete
+test: select_into select_distinct select_distinct_on select_implicit select_having subselect union case join aggregates transactions random portals arrays btree_index hash_index func_index update namespace prepared_xacts delete
# ----------
# Another group of parallel tests
diff --git a/src/test/regress/serial_schedule b/src/test/regress/serial_schedule
index 04206c3..4f8b460 100644
--- a/src/test/regress/serial_schedule
+++ b/src/test/regress/serial_schedule
@@ -98,6 +98,7 @@ test: portals
test: arrays
test: btree_index
test: hash_index
+test: func_index
test: update
test: delete
test: namespace
diff --git a/src/test/regress/sql/func_index.sql b/src/test/regress/sql/func_index.sql
new file mode 100644
index 0000000..4923382
--- /dev/null
+++ b/src/test/regress/sql/func_index.sql
@@ -0,0 +1,29 @@
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (surjective=false);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (surjective=true);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name'));
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+
+
Konstantin Knizhnik <k.knizhnik@postgrespro.ru> 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
On 2017-05-25 12:37:40 -0400, Tom Lane wrote:
Konstantin Knizhnik <k.knizhnik@postgrespro.ru> 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
On 25.05.2017 19:37, Tom Lane wrote:
Konstantin Knizhnik <k.knizhnik@postgrespro.ru> 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
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
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: Konstantin Knizhnik 2017-05-29 <592BBD90.3060104@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
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]https://www.youtube.com/watch?v=npw4s1QTmPg 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
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
On 29.05.2017 20:21, Christoph Berg wrote:
I think the term you were looking for is "projection".
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: Konstantin Knizhnik 2017-05-30 <f97118e3-821c-10a8-85ec-0af3f1dfd01d@postgrespro.ru>
On 29.05.2017 20:21, Christoph Berg wrote:
I think the term you were looking for is "projection".
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
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
Attachments:
projection.patchtext/x-patch; name=projection.patchDownload
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 ] <replaceable class=
<para>
The optional <literal>WITH</> clause specifies <firstterm>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:
+ </para>
+
+ <variablelist>
+ <varlistentry>
+ <term><literal>projection</></term>
+ <listitem>
+ <para>
+ 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<literal>(bookinfo->>'isbn')</literal> 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.
+ </para>
+ </listitem>
+ </varlistentry>
+ </variablelist>
+
+ <para>
+ The B-tree, hash, GiST and SP-GiST index methods all accept this parameter:
</para>
<variablelist>
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
{
@@ -4199,6 +4205,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 */
@@ -4411,6 +4418,81 @@ heap_tuple_attr_equals(TupleDesc tupdesc, int attrnum,
}
/*
+ * For functional projection index compare new and old values of indexed expression.
+ * This function is used instead of comparison of modified attributes sets for non-injective functions.
+ */
+static bool ProjectionIsNotChanged(Relation relation, HeapTuple oldtup, HeapTuple newtup)
+{
+ ListCell *l;
+ List *indexoidlist = RelationGetIndexList(relation);
+ EState *estate = CreateExecutorState();
+ ExprContext *econtext = GetPerTupleExprContext(estate);
+ TupleTableSlot *slot = MakeSingleTupleTableSlot(RelationGetDescr(relation));
+ bool equals = true;
+ 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);
+ Relation indexDesc = index_open(indexOid, AccessShareLock);
+ IndexInfo *indexInfo = BuildIndexInfo(indexDesc);
+ int i;
+
+ if (indexInfo->ii_Projection)
+ {
+ 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])
+ {
+ equals = false;
+ break;
+ }
+ else if (!old_isnull[i])
+ {
+ Form_pg_attribute att = RelationGetDescr(indexDesc)->attrs[i];
+ if (!datumIsEqual(old_values[i], new_values[i], att->attbyval, att->attlen))
+ {
+ equals = false;
+ break;
+ }
+ }
+ }
+ }
+ index_close(indexDesc, AccessShareLock);
+
+ if (!equals)
+ {
+ break;
+ }
+ }
+ ExecDropSingleTupleTableSlot(slot);
+ FreeExecutorState(estate);
+
+ return equals;
+}
+
+
+/*
* Check which columns are being updated.
*
* Given an updated tuple, determine (and return into the output bitmapset),
@@ -4435,7 +4517,6 @@ HeapDetermineModifiedColumns(Relation relation, Bitmapset *interesting_cols,
modified = bms_add_member(modified,
attnum - FirstLowInvalidHeapAttributeNumber);
}
-
return modified;
}
diff --git a/src/backend/catalog/index.c b/src/backend/catalog/index.c
index dde8dd3..e06927a 100644
--- a/src/backend/catalog/index.c
+++ b/src/backend/catalog/index.c
@@ -26,6 +26,7 @@
#include "access/amapi.h"
#include "access/multixact.h"
#include "access/relscan.h"
+#include "access/reloptions.h"
#include "access/sysattr.h"
#include "access/transam.h"
#include "access/visibilitymap.h"
@@ -86,6 +87,13 @@ typedef struct
tups_inserted;
} v_i_state;
+/* options common to all indexes */
+typedef struct
+{
+ int32 vl_len_;
+ bool projection;
+} index_options;
+
/* non-export function prototypes */
static bool relationHasPrimaryKey(Relation rel);
static TupleDesc ConstructTupleDescriptor(Relation heapRelation,
@@ -1676,6 +1684,40 @@ BuildIndexInfo(Relation index)
ii->ii_ExclusionStrats = NULL;
}
+ if (ii->ii_Expressions)
+ {
+ HeapTuple tuple;
+ Datum reloptions;
+ bool isnull;
+
+ ii->ii_Projection = true; /* by default functional index is considered as non-injective */
+
+ tuple = SearchSysCache1(RELOID, ObjectIdGetDatum(RelationGetRelid(index)));
+ if (!HeapTupleIsValid(tuple))
+ elog(ERROR, "cache lookup failed for relation %u", RelationGetRelid(index));
+
+ reloptions = SysCacheGetAttr(RELOID, tuple,
+ Anum_pg_class_reloptions, &isnull);
+ if (!isnull)
+ {
+ static const relopt_parse_elt tab[] = {
+ {"projection", RELOPT_TYPE_BOOL, offsetof(index_options, projection)}
+ };
+ int numoptions;
+ relopt_value *options = parseRelOptions(reloptions, false,
+ RELOPT_KIND_INDEX,
+ &numoptions);
+ if (numoptions != 0)
+ {
+ index_options optstruct;
+ fillRelOptions((void *)&optstruct, sizeof(bool), options, numoptions, false, tab, lengthof(tab));
+ ii->ii_Projection = optstruct.projection;
+ pfree(options);
+ }
+ }
+ ReleaseSysCache(tuple);
+ }
+
/* other info */
ii->ii_Unique = indexStruct->indisunique;
ii->ii_ReadyForInserts = IndexIsReady(indexStruct);
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index c2e8361..4b85c4b 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -4854,6 +4854,7 @@ RelationGetIndexAttrBitmap(Relation relation, IndexAttrBitmapKind attrKind)
List *newindexoidlist;
Oid relpkindex;
Oid relreplindex;
+ bool projection = false;
ListCell *l;
MemoryContext oldcxt;
@@ -4963,9 +4964,15 @@ restart:
}
}
- /* Collect all attributes used in expressions, too */
- pull_varattnos((Node *) indexInfo->ii_Expressions, 1, &indexattrs);
-
+ if (indexInfo->ii_Projection)
+ {
+ projection = true;
+ }
+ else
+ {
+ /* Collect all attributes used in expressions, too */
+ pull_varattnos((Node *) indexInfo->ii_Expressions, 1, &indexattrs);
+ }
/* Collect all attributes in the index predicate, too */
pull_varattnos((Node *) indexInfo->ii_Predicate, 1, &indexattrs);
@@ -5010,6 +5017,8 @@ restart:
bms_free(relation->rd_idattr);
relation->rd_idattr = NULL;
+ relation->rd_projection = projection;
+
/*
* Now save copies of the bitmaps in the relcache entry. We intentionally
* set rd_indexattr last, because that's the one that signals validity of
diff --git a/src/bin/psql/tab-complete.c b/src/bin/psql/tab-complete.c
index d4b6976..8c1b2a6 100644
--- a/src/bin/psql/tab-complete.c
+++ b/src/bin/psql/tab-complete.c
@@ -1661,11 +1661,11 @@ psql_completion(const char *text, int start, int end)
COMPLETE_WITH_CONST("(");
/* ALTER INDEX <foo> SET|RESET ( */
else if (Matches5("ALTER", "INDEX", MatchAny, "RESET", "("))
- COMPLETE_WITH_LIST3("fillfactor", "fastupdate",
- "gin_pending_list_limit");
+ COMPLETE_WITH_LIST4("fillfactor", "fastupdate",
+ "gin_pending_list_limit", "projection");
else if (Matches5("ALTER", "INDEX", MatchAny, "SET", "("))
- COMPLETE_WITH_LIST3("fillfactor =", "fastupdate =",
- "gin_pending_list_limit =");
+ COMPLETE_WITH_LIST4("fillfactor =", "fastupdate =",
+ "gin_pending_list_limit =", "projection = ");
/* ALTER LANGUAGE <name> */
else if (Matches3("ALTER", "LANGUAGE", MatchAny))
diff --git a/src/include/access/reloptions.h b/src/include/access/reloptions.h
index 91b2cd7..1fba0f0 100644
--- a/src/include/access/reloptions.h
+++ b/src/include/access/reloptions.h
@@ -51,6 +51,7 @@ typedef enum relopt_kind
RELOPT_KIND_PARTITIONED = (1 << 11),
/* if you add a new kind, make sure you update "last_default" too */
RELOPT_KIND_LAST_DEFAULT = RELOPT_KIND_PARTITIONED,
+ RELOPT_KIND_INDEX = RELOPT_KIND_BTREE|RELOPT_KIND_HASH|RELOPT_KIND_GIN|RELOPT_KIND_SPGIST,
/* some compilers treat enums as signed ints, so we can't use 1 << 31 */
RELOPT_KIND_MAX = (1 << 30)
} relopt_kind;
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index d33392f..509dd2b 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -147,6 +147,7 @@ typedef struct IndexInfo
bool ii_ReadyForInserts;
bool ii_Concurrent;
bool ii_BrokenHotChain;
+ bool ii_Projection;
void *ii_AmCache;
MemoryContext ii_Context;
} IndexInfo;
diff --git a/src/include/utils/rel.h b/src/include/utils/rel.h
index 8476896..2c5ad7b 100644
--- a/src/include/utils/rel.h
+++ b/src/include/utils/rel.h
@@ -125,6 +125,8 @@ typedef struct RelationData
List *rd_fkeylist; /* list of ForeignKeyCacheInfo (see below) */
bool rd_fkeyvalid; /* true if list has been computed */
+ bool rd_projection; /* relation contains functional index with non-injective function */
+
MemoryContext rd_partkeycxt; /* private memory cxt for the below */
struct PartitionKeyData *rd_partkey; /* partition key, or NULL */
MemoryContext rd_pdcxt; /* private context for partdesc */
diff --git a/src/test/regress/expected/func_index.out b/src/test/regress/expected/func_index.out
new file mode 100644
index 0000000..06f0de9
--- /dev/null
+++ b/src/test/regress/expected/func_index.out
@@ -0,0 +1,29 @@
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (projection=false);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (projection=true);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+DEBUG: Use hot update
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+DEBUG: Use hot update
+set client_min_messages=notice;
+drop table keyvalue;
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name'));
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+DEBUG: Use hot update
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+DEBUG: Use hot update
+set client_min_messages=notice;
+drop table keyvalue;
diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule
index 1f8f098..06fd9aa 100644
--- a/src/test/regress/parallel_schedule
+++ b/src/test/regress/parallel_schedule
@@ -79,7 +79,7 @@ ignore: random
# ----------
# Another group of parallel tests
# ----------
-test: select_into select_distinct select_distinct_on select_implicit select_having subselect union case join aggregates transactions random portals arrays btree_index hash_index update namespace prepared_xacts delete
+test: select_into select_distinct select_distinct_on select_implicit select_having subselect union case join aggregates transactions random portals arrays btree_index hash_index func_index update namespace prepared_xacts delete
# ----------
# Another group of parallel tests
diff --git a/src/test/regress/serial_schedule b/src/test/regress/serial_schedule
index 04206c3..4f8b460 100644
--- a/src/test/regress/serial_schedule
+++ b/src/test/regress/serial_schedule
@@ -98,6 +98,7 @@ test: portals
test: arrays
test: btree_index
test: hash_index
+test: func_index
test: update
test: delete
test: namespace
diff --git a/src/test/regress/sql/func_index.sql b/src/test/regress/sql/func_index.sql
new file mode 100644
index 0000000..9540c07
--- /dev/null
+++ b/src/test/regress/sql/func_index.sql
@@ -0,0 +1,29 @@
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (projection=false);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (projection=true);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name'));
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+
+
On Fri, Jun 9, 2017 at 8:08 PM, Konstantin Knizhnik
<k.knizhnik@postgrespro.ru> 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
On 1 September 2017 at 05:40, Thomas Munro
<thomas.munro@enterprisedb.com> wrote:
On Fri, Jun 9, 2017 at 8:08 PM, Konstantin Knizhnik
<k.knizhnik@postgrespro.ru> 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 Riggs 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
On 01.09.2017 09:25, Simon Riggs wrote:
On 1 September 2017 at 05:40, Thomas Munro
<thomas.munro@enterprisedb.com> wrote:On Fri, Jun 9, 2017 at 8:08 PM, Konstantin Knizhnik
<k.knizhnik@postgrespro.ru> 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
Attachments:
projection.patchtext/x-patch; name=projection.patchDownload
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 ] <replaceable class=
<para>
The optional <literal>WITH</> clause specifies <firstterm>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:
+ </para>
+
+ <variablelist>
+ <varlistentry>
+ <term><literal>projection</></term>
+ <listitem>
+ <para>
+ 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<literal>(bookinfo->>'isbn')</literal> 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.
+ </para>
+ </listitem>
+ </varlistentry>
+ </variablelist>
+
+ <para>
+ The B-tree, hash, GiST and SP-GiST index methods all accept this parameter:
</para>
<variablelist>
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 = RelationGetIndexAttrBitmap(relation,
INDEX_ATTR_BITMAP_IDENTITY_KEY);
-
-
block = ItemPointerGetBlockNumber(otid);
buffer = ReadBuffer(relation, block);
page = BufferGetPage(buffer);
@@ -4176,8 +4178,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
{
@@ -4214,6 +4220,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 */
@@ -4426,6 +4433,81 @@ heap_tuple_attr_equals(TupleDesc tupdesc, int attrnum,
}
/*
+ * For functional projection index compare new and old values of indexed expression.
+ * This function is used instead of comparison of modified attributes sets for non-injective functions.
+ */
+static bool ProjectionIsNotChanged(Relation relation, HeapTuple oldtup, HeapTuple newtup)
+{
+ ListCell *l;
+ List *indexoidlist = RelationGetIndexList(relation);
+ EState *estate = CreateExecutorState();
+ ExprContext *econtext = GetPerTupleExprContext(estate);
+ TupleTableSlot *slot = MakeSingleTupleTableSlot(RelationGetDescr(relation));
+ bool equals = true;
+ 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);
+ Relation indexDesc = index_open(indexOid, AccessShareLock);
+ IndexInfo *indexInfo = BuildIndexInfo(indexDesc);
+ int i;
+
+ if (indexInfo->ii_Projection)
+ {
+ 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])
+ {
+ equals = false;
+ break;
+ }
+ else if (!old_isnull[i])
+ {
+ Form_pg_attribute att = TupleDescAttr(RelationGetDescr(indexDesc), i);
+ if (!datumIsEqual(old_values[i], new_values[i], att->attbyval, att->attlen))
+ {
+ equals = false;
+ break;
+ }
+ }
+ }
+ }
+ index_close(indexDesc, AccessShareLock);
+
+ if (!equals)
+ {
+ break;
+ }
+ }
+ ExecDropSingleTupleTableSlot(slot);
+ FreeExecutorState(estate);
+
+ return equals;
+}
+
+
+/*
* Check which columns are being updated.
*
* Given an updated tuple, determine (and return into the output bitmapset),
@@ -4450,7 +4532,6 @@ HeapDetermineModifiedColumns(Relation relation, Bitmapset *interesting_cols,
modified = bms_add_member(modified,
attnum - FirstLowInvalidHeapAttributeNumber);
}
-
return modified;
}
diff --git a/src/backend/catalog/index.c b/src/backend/catalog/index.c
index c7b2f03..64ca678 100644
--- a/src/backend/catalog/index.c
+++ b/src/backend/catalog/index.c
@@ -26,6 +26,7 @@
#include "access/amapi.h"
#include "access/multixact.h"
#include "access/relscan.h"
+#include "access/reloptions.h"
#include "access/sysattr.h"
#include "access/transam.h"
#include "access/visibilitymap.h"
@@ -86,6 +87,13 @@ typedef struct
tups_inserted;
} v_i_state;
+/* options common to all indexes */
+typedef struct
+{
+ int32 vl_len_;
+ bool projection;
+} index_options;
+
/* non-export function prototypes */
static bool relationHasPrimaryKey(Relation rel);
static TupleDesc ConstructTupleDescriptor(Relation heapRelation,
@@ -1678,6 +1686,40 @@ BuildIndexInfo(Relation index)
ii->ii_ExclusionStrats = NULL;
}
+ if (ii->ii_Expressions)
+ {
+ HeapTuple tuple;
+ Datum reloptions;
+ bool isnull;
+
+ ii->ii_Projection = true; /* by default functional index is considered as non-injective */
+
+ tuple = SearchSysCache1(RELOID, ObjectIdGetDatum(RelationGetRelid(index)));
+ if (!HeapTupleIsValid(tuple))
+ elog(ERROR, "cache lookup failed for relation %u", RelationGetRelid(index));
+
+ reloptions = SysCacheGetAttr(RELOID, tuple,
+ Anum_pg_class_reloptions, &isnull);
+ if (!isnull)
+ {
+ static const relopt_parse_elt tab[] = {
+ {"projection", RELOPT_TYPE_BOOL, offsetof(index_options, projection)}
+ };
+ int numoptions;
+ relopt_value *options = parseRelOptions(reloptions, false,
+ RELOPT_KIND_INDEX,
+ &numoptions);
+ if (numoptions != 0)
+ {
+ index_options optstruct;
+ fillRelOptions((void *)&optstruct, sizeof(bool), options, numoptions, false, tab, lengthof(tab));
+ ii->ii_Projection = optstruct.projection;
+ pfree(options);
+ }
+ }
+ ReleaseSysCache(tuple);
+ }
+
/* other info */
ii->ii_Unique = indexStruct->indisunique;
ii->ii_ReadyForInserts = IndexIsReady(indexStruct);
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index b8e3780..b89fdb3 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -4866,6 +4866,7 @@ RelationGetIndexAttrBitmap(Relation relation, IndexAttrBitmapKind attrKind)
List *newindexoidlist;
Oid relpkindex;
Oid relreplindex;
+ bool projection = false;
ListCell *l;
MemoryContext oldcxt;
@@ -4975,9 +4976,15 @@ restart:
}
}
- /* Collect all attributes used in expressions, too */
- pull_varattnos((Node *) indexInfo->ii_Expressions, 1, &indexattrs);
-
+ if (indexInfo->ii_Projection)
+ {
+ projection = true;
+ }
+ else
+ {
+ /* Collect all attributes used in expressions, too */
+ pull_varattnos((Node *) indexInfo->ii_Expressions, 1, &indexattrs);
+ }
/* Collect all attributes in the index predicate, too */
pull_varattnos((Node *) indexInfo->ii_Predicate, 1, &indexattrs);
@@ -5022,6 +5029,8 @@ restart:
bms_free(relation->rd_idattr);
relation->rd_idattr = NULL;
+ relation->rd_projection = projection;
+
/*
* Now save copies of the bitmaps in the relcache entry. We intentionally
* set rd_indexattr last, because that's the one that signals validity of
diff --git a/src/bin/psql/tab-complete.c b/src/bin/psql/tab-complete.c
index 1583cfa..91be7fa 100644
--- a/src/bin/psql/tab-complete.c
+++ b/src/bin/psql/tab-complete.c
@@ -1653,11 +1653,11 @@ psql_completion(const char *text, int start, int end)
COMPLETE_WITH_CONST("(");
/* ALTER INDEX <foo> SET|RESET ( */
else if (Matches5("ALTER", "INDEX", MatchAny, "RESET", "("))
- COMPLETE_WITH_LIST3("fillfactor", "fastupdate",
- "gin_pending_list_limit");
+ COMPLETE_WITH_LIST4("fillfactor", "fastupdate",
+ "gin_pending_list_limit", "projection");
else if (Matches5("ALTER", "INDEX", MatchAny, "SET", "("))
- COMPLETE_WITH_LIST3("fillfactor =", "fastupdate =",
- "gin_pending_list_limit =");
+ COMPLETE_WITH_LIST4("fillfactor =", "fastupdate =",
+ "gin_pending_list_limit =", "projection = ");
/* ALTER LANGUAGE <name> */
else if (Matches3("ALTER", "LANGUAGE", MatchAny))
diff --git a/src/include/access/reloptions.h b/src/include/access/reloptions.h
index 5cdaa3b..6015515 100644
--- a/src/include/access/reloptions.h
+++ b/src/include/access/reloptions.h
@@ -51,6 +51,7 @@ typedef enum relopt_kind
RELOPT_KIND_PARTITIONED = (1 << 11),
/* if you add a new kind, make sure you update "last_default" too */
RELOPT_KIND_LAST_DEFAULT = RELOPT_KIND_PARTITIONED,
+ RELOPT_KIND_INDEX = RELOPT_KIND_BTREE|RELOPT_KIND_HASH|RELOPT_KIND_GIN|RELOPT_KIND_SPGIST,
/* some compilers treat enums as signed ints, so we can't use 1 << 31 */
RELOPT_KIND_MAX = (1 << 30)
} relopt_kind;
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 90a60ab..061341f 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -147,6 +147,7 @@ typedef struct IndexInfo
bool ii_ReadyForInserts;
bool ii_Concurrent;
bool ii_BrokenHotChain;
+ bool ii_Projection;
void *ii_AmCache;
MemoryContext ii_Context;
} IndexInfo;
diff --git a/src/include/utils/rel.h b/src/include/utils/rel.h
index 4bc61e5..4e02fbe 100644
--- a/src/include/utils/rel.h
+++ b/src/include/utils/rel.h
@@ -125,6 +125,8 @@ typedef struct RelationData
List *rd_fkeylist; /* list of ForeignKeyCacheInfo (see below) */
bool rd_fkeyvalid; /* true if list has been computed */
+ bool rd_projection; /* relation contains functional index with non-injective function */
+
MemoryContext rd_partkeycxt; /* private memory cxt for the below */
struct PartitionKeyData *rd_partkey; /* partition key, or NULL */
MemoryContext rd_pdcxt; /* private context for partdesc */
diff --git a/src/test/regress/expected/func_index.out b/src/test/regress/expected/func_index.out
new file mode 100644
index 0000000..06f0de9
--- /dev/null
+++ b/src/test/regress/expected/func_index.out
@@ -0,0 +1,29 @@
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (projection=false);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (projection=true);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+DEBUG: Use hot update
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+DEBUG: Use hot update
+set client_min_messages=notice;
+drop table keyvalue;
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name'));
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+DEBUG: Use hot update
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+DEBUG: Use hot update
+set client_min_messages=notice;
+drop table keyvalue;
diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule
index 2fd3f2b..8f2cd16 100644
--- a/src/test/regress/parallel_schedule
+++ b/src/test/regress/parallel_schedule
@@ -79,7 +79,7 @@ ignore: random
# ----------
# Another group of parallel tests
# ----------
-test: select_into select_distinct select_distinct_on select_implicit select_having subselect union case join aggregates transactions random portals arrays btree_index hash_index update namespace prepared_xacts delete
+test: select_into select_distinct select_distinct_on select_implicit select_having subselect union case join aggregates transactions random portals arrays btree_index hash_index func_index update namespace prepared_xacts delete
# ----------
# Another group of parallel tests
diff --git a/src/test/regress/serial_schedule b/src/test/regress/serial_schedule
index 76b0de3..ebff4ae 100644
--- a/src/test/regress/serial_schedule
+++ b/src/test/regress/serial_schedule
@@ -99,6 +99,7 @@ test: portals
test: arrays
test: btree_index
test: hash_index
+test: func_index
test: update
test: delete
test: namespace
diff --git a/src/test/regress/sql/func_index.sql b/src/test/regress/sql/func_index.sql
new file mode 100644
index 0000000..9540c07
--- /dev/null
+++ b/src/test/regress/sql/func_index.sql
@@ -0,0 +1,29 @@
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (projection=false);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (projection=true);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name'));
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+
+
On 1 September 2017 at 09:47, Konstantin Knizhnik
<k.knizhnik@postgrespro.ru> wrote:
On 01.09.2017 09:25, Simon Riggs wrote:
On 1 September 2017 at 05:40, Thomas Munro
<thomas.munro@enterprisedb.com> wrote:On Fri, Jun 9, 2017 at 8:08 PM, Konstantin Knizhnik
<k.knizhnik@postgrespro.ru> 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 Riggs 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
On 12.09.2017 19:28, Simon Riggs wrote:
On 1 September 2017 at 09:47, Konstantin Knizhnik
<k.knizhnik@postgrespro.ru> wrote:On 01.09.2017 09:25, Simon Riggs wrote:
On 1 September 2017 at 05:40, Thomas Munro
<thomas.munro@enterprisedb.com> wrote:On Fri, Jun 9, 2017 at 8:08 PM, Konstantin Knizhnik
<k.knizhnik@postgrespro.ru> 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: Konstantin Knizhnik 2017-09-01 <f530ede0-1bf6-879c-c362-34325514f692@postgrespro.ru>
+ 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
On 13.09.2017 10:51, Christoph Berg wrote:
Re: Konstantin Knizhnik 2017-09-01 <f530ede0-1bf6-879c-c362-34325514f692@postgrespro.ru>
+ 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: Konstantin Knizhnik 2017-09-13 <2393c4b3-2ec4-dc68-4ea9-670597b561fe@postgrespro.ru>
On 13.09.2017 10:51, Christoph Berg wrote:
Re: Konstantin Knizhnik 2017-09-01 <f530ede0-1bf6-879c-c362-34325514f692@postgrespro.ru>
+ 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
On 13.09.2017 13:14, Christoph Berg wrote:
Re: Konstantin Knizhnik 2017-09-13 <2393c4b3-2ec4-dc68-4ea9-670597b561fe@postgrespro.ru>
On 13.09.2017 10:51, Christoph Berg wrote:
Re: Konstantin Knizhnik 2017-09-01 <f530ede0-1bf6-879c-c362-34325514f692@postgrespro.ru>
+ 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
On 13 September 2017 at 11:30, Konstantin Knizhnik
<k.knizhnik@postgrespro.ru> 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 Riggs 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
On 13.09.2017 14:00, Simon Riggs wrote:
On 13 September 2017 at 11:30, Konstantin Knizhnik
<k.knizhnik@postgrespro.ru> 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_updateYes, 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
On 13.09.2017 14:00, Simon Riggs wrote:
On 13 September 2017 at 11:30, Konstantin Knizhnik
<k.knizhnik@postgrespro.ru> 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_updateYes, 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
Attachments:
projection-autotune.patchtext/x-patch; name=projection-autotune.patchDownload
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 ] <replaceable class=
<para>
The optional <literal>WITH</> clause specifies <firstterm>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:
+ </para>
+
+ <variablelist>
+ <varlistentry>
+ <term><literal>projection</></term>
+ <listitem>
+ <para>
+ 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<literal>(bookinfo->>'isbn')</literal> 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.
+ </para>
+ </listitem>
+ </varlistentry>
+ </variablelist>
+
+ <para>
+ The B-tree, hash, GiST and SP-GiST index methods all accept this parameter:
</para>
<variablelist>
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 = RelationGetIndexAttrBitmap(relation,
INDEX_ATTR_BITMAP_IDENTITY_KEY);
-
-
block = ItemPointerGetBlockNumber(otid);
buffer = ReadBuffer(relation, block);
page = BufferGetPage(buffer);
@@ -4176,8 +4178,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
{
@@ -4214,6 +4220,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 */
@@ -4426,6 +4433,81 @@ heap_tuple_attr_equals(TupleDesc tupdesc, int attrnum,
}
/*
+ * For functional projection index compare new and old values of indexed expression.
+ * This function is used instead of comparison of modified attributes sets for non-injective functions.
+ */
+static bool ProjectionIsNotChanged(Relation relation, HeapTuple oldtup, HeapTuple newtup)
+{
+ ListCell *l;
+ List *indexoidlist = RelationGetIndexList(relation);
+ EState *estate = CreateExecutorState();
+ ExprContext *econtext = GetPerTupleExprContext(estate);
+ TupleTableSlot *slot = MakeSingleTupleTableSlot(RelationGetDescr(relation));
+ bool equals = true;
+ 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);
+ Relation indexDesc = index_open(indexOid, AccessShareLock);
+ IndexInfo *indexInfo = BuildIndexInfo(indexDesc);
+ int i;
+
+ if (indexInfo->ii_Projection)
+ {
+ 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])
+ {
+ equals = false;
+ break;
+ }
+ else if (!old_isnull[i])
+ {
+ Form_pg_attribute att = TupleDescAttr(RelationGetDescr(indexDesc), i);
+ if (!datumIsEqual(old_values[i], new_values[i], att->attbyval, att->attlen))
+ {
+ equals = false;
+ break;
+ }
+ }
+ }
+ }
+ index_close(indexDesc, AccessShareLock);
+
+ if (!equals)
+ {
+ break;
+ }
+ }
+ ExecDropSingleTupleTableSlot(slot);
+ FreeExecutorState(estate);
+
+ return equals;
+}
+
+
+/*
* Check which columns are being updated.
*
* Given an updated tuple, determine (and return into the output bitmapset),
@@ -4450,7 +4532,6 @@ HeapDetermineModifiedColumns(Relation relation, Bitmapset *interesting_cols,
modified = bms_add_member(modified,
attnum - FirstLowInvalidHeapAttributeNumber);
}
-
return modified;
}
diff --git a/src/backend/catalog/index.c b/src/backend/catalog/index.c
index c7b2f03..1bf44d2 100644
--- a/src/backend/catalog/index.c
+++ b/src/backend/catalog/index.c
@@ -26,6 +26,7 @@
#include "access/amapi.h"
#include "access/multixact.h"
#include "access/relscan.h"
+#include "access/reloptions.h"
#include "access/sysattr.h"
#include "access/transam.h"
#include "access/visibilitymap.h"
@@ -55,6 +56,7 @@
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
#include "parser/parser.h"
+#include "pgstat.h"
#include "storage/bufmgr.h"
#include "storage/lmgr.h"
#include "storage/predicate.h"
@@ -86,6 +88,13 @@ typedef struct
tups_inserted;
} v_i_state;
+/* options common to all indexes */
+typedef struct
+{
+ int32 vl_len_;
+ bool projection;
+} index_options;
+
/* non-export function prototypes */
static bool relationHasPrimaryKey(Relation rel);
static TupleDesc ConstructTupleDescriptor(Relation heapRelation,
@@ -1628,6 +1637,9 @@ index_drop(Oid indexId, bool concurrent)
* ----------------------------------------------------------------
*/
+#define MIN_UPDATES_THRESHOLD 10
+#define HOT_RATIO_THRESHOLD 2
+
/* ----------------
* BuildIndexInfo
* Construct an IndexInfo record for an open index
@@ -1678,6 +1690,50 @@ BuildIndexInfo(Relation index)
ii->ii_ExclusionStrats = NULL;
}
+ if (ii->ii_Expressions)
+ {
+ HeapTuple tuple;
+ Datum reloptions;
+ bool isnull;
+ PgStat_StatTabEntry* stat = pgstat_fetch_stat_tabentry(index->rd_index->indrelid);
+
+ ii->ii_Projection = true; /* by default functional index is considered as non-injective */
+
+ 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;
+ }
+
+ tuple = SearchSysCache1(RELOID, ObjectIdGetDatum(RelationGetRelid(index)));
+ if (!HeapTupleIsValid(tuple))
+ elog(ERROR, "cache lookup failed for relation %u", RelationGetRelid(index));
+
+ reloptions = SysCacheGetAttr(RELOID, tuple,
+ Anum_pg_class_reloptions, &isnull);
+ if (!isnull)
+ {
+ static const relopt_parse_elt tab[] = {
+ {"projection", RELOPT_TYPE_BOOL, offsetof(index_options, projection)}
+ };
+ int numoptions;
+ relopt_value *options = parseRelOptions(reloptions, false,
+ RELOPT_KIND_INDEX,
+ &numoptions);
+ if (numoptions != 0)
+ {
+ index_options optstruct;
+ fillRelOptions((void *)&optstruct, sizeof(bool), options, numoptions, false, tab, lengthof(tab));
+ ii->ii_Projection = optstruct.projection;
+ pfree(options);
+ }
+ }
+ ReleaseSysCache(tuple);
+ }
+
/* other info */
ii->ii_Unique = indexStruct->indisunique;
ii->ii_ReadyForInserts = IndexIsReady(indexStruct);
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index b8e3780..b89fdb3 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -4866,6 +4866,7 @@ RelationGetIndexAttrBitmap(Relation relation, IndexAttrBitmapKind attrKind)
List *newindexoidlist;
Oid relpkindex;
Oid relreplindex;
+ bool projection = false;
ListCell *l;
MemoryContext oldcxt;
@@ -4975,9 +4976,15 @@ restart:
}
}
- /* Collect all attributes used in expressions, too */
- pull_varattnos((Node *) indexInfo->ii_Expressions, 1, &indexattrs);
-
+ if (indexInfo->ii_Projection)
+ {
+ projection = true;
+ }
+ else
+ {
+ /* Collect all attributes used in expressions, too */
+ pull_varattnos((Node *) indexInfo->ii_Expressions, 1, &indexattrs);
+ }
/* Collect all attributes in the index predicate, too */
pull_varattnos((Node *) indexInfo->ii_Predicate, 1, &indexattrs);
@@ -5022,6 +5029,8 @@ restart:
bms_free(relation->rd_idattr);
relation->rd_idattr = NULL;
+ relation->rd_projection = projection;
+
/*
* Now save copies of the bitmaps in the relcache entry. We intentionally
* set rd_indexattr last, because that's the one that signals validity of
diff --git a/src/bin/psql/tab-complete.c b/src/bin/psql/tab-complete.c
index 1583cfa..91be7fa 100644
--- a/src/bin/psql/tab-complete.c
+++ b/src/bin/psql/tab-complete.c
@@ -1653,11 +1653,11 @@ psql_completion(const char *text, int start, int end)
COMPLETE_WITH_CONST("(");
/* ALTER INDEX <foo> SET|RESET ( */
else if (Matches5("ALTER", "INDEX", MatchAny, "RESET", "("))
- COMPLETE_WITH_LIST3("fillfactor", "fastupdate",
- "gin_pending_list_limit");
+ COMPLETE_WITH_LIST4("fillfactor", "fastupdate",
+ "gin_pending_list_limit", "projection");
else if (Matches5("ALTER", "INDEX", MatchAny, "SET", "("))
- COMPLETE_WITH_LIST3("fillfactor =", "fastupdate =",
- "gin_pending_list_limit =");
+ COMPLETE_WITH_LIST4("fillfactor =", "fastupdate =",
+ "gin_pending_list_limit =", "projection = ");
/* ALTER LANGUAGE <name> */
else if (Matches3("ALTER", "LANGUAGE", MatchAny))
diff --git a/src/include/access/reloptions.h b/src/include/access/reloptions.h
index 5cdaa3b..6015515 100644
--- a/src/include/access/reloptions.h
+++ b/src/include/access/reloptions.h
@@ -51,6 +51,7 @@ typedef enum relopt_kind
RELOPT_KIND_PARTITIONED = (1 << 11),
/* if you add a new kind, make sure you update "last_default" too */
RELOPT_KIND_LAST_DEFAULT = RELOPT_KIND_PARTITIONED,
+ RELOPT_KIND_INDEX = RELOPT_KIND_BTREE|RELOPT_KIND_HASH|RELOPT_KIND_GIN|RELOPT_KIND_SPGIST,
/* some compilers treat enums as signed ints, so we can't use 1 << 31 */
RELOPT_KIND_MAX = (1 << 30)
} relopt_kind;
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 90a60ab..061341f 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -147,6 +147,7 @@ typedef struct IndexInfo
bool ii_ReadyForInserts;
bool ii_Concurrent;
bool ii_BrokenHotChain;
+ bool ii_Projection;
void *ii_AmCache;
MemoryContext ii_Context;
} IndexInfo;
diff --git a/src/include/utils/rel.h b/src/include/utils/rel.h
index 4bc61e5..4e02fbe 100644
--- a/src/include/utils/rel.h
+++ b/src/include/utils/rel.h
@@ -125,6 +125,8 @@ typedef struct RelationData
List *rd_fkeylist; /* list of ForeignKeyCacheInfo (see below) */
bool rd_fkeyvalid; /* true if list has been computed */
+ bool rd_projection; /* relation contains functional index with non-injective function */
+
MemoryContext rd_partkeycxt; /* private memory cxt for the below */
struct PartitionKeyData *rd_partkey; /* partition key, or NULL */
MemoryContext rd_pdcxt; /* private context for partdesc */
diff --git a/src/test/regress/expected/func_index.out b/src/test/regress/expected/func_index.out
new file mode 100644
index 0000000..06f0de9
--- /dev/null
+++ b/src/test/regress/expected/func_index.out
@@ -0,0 +1,29 @@
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (projection=false);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (projection=true);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+DEBUG: Use hot update
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+DEBUG: Use hot update
+set client_min_messages=notice;
+drop table keyvalue;
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name'));
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+DEBUG: Use hot update
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+DEBUG: Use hot update
+set client_min_messages=notice;
+drop table keyvalue;
diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule
index 2fd3f2b..8f2cd16 100644
--- a/src/test/regress/parallel_schedule
+++ b/src/test/regress/parallel_schedule
@@ -79,7 +79,7 @@ ignore: random
# ----------
# Another group of parallel tests
# ----------
-test: select_into select_distinct select_distinct_on select_implicit select_having subselect union case join aggregates transactions random portals arrays btree_index hash_index update namespace prepared_xacts delete
+test: select_into select_distinct select_distinct_on select_implicit select_having subselect union case join aggregates transactions random portals arrays btree_index hash_index func_index update namespace prepared_xacts delete
# ----------
# Another group of parallel tests
diff --git a/src/test/regress/serial_schedule b/src/test/regress/serial_schedule
index 76b0de3..ebff4ae 100644
--- a/src/test/regress/serial_schedule
+++ b/src/test/regress/serial_schedule
@@ -99,6 +99,7 @@ test: portals
test: arrays
test: btree_index
test: hash_index
+test: func_index
test: update
test: delete
test: namespace
diff --git a/src/test/regress/sql/func_index.sql b/src/test/regress/sql/func_index.sql
new file mode 100644
index 0000000..9540c07
--- /dev/null
+++ b/src/test/regress/sql/func_index.sql
@@ -0,0 +1,29 @@
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (projection=false);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (projection=true);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name'));
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+
+
On 14 September 2017 at 10:42, Konstantin Knizhnik
<k.knizhnik@postgrespro.ru> wrote:
On 13.09.2017 14:00, Simon Riggs wrote:
On 13 September 2017 at 11:30, Konstantin Knizhnik
<k.knizhnik@postgrespro.ru> 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_updateYes, 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 2if (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 10000? 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 Riggs 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
On 14.09.2017 13:19, Simon Riggs wrote:
On 14 September 2017 at 10:42, Konstantin Knizhnik
<k.knizhnik@postgrespro.ru> wrote:On 13.09.2017 14:00, Simon Riggs wrote:
On 13 September 2017 at 11:30, Konstantin Knizhnik
<k.knizhnik@postgrespro.ru> 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_updateYes, 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 2if (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 10000? 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
Attachments:
projection-autotune2.patchtext/x-patch; name=projection-autotune2.patchDownload
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 ] <replaceable class=
<para>
The optional <literal>WITH</> clause specifies <firstterm>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:
+ </para>
+
+ <variablelist>
+ <varlistentry>
+ <term><literal>projection</></term>
+ <listitem>
+ <para>
+ 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<literal>(bookinfo->>'isbn')</literal> 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.
+ </para>
+ </listitem>
+ </varlistentry>
+ </variablelist>
+
+ <para>
+ The B-tree, hash, GiST and SP-GiST index methods all accept this parameter:
</para>
<variablelist>
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..f672c14 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 = RelationGetIndexAttrBitmap(relation,
INDEX_ATTR_BITMAP_IDENTITY_KEY);
-
-
block = ItemPointerGetBlockNumber(otid);
buffer = ReadBuffer(relation, block);
page = BufferGetPage(buffer);
@@ -4176,8 +4178,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
{
@@ -4214,6 +4220,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 */
@@ -4426,6 +4433,92 @@ heap_tuple_attr_equals(TupleDesc tupdesc, int attrnum,
}
/*
+ * For functional projection index compare new and old values of indexed expression.
+ * This function is used instead of comparison of modified attributes sets for non-injective functions.
+ */
+static bool ProjectionIsNotChanged(Relation relation, HeapTuple oldtup, HeapTuple newtup)
+{
+ ListCell *l;
+ List *indexoidlist = RelationGetIndexList(relation);
+ EState *estate = CreateExecutorState();
+ ExprContext *econtext = GetPerTupleExprContext(estate);
+ TupleTableSlot *slot = MakeSingleTupleTableSlot(RelationGetDescr(relation));
+ bool equals = true;
+ 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);
+ Relation indexDesc = index_open(indexOid, AccessShareLock);
+ IndexInfo *indexInfo = BuildIndexInfo(indexDesc);
+ int i;
+
+ if (indexInfo->ii_Projection)
+ {
+ 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])
+ {
+ equals = false;
+ break;
+ }
+ else if (!old_isnull[i])
+ {
+ Form_pg_attribute att = TupleDescAttr(RelationGetDescr(indexDesc), i);
+ if (!datumIsEqual(old_values[i], new_values[i], att->attbyval, att->attlen))
+ {
+ equals = false;
+ break;
+ }
+ }
+ }
+ }
+ index_close(indexDesc, AccessShareLock);
+
+ if (!equals)
+ {
+ break;
+ }
+ }
+ ExecDropSingleTupleTableSlot(slot);
+ FreeExecutorState(estate);
+
+ if (relation->pgstat_info)
+ {
+ if (equals)
+ {
+ relation->pgstat_info->t_counts.t_hot_update_hits += 1;
+ }
+ else
+ {
+ relation->pgstat_info->t_counts.t_hot_update_misses += 1;
+ }
+ }
+ return equals;
+}
+
+
+/*
* Check which columns are being updated.
*
* Given an updated tuple, determine (and return into the output bitmapset),
@@ -4450,7 +4543,6 @@ HeapDetermineModifiedColumns(Relation relation, Bitmapset *interesting_cols,
modified = bms_add_member(modified,
attnum - FirstLowInvalidHeapAttributeNumber);
}
-
return modified;
}
diff --git a/src/backend/catalog/index.c b/src/backend/catalog/index.c
index c7b2f03..280052a 100644
--- a/src/backend/catalog/index.c
+++ b/src/backend/catalog/index.c
@@ -26,6 +26,7 @@
#include "access/amapi.h"
#include "access/multixact.h"
#include "access/relscan.h"
+#include "access/reloptions.h"
#include "access/sysattr.h"
#include "access/transam.h"
#include "access/visibilitymap.h"
@@ -55,6 +56,7 @@
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
#include "parser/parser.h"
+#include "pgstat.h"
#include "storage/bufmgr.h"
#include "storage/lmgr.h"
#include "storage/predicate.h"
@@ -86,6 +88,13 @@ typedef struct
tups_inserted;
} v_i_state;
+/* options common to all indexes */
+typedef struct
+{
+ int32 vl_len_;
+ bool projection;
+} index_options;
+
/* non-export function prototypes */
static bool relationHasPrimaryKey(Relation rel);
static TupleDesc ConstructTupleDescriptor(Relation heapRelation,
@@ -1628,6 +1637,9 @@ index_drop(Oid indexId, bool concurrent)
* ----------------------------------------------------------------
*/
+#define MIN_UPDATES_THRESHOLD 10
+#define MIHOT_HITS_PERCENT 10
+
/* ----------------
* BuildIndexInfo
* Construct an IndexInfo record for an open index
@@ -1678,6 +1690,51 @@ BuildIndexInfo(Relation index)
ii->ii_ExclusionStrats = NULL;
}
+ if (ii->ii_Expressions)
+ {
+ HeapTuple tuple;
+ Datum reloptions;
+ bool isnull;
+ PgStat_StatTabEntry* stat = pgstat_fetch_stat_tabentry(index->rd_index->indrelid);
+
+ ii->ii_Projection = true; /* by default functional index is considered as non-injective */
+
+ if (stat != NULL
+ && stat->hot_update_hits + stat->hot_update_misses > MIN_UPDATES_THRESHOLD
+ && stat->hot_update_hits*100 / (stat->hot_update_hits + stat->hot_update_misses) < MIHOT_HITS_PERCENT)
+ {
+ /* 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;
+ }
+
+ tuple = SearchSysCache1(RELOID, ObjectIdGetDatum(RelationGetRelid(index)));
+ if (!HeapTupleIsValid(tuple))
+ elog(ERROR, "cache lookup failed for relation %u", RelationGetRelid(index));
+
+ reloptions = SysCacheGetAttr(RELOID, tuple,
+ Anum_pg_class_reloptions, &isnull);
+ if (!isnull)
+ {
+ static const relopt_parse_elt tab[] = {
+ {"projection", RELOPT_TYPE_BOOL, offsetof(index_options, projection)}
+ };
+ int numoptions;
+ relopt_value *options = parseRelOptions(reloptions, false,
+ RELOPT_KIND_INDEX,
+ &numoptions);
+ if (numoptions != 0)
+ {
+ index_options optstruct;
+ fillRelOptions((void *)&optstruct, sizeof(bool), options, numoptions, false, tab, lengthof(tab));
+ ii->ii_Projection = optstruct.projection;
+ pfree(options);
+ }
+ }
+ ReleaseSysCache(tuple);
+ }
+
/* other info */
ii->ii_Unique = indexStruct->indisunique;
ii->ii_ReadyForInserts = IndexIsReady(indexStruct);
diff --git a/src/backend/postmaster/pgstat.c b/src/backend/postmaster/pgstat.c
index 1f75e2e..66d4825 100644
--- a/src/backend/postmaster/pgstat.c
+++ b/src/backend/postmaster/pgstat.c
@@ -4571,6 +4571,8 @@ pgstat_get_tab_entry(PgStat_StatDBEntry *dbentry, Oid tableoid, bool create)
result->tuples_updated = 0;
result->tuples_deleted = 0;
result->tuples_hot_updated = 0;
+ result->hot_update_hits = 0;
+ result->hot_update_misses = 0;
result->n_live_tuples = 0;
result->n_dead_tuples = 0;
result->changes_since_analyze = 0;
@@ -5701,6 +5703,8 @@ pgstat_recv_tabstat(PgStat_MsgTabstat *msg, int len)
tabentry->tuples_updated = tabmsg->t_counts.t_tuples_updated;
tabentry->tuples_deleted = tabmsg->t_counts.t_tuples_deleted;
tabentry->tuples_hot_updated = tabmsg->t_counts.t_tuples_hot_updated;
+ tabentry->hot_update_hits = tabmsg->t_counts.t_hot_update_hits;
+ tabentry->hot_update_misses = tabmsg->t_counts.t_hot_update_misses;
tabentry->n_live_tuples = tabmsg->t_counts.t_delta_live_tuples;
tabentry->n_dead_tuples = tabmsg->t_counts.t_delta_dead_tuples;
tabentry->changes_since_analyze = tabmsg->t_counts.t_changed_tuples;
@@ -5728,6 +5732,8 @@ pgstat_recv_tabstat(PgStat_MsgTabstat *msg, int len)
tabentry->tuples_updated += tabmsg->t_counts.t_tuples_updated;
tabentry->tuples_deleted += tabmsg->t_counts.t_tuples_deleted;
tabentry->tuples_hot_updated += tabmsg->t_counts.t_tuples_hot_updated;
+ tabentry->hot_update_hits += tabmsg->t_counts.t_hot_update_hits;
+ tabentry->hot_update_misses += tabmsg->t_counts.t_hot_update_misses;
/* If table was truncated, first reset the live/dead counters */
if (tabmsg->t_counts.t_truncated)
{
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index b8e3780..b89fdb3 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -4866,6 +4866,7 @@ RelationGetIndexAttrBitmap(Relation relation, IndexAttrBitmapKind attrKind)
List *newindexoidlist;
Oid relpkindex;
Oid relreplindex;
+ bool projection = false;
ListCell *l;
MemoryContext oldcxt;
@@ -4975,9 +4976,15 @@ restart:
}
}
- /* Collect all attributes used in expressions, too */
- pull_varattnos((Node *) indexInfo->ii_Expressions, 1, &indexattrs);
-
+ if (indexInfo->ii_Projection)
+ {
+ projection = true;
+ }
+ else
+ {
+ /* Collect all attributes used in expressions, too */
+ pull_varattnos((Node *) indexInfo->ii_Expressions, 1, &indexattrs);
+ }
/* Collect all attributes in the index predicate, too */
pull_varattnos((Node *) indexInfo->ii_Predicate, 1, &indexattrs);
@@ -5022,6 +5029,8 @@ restart:
bms_free(relation->rd_idattr);
relation->rd_idattr = NULL;
+ relation->rd_projection = projection;
+
/*
* Now save copies of the bitmaps in the relcache entry. We intentionally
* set rd_indexattr last, because that's the one that signals validity of
diff --git a/src/bin/psql/tab-complete.c b/src/bin/psql/tab-complete.c
index 1583cfa..91be7fa 100644
--- a/src/bin/psql/tab-complete.c
+++ b/src/bin/psql/tab-complete.c
@@ -1653,11 +1653,11 @@ psql_completion(const char *text, int start, int end)
COMPLETE_WITH_CONST("(");
/* ALTER INDEX <foo> SET|RESET ( */
else if (Matches5("ALTER", "INDEX", MatchAny, "RESET", "("))
- COMPLETE_WITH_LIST3("fillfactor", "fastupdate",
- "gin_pending_list_limit");
+ COMPLETE_WITH_LIST4("fillfactor", "fastupdate",
+ "gin_pending_list_limit", "projection");
else if (Matches5("ALTER", "INDEX", MatchAny, "SET", "("))
- COMPLETE_WITH_LIST3("fillfactor =", "fastupdate =",
- "gin_pending_list_limit =");
+ COMPLETE_WITH_LIST4("fillfactor =", "fastupdate =",
+ "gin_pending_list_limit =", "projection = ");
/* ALTER LANGUAGE <name> */
else if (Matches3("ALTER", "LANGUAGE", MatchAny))
diff --git a/src/include/access/reloptions.h b/src/include/access/reloptions.h
index 5cdaa3b..6015515 100644
--- a/src/include/access/reloptions.h
+++ b/src/include/access/reloptions.h
@@ -51,6 +51,7 @@ typedef enum relopt_kind
RELOPT_KIND_PARTITIONED = (1 << 11),
/* if you add a new kind, make sure you update "last_default" too */
RELOPT_KIND_LAST_DEFAULT = RELOPT_KIND_PARTITIONED,
+ RELOPT_KIND_INDEX = RELOPT_KIND_BTREE|RELOPT_KIND_HASH|RELOPT_KIND_GIN|RELOPT_KIND_SPGIST,
/* some compilers treat enums as signed ints, so we can't use 1 << 31 */
RELOPT_KIND_MAX = (1 << 30)
} relopt_kind;
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 90a60ab..061341f 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -147,6 +147,7 @@ typedef struct IndexInfo
bool ii_ReadyForInserts;
bool ii_Concurrent;
bool ii_BrokenHotChain;
+ bool ii_Projection;
void *ii_AmCache;
MemoryContext ii_Context;
} IndexInfo;
diff --git a/src/include/pgstat.h b/src/include/pgstat.h
index cb05d9b..dc9bf3f 100644
--- a/src/include/pgstat.h
+++ b/src/include/pgstat.h
@@ -105,6 +105,8 @@ typedef struct PgStat_TableCounts
PgStat_Counter t_tuples_updated;
PgStat_Counter t_tuples_deleted;
PgStat_Counter t_tuples_hot_updated;
+ PgStat_Counter t_hot_update_hits;
+ PgStat_Counter t_hot_update_misses;
bool t_truncated;
PgStat_Counter t_delta_live_tuples;
@@ -566,7 +568,7 @@ typedef union PgStat_Msg
* ------------------------------------------------------------
*/
-#define PGSTAT_FILE_FORMAT_ID 0x01A5BC9D
+#define PGSTAT_FILE_FORMAT_ID 0x01A5BC9E
/* ----------
* PgStat_StatDBEntry The collector's data per database
@@ -626,6 +628,9 @@ typedef struct PgStat_StatTabEntry
PgStat_Counter tuples_deleted;
PgStat_Counter tuples_hot_updated;
+ PgStat_Counter hot_update_hits;
+ PgStat_Counter hot_update_misses;
+
PgStat_Counter n_live_tuples;
PgStat_Counter n_dead_tuples;
PgStat_Counter changes_since_analyze;
diff --git a/src/include/utils/rel.h b/src/include/utils/rel.h
index 4bc61e5..4e02fbe 100644
--- a/src/include/utils/rel.h
+++ b/src/include/utils/rel.h
@@ -125,6 +125,8 @@ typedef struct RelationData
List *rd_fkeylist; /* list of ForeignKeyCacheInfo (see below) */
bool rd_fkeyvalid; /* true if list has been computed */
+ bool rd_projection; /* relation contains functional index with non-injective function */
+
MemoryContext rd_partkeycxt; /* private memory cxt for the below */
struct PartitionKeyData *rd_partkey; /* partition key, or NULL */
MemoryContext rd_pdcxt; /* private context for partdesc */
diff --git a/src/test/regress/expected/func_index.out b/src/test/regress/expected/func_index.out
new file mode 100644
index 0000000..06f0de9
--- /dev/null
+++ b/src/test/regress/expected/func_index.out
@@ -0,0 +1,29 @@
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (projection=false);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (projection=true);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+DEBUG: Use hot update
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+DEBUG: Use hot update
+set client_min_messages=notice;
+drop table keyvalue;
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name'));
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+DEBUG: Use hot update
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+DEBUG: Use hot update
+set client_min_messages=notice;
+drop table keyvalue;
diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule
index 2fd3f2b..8f2cd16 100644
--- a/src/test/regress/parallel_schedule
+++ b/src/test/regress/parallel_schedule
@@ -79,7 +79,7 @@ ignore: random
# ----------
# Another group of parallel tests
# ----------
-test: select_into select_distinct select_distinct_on select_implicit select_having subselect union case join aggregates transactions random portals arrays btree_index hash_index update namespace prepared_xacts delete
+test: select_into select_distinct select_distinct_on select_implicit select_having subselect union case join aggregates transactions random portals arrays btree_index hash_index func_index update namespace prepared_xacts delete
# ----------
# Another group of parallel tests
diff --git a/src/test/regress/serial_schedule b/src/test/regress/serial_schedule
index 76b0de3..ebff4ae 100644
--- a/src/test/regress/serial_schedule
+++ b/src/test/regress/serial_schedule
@@ -99,6 +99,7 @@ test: portals
test: arrays
test: btree_index
test: hash_index
+test: func_index
test: update
test: delete
test: namespace
diff --git a/src/test/regress/sql/func_index.sql b/src/test/regress/sql/func_index.sql
new file mode 100644
index 0000000..9540c07
--- /dev/null
+++ b/src/test/regress/sql/func_index.sql
@@ -0,0 +1,29 @@
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (projection=false);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (projection=true);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name'));
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+
+
On 14 September 2017 at 16:37, Konstantin Knizhnik
<k.knizhnik@postgrespro.ru> 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 10000? 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 Riggs 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
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 10000? 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
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
Attachments:
projection-autotune3.patchtext/x-patch; name=projection-autotune3.patchDownload
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 ] <replaceable class=
<para>
The optional <literal>WITH</> clause specifies <firstterm>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:
+ </para>
+
+ <variablelist>
+ <varlistentry>
+ <term><literal>projection</></term>
+ <listitem>
+ <para>
+ 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<literal>(bookinfo->>'isbn')</literal> 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.
+ </para>
+ </listitem>
+ </varlistentry>
+ </variablelist>
+
+ <para>
+ The B-tree, hash, GiST and SP-GiST index methods all accept this parameter:
</para>
<variablelist>
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..2d735ef 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);
/*
@@ -3480,6 +3484,7 @@ heap_update(Relation relation, ItemPointer otid, HeapTuple newtup,
HTSU_Result result;
TransactionId xid = GetCurrentTransactionId();
Bitmapset *hot_attrs;
+ Bitmapset *warm_attrs;
Bitmapset *key_attrs;
Bitmapset *id_attrs;
Bitmapset *interesting_attrs;
@@ -3543,12 +3548,11 @@ heap_update(Relation relation, ItemPointer otid, HeapTuple newtup,
* Note that we get copies of each bitmap, so we need not worry about
* relcache flush happening midway through.
*/
- hot_attrs = RelationGetIndexAttrBitmap(relation, INDEX_ATTR_BITMAP_ALL);
+ hot_attrs = RelationGetIndexAttrBitmap(relation, INDEX_ATTR_BITMAP_HOT);
+ warm_attrs = RelationGetIndexAttrBitmap(relation, INDEX_ATTR_BITMAP_WARM);
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);
@@ -3568,6 +3572,7 @@ heap_update(Relation relation, ItemPointer otid, HeapTuple newtup,
if (!PageIsFull(page))
{
interesting_attrs = bms_add_members(interesting_attrs, hot_attrs);
+ interesting_attrs = bms_add_members(interesting_attrs, warm_attrs);
hot_attrs_checked = true;
}
interesting_attrs = bms_add_members(interesting_attrs, key_attrs);
@@ -3805,7 +3810,7 @@ l2:
* preserve it as locker.
*/
checked_lockers = true;
- locker_remains = true;
+ locker_remains = true;
can_continue = true;
}
else
@@ -3866,6 +3871,7 @@ l2:
if (vmbuffer != InvalidBuffer)
ReleaseBuffer(vmbuffer);
bms_free(hot_attrs);
+ bms_free(warm_attrs);
bms_free(key_attrs);
bms_free(id_attrs);
bms_free(modified_attrs);
@@ -4176,8 +4182,13 @@ 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)
+ && (!bms_overlap(modified_attrs, warm_attrs)
+ || ProjectionIsNotChanged(relation, &oldtup, newtup)))
+ {
use_hot_update = true;
+ }
}
else
{
@@ -4214,6 +4225,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 */
@@ -4339,6 +4351,7 @@ l2:
heap_freetuple(old_key_tuple);
bms_free(hot_attrs);
+ bms_free(warm_attrs);
bms_free(key_attrs);
bms_free(id_attrs);
bms_free(modified_attrs);
@@ -4426,6 +4439,93 @@ heap_tuple_attr_equals(TupleDesc tupdesc, int attrnum,
}
/*
+ * For functional projection index compare new and old values of indexed expression.
+ * This function is used instead of comparison of modified attributes sets for non-injective functions.
+ */
+static bool ProjectionIsNotChanged(Relation relation, HeapTuple oldtup, HeapTuple newtup)
+{
+ ListCell *l;
+ List *indexoidlist = RelationGetIndexList(relation);
+ EState *estate = CreateExecutorState();
+ ExprContext *econtext = GetPerTupleExprContext(estate);
+ TupleTableSlot *slot = MakeSingleTupleTableSlot(RelationGetDescr(relation));
+ bool equals = true;
+ Datum old_values[INDEX_MAX_KEYS];
+ bool old_isnull[INDEX_MAX_KEYS];
+ Datum new_values[INDEX_MAX_KEYS];
+ bool new_isnull[INDEX_MAX_KEYS];
+ int indexno = 0;
+ econtext->ecxt_scantuple = slot;
+
+ foreach(l, indexoidlist)
+ {
+ if (bms_is_member(indexno, relation->rd_projidx))
+ {
+ Oid indexOid = lfirst_oid(l);
+ Relation indexDesc = index_open(indexOid, AccessShareLock);
+ IndexInfo *indexInfo = BuildIndexInfo(indexDesc);
+ int i;
+
+ 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])
+ {
+ equals = false;
+ break;
+ }
+ else if (!old_isnull[i])
+ {
+ Form_pg_attribute att = TupleDescAttr(RelationGetDescr(indexDesc), i);
+ if (!datumIsEqual(old_values[i], new_values[i], att->attbyval, att->attlen))
+ {
+ equals = false;
+ break;
+ }
+ }
+ }
+ index_close(indexDesc, AccessShareLock);
+
+ if (!equals)
+ {
+ break;
+ }
+ }
+ indexno += 1;
+ }
+ ExecDropSingleTupleTableSlot(slot);
+ FreeExecutorState(estate);
+
+ if (relation->pgstat_info)
+ {
+ if (equals)
+ {
+ relation->pgstat_info->t_counts.t_hot_update_hits += 1;
+ }
+ else
+ {
+ relation->pgstat_info->t_counts.t_hot_update_misses += 1;
+ }
+ }
+ return equals;
+}
+
+
+/*
* Check which columns are being updated.
*
* Given an updated tuple, determine (and return into the output bitmapset),
@@ -4450,7 +4550,6 @@ HeapDetermineModifiedColumns(Relation relation, Bitmapset *interesting_cols,
modified = bms_add_member(modified,
attnum - FirstLowInvalidHeapAttributeNumber);
}
-
return modified;
}
diff --git a/src/backend/catalog/index.c b/src/backend/catalog/index.c
index c7b2f03..359a92f 100644
--- a/src/backend/catalog/index.c
+++ b/src/backend/catalog/index.c
@@ -26,6 +26,7 @@
#include "access/amapi.h"
#include "access/multixact.h"
#include "access/relscan.h"
+#include "access/reloptions.h"
#include "access/sysattr.h"
#include "access/transam.h"
#include "access/visibilitymap.h"
@@ -3562,7 +3563,7 @@ reindex_relation(Oid relid, int flags, int options)
/* Ensure rd_indexattr is valid; see comments for RelationSetIndexList */
if (is_pg_class)
- (void) RelationGetIndexAttrBitmap(rel, INDEX_ATTR_BITMAP_ALL);
+ (void) RelationGetIndexAttrBitmap(rel, INDEX_ATTR_BITMAP_HOT);
PG_TRY();
{
diff --git a/src/backend/postmaster/pgstat.c b/src/backend/postmaster/pgstat.c
index 1f75e2e..66d4825 100644
--- a/src/backend/postmaster/pgstat.c
+++ b/src/backend/postmaster/pgstat.c
@@ -4571,6 +4571,8 @@ pgstat_get_tab_entry(PgStat_StatDBEntry *dbentry, Oid tableoid, bool create)
result->tuples_updated = 0;
result->tuples_deleted = 0;
result->tuples_hot_updated = 0;
+ result->hot_update_hits = 0;
+ result->hot_update_misses = 0;
result->n_live_tuples = 0;
result->n_dead_tuples = 0;
result->changes_since_analyze = 0;
@@ -5701,6 +5703,8 @@ pgstat_recv_tabstat(PgStat_MsgTabstat *msg, int len)
tabentry->tuples_updated = tabmsg->t_counts.t_tuples_updated;
tabentry->tuples_deleted = tabmsg->t_counts.t_tuples_deleted;
tabentry->tuples_hot_updated = tabmsg->t_counts.t_tuples_hot_updated;
+ tabentry->hot_update_hits = tabmsg->t_counts.t_hot_update_hits;
+ tabentry->hot_update_misses = tabmsg->t_counts.t_hot_update_misses;
tabentry->n_live_tuples = tabmsg->t_counts.t_delta_live_tuples;
tabentry->n_dead_tuples = tabmsg->t_counts.t_delta_dead_tuples;
tabentry->changes_since_analyze = tabmsg->t_counts.t_changed_tuples;
@@ -5728,6 +5732,8 @@ pgstat_recv_tabstat(PgStat_MsgTabstat *msg, int len)
tabentry->tuples_updated += tabmsg->t_counts.t_tuples_updated;
tabentry->tuples_deleted += tabmsg->t_counts.t_tuples_deleted;
tabentry->tuples_hot_updated += tabmsg->t_counts.t_tuples_hot_updated;
+ tabentry->hot_update_hits += tabmsg->t_counts.t_hot_update_hits;
+ tabentry->hot_update_misses += tabmsg->t_counts.t_hot_update_misses;
/* If table was truncated, first reset the live/dead counters */
if (tabmsg->t_counts.t_truncated)
{
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index b8e3780..a8e5f33 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -68,8 +68,10 @@
#include "miscadmin.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
+#include "optimizer/cost.h"
#include "optimizer/prep.h"
#include "optimizer/var.h"
+#include "pgstat.h"
#include "rewrite/rewriteDefine.h"
#include "rewrite/rowsecurity.h"
#include "storage/lmgr.h"
@@ -2346,10 +2348,12 @@ RelationDestroyRelation(Relation relation, bool remember_tupdesc)
FreeTriggerDesc(relation->trigdesc);
list_free_deep(relation->rd_fkeylist);
list_free(relation->rd_indexlist);
- bms_free(relation->rd_indexattr);
+ bms_free(relation->rd_hotattr);
+ bms_free(relation->rd_warmattr);
bms_free(relation->rd_keyattr);
bms_free(relation->rd_pkattr);
bms_free(relation->rd_idattr);
+ bms_free(relation->rd_projidx);
if (relation->rd_pubactions)
pfree(relation->rd_pubactions);
if (relation->rd_options)
@@ -4596,12 +4600,12 @@ insert_ordered_oid(List *list, Oid datum)
*
* It is up to the caller to make sure the given list is correctly ordered.
*
- * We deliberately do not change rd_indexattr here: even when operating
+ * We deliberately do not change rd_hotattr here: even when operating
* with a temporary partial index list, HOT-update decisions must be made
* correctly with respect to the full index set. It is up to the caller
- * to ensure that a correct rd_indexattr set has been cached before first
+ * to ensure that a correct rd_hotattr set has been cached before first
* calling RelationSetIndexList; else a subsequent inquiry might cause a
- * wrong rd_indexattr set to get computed and cached. Likewise, we do not
+ * wrong rd_hotattr set to get computed and cached. Likewise, we do not
* touch rd_keyattr, rd_pkattr or rd_idattr.
*/
void
@@ -4831,6 +4835,97 @@ RelationGetIndexPredicate(Relation relation)
return result;
}
+#define MIN_UPDATES_THRESHOLD 10
+#define MIN_HOT_HITS_PERCENT 10
+#define MAX_HOT_INDEX_EXPR_COST 1000
+
+/* options common to all indexes */
+typedef struct
+{
+ int32 vl_len_;
+ bool projection;
+} index_options;
+
+/*
+ * Check if functional index is projection: index expression returns some subset of
+ * its argument values. During hot update check projection indexes are handled in special way:
+ * instead of checking if any of attributes used in indexed expression was updated,
+ * we should calculate and compare values of index expression for old and new tuple values.
+ *
+ * Decision made by this function 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)
+ */
+static bool IsProjectionFunctionalIndex(Relation index, IndexInfo* ii)
+{
+ bool is_projection = false;
+
+ if (ii->ii_Expressions)
+ {
+ HeapTuple tuple;
+ Datum reloptions;
+ bool isnull;
+ PgStat_StatTabEntry* stat = pgstat_fetch_stat_tabentry(index->rd_index->indrelid);
+
+ is_projection = true; /* by default functional index is considered as non-injective */
+
+ if (stat != NULL
+ && stat->hot_update_hits + stat->hot_update_misses > MIN_UPDATES_THRESHOLD
+ && stat->hot_update_hits*100 / (stat->hot_update_hits + stat->hot_update_misses) < MIN_HOT_HITS_PERCENT)
+ {
+ /* If percent of hot updates is small, then disable projection index function
+ * optimization to eliminate overhead of extra index expression evaluations.
+ */
+ is_projection = false;
+ }
+ else
+ {
+ QualCost index_expr_cost;
+ cost_qual_eval(&index_expr_cost, ii->ii_Expressions, NULL);
+ /*
+ * If index expression is too expensive, then disable projection optimization, because
+ * extra evaluation of index expression is expected to be more expensive than index update.
+ * Current implementation of projection optimization has to calculate index expression twice
+ * in case of hit (value of index expression is not changed) and three times if values are different.
+ */
+ if (index_expr_cost.startup + index_expr_cost.per_tuple > MAX_HOT_INDEX_EXPR_COST)
+ {
+ is_projection = false;
+ }
+ }
+ tuple = SearchSysCache1(RELOID, ObjectIdGetDatum(RelationGetRelid(index)));
+ if (!HeapTupleIsValid(tuple))
+ elog(ERROR, "cache lookup failed for relation %u", RelationGetRelid(index));
+
+ reloptions = SysCacheGetAttr(RELOID, tuple,
+ Anum_pg_class_reloptions, &isnull);
+ if (!isnull)
+ {
+ static const relopt_parse_elt tab[] = {
+ {"projection", RELOPT_TYPE_BOOL, offsetof(index_options, projection)}
+ };
+ int numoptions;
+ relopt_value *options = parseRelOptions(reloptions, false,
+ RELOPT_KIND_INDEX,
+ &numoptions);
+ if (numoptions != 0)
+ {
+ index_options optstruct;
+ fillRelOptions((void *)&optstruct, sizeof(bool), options, numoptions, false, tab, lengthof(tab));
+ is_projection = optstruct.projection;
+ pfree(options);
+ }
+ }
+ ReleaseSysCache(tuple);
+ }
+ return is_projection;
+}
+
/*
* RelationGetIndexAttrBitmap -- get a bitmap of index attribute numbers
*
@@ -4858,24 +4953,29 @@ RelationGetIndexPredicate(Relation relation)
Bitmapset *
RelationGetIndexAttrBitmap(Relation relation, IndexAttrBitmapKind attrKind)
{
- Bitmapset *indexattrs; /* indexed columns */
+ Bitmapset *hotattrs; /* identifies columns used in non-projection indexes */
+ Bitmapset *warmattrs; /* identifies columns used in projection indexes */
Bitmapset *uindexattrs; /* columns in unique indexes */
Bitmapset *pkindexattrs; /* columns in the primary index */
Bitmapset *idindexattrs; /* columns in the replica identity */
+ Bitmapset *projindexes; /* projection indexes */
List *indexoidlist;
List *newindexoidlist;
Oid relpkindex;
Oid relreplindex;
ListCell *l;
MemoryContext oldcxt;
+ int indexno;
/* Quick exit if we already computed the result. */
- if (relation->rd_indexattr != NULL)
+ if (relation->rd_hotattr != NULL)
{
switch (attrKind)
{
- case INDEX_ATTR_BITMAP_ALL:
- return bms_copy(relation->rd_indexattr);
+ case INDEX_ATTR_BITMAP_HOT:
+ return bms_copy(relation->rd_hotattr);
+ case INDEX_ATTR_BITMAP_WARM:
+ return bms_copy(relation->rd_warmattr);
case INDEX_ATTR_BITMAP_KEY:
return bms_copy(relation->rd_keyattr);
case INDEX_ATTR_BITMAP_PRIMARY_KEY:
@@ -4912,7 +5012,7 @@ restart:
relreplindex = relation->rd_replidindex;
/*
- * For each index, add referenced attributes to indexattrs.
+ * For each index, add referenced attributes to hotattrs.
*
* Note: we consider all indexes returned by RelationGetIndexList, even if
* they are not indisready or indisvalid. This is important because an
@@ -4921,10 +5021,13 @@ restart:
* CONCURRENTLY is far enough along that we should ignore the index, it
* won't be returned at all by RelationGetIndexList.
*/
- indexattrs = NULL;
+ hotattrs = NULL;
+ warmattrs = NULL;
uindexattrs = NULL;
pkindexattrs = NULL;
idindexattrs = NULL;
+ projindexes = NULL;
+ indexno = 0;
foreach(l, indexoidlist)
{
Oid indexOid = lfirst_oid(l);
@@ -4958,8 +5061,8 @@ restart:
if (attrnum != 0)
{
- indexattrs = bms_add_member(indexattrs,
- attrnum - FirstLowInvalidHeapAttributeNumber);
+ hotattrs = bms_add_member(hotattrs,
+ attrnum - FirstLowInvalidHeapAttributeNumber);
if (isKey)
uindexattrs = bms_add_member(uindexattrs,
@@ -4975,13 +5078,21 @@ restart:
}
}
- /* Collect all attributes used in expressions, too */
- pull_varattnos((Node *) indexInfo->ii_Expressions, 1, &indexattrs);
-
+ if (IsProjectionFunctionalIndex(indexDesc, indexInfo))
+ {
+ projindexes = bms_add_member(projindexes, indexno);
+ pull_varattnos((Node *) indexInfo->ii_Expressions, 1, &warmattrs);
+ }
+ else
+ {
+ /* Collect all attributes used in expressions, too */
+ pull_varattnos((Node *) indexInfo->ii_Expressions, 1, &hotattrs);
+ }
/* Collect all attributes in the index predicate, too */
- pull_varattnos((Node *) indexInfo->ii_Predicate, 1, &indexattrs);
+ pull_varattnos((Node *) indexInfo->ii_Predicate, 1, &hotattrs);
index_close(indexDesc, AccessShareLock);
+ indexno += 1;
}
/*
@@ -5007,24 +5118,30 @@ restart:
bms_free(uindexattrs);
bms_free(pkindexattrs);
bms_free(idindexattrs);
- bms_free(indexattrs);
+ bms_free(hotattrs);
+ bms_free(warmattrs);
+ bms_free(projindexes);
goto restart;
}
/* Don't leak the old values of these bitmaps, if any */
- bms_free(relation->rd_indexattr);
- relation->rd_indexattr = NULL;
+ bms_free(relation->rd_hotattr);
+ relation->rd_hotattr = NULL;
+ bms_free(relation->rd_warmattr);
+ relation->rd_warmattr = NULL;
bms_free(relation->rd_keyattr);
relation->rd_keyattr = NULL;
bms_free(relation->rd_pkattr);
relation->rd_pkattr = NULL;
bms_free(relation->rd_idattr);
relation->rd_idattr = NULL;
+ bms_free(relation->rd_projidx);
+ relation->rd_projidx = NULL;
/*
* Now save copies of the bitmaps in the relcache entry. We intentionally
- * set rd_indexattr last, because that's the one that signals validity of
+ * set rd_hotattr last, because that's the one that signals validity of
* the values; if we run out of memory before making that copy, we won't
* leave the relcache entry looking like the other ones are valid but
* empty.
@@ -5033,14 +5150,18 @@ restart:
relation->rd_keyattr = bms_copy(uindexattrs);
relation->rd_pkattr = bms_copy(pkindexattrs);
relation->rd_idattr = bms_copy(idindexattrs);
- relation->rd_indexattr = bms_copy(indexattrs);
+ relation->rd_hotattr = bms_copy(hotattrs);
+ relation->rd_warmattr = bms_copy(warmattrs);
+ relation->rd_projidx = bms_copy(projindexes);
MemoryContextSwitchTo(oldcxt);
/* We return our original working copy for caller to play with */
switch (attrKind)
{
- case INDEX_ATTR_BITMAP_ALL:
- return indexattrs;
+ case INDEX_ATTR_BITMAP_HOT:
+ return hotattrs;
+ case INDEX_ATTR_BITMAP_WARM:
+ return warmattrs;
case INDEX_ATTR_BITMAP_KEY:
return uindexattrs;
case INDEX_ATTR_BITMAP_PRIMARY_KEY:
@@ -5658,10 +5779,12 @@ load_relcache_init_file(bool shared)
rel->rd_oidindex = InvalidOid;
rel->rd_pkindex = InvalidOid;
rel->rd_replidindex = InvalidOid;
- rel->rd_indexattr = NULL;
+ rel->rd_hotattr = NULL;
+ rel->rd_warmattr = NULL;
rel->rd_keyattr = NULL;
rel->rd_pkattr = NULL;
rel->rd_idattr = NULL;
+ rel->rd_projidx = NULL;
rel->rd_pubactions = NULL;
rel->rd_statvalid = false;
rel->rd_statlist = NIL;
diff --git a/src/bin/psql/tab-complete.c b/src/bin/psql/tab-complete.c
index 1583cfa..91be7fa 100644
--- a/src/bin/psql/tab-complete.c
+++ b/src/bin/psql/tab-complete.c
@@ -1653,11 +1653,11 @@ psql_completion(const char *text, int start, int end)
COMPLETE_WITH_CONST("(");
/* ALTER INDEX <foo> SET|RESET ( */
else if (Matches5("ALTER", "INDEX", MatchAny, "RESET", "("))
- COMPLETE_WITH_LIST3("fillfactor", "fastupdate",
- "gin_pending_list_limit");
+ COMPLETE_WITH_LIST4("fillfactor", "fastupdate",
+ "gin_pending_list_limit", "projection");
else if (Matches5("ALTER", "INDEX", MatchAny, "SET", "("))
- COMPLETE_WITH_LIST3("fillfactor =", "fastupdate =",
- "gin_pending_list_limit =");
+ COMPLETE_WITH_LIST4("fillfactor =", "fastupdate =",
+ "gin_pending_list_limit =", "projection = ");
/* ALTER LANGUAGE <name> */
else if (Matches3("ALTER", "LANGUAGE", MatchAny))
diff --git a/src/include/access/reloptions.h b/src/include/access/reloptions.h
index 5cdaa3b..6015515 100644
--- a/src/include/access/reloptions.h
+++ b/src/include/access/reloptions.h
@@ -51,6 +51,7 @@ typedef enum relopt_kind
RELOPT_KIND_PARTITIONED = (1 << 11),
/* if you add a new kind, make sure you update "last_default" too */
RELOPT_KIND_LAST_DEFAULT = RELOPT_KIND_PARTITIONED,
+ RELOPT_KIND_INDEX = RELOPT_KIND_BTREE|RELOPT_KIND_HASH|RELOPT_KIND_GIN|RELOPT_KIND_SPGIST,
/* some compilers treat enums as signed ints, so we can't use 1 << 31 */
RELOPT_KIND_MAX = (1 << 30)
} relopt_kind;
diff --git a/src/include/pgstat.h b/src/include/pgstat.h
index cb05d9b..dc9bf3f 100644
--- a/src/include/pgstat.h
+++ b/src/include/pgstat.h
@@ -105,6 +105,8 @@ typedef struct PgStat_TableCounts
PgStat_Counter t_tuples_updated;
PgStat_Counter t_tuples_deleted;
PgStat_Counter t_tuples_hot_updated;
+ PgStat_Counter t_hot_update_hits;
+ PgStat_Counter t_hot_update_misses;
bool t_truncated;
PgStat_Counter t_delta_live_tuples;
@@ -566,7 +568,7 @@ typedef union PgStat_Msg
* ------------------------------------------------------------
*/
-#define PGSTAT_FILE_FORMAT_ID 0x01A5BC9D
+#define PGSTAT_FILE_FORMAT_ID 0x01A5BC9E
/* ----------
* PgStat_StatDBEntry The collector's data per database
@@ -626,6 +628,9 @@ typedef struct PgStat_StatTabEntry
PgStat_Counter tuples_deleted;
PgStat_Counter tuples_hot_updated;
+ PgStat_Counter hot_update_hits;
+ PgStat_Counter hot_update_misses;
+
PgStat_Counter n_live_tuples;
PgStat_Counter n_dead_tuples;
PgStat_Counter changes_since_analyze;
diff --git a/src/include/utils/rel.h b/src/include/utils/rel.h
index 4bc61e5..3427ec1 100644
--- a/src/include/utils/rel.h
+++ b/src/include/utils/rel.h
@@ -141,10 +141,12 @@ typedef struct RelationData
List *rd_statlist; /* list of OIDs of extended stats */
/* data managed by RelationGetIndexAttrBitmap: */
- Bitmapset *rd_indexattr; /* identifies columns used in indexes */
+ Bitmapset *rd_hotattr; /* identifies columns used in non-projection indexes */
+ Bitmapset *rd_warmattr; /* identifies columns used in projection indexes */
Bitmapset *rd_keyattr; /* cols that can be ref'd by foreign keys */
Bitmapset *rd_pkattr; /* cols included in primary key */
Bitmapset *rd_idattr; /* included in replica identity index */
+ Bitmapset *rd_projidx; /* projection indexes */
PublicationActions *rd_pubactions; /* publication actions */
diff --git a/src/include/utils/relcache.h b/src/include/utils/relcache.h
index 3c53cef..4d03c19 100644
--- a/src/include/utils/relcache.h
+++ b/src/include/utils/relcache.h
@@ -48,7 +48,8 @@ extern List *RelationGetIndexPredicate(Relation relation);
typedef enum IndexAttrBitmapKind
{
- INDEX_ATTR_BITMAP_ALL,
+ INDEX_ATTR_BITMAP_HOT,
+ INDEX_ATTR_BITMAP_WARM,
INDEX_ATTR_BITMAP_KEY,
INDEX_ATTR_BITMAP_PRIMARY_KEY,
INDEX_ATTR_BITMAP_IDENTITY_KEY
diff --git a/src/test/regress/expected/func_index.out b/src/test/regress/expected/func_index.out
new file mode 100644
index 0000000..06f0de9
--- /dev/null
+++ b/src/test/regress/expected/func_index.out
@@ -0,0 +1,29 @@
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (projection=false);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (projection=true);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+DEBUG: Use hot update
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+DEBUG: Use hot update
+set client_min_messages=notice;
+drop table keyvalue;
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name'));
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+DEBUG: Use hot update
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+DEBUG: Use hot update
+set client_min_messages=notice;
+drop table keyvalue;
diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule
index 2fd3f2b..8f2cd16 100644
--- a/src/test/regress/parallel_schedule
+++ b/src/test/regress/parallel_schedule
@@ -79,7 +79,7 @@ ignore: random
# ----------
# Another group of parallel tests
# ----------
-test: select_into select_distinct select_distinct_on select_implicit select_having subselect union case join aggregates transactions random portals arrays btree_index hash_index update namespace prepared_xacts delete
+test: select_into select_distinct select_distinct_on select_implicit select_having subselect union case join aggregates transactions random portals arrays btree_index hash_index func_index update namespace prepared_xacts delete
# ----------
# Another group of parallel tests
diff --git a/src/test/regress/serial_schedule b/src/test/regress/serial_schedule
index 76b0de3..ebff4ae 100644
--- a/src/test/regress/serial_schedule
+++ b/src/test/regress/serial_schedule
@@ -99,6 +99,7 @@ test: portals
test: arrays
test: btree_index
test: hash_index
+test: func_index
test: update
test: delete
test: namespace
diff --git a/src/test/regress/sql/func_index.sql b/src/test/regress/sql/func_index.sql
new file mode 100644
index 0000000..9540c07
--- /dev/null
+++ b/src/test/regress/sql/func_index.sql
@@ -0,0 +1,29 @@
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (projection=false);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name')) with (projection=true);
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+
+create table keyvalue(id integer primary key, info jsonb);
+create index nameindex on keyvalue((info->>'name'));
+set client_min_messages=debug1;
+insert into keyvalue values (1, '{"name": "john", "data": "some data"}');
+update keyvalue set info='{"name": "john", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some other data"}' where id=1;
+update keyvalue set info='{"name": "smith", "data": "some more data"}' where id=1;
+set client_min_messages=notice;
+drop table keyvalue;
+
+
On 15 September 2017 at 16:34, Konstantin Knizhnik
<k.knizhnik@postgrespro.ru> wrote:
Attached please find yet another version of the patch.
Thanks. I'm reviewing it.
--
Simon Riggs 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
On Wed, Sep 13, 2017 at 7:00 AM, Simon Riggs <simon@2ndquadrant.com> 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>10000) 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
On Thu, May 25, 2017 at 7:30 PM, Konstantin Knizhnik
<k.knizhnik@postgrespro.ru> 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
On Thu, Sep 28, 2017 at 11:24 PM, Oleg Bartunov <obartunov@gmail.com> wrote:
On Thu, May 25, 2017 at 7:30 PM, Konstantin Knizhnik
<k.knizhnik@postgrespro.ru> 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.
sorry, now with picture attached.
Attachments:
Screen Shot 2017-09-28 at 22.58.42.pngimage/png; name="Screen Shot 2017-09-28 at 22.58.42.png"Download
�PNG
IHDR � H ��, %iCCPICC Profile H���TSI���$$$�@(RBo���k�R! $�A��,*�T,X��Z YT�^��TP�u�`��$������s����s����7o� ���"Q&�@�0W������$u2��46'G�����n�o�Hh�m�����_M���� �DAN��p� w���� z��xV�2��b(������"�9��bb�� '�@e��i (Iu1�8i0�R)d[!W �����gs!B��5��d������-g�hN6;m����L�_�#�d��?����L����Q���hi����13T�T���)��� �pe�R��K����?rr��3 P*��
Y��$#�g�=�b�X�&��c��Q�xf�p~4_�6����c�p%/' f$&U���!�(�e��<�'�����ANFL����|����$�R���c +g��$U-����V��?,�,�M��e� ��r&�������z��0nX'V&�����eF
�c��� ��r[N^����\����� �%�W�F����L��?` l)`&H����^0��@� �{FF$�z������x gt���������W~����<���
9��=qw<^�a��]p��qL��Y�Db01�h9CP �!/p`���A(��`UR
����� �������]��8�?*��M0�0k�pu)�W��A���/��C�8�6�X��ks��oO��i���&��Q�&��l�c������im����J��o����������?Fb��C�9�$vk� ;�5b��cR]Oekcd�h���G0c[g�c;���������ry�s���L�� ������5��r��e���9 ���[�[�lOG���[ p-���o>6���v@��g�~� 8v�#��}��B ��m��.X�=p��� bA"��3dA���<���
���6����� h ��$8.���&��Jx ��{0� �!tD1@Lk�qA<� $�F�d$
"d�)A��M���9��D. ��]��A� �Q����j��G]P4�E��ih6���+�
h%��GO����h��� ��10C�s���H, K����+�*�}X|������q:��m�z
��p��/�K�Mx
^������x��@#�� na2!�0�PD('�"!���T�=�Hd����[M$��K�[���-�v�b?�D�&Y�<H�$6)�TD�H�C:A�F�"}TPT0P�WTHR*(�+�V8�pM��� Y�lJv#G���9���*r�
��<@Q��S<(��t�b��>���[EEE#EW�I��E�(�W�T�DU�ZQ��S��
j5��z���F����iI�\�
Z-����]i�K���P�B�^���+e������t�|�r�C�W�{U�*f*~*l�**GUn����U�T#U�TKUw�^P}�FR3SP����T;�������~t} ��~���NT7Wg������UoS��P����1[�B��Fc�1X�L�J�A�-�gM=MM��r�}��4?h�����ik�����Y������Z�A���c�3Ig��V�3:�c������)sp�=]T�J7Zw��N����z�zAz"��z��z������k�����
<
k
N�`j0}���
���>C]�`C���6�#s�8���F�)�.���k�[��LL�M�����3%����M���3�`fn�`��������9�<��������"�����%���2�r��U+����oUau��v�Xo�nK�:V8�r�m���M�M�M�8���q���o2>i������u������o�fbW`�d�����c_a����������� � ['�q�;�;.ulu����$v����l���������K�K��yW����B�f�OnNn�n��r�q�p���|��D����O<�<�;<:<�����=;���^�^����������X�����y�k�+�=�����o�_�?��_����)�Q�Q`Z`]`_�c����`Bph����,=�U��q�r:��)�q�U�8�)
_� �4B� "Y�k"F�GeG�6�8)jR���h��y��b�13bv�����]{?�"N��?5�6�C�BYB�����O����(HlL"%�'�J��0e�����S����f>m���u�gN?6Cy{��dBrB���Av$�����J����������zs�r{x�2��T�����iik�z�^�r~��O�I�:=8}[������������Y
Y�YG�j�����3g�lY��D�n�������]9H����\u��}Yb!�I����W��qV��C�Ugg_�c5g��g�������r���3��x^�|��; R�.4^X��kQ�������/�-(+x�$aIS�^���'?�TW�T$.���}��e�2�����7.�Z�-�Xb[R^2X�)�����~Z���m���������n��Z]S�Z�_�dM�������k�����B���m�)�%�;6�mh�h�q���M�M7+|+�o���|��-�-��zo��Mo[��������Q_iVY���3ogwU|��_\~�����d��jauGMt��Z������W��u���=S�\����q�����K��/~M��������\�;lzx����z�~N}_���1���h���&��#��������������)����?��"j�=�v�I�����&��qz���3�g��
<{�����=�7_p�p�����KN��/;^>����G�����8_i��z��}b��k^�N^��~�����7�o���s{���;�;��f�}}/����E��<,�����?�w8u�����8���'�'/��<�*��u�?3xV���ysO`��S^t���-�S����,^�����}���^�_�)}������w��Q���g��P�Q�c�'�O�>'|~60k�4��������_e
��b��W �
MM�M5 �D��p ���Lf��<)#��X~~�� �� �- ��l��2������ upm����`/�E�'�����z �� �"�24��
��@K��L(5�t����L��?�� a�p;Qp pHYs % %IR$� �iTXtXML:com.adobe.xmp <x:xmpmeta xmlns:x="adobe:ns:meta/" x:xmptk="XMP Core 5.4.0">
<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#">
<rdf:Description rdf:about=""
xmlns:exif="http://ns.adobe.com/exif/1.0/">
<exif:PixelXDimension>1932</exif:PixelXDimension>
<exif:PixelYDimension>1096</exif:PixelYDimension>
</rdf:Description>
</rdf:RDF>
</x:xmpmeta>
'?�+ iDOT $ ( $ $ k8n��; @ IDATx���L������EJ�^�u�Jr�T+B(����(���[�V������B�J.��
)�����R�Vrgw~�{8cvv�����������kf���s���93�?��~�9&O��@ @ @ @ @ @ @ ���A`v��#� � � � � � � � �17 � � � � � � ��az�i6 � � � � � � �c��u�a�}� � � � � � � �����z��E�� � � � � � � ���P����Rczs? � � � � � � � a$0e��0��4@ @ @ @ @ @ p
;)x� � � � � � � �� �qx]oZ� � � � � � � 8��<A @ @ @ @ @ @ �K��8��7�E @ @ @ @ @ @ ��N
� � � � � � � � �%@`^���"� � � � � � � Nc'O@ @ @ @ @ @ @ �� 0��Mk@ @ @ @ @ @ @ � ����' � � � � � � �@x ����� � � � � � � ��S���I�@ @ @ @ @ @ @ ����z�Z@ @ @ @ @ @ @�)@`��� � � � � � � ^��u�i- � � � � � � � 0vR�@ @ @ @ @ @ /�����@ @ @ @ @ @ p
;)x� � � � � � � �� �qx]oZ� � � � � � � 8��<A @ @ @ @ @ @ �K��8��7�E @ @ @ @ @ @ ��N
� � � � � � � � �%@`^���"� � � � � � � Nc'O@ @ @ @ @ @ @ �� 0��Mk@ @ @ @ @ @ @ � ����' � � � � � � �@x ����� � � � � � � ��S���I�@ @ @ @ @ @ @ ����z�Z@ @ @ @ @ @ @�)@`��� � � � � � � ^��u�i- � � � � � � � 0vR�@ @ @ @ @ @ /�����@ @ @ @ @ @ p
;)x� � � � � � � �� �qx]oZ� � � � � � � 8��<A @ @ @ @ @ @ �K��8��7�E @ @ @ @ @ @ ��N
� � � � � � � � �%@`^���"� � � � � � � Nc'O@ @ @ @ @ @ @ �� 0��Mk@ @ @ @ @ @ @ � ����' � � � � � � �@x ����� � � � � � � ��S���I�@ @ @ @ @ @ @ ����z�Z@ @ @ @ @ @ @�)@`��� � � � � � � ^��u�i- � � � � � � � 0vR�@ @ @ @ @ @ /�����@ @ @ @ @ @ p
;)x� � � � � � � �� �qx]oZ� � � � � � � 8��<A @ @ @ @ @ @ �K��8��7�E @ @ @ @ @ @ ��N
� � � � � � � � �%@`^���"� � � � � � � Nc'O@ @ @ @ @ @ @ �� 0��Mk@ @ @ @ @ @ @ � ����' � � � � � � �@x ����� � � � � � � ��S���I�@ @ @ @ @ @ @ ����z�Z@ @ @ @ @ @ @�)@`��� � � � � � � ^��u�i- � � � � � � � 0vR�@ @ @ @ @ @ /�����@ @ @ @ @ @ p
;)x� � � � � � � �� �qx]oZ� � � � � � � 8��<A @ @ @ @ @ @ �K��8��7�E @ @ @ @ @ @ ��N
� � � � � � � � �%@`^���"� � � � � � � Nc'O@ @ @ @ @ @ @ �� 0��Mk@ @ @ @ @ @ @ � ����'�.p����������r���D�>�==~RN�:#����s�i��p�T9r����K���-����B��P��rM�BrU���
��7]{��\��\�mS�Y@ @ @ @ @ @ �.���JP��"�������o�e����<�%�Par�����o�E���]*F�!eK�&�)�%��� � � � � � � X 0��D��P��?]�I��~-�7l��NdMH�M���K�!������%U�*!yr����@ @ @ @ @ @ � 0���#es����w?[)o/Z!�����j�3g�W��t~��<po���/[��� � � � � � � �� �qh^WZ�"���������s>��{�t��=��Y�&y��
�PU��=+I�@ @ @ @ @ @ BB��8$.#��&�8c�$L���H���;W.�U������ W���f�zR)@ @ @ @ @ @ �� 0�kG�}�����PF�^$�ii>Jg��e"o�����F���e��R;@ @ @ @ @ @ �� 0�KEE�Ps�5MVo�����}�7_/�O>,�O��|y�d��RA@ @ @ @ @ @ ��-@`����@���k$n�;�������mX[&u!8*K-@ @ @ @ @ @ �� �q��4T���!K�~/#�_,_l����A[6����N�2��fU��7J����m�� � � � � � � �G�����sVN�=+�F�-3SV�x�����;��p�UR\�����E��b�_#����9wN�����y���y�������������������*�)c:���J����ph@ @ @ @ @ @ �P 0�+f�IMK���O�w>���������L)�.%eK�&%n�^
��9r�<OZ�C��:-��}H~��/Y�q���y������=��s�@� ;������#���@ @ @ @ @ @ �L��8�.x�5���Y2v^�-���p!iQ��<v_y�rw gb;�����)�n�%+6m�o~�)���Cg8F�z�eL�R�����@ @ @ @ @ @ WcW
���
�U`��%g�R�JY�R)��&������������(���A����V�����AJh�h� � � � � � � `&@`l&��l-��{���r����������YU:>]Wz:�er����o7��w>�]{�g�hw/~�����x����.�� � � � � � � .�.<
���)�m|���k��[�[5����6�V!��i�d���r��)[�����e\�V��� � � � � � � �� �q�]��h�C�_���!��]"���W[?-]�>*�r��w�KR~�/���Kd���r���L�S�w���R����:;#� � � � � � �� �qh^��n��=I���������\{�L�����xOP���������������5��������Q�:;#� � � � � � �� �q�]��oQ���d����j��7\+�&�/��~����/�H�)��?�������OF���%�����P@ @ @ @ @ @ T�C���h�>]�Ib���P������z�
M�u���)Y�a���x�,]���9{���\��4���q�������Y@ @ @ @ @ @ 0����4�n����q�_u�|t_�U��_�d��_n�Q��;Z�=~"�j6�QE��S���9�F� � � � � � �@@�������k�T}���=�j��j��SI���,������j��
eH����� � � � � � � �!@`�1,Z1a�g�9����`PWy�z%�� ��G�;����������N�Xy�nt���# � � � � � �@��5��4Qf�����(w�,�Or��ay�`*�k�~��}�������]�������R�D���g'@ @ @ @ @ @ �� 0�k-P�PWi�_����r{��I���f�|0���Wi��u������_)*R���O�(�?��� @ @ @ @ @ @ ������M���?$e[����OZjs�M������E����%f�r��iK6��:���1�Z���5 � � � � � �@��E�&~�y���$��Rs�?������R�P(4k�Ji=t�e�6�!��7��_���j�#� � � � � � �� �q\�Ph�{K���^�`�)u�'�W�\>
�|o��z����U�F�Gv��y���@ @ @ @ @ @ �S��88�[��:a�|I���R��p�k��"W�T>�
-Y�YzLH�m����YIq-�c�z~�� � � � � � � �+@`��.�j�z��23e��6?]��|�g�l(:|����>T6�������������#G���0 � � � � � �@�
����7�?F>^��R�;4�+c���T6Tm�����,���W�7��<z_y���0 � � � � � �@�
����;��u���n��6�m���������\�#-`���(?��eJ�����;W.��P@ @ @ @ @ @ ������K�S���� �f�.KM���S��B����^�F�DY�����phip?���B�0 � � � � � ��Az����g���}�����~���~-����a��&�L���f��(T��=�dTo�26@xD @ @ @ @ @ BX��8�/n�4M��������Zjs_d�{��D5�&'O������\9s�WJ��K�(�f@ @ @ @ @ @ �` 0�+�WCR���Wo��Rk��YE>H��T6
�z�=��"����am������0 � � � � � �@� �5�;���uY��Km�u�|3)Ar��e�|�:��R��~�g�!�M�����y�0������� � � � � � �@� �5�7K/s������#d��ar��E-��Bc��H�q��j�;�b����~�Ca@ @ @ @ @ @ �� 0����>��g����?��s���#���z��g�J�Ae�����Z)*R���/����@ @ @ @ @ @ �K��8��W��V�_�`�IKsX2(u��������.Z��?(�[����pY�������SV�^�� � � � � � � A+@`��.�*�B�r�{�5���=������Gk�L���q���2�SGe3 � � � � � �@�
���z?��8����-�z%Y0�����P���k���q��Z���r�@��3��}(� � � � � � <��s�����?�R��>��C�<y���b��� ���G���%�����+�M��I����T�B � � � � � � �%@`\�+�k���}X���N��L��%9�CX��7��^#��5��W��^<����Z�t;@ @ @ @ @ @ �W��8x�]X��Y�x��l������[v�-�^GYm��K��/}>�m&��i��@ @ @ @ @ @ �O��8��YX�X��U=d�Y���VZ=R��]B��gk��G^y�r[?ZC����ry
"� � � � � � � �q�\+j� �9{N�k/�v�f����+��C�[.���?�������Z����tL_��#���B @ @ @ @ @ ���V������~�Gz�.����d���N��R�6�m�|�JMK����he��h�4}�\S�����A @ @ @ @ @ "� �XT��@��A�Oc�q]ZI��6^^��#���;�
���"W����t����2~�O�2���+�|3)A*F��a+@ @ @ @ @ @ �[��8��_��>���2x�G~����dYR?)_�v���l����H�.���m���2�d��W��B2{�L�?z�'���d���dDO�W����D @ @ @ @ @ ���N��M`����p�!nk}��P�vY�F?Q���ZTP|�@���/�e���/����VI���,�zf�Xi^7�ry
"� � � � � � � �qp\'j�&p����UO���n[|�l��C2��6��T��e�H�� ��r��!+���=�m:|@�I�v�4�9���c�����Z.OA@ @ @ @ @ @ �� 0��D-=,\�A��7����&uA�6����
%���P�M��)_�<����r��7�p���z�OR�c����Y:H�1����,�� � � � � � �@�����zN�-��_�a��UW�/)��H��Kx/h�V5��Z�..R��l�6Tn��j��!���G��<@��=g� ]�<*#;4�T�B � � � � � � �#@`<���z8u��4�=R�m��a��U%o�A�;@n��*�3�5����F��8o��zP���A�teO����}R��>�������Dm���+E)� � � � � � D�At���g���H�.�e��y.�e�������J�����
|�
��h�Y�>rT?�
���zG���Am���}�\�����S����~u������B @ @ @ @ @ ���V�����]{�~���`�K��z5o(C�6����_m�.������W�������,�����C�H�V����c�viR���7����B @ @ @ @ @ ���V����������d��o���]���=��L������\��'�RS�q|�,\��y������c�J�9��.��}�U`�[�����7�QE�&�Y*K!@ @ @ @ @ @ �� 0�kEM-
$�M�n�gY,}���v��+�>vqE&�}�q�<�mh����*�GC�g��������!��?i�`
�//���T�B � � � � � � �#@`<����!��;��i���C$�������%w.{�3�K�)�,IW��2��O��
/���������'�W���\������j��3�e��
�������4G�m�%O�` � � � � � �#@`l�#G��='��Q�/��f}�{B����}<��� )�������K���ez�v��.��-��!U^�/����t~�A��=����%�I������S��|����]��V�u����:������3g��p!-��In��j��?v��,]�EV|�MTP~X��95-M~���E������:�U�
x<������?���}��Z ]��H)��q�7����g���u�o��%�}]�����~�J6��M��8%9��[�������%u*�#�����|����|���~�/���a�O;��[[>R��<\�^�Fsu_T/��o7��s���*J���E��jx���~/+��!�������R�P�V��$�L���z�\_�J������������)%�7]������{����vK�+I���4��F��a�/���?$o��R���R�����L�Z���F
P?.xB��D��y�m� � � � � � � @`
W�6�
���L��r���T������L���7������I��72����eb�2���+�m�Y���*Fo[_�oZ�>���W1��'�cB��r*�{��]2�S)y�^~��CR�e���U��\�hI|��i�9k�J��"���������9�=���q��B�tm��{���s���Sg��F�����z��*�N�>_��K�C^��'�K�.#;45O��2���e���D�]m���zy���E����l�u��y�����w�������Y�����)����rs�"�)��tm�H���o/�B��xK��\���3m�oO�������H�5WJ�r�l�1L��1tU�]�mQ?�P����=|A�������#��,� 7^s���� � � � � � J��t5iK������m�:C�<�P�W���'eK�����g^'s�X��p�&���^�
�x��
[��6�����#5���m}W�f�q��@��2�$��#S�bU�
�SS������e��[��F�%�V�����%�G�=w�"�h�TX����z���z����jy���2�_��K?]�I�5B/���G�+'�*�\���K�{L�
����Z��#R������������1�3n��2v���T���z�����N�a�#��Id�8�<��!�����=�y����M�G���2��e��y����,�������U=`?_��,\�A��z�~2�����R6���--M�_�����CU�\����=�7��E���U�$�wH������w�G�q��Y#�N�g��������Q�jQ!�c�W�zZ��+
�������������j���/���-^!/
�jV�����|m�d�����9����{
�|�V�'9���i�0�^p�t{�zV7�9\�w�X0^n������� � � � � � ! @`�&x�������)��mU�5U�yeA���O�R��,�Bo�=K�[5����NW��j����N��f�����_�V�����C������|�z��WU��f�8�
&��B��W�h�O����L����m�[�p�3�����{<�j�6-��8z�>��*�T�����.�;$�7ZXYC��<�}s�u��f��?���Q��Zx��������F5���Z����'��36y}T��x�.r���2��6��������q���L��rHF[�c������`�-�����V��?�K�T��c�C1�!�?���p�}Y�
�4~��Y�[7u�3�U�q�����50V��� �D�Kji�P5y�Mc������P�*�U=���B�Y��;�$�����F�]�aZ�W|� ~=y���2GJk?0X7u�i`�~�P��PY�a�>��>-�V?8���Y�~�`�����g�8c3(�#� Re��d��[dn�I��d��ED����wJ���r���+�f^!��e���c;�3qs�gKu������~b)b�|�,��s��)'+�>�Lk�T��/�+5-�@ @ �� 0����U�P�.�e��]~��C��26�y��Q�������:<']�!y�^T��������U=uU�������/�H�[o�p:��
��PC��!|}-F�U`�e���Ha�]�<I��W����������b%06�����v��9�{5o(C�656������W�k����{;����\�|��G�7H_�}�����j���u�We����<�F��cGM�)�������j�����M�{���#���{���~�����9�������/��Zh���
�P�������?*�UC���
?����b��6��Z��X��K�.��z����[����^��?V��[��^���S-���z:?���nG�������@ ��H��X��.������9�$&a���@���e;�4�B�Y����qBb�]"j&������������J�*�����g%
�J���R��7��!<��=d��DiP<��i��@���\�5�#V�b�.Q��vk�T�3,�.
GF @ �H��8�.U
\@�����M��V5���C�K���[�ET�������v���4}1�����e�[��nQ�����2V9+EE�� ����R{2������\Wy}�� ���I�e�F����w^��#��O���M���}�xQ=���xz�v�����F%�u������������jQ��t,�~�M��;�k�c�G5��
U�����\�ov
��;�g�l�����=^���el��8o���t�X}�o'�
Z�j��=�z"��ZV�Y\�� ��}m�m��lQ����Z-��({
�U/�Jm���������zP����?��z�We��=�z�=�U�W���
���v�6���V���\���n��j`�FP#
�a�7�=T.^
�k�ucC�G@ k�,i/���$G3�aI��H:���}��X�@��;e����s�����q�l��d���=�1)��G��Y"���/�2�������2�����`�#�J��diV������ � �@h
��u�U��� �h=�������z����UOU+��=;�m=�s/H �~��*t�2n�>���6��������U�7�E�j_��2Z
�k�'0VV/�xK�P���?������K�d�������2��g���������&��������������� ���^j"}�{B�d�jn����oC}�R����U?����M�~�C\e����6���v/�^��������Me"oU_�k[�q��6�pY}���b7��U�C�w�67t�6�u�b7�s=�2�cc�j5O���^�l�������x]��;'��<�Mk���a����<J����d���R�i���.�<�p�J`��6�r����>�M�\
���� �F�7k?PV�cO*��&pRv/I��;Nh�b��qHS�q"�%vHc�3�Hn�7u��$<���:g�V��%�kK�I[�*�q h��%u�,�[��wq�a��tX���#dN7�08
��8����%�y�� � �'@`l�%G
� >��I�X�m������D���������-������������K�L~M�iCE���u���U/=(�u��1�eL�z1��������������z������
}�i�9�U��z����)%_���CM#0���YbjV5=����K�7f�{K����Us���w���V!����[�GM��iC��c�c-`�S���h���������J���'�C;���\%������Z����J�E�[��BzD'�X���a����E����K�;#�^�>����>{<�Z�RZ
y�yZ5g��e�����/����_��l�7�3R����XZ>��lW����5��<@�Uo{����a�c�3]����i���w����5X������_���O*��G���j(x5$�������n������cc��H`lH�xd����M^���eh<m���~2qX7��%�����u��_�Wd���.�C��9/g��'Jb��u]�a��2�&qO=!-�Ul.�#��}��2�g�%�T��Ev���c�^z�l�;��E
�&i7�t�J��]�j��_\�.|\�
�!U7x8R�D�/�� ��W��N��
$0�8�q��a,����M�gX��7h) � �[����%BP���S���j��\�j�Uo��
�z��`��l�+
���;{n�o��������U��g����
2�����o�k?�=w�\z`�m8d�8F`���w�w��� T�]������.�'��-�u���C%�a����I�jR��zOS�����c�s��|��:���/=X���]�W{N�9���@��n��x~[��\1��fR��v#0V���3������UO�7���;Y9�x����W�;���4/;�};=]OFw<�gP��Y��?5W��� �^�e�����%��~�0�����[.#f/�p�U{��WA�T�G�z����.��q�[n��{~MV~�C���z ���y����O��"$����~����^�j�tlTO��Z�;���X]KuMU �~��z^�._�+k#�!����u;������������FVv����������Y���
����#d��md����S��4w�O����5f�
�o����DV�_�n�z��52�t-I���6�<��k=;I��E/4U�0i��Z���L-��j�p���&�z���D'����������ff������<0�z!L���[�nlD @ �L��8�.8�=/�z�>����i�_OFy���U^��DO��:#3��������g�||���^y�u���[_��(}.X��������N�JW���U�
�A����fe���l��zU��������U`\N����1mW��fy����z�6K/s���{��;_t���d�������W�
e��X�W�kl�����Y���I�g�k`�����y��8��7�����6��U�U�r5��
�w��W�a�U]�VN���-7��W�P�_~�MVhCBo���VA��o,�}��S��{V�}l��=�[����n����X����M�D�J�`PW��XO���|�����\�9���[`�z2?�1A������G�j���O=l�v>;)zb����i���$T;����Yof���!"�����(
,��tH���gqGc�PaU��s���kX��X?�`c������
����c[V��jp��,`�oA��iz���qL�����|7S7@ @�R_jq��m���OkC[]T/�wLz������u�a�-O�����������^�����s��ybg�w�_~��N��)�k�i��K�z>��2w����7�Z�����#W�j������������r�a��].q����V����U���;y>�n�H
y�w[�0z�R���,t������
����z}��X�[g�������)_�<���~�sKi�h
��������������V�is�;�����O�~�=]������P��� ��*�6[���{T���>Q?<�`�j}.hU^
'���~�����q�v?�G,��EFW�w3;��������f�N1z��
Im@�F�������jg���m��%k7�����kVs��Z6�=��g���aS�^�����_7������U����A�
_��V��KB���_�i���v�g��8��i�7h�3v�;C�4(�c�McsD�d7�� ;������'�x�8�)=�����X���B��Va�����6�����#0����#� � !&@`b���'P��0�|��vRs�yT=���;e�^y;���W��k������^��[�y�}���
����}#�'���(P������}-�F`|�6����jNZ���K���������s��X
s�������Y����$��������pm>�k�����PN��=��&��q�
2�;�*�n�%��&j�l���R|�����<�m���S{�$/4��V���Sg����=�Bh���6�r���d��ez��/5���5��g������Uo�q�S�c(_n���|��Y�&}Nd57��Y��z�[]���e��)��t��
eH��^{�}��h}hj5�w��O�����|����9sh?^p�O�:���V�xhwy��
���G�t~�0�l����6f_��
������V�
���M+d��(i��P���������:~.�L��=�C��s�������1Rw(][��q���k? ��<Z�p���U���?����$n�Q��IDL����L�����<^f���� No�oA��I`7 uD @ �� �q&��5��<�w����k+�[5��Q~�u����R�~��67�������[����KZc�5����o����yu�|o�����~u���]�uf/��X��z�^{������1��������q��k�q|����=E
O����|'
��L��|�G���zl�<}F1U�������c��>���q �)��{U�����d����������H/�����'k��������qzo[o�PC8��j���S�A���x���:n��=1��P���S?�PC��`Z��B���Wcucv5���A]�6��j�;�������^��z /�3�f�t~�0�l����6f_���� ��Jtli|�5�����4���u2{�j9��]���$�<M����B�#��}��2��9�3�����$e��W$�;Q4��?'�x�f=/�I�����4��Qb�����n��u�n^z�k�~��/di�{�������9��]��i��?�3�{���
��!� � �E�����s��$���p}�Y+u��������
K<�������>w��9������-��_{ZT��/��Ki�'����z�&kC�Z]^����?e��k`��;��=�-��r
�U@��jo����K���������{$����\�jx��G{;D�m����a�.����%j��
�n��_��X�xC�� @ IDAT���x^��xVCd9>>]}=���e����)�Q�.�G�|�7-"���3�n��=�-v�5�|�������^<?�����a�zx�I�����#���T���M�
��F�z��a�=b%0V=���x]���Un��*Y��`�h�:�K�����}i��6�^5�������6z���/9s���K���������J�;#���������?����y�0~b���������j��~!vRv�m$��R��,V=�����Iq�����{�T5�5����S[#�K����T����\g��N��d���R<�g`w�����_�3\�G/�I������+�K�I�A�s��._
����.�]�"������9��>wm���i���u���Yu?q\@ @ ����z�Z�W��&��T��9�*5���Q��v�{��*���1Q����b�������d~�
�G��H��������Q<�S�tC!�R�"�2��Q+�0�Xg�x)����!�^�����^G5$��z�+m��c�U��^��[��+r��I}���Z�\u��r�cu��C���)+E��
���7Q�H��B�����L�oCf}$����,�\V\���'���E�lL7�����jXs5���sY�f�S���C�����M��C����et��z+��*������6�zT=���.���W?�p
��Q��o����?�>�����������c!06${4�l����Jf_�2��X�Y3X���p�D����t����Ekq~��xY�5A*�J���l 0v��i�Nd��������^>��������������j��.`��k��?MCW��~WP?@ @ kao?t~��4�9,=1i#���sir>.�T"�:U6c���e�+u����g���+���K���[�-�[
�����`�G����{���V���]����K��R�`�l�>�k��������7��U��{P"�������%n�>�n��O���-���n����r���R��fE���������������i�_��y�Y��X�j����-�E�q�7����-�{�~1v��/y��Xv�V��v����������w���� ������5������0v��������;~����k�k�@�R�����������T��@����ji����_�����Q�����m���������6�K�����|����I������*���T�Z�j��C��Vs)�u�a\��0Y�q���z�T�7J��u���|�����k`���I�v^��� ��3u5��P��� �����0����ea��r��6���
V��z����E��
���x��P/���3���>� ���_�0��@P�}����O���3�< � ��o�� �o{s����]_�
�����J��~���@�����E��9���r���K���%��#�\�Oj+,�o�Rn(��Bi�Z a�|I��yXg�s�p�U���^���e���������k5l����L�>��Y�Z`����V�Q����������I��"����� ���!����E�w��!'N���{��;�����2�����1������UO�n�������b7J��I�M���W���s�����m������=Q�����cro�b��c�^e��� >�u6v>~����I��w\����������^�MkUs��z�OX��^�_����)j��������~tr�l����*�]����Mk�'�c���\-�V|���VmTm��%��Vum����N�w?�*+7o����+����6z3������n[f5,����8i���������l�brOd1)}��R >��������]{d������9��6yT�������/����� ���Q��������0��L� ���a�7N�I����R�� y�a���������6���s#��Q
j�W!�c�F���S��������)�g5����o�v��f_�
�|
EmwXl4�Bh�T��$K��v������<f����D������g���D`�e���/�8$�^��s��g��O@ @ 2'6���������%�<9s�S�����o��E�C����*T��eO}xc+
Q�<}��q
����M��Mi�������#���V|��k����>�Ln�������3��r �S���)rT�����R�JY����2G�l�I���&}xc5<�����7jC'��o�����8��V����W8�[72=��y�zN�6������~N�Z��m�8^�=m��.55M^jXK�sUp���o�p6E^]��<�NJ�|���RF�6�������z�&kC�+����t��}�����(��5���{��.�f���
�� ����*����ZY�m��?�����~<P1*R�<TURU���`V�}m����������5M��~hP���e�6����X���������Y�������uV?P����4�{d�`�����u���>����u|��4~�����|m�E�
_����}I�v0�:�X�Wj,�~>?R���#j&����������$����I_�����}�'0v��$��?'|�fy��=���$c1m/����d� 0�������Ap��" � �@f�3�w ��6"���v��.s�%8[��B�A%��*���K�����7�>l@�{��H�d�w������j��ryUPY�
���@j_� W��V#����
UR�3����RP�1�z��r����f�3�H��}�����W���;���>.g����|��:-d���k,��?�����������3Z�_HTO�+
x�a�j�5��y�����1#t_c�i����V�f�i�����~*\WC��{uL�����k���k�����6|ag�j�%��!� �G`Q_�6-���|������6�n��u��=��}.cc����
���@��YQ����g�qfq3����&� �����
��$0���*#� � �#@`���e,����d���$�6�,K��yO��������yl���8������}�gmf������*X-N9@�)`�E�
_�9�����KBU.� ����Y5��{�����t�J��������%~���P��0�������/.
gJ��s"��k�j�U;{�L"0�*t��
���2!��]��I`B� MA @ �$@`�I%��{���2��H)���8+.Q� ��|j���)���^���p�6�l���k=S�
��/�lxk�>����x� �0�"��/�L�n�%���� *u�@)]%Qvx:_����D�:��u�D�/�� �l�����*\��������?���oJ�<��2"Zb�4�;�FI���Iq��(������d�b�qf���;IV��=B"c�I\�2r_��\$c��?'���U���9'����2�����\��=����;���\��M�'/�I�<0>(�f ��'����I�<�Z#�q������>2�xY��R�fMp��i��;�2��9HT��R�x�faVQc��^�'��v����Cu_iV��Q:���sf�\�;i���h���:�?/<�u9,���f���&����&":V�4�G������s��{��}~�}��Ye)��6��Z�����6��� � � �[���r_?�u�L�)����,�
�9b�{m����Y�x���>�����&K�l��<�dk��j�b�y~Y@ �����;���}I�v�����n`
�������i=�"�*Cc�:,u�G�����$.]����&�O��1�L���E���k��2.]�������1OYi��eq�V�x�KQS�����j�����|�ycxb�����Q/=�4�t��N����0j��������2zp�tu2������z���{I�,�f�$%�3���Z��s
}�����ev�t=�������B]����K�7�����T���R�\��H��y��������N��F��p��YU8������G!�>�$J�&/��f�\~0�>�&H�gz��������]������>����V�Se���<��"C�+T�7��t�`��u��^Q���R������C��P��������^&�s�{����c��%��5�{f���@ @ T���J��r�>�qV=[W�����6�qjZ�m�|�_�<W7���e�@������)������ph��)� �
�A6|a�z�t�m������_�_h���������R�D��JwO�����P��
�{��/[M��-�"&�������Y�����CY�&D6����Kg[{�i�T�v�g���j�J��3dL��=xm3���z����F������t��y�#��}%�?������Y����eRN�{K���������<a������"�]��������?�E�7g%J����������K/�7���$�����w�����n����Y��=};���8����ep��20������+[>s��^�t<�����v������6��f��gd�Bk�-���q�����|���� � � !'@`��T�.��d����p�>{W9q�I�>��J�{��L����ce� �Cjw,_n����^y�1��Y��)� �
��k�v�'J���KBU��/�������<O=�l�����/�����ON`lv��i?�-�/m]�����y��e�����j�a���q���2�yCi>�m8lc�������K����'����ij[�2TD[����{��{�
�^g�^GD'����������;��.���Bf�b���63�5��FOh:Y>KnX�o�9t10�',Vu����F��?��Y|���}���e��A{������-?d��v���=o�=j��q ����c:�����=1����2��Fi@ @ � 0�wO������''CS�} ��f��K2u���� ���I�<��a�w����^r��1��������W�ry
"� ��_��������=7��P��1��k���$�����}��tU����@�NSc�Kg~O�wo������:r|�`iXk�==Ucl��y�������v������Z��j�e60N����K��s����J^����]�
7z�I)o�O�],�����5�r�cp����.�5�����KV^��U�D�f�9t>0� W��9d��!����bu�#��}��2)�?�qV��}�,��$x���r�]?p�=����� fb._���
����F����WN���w}I��@:��a�r��v����<E @ !c3_��R��+Ee��Y�b�4�`gR����49r���?~V�9}.����L��<Q����gGs��������[,���r����))���#O=XY���c~/[N�:#�Z/�Z'�����g�I��RR�S��J�H����M����,3SVJ��oZ����e���R��,�CA@�U��]��s=Q��f_�B�|!��8YY�t�q{��NZ�.�������������������n��m��E�����3,6�IR���z��1��q�#�X��r��=�^L}��Z �C�y���"&��z����g�Z.����>o�����\�~l����+�g�u�"���hV9} c�!���fI��2���kaWS�k;W�Ol��z�:����/,.��Q/��F�>���a���q�������V�� �w|�a�t>�.\� �Wv�("�v���z�Fd6$5���
����F�IL�'d�h���w����o���=�{���<E @ -#0m���^n�����W$�[�������X�w������O��g�<�����.I=��$�����<�m1�9l���j�p4�=�������:u���A���c���#mw������3��1�c�5;%:����:�@ W��)�m���+��vD'ms-j����]I���8����]�-���#%6��8������co1sSqh��l9�6GRta�m�Nr���Yt�]I�������\3s�-���S������cDd������2E���I�k���s�)�9b��z�f��E8��W;�@nG��f��zf|Ok�"��c�:Rv�p9�9����;���:�}����qLM���1�� )�]�}��+��#2C]�:���I���>+O�|&�u�X�H�r�s?8�j����3�Z�����r�q���K_����{���p$7������+u�&Mp${�.��:���cb�Z�B�*������o��!���H�-��|�3hD���u���Qm���_{�]"K^�u��?�"�MgZ��P��I��q�|vi<�|�DVsDGFx�W�����OJ�hw���`�����i�>wm�������{TY�qLH���=z �~�{����{6�Ay� � j�'Ov�[��A`�$���S�.mX����7MX�Wp\y��P��m{�>��c�����������2��t4�7�1t��������S���R�[��P��<|����F,��;�1���)� x0�B��/�<�P_g�%�����/����~���m8�6�e���ma����v����{� �=��1���XOk��z ;��@DSG��������~<�)<2,U�$���>��}1������8�?��c���/�*�N�'(v���bx�L�50>�8���$X�#�r�8�k���Y�������+�>5�;�����:o��������n?�p?���s�9�P�xxx�����G���M�w��\�w���s��>7\���k� �v$�k�X�����W(�+���}�MP�q�#���E]���^�f��6������������V��4����~�����g���0�@ @ T�]�b�����
�`�!�u��Z�o����?;�&��m���8���P=��^T�^���m}=������������i�s�'_Z:6�@ 3�/t=}})���������/���|�7
D5?����v"/m'06�5������~i��>�z%%�N�����sx;�����el�O��� R V'x����~�L���JP���Fo=u�y����~�K�/r���/���������J�d�#���el�w���/���r-��D�t$����no�>t������PimT�}���[��n{�17^���30���v��+��������\���K�g���~�H��%4�����}i���������@ @ ���8�j������r��
z���M���k���[��|�����v�_��������2��e�l_���sR����������S�d����i����o?z�L�x��2����%�N$eKhc� �
��1�3��s�����U�p���(��f�B�����9��.��=������:'��)���JB�����>���:��)����5�J��C�o�kn]��Sw���>���������*g7�b��drneU��4�M�}�x�o���]f7�*��e��M����>������J>���l)���)��k�L������J�9;<��T��$K���<ow]k�sH�J��/di�{��]����m�n�kd`�Z����[]+J��/%�rA��v��{%��Y>���$����������s7+�0v�c@���[dl��$n�A���<�����~�S�����{kT�G@ @ ��"`�aL`�rE.g`|��9���f9v�w������
�Z4������Z�e)����w��6\Y��|2��T����}T�
���1�,v��k�D��i��f��P�����?�3�RM��m!O ��^�fW������R�v��@�lV�jK���R�\��p�A��~�!���:Pi�MY&�]�������4�����+�K����"�v���]$��+����]�%��)B"c����
�jm=�!u�@)]%Q2D������
����6�bz-T���g�Sh�f�����<���%&�[���Vgq�'�>���������`�u3m�%�� �{%3�����f��� 0���������������=��u � � �N����%�������l�
��y�Y�U�n�R�>%��/t���&�-M����������X��$@(�7��^T�A��`A��xQ?,�X.W������6AE�bAz�'jBH��6���sv�n��g���g���3���q�y���QF����y��D����<��s�68O�]D�k���vIx�H���/��}4D ,k�T�^�t�Zv�rK|c]K�����%����+���*T��H�6�U3;^+�nX�����f���m<�X�N6�a��p N�����\����ow�����d��m����� f��::U(H�����J�i������W�������q�V�6�W�]�O�q�b���m������Q��C;����6g)��H�H�H�H � P0�h��������k�Y�,oT��%��wK��)��&c"���K����/8.�������c������_/;�o�#w��nW:z��I�H 7��n�����`AL�����0D�p��=v�
xa��rM�87�w}�v��$3m;�����E�z}���O���T�-A����J���62�O���+c�&�6���8�fV��0@���,/�����vB�[c�T=��F�MM�>.�p��Tq]�w�M�[����J����`3�!��]�N�o�V�����~����1��0m��l��Q$@$@$@$@O���E��`<r�6��{���,��r%���>�pV�����*K��#��'p�C�0��5�K1��ux��>9�{u�L<>vb�8�/�cc���QhY��]2�# ���~
Qb�E5U4�D� �iW.W�')�~=_�r\���~��O;�[����Z�Z��������<t�1�K\tE����.F�FN�p���������L0��-��&���4��?����1�!����������\W��^�N���5��� ��������[������8����w��7o���By��� �~�������p�����$@$@$@$@�� c���o�����`��[,J�7�x�"���ZV.��&c"�@ V�R�"E�`���[�����}�XL������.�i\��;1�
���\E�W �N@� �������EBy����vQMe�����������f!;?������K��%;A����7M�� ��L�����5�����d�~��mg7,�����CA��U�|����}�M��[;��P�����yoQ����v����3�����S�8wk�ei}��|h����<��n�r����sq�h�uU�`~7�e����3
�+ �@���E#��`<E���W��6 E���_����]�$y�i�N����P���yB��bJ�,A��
�4��;��x,���pT�r�K����~�]���hq�c��s�qo���|�q�P'�f�>�����>�� 4�k����u8��gd�I�e�H���u��(��#��q��]j�=����0�C�����~��;m�t�����1����&��:m�
om5j�����C�}Xoyj4l���V��y��x���k���;��l�$7������v�B\�W�����O;��)�{���s7l{mwQ����O���n��� ������n��\h��a_���}jyz�n�r��a7v�2��Fm���S���' �X�-�.��/���]�m�(�u��n�qu���7�f*�h��4�LN���4l9�����,i�'��T-\D8*[����E�R��_
+��i�8�Yq�Le)��e��c�~�8v9�w(=��^R7o(�D�2�n�K��r���/���J��:/����&�ID���?����g�D�2�p�c/?'bs��7P�li�g�L�����}i���x�v�6��w�x�=}��x)}�B�TU�N\�7�X�*�B�Jq�x7������H=��{k�X����p:��(�O
�<!C����,��vn��^0�}��:���a��t�>zj�����S�c)O�bE=���T����^���X�y� �����}�X���mR'�C��a��RU���b�RMd�b�y�Ly��_�v��% ��7P����Cp��.,�i��[$�,�i�T6n������vQU�uM��`lA���������_n
56.�M��V�tW�r����N�g%����k����X3O�]�4?�X�v:��In�vs�u��u����Qnn�?}^��_����}�c4,�����~���p.V��J�>������bq<����{;5��n}�#��8�5�@;�����w](oX�M������=���+O$@$@$@$�([�a~�����?g� ��-M��).�oQ�(�(�������m!�K A, k+���eqe�r��V|� /"n���(&�N��-�/-�#�R/y���D k_�noQ-��������.r\�ZU+����x�Y?��mX��9��
��5J<���=��a?�UdT+]�U���W�-�*q��Y� ����S���7���9�k�
��<�"<~�6u������U6St9��r%`NU��l>