Re: [HACKERS][PROPOSAL] Covering + unique indexes.
Proposal Clarification. I see that discussion become too complicated. So, I'd like to clarify what we are talking about. We are discussing 2 different improvements of index. The one is "partially unique index" and the other "index with included columns". Let's look at example. - We have a table tbl(f1, f2, f3, f4). - We want to have an unique index on (f1,f2). - We want to have an index on (f1, f2, f3) which allow us to use index for complex "where" clauses. - We would like to have a covering index on all columns to avoid reading of heap pages. What are we doing now: CREATE UNIQUE INDEX on tbl(f1,f2); CREATE INDEX on tbl(f1, f2, f3, f4); What's wrong? - Two indexes with repeated data. Overhead to data manipulation operations and database size. - We don't need f4 as index key. But we have to... - Problem related to previous. It's possible that f4 has no opclass for our index. So there's no way to include it to index. While we don't need any opclass at all. Suggestions. CREATE INDEX idx ON tbl (f1, f2, f3) [UNIQUE ON (f1, f2)] [INCLUDE (f4)]; Let's review it stepby step. 1. "partially unique index" CREATE INDEX idx ON tbl (f1, f2, f3) UNIQUE ON (f1, f2); It means that we want to have columns (f1, f2, f3) as index keys in our index. But we want enforce uniqueness only on first two. It allows us insert (1,1,1), (1,2,1) and restricts insert (1,1,1), (1,1,2). It doesn't affect "select" queries. Following query can use index-only scan. SELECT f1,f2, f3 where f1 ... and f2 ... and f3 ; We haven't to maintain two indexes now. Just one! _bt_iseual() <http://doxygen.postgresql.org/nbtinsert_8c.html#abcfb7a3dcd40a5d1759652239f3a0115> works with (f1, f2) _bt_compare() <http://doxygen.postgresql.org/nbtsearch_8c.html#af689dabb25e99f551b68aa9b7a1e6ea6> works with (f1,f2,f3) 2. "index with included columns" It goes well with both unique and non-unique indexes. CREATE INDEX idx ON tbl (f1, f2, f3) INCLUDE (f4); What we get here: - f4 is not search key. - f4 could not have opclass for our index - f4 is only in the leaf pages and it's not bloating internal nodes of b-tree. - f4 can still be retrieved without going to the heap, so including it in the leaf nodes makes it possible to do index-only scans more often Following query can use index-only scan: SELECT f1,f2, f3, f4 where f1 ... and f2 ... and f3 ; And this one wouldn't use index-only scan because recheck on f4 is required. SELECT f1,f2, f3, f4 where f1 ... and f2 ... and f3 and f4; Catalog changes: Now: pg_index <http://doxygen.postgresql.org/pg__index_8h.html#a5065be0408f03576083a30c97b43a09a> int16 indnatts; /* number of columns in index */ bool indisunique; /* is this a unique index? */ New: pg_index int16 ind_n_unique_atts; /* number of unique columns in index. counted from begin of index. 0 means that index is not unique */ int16 ind_n_key_atts; /* number of index key columns in index. counted from begin of index.*/ int16 ind_n_total_atts; /* number of columns in index.*/ In our case: ind_n_unique_atts = 2; // f1, f2 ind_n_key_atts = 3; // f1, f2, f3 ind_n_total_atts = 4; // f1, f2, f3, f4 P.S. I use many ideas from discussion without quotations just because I'd like to keep this message readable. Thanks to everyone. -- Anastasia Lubennikova Postgres Professional: http://www.postgrespro.com The Russian Postgres Company
Re: [HACKERS][PROPOSAL] Covering + unique indexes.
15.09.2015 12:11, Vik Fearing: On 09/15/2015 10:57 AM, David Rowley wrote: I agree, that form CREATE UNIQUE INDEX i ON t (f1, f2, f3) INCLUDE (f4) is clear. f4 will be used in row compare and actually planner will be able to use it as unique index (f1, f2, f3) with additional f4 or as as unique index (f1, f2, f3, f4), because uniqueness on (f1, f2, f3) gives warranty of uniqueness on (f1, f2, f3, f4) I'd vote for this too. However, INCLUDE does not seem to be a reserved word at the moment. What about CREATE UNIQUE INDEX i ON t (f1, f2, f3) WITH (f4); ? WITH seems ambiguity to me. It refers to CTE, so I expect to see after that a kind of query expression. But maybe that's just matter of habit. BTW, that's the first syntax change I'm working with. Is there any convention in PostgreSQL about new keywords and so on? Where can I find it? -- Anastasia Lubennikova Postgres Professional: http://www.postgrespro.com The Russian Postgres Company -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS][PROPOSAL] Covering + unique indexes.
15.09.2015 12:18, David Rowley:
On 12 September 2015 at 00:45, Anastasia Lubennikova
<a.lubennik...@postgrespro.ru <mailto:a.lubennik...@postgrespro.ru>>
wrote:
I've started work on a patch that allows to combine covering and
unique functionality.
Great to hear someone is working on this!
Thank you! It looks like very interesting project to me)
Next issue is pg_index changes.
Now there's only a boolean flag
* bool indisunique; /* is this a unique index? */
But new algorithm requires to store a single number
* unit16n_unique_columns; /* number of first columns of index
which has unique constrains. */
I think, that numbers of all attributes themselves are not needed.
Is it right?
I think the total number of attributes is already in indnatts.
I imagine you're planning to keep the indexed columns at the start of
the indkey[] array, and just use n_unique_columns to mark how many of
the indkey[] attributes to check as indexed columns. I'd imagine the
change would be fairly simple from a planner point of view as you'd
just need to check columns 1 to n_unique_columns instead of 1 to
indnatts. Although I have a tendency to under estimate these things :(
I've asked that for the same reason. I'm not too deep in access method
and btree code, so I don't want to miss any hidden dependencies.
As I see it, changes are required in _bt_isequal()
<http://doxygen.postgresql.org/nbtinsert_8c.html#abcfb7a3dcd40a5d1759652239f3a0115>.
Instead of
for (i = 1; i <= keysz; i++) {} // where /keysz/ is actually /natts//=
rel->rd_rel->relnatts;
/Look at _bt_check_uinque
<http://doxygen.postgresql.org/nbtinsert_8c.html#a96eb8c53ffdf53f139b037194a9721a3>
and pg_class
<http://doxygen.postgresql.org/pg__class_8h.html#ac8bf924d36feee5f3ca4c36aa01c75ec>
for more info.
cycle should be
for (i = 1; i <= nuinique; i++) {} // where /nunique /is value of
/rel->rd_index->//indnuinque
//indnuinque /is a new field, which I suggest to add to pg_index
<http://doxygen.postgresql.org/pg__index_8h.html#a5065be0408f03576083a30c97b43a09a>
instead of /indisunique/ (or may be in addition to it).
But I'm doubt about the problem which Jim has mentioned.
>Are we certain that no index type could ever support an index on (f1,
f2, f3) UNIQUE(f1, f3)? Even if it >doesn't make sense for btree,
perhaps some other index could handle it.
If it's really so, we certainly have to keep in pg_index
<http://doxygen.postgresql.org/pg__index_8h.html#a5065be0408f03576083a30c97b43a09a>
not just number of unique columns (/indnunique/), but their numbers
themselves (an array /indnuniqueatts/ on the model of /indnatts/).
I imagine you don't want to name the new column n_unique_columns,
since it does not fit too well with non-unique indexes.
Hm, I think that it would be quite clear to set it to zero for
non-unique indexes.
/(nunique == 0)/ is equal to /(indisunique==false)/.
But maybe I've missed some reason why we should to save /indisunique/ flag.
Perhaps just indindexedatts, or something slightly along those lines.
But perhaps it would be a good idea to also rename "ncolumns" in code,
to ensure that any non-updated code does not even compile. Perhaps
including "tot" or "total" in there might help indicate it's new meaning.
I hope, that all these changes are not needed. Just continue to use
/ncolumns/ for all indexed columns. And new variable /nuinique/ (or
something like that) is for number of unique columns in the index.
--
Anastasia Lubennikova
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
[HACKERS][PROPOSAL] Covering + unique indexes.
Hi, hackers!
Use case:
Index-only scans is a wonderful feature that allows to speed up select
queries of indexed columns.
Therefore some users want to create multicolumn indexes on columns which
are queried often.
But if there's unique constraint on some column, they have to maintain
another unique index.
Even if the column is already in covering index.
This adds overhead to data manipulation operations and database size.
I've started work on a patch that allows to combine covering and unique
functionality.
The main idea is to allow user create multicolumn indexes with a
definite number of unique columns.
For example (don't mind SQL syntax here, please):
CREATE INDEX index ON table (c1, c2, c3) UNIQUE ON (c1, c2);
Created index has three columns, but only two of them have unique
constraint.
This idea has obvious restriction. We can set unique only for first
index columns.
There is no clear way to maintain following index.
CREATE INDEX index ON table (c1, c2, c3) UNIQUE ON (c1, c3);
So I suggest following syntax:
CREATE [UNIQUE {ON FIRST {COLUMN | n_unique_column COLUMNS}} INDEX ON
table_name (column_name1, column_name2 ...);
Examples:
CREATE UNIQUE INDEX ON table_name (c1, c2, c3); // (c1,c2, c3) must be
UNIQUE. That's how it works now.
CREATE UNIQUE ON FIRST COLUMN INDEX ON table_name (c1, c2, c3); // (c1)
must be UNIQUE
CREATE UNIQUE ON FIRST 2 COLUMNS INDEX ON table_name (c1, c2, c3); //
(c1,c2) must be UNIQUE
CREATE UNIQUE ON FIRST 3 COLUMNS INDEX ON table_name (c1, c2, c3); //
(c1,c2, c3) must be UNIQUE
Next issue is pg_index changes.
Now there's only a boolean flag
* bool indisunique; /* is this a unique index? */
But new algorithm requires to store a single number
* unit16n_unique_columns; /* number of first columns of index which
has unique constrains. */
I think, that numbers of all attributes themselves are not needed. Is it
right?
I'd like to see your suggestions about syntax changes.
And of course any other comments are welcome.
--
Anastasia Lubennikova
Postgres Professional:http://www.postgrespro.com
The Russian Postgres Company
Re: [HACKERS] [PATCH] Microvacuum for gist.
Fixed patch is attached.
08.09.2015 13:47, Teodor Sigaev:
BTW, I slightly modify your test to provide more stable results.
Thank you, I tried it, Results are nearly the same.
Without microvacuum
Time: 312,955 ms
Time: 264,597 ms
Time: 243,286 ms
Time: 243,679 ms
With microvacuum:
Time: 354,097 ms
Time: 82,206 ms
Time: 11,714 ms
Time: 11,277 ms
--
Anastasia Lubennikova
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c
index 0e49959..bb48782 100644
--- a/src/backend/access/gist/gist.c
+++ b/src/backend/access/gist/gist.c
@@ -36,6 +36,7 @@ static bool gistinserttuples(GISTInsertState *state, GISTInsertStack *stack,
bool unlockbuf, bool unlockleftchild);
static void gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
GISTSTATE *giststate, List *splitinfo, bool releasebuf);
+static void gistvacuumpage(Relation rel, Page page, Buffer buffer);
#define ROTATEDIST(d) do { \
@@ -209,6 +210,17 @@ gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate,
* because the tuple vector passed to gistSplit won't include this tuple.
*/
is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
+
+ /*
+ * If leaf page is full, try at first to delete dead tuples. And then
+ * check again.
+ */
+ if (is_split && GistPageIsLeaf(page) && GistPageHasGarbage(page))
+ {
+ gistvacuumpage(rel, page, buffer);
+ is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
+ }
+
if (is_split)
{
/* no space for insertion */
@@ -1440,3 +1452,70 @@ freeGISTstate(GISTSTATE *giststate)
/* It's sufficient to delete the scanCxt */
MemoryContextDelete(giststate->scanCxt);
}
+
+/*
+ * gistvacuumpage() -- try to remove LP_DEAD items from the given page.
+ */
+static void
+gistvacuumpage(Relation rel, Page page, Buffer buffer)
+{
+ OffsetNumber deletable[MaxOffsetNumber];
+ int ndeletable = 0;
+ OffsetNumber offnum, maxoff;
+
+ /*
+ * Scan over all items to see which ones need to be deleted according to
+ * LP_DEAD flags.
+ */
+ maxoff = PageGetMaxOffsetNumber(page);
+ for (offnum = FirstOffsetNumber;
+ offnum <= maxoff;
+ offnum = OffsetNumberNext(offnum))
+ {
+ ItemId itemId = PageGetItemId(page, offnum);
+
+ if (ItemIdIsDead(itemId))
+ deletable[ndeletable++] = offnum;
+ }
+
+ if (ndeletable > 0)
+ {
+ START_CRIT_SECTION();
+
+ PageIndexMultiDelete(page, deletable, ndeletable);
+
+ /*
+ * Mark the page as not containing any LP_DEAD items. This is not
+ * certainly true (there might be some that have recently been marked,
+ * but weren't included in our target-item list), but it will almost
+ * always be true and it doesn't seem worth an additional page scan to
+ * check it. Remember that F_HAS_GARBAGE is only a hint anyway.
+ */
+ GistClearPageHasGarbage(page);
+
+ MarkBufferDirty(buffer);
+
+ /* XLOG stuff */
+ if (RelationNeedsWAL(rel))
+ {
+ XLogRecPtr recptr;
+
+ recptr = gistXLogUpdate(rel->rd_node, buffer,
+ deletable, ndeletable,
+ NULL, 0, InvalidBuffer);
+
+ PageSetLSN(page, recptr);
+ }
+ else
+ PageSetLSN(page, gistGetFakeLSN(rel));
+
+ END_CRIT_SECTION();
+ }
+
+ /*
+ * Note: if we didn't find any LP_DEAD items, then the page's
+ * F_HAS_GARBAGE hint bit is falsely set. We do not bother expending a
+ * separate write to clear it, however. We will clear it when we split
+ * the page.
+ */
+}
diff --git a/src/backend/access/gist/gistget.c b/src/backend/access/gist/gistget.c
index 20f695c..8a8d121 100644
--- a/src/backend/access/gist/gistget.c
+++ b/src/backend/access/gist/gistget.c
@@ -24,6 +24,74 @@
#include "utils/memutils.h"
#include "utils/rel.h"
+/*
+ * gistkillitems() -- set LP_DEAD state for items an indexscan caller has
+ * told us were killed.
+ *
+ * We re-read page here, so it's important to check page LSN. If the page
+ * has been modified since the last read (as determined by LSN), we cannot
+ * flag any entries because it is possible that the old entry was vacuumed
+ * away and the TID was re-used by a completely different heap tuple.
+ */
+static void
+gistkillitems(IndexScanDesc scan)
+{
+ GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
+ Buffer buffer;
+ Page page;
+ OffsetNumber offnum;
+ ItemId iid;
+ int i;
+ bool killedsomething = false;
+
+ Assert(so->curBlkno != InvalidBlockNumber);
+ Assert(so->killedItems != NULL);
+
+ buffer = ReadBuffer(scan->indexRelation, so->curBlkno);
+ if (!BufferIsValid(buffer))
+ return;
+
+ LockBuffer(buffer, GIST_SHARE);
+ gistcheckpage(scan->indexRelation, buffer);
+ page = BufferGetPage(buffer);
+
+ /*
+ * If page LSN differs it means that the page was modified since the last read.
+ * killedItems could be not valid so LP_DEAD hints applying is not safe.
+ */
+ if(PageGetLSN(page) != so->curPageLSN)
+ {
+ UnlockReleaseBuffer(buffer);
+ so-&g
Re: [HACKERS] [PATCH] Microvacuum for gist.
04.09.2015 15:11, Teodor Sigaev:
Some notices
1 gistvacuumpage():
OffsetNumber deletable[MaxOffsetNumber];
Seems, MaxOffsetNumber is too much, MaxIndexTuplesPerPage is enough
Fixed.
2 Loop in gistkillitems() for searching heap pointer. It seems to me that
it could be a performance problem. To fix it, it's needed to remember
index tuple's offset number somewhere near
GISTScanOpaqueData->killedItems. And
gistkillitems() will loop over offsets and compare heap pointer from
killedItems and index tuple, if they doesn't match then just skip this
index tuple.
Thanks for suggestion. I've rewritten this function. Now killedItems[]
contains only OffsetNumbers of tuples which we are going to delete.
PageLSN check is enough to ensure that nothing has changed on the page.
Heap pointer recheck is unnecessary. (It's really important for btree,
where tuple could be inserted in the middle of page. But we can't have
such situation for GiST index page).
It works 50% faster than before.
3 Connected with previous, could you show some performance tests?
Perfomance test is attached.
Test is following - portion of tuples is deleted and after that selected
several times.
Without microvacuum. All 'select' queries are executed at about same time
Time: 360,468 ms
Time: 243,197 ms
Time: 238,310 ms
Time: 238,018 ms
With microvacuum. First 'select' invokes gistkillitems(). It's executed
a bit slower than before.
But following queries are executed significantly faster than without
microvacuum.
Time: 368,780 ms
Time: 69,769 ms
Time: 9,545 ms
Time: 12,427 ms
Please, review the patch again. I could have missed something.
P.S. Do I need to write any documentation update?
--
Anastasia Lubennikova
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
*** a/src/backend/access/gist/gist.c
--- b/src/backend/access/gist/gist.c
***
*** 36,41 static bool gistinserttuples(GISTInsertState *state, GISTInsertStack *stack,
--- 36,42
bool unlockbuf, bool unlockleftchild);
static void gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
GISTSTATE *giststate, List *splitinfo, bool releasebuf);
+ static void gistvacuumpage(Relation rel, Page page, Buffer buffer);
#define ROTATEDIST(d) do { \
***
*** 209,214 gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate,
--- 210,226
* because the tuple vector passed to gistSplit won't include this tuple.
*/
is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
+
+ /*
+ * If leaf page is full, try at first to delete dead tuples. And then
+ * check again.
+ */
+ if (is_split && GistPageIsLeaf(page) && GistPageHasGarbage(page))
+ {
+ gistvacuumpage(rel, page, buffer);
+ is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
+ }
+
if (is_split)
{
/* no space for insertion */
***
*** 1440,1442 freeGISTstate(GISTSTATE *giststate)
--- 1452,1523
/* It's sufficient to delete the scanCxt */
MemoryContextDelete(giststate->scanCxt);
}
+
+ /*
+ * gistvacuumpage() -- try to remove LP_DEAD items from the given page.
+ */
+ static void
+ gistvacuumpage(Relation rel, Page page, Buffer buffer)
+ {
+ OffsetNumber deletable[MaxOffsetNumber];
+ int ndeletable = 0;
+ OffsetNumber offnum,
+ minoff,
+ maxoff;
+
+ /*
+ * Scan over all items to see which ones need to be deleted according to
+ * LP_DEAD flags.
+ */
+ maxoff = PageGetMaxOffsetNumber(page);
+ for (offnum = FirstOffsetNumber;
+ offnum <= maxoff;
+ offnum = OffsetNumberNext(offnum))
+ {
+ ItemId itemId = PageGetItemId(page, offnum);
+
+ if (ItemIdIsDead(itemId))
+ deletable[ndeletable++] = offnum;
+ }
+
+ if (ndeletable > 0)
+ {
+ START_CRIT_SECTION();
+
+ PageIndexMultiDelete(page, deletable, ndeletable);
+
+ /*
+ * Mark the page as not containing any LP_DEAD items. This is not
+ * certainly true (there might be some that have recently been marked,
+ * but weren't included in our target-item list), but it will almost
+ * always be true and it doesn't seem worth an additional page scan to
+ * check it. Remember that F_HAS_GARBAGE is only a hint anyway.
+ */
+ GistClearPageHasGarbage(page);
+
+ MarkBufferDirty(buffer);
+
+ /* XLOG stuff */
+ if (RelationNeedsWAL(rel))
+ {
+ XLogRecPtr recptr;
+
+ recptr = gistXLogUpdate(rel->rd_node, buffer,
+ deletable, ndeletable,
+ NULL, 0, InvalidBuffer);
+
+ PageSetLSN(page, recptr);
+ }
+ else
+ PageSetLSN(page, gistGetFakeLSN(rel));
+
+ END_CRIT_SECTION();
+ }
+
+ /*
+ * Note: if we didn't find any LP_DEAD items, then the page's
+ * F_HAS_GARBAGE hint bit is falsely set. We do not bother expending a
+ * separate write to clear it, however. We will clear it when we split
+ * the page.
+ */
+ }
*** a/src/backend/access/gist/gistget.
Re: [HACKERS] PATCH: index-only scans with partial indexes
25.08.2015 20:19, Jeff Janes пишет: On Fri, Jul 10, 2015 at 11:29 AM, Tomas Vondra <tomas.von...@2ndquadrant.com <mailto:tomas.von...@2ndquadrant.com>> wrote: Hi, currently partial indexes end up not using index only scans in most cases, because check_index_only() is overly conservative, as explained in this comment: * XXX this is overly conservative for partial indexes, since we will * consider attributes involved in the index predicate as required even * though the predicate won't need to be checked at runtime. (The same * is true for attributes used only in index quals, if we are certain * that the index is not lossy.) However, it would be quite expensive * to determine that accurately at this point, so for now we take the * easy way out. In other words, unless you include columns from the index predicate to the index, the planner will decide index only scans are not possible. Which is a bit unfortunate, because those columns are not needed at runtime, and will only increase the index size (and the main benefit of partial indexes is size reduction). The attached patch fixes this by only considering clauses that are not implied by the index predicate. The effect is simple: create table t as select i as a, i as b from generate_series(1,1000) s(i); create index tidx_partial on t(b) where a > 1000 and a < 2000; vacuum freeze t; analyze t; explain analyze select count(b) from t where a > 1000 and a < 2000; However, "explain analyze select sum(b) from t where a > 1000 and a < 1999;" still doesn't use the index only scan. Isn't that also implied by the predicate? In this example it doesn't use IndexOnlyScan correctly. If I understand partial indexes right, if index predicate and search clause are not equal, index scan must recheck values when it's fetching them. 'tidx_partial' in example above has no information about 'a' attribute, beside the index->indpred, so it is impossible to recheck qual without referencing to table. In example: create index tidx_partial on t(a) where a > 1000 and a < 2000; explain analyze select sum(a) from t where a > 1000 and a < 1999; it can use IndexOnlyScan. -- Anastasia Lubennikova Postgres Professional: http://www.postgrespro.com The Russian Postgres Company
Re: [HACKERS] [PROPOSAL] Effective storage of duplicates in B-tree index.
01.09.2015 21:23, Peter Geoghegan: On Mon, Aug 31, 2015 at 12:41 AM, Anastasia Lubennikova <a.lubennik...@postgrespro.ru> wrote: Now new B-tree index tuple must be inserted for each table row that we index. It can possibly cause page split. Because of MVCC even unique index could contain duplicates. Storing duplicates in posting list/tree helps to avoid superfluous splits. I'm glad someone is thinking about this, because it is certainly needed. I thought about working on it myself, but there is always something else to do. I should be able to assist with review, though. Thank you) So it seems to be very useful improvement. Of course it requires a lot of changes in B-tree implementation, so I need approval from community. 1. Compatibility. It's important to save compatibility with older index versions. I'm going to change BTREE_VERSION to 3. And use new (posting) features for v3, saving old implementation for v2. Any objections? It might be better to just have a flag bit for pages that are compressed -- there are IIRC 8 free bits in the B-Tree page special area flags variable. But no real opinion on this from me, yet. You have plenty of bitspace to work with to mark B-Tree pages, in any case. Hmm.. If we are talking about storing duplicates in posting lists (and trees) as in GIN, I don't see a way how to apply it to separate pages, while not applying to others. Look some notes below . 2. There are several tricks to handle non-unique keys in B-tree. More info in btree readme (chapter - Differences to the Lehman & Yao algorithm). In the new version they'll become useless. Am I right? I think that the L algorithm makes assumptions for the sake of simplicity, rather than because they really believed that there were real problems. For example, they say that deletion can occur offline or something along those lines, even though that's clearly impractical. They say that because they didn't want to write a paper about deletion within B-Trees, I suppose. See also, my opinion of how they claim to not need read locks [1]. Also, note that despite the fact that the GIN README mentions "Lehman & Yao style right links", it doesn't actually do the L trick of avoiding lock coupling -- the whole point of L -- so that remark is misleading. This must be why B-Tree has much better concurrency than GIN in practice. Yes, thanks for extensive explanation. I mean such tricks as moving right in _bt_findinsertloc(), for example. /*-- * If we will need to split the page to put the item on this page, * check whether we can put the tuple somewhere to the right, * instead. Keep scanning right until we *(a) find a page with enough free space, *(b) reach the last page where the tuple can legally go, or *(c) get tired of searching. * (c) is not flippant; it is important because if there are many * pages' worth of equal keys, it's better to split one of the early * pages than to scan all the way to the end of the run of equal keys * on every insert. We implement "get tired" as a random choice, * since stopping after scanning a fixed number of pages wouldn't work * well (we'd never reach the right-hand side of previously split * pages). Currently the probability of moving right is set at 0.99, * which may seem too high to change the behavior much, but it does an * excellent job of preventing O(N^2) behavior with many equal keys. *-- */ If there is no multiple tuples with the same key, we shouldn't care about it at all. It would be possible to skip these steps in "effective B-tree implementation". That's why I want to change btree_version. So I'm really talking about a slightly different thing -- prefix compression, rather than handling duplicates. Whether or not you should do prefix compression instead of deduplication is certainly not clear to me, but it should be considered. Also, I always imagined that prefix compression would use the highkey as the thing that is offset for each "real" IndexTuple, because it's there anyway, and that's simple. However, I suppose that that means that duplicate handling can't really work in a way that makes duplicates have a fixed cost, which may be a particularly important property to you. You're right, that is two different techniques. 1. Effective storing of duplicates, which I propose, works with equal keys. And allow us to delete repeats. Index tuples are stored like this: IndexTupleData + Attrs (key) | IndexTupleData + Attrs (key) | IndexTupleData + Attrs (key) If all Attrs are equal, it seems reasonable not to repeat them. So we can store it in following structure: MetaData + Attrs (key) | IndexTupleData | IndexTupleData | IndexTupleData It is a posting list. It doesn't require significant changes in index page layout, because we can use ordinary IndexTupleData for meta informa
Re: [HACKERS] [PATCH] Microvacuum for gist.
Hi,
I don't know too much about gist, but did a quick read through. Mostly
spotting some stylistic issues. Please fix those making it easier for
the next reviewer.
Thank you for review! All mentioned issues are fixed.
--
Anastasia Lubennikova
Postgres Professional:http://www.postgrespro.com
The Russian Postgres Company
diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c
index 0e49959..f658831 100644
--- a/src/backend/access/gist/gist.c
+++ b/src/backend/access/gist/gist.c
@@ -36,6 +36,7 @@ static bool gistinserttuples(GISTInsertState *state, GISTInsertStack *stack,
bool unlockbuf, bool unlockleftchild);
static void gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
GISTSTATE *giststate, List *splitinfo, bool releasebuf);
+static void gistvacuumpage(Relation rel, Page page, Buffer buffer);
#define ROTATEDIST(d) do { \
@@ -209,6 +210,17 @@ gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate,
* because the tuple vector passed to gistSplit won't include this tuple.
*/
is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
+
+ /*
+ * If leaf page is full, try at first to delete dead tuples. And then
+ * check again.
+ */
+ if (is_split && GistPageIsLeaf(page) && GistPageHasGarbage(page))
+ {
+ gistvacuumpage(rel, page, buffer);
+ is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
+ }
+
if (is_split)
{
/* no space for insertion */
@@ -1440,3 +1452,72 @@ freeGISTstate(GISTSTATE *giststate)
/* It's sufficient to delete the scanCxt */
MemoryContextDelete(giststate->scanCxt);
}
+
+/*
+ * gistvacuumpage() -- try to remove LP_DEAD items from the given page.
+ */
+static void
+gistvacuumpage(Relation rel, Page page, Buffer buffer)
+{
+ OffsetNumber deletable[MaxOffsetNumber];
+ int ndeletable = 0;
+ OffsetNumber offnum,
+minoff,
+maxoff;
+
+ /*
+ * Scan over all items to see which ones need to be deleted according to
+ * LP_DEAD flags.
+ */
+ maxoff = PageGetMaxOffsetNumber(page);
+ for (offnum = FirstOffsetNumber;
+ offnum <= maxoff;
+ offnum = OffsetNumberNext(offnum))
+ {
+ ItemId itemId = PageGetItemId(page, offnum);
+
+ if (ItemIdIsDead(itemId))
+ deletable[ndeletable++] = offnum;
+ }
+
+ if (ndeletable > 0)
+ {
+ START_CRIT_SECTION();
+
+ PageIndexMultiDelete(page, deletable, ndeletable);
+
+ /*
+ * Mark the page as not containing any LP_DEAD items. This is not
+ * certainly true (there might be some that have recently been marked,
+ * but weren't included in our target-item list), but it will almost
+ * always be true and it doesn't seem worth an additional page scan to
+ * check it. Remember that F_HAS_GARBAGE is only a hint anyway.
+ */
+ GistClearPageHasGarbage(page);
+
+ MarkBufferDirty(buffer);
+
+ /* XLOG stuff */
+ if (RelationNeedsWAL(rel))
+ {
+ XLogRecPtr recptr;
+
+ recptr = gistXLogUpdate(rel->rd_node, buffer,
+ deletable, ndeletable,
+ NULL, 0, InvalidBuffer);
+
+ PageSetLSN(page, recptr);
+ }
+ else
+ PageSetLSN(page, gistGetFakeLSN(rel));
+
+ END_CRIT_SECTION();
+ }
+
+ /*
+ * Note: if we didn't find any LP_DEAD items, then the page's
+ * F_HAS_GARBAGE hint bit is falsely set. We do not bother expending a
+ * separate write to clear it, however. We will clear it when we split
+ * the page.
+ */
+}
diff --git a/src/backend/access/gist/gistget.c b/src/backend/access/gist/gistget.c
index 20f695c..e655a05 100644
--- a/src/backend/access/gist/gistget.c
+++ b/src/backend/access/gist/gistget.c
@@ -24,6 +24,97 @@
#include "utils/memutils.h"
#include "utils/rel.h"
+/*
+ * gistkillitems() -- set LP_DEAD state for items an indexscan caller has
+ * told us were killed.
+ *
+ * We match items by heap TID before mark them. If an item has moved off
+ * the current page due to a split, we'll fail to find it and do nothing
+ * (this is not an error case --- we assume the item will eventually get
+ * marked in a future indexscan).
+ *
+ * We re-read page here, so it's important to check page LSN. If the page
+ * has been modified since the last read (as determined by LSN), we cannot
+ * flag any antries because it is possible that the old entry was vacuumed
+ * away and the TID was re-used by a completely different heap tuple.
+ */
+static void
+gistkillitems(IndexScanDesc scan)
+{
+ GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
+ Buffer buffer;
+ Page page;
+ OffsetNumber minoff;
+ OffsetNumber maxoff;
+ int i;
+ bool killedsomething = false;
+
+ Assert(so->curBlkno != InvalidBlockNumber);
+
+ buffer = ReadBuffer(scan->indexRelation, so->curBlkno);
+ if (!BufferIsValid(buffer))
+ return;
+
+ LockBuffer(buffer, GIST_SHARE);
+ gistcheckpage(scan->indexRelation, buffer);
+ page = BufferGetPage(buffer);
+
+ /*
+ * If page LSN differs it means that the page was modified since the last read.
+ * killedItemes could be not valid so LP_DEA
Re: [HACKERS] Should \o mean "everything?"
31.08.2015 23:25, David Fetter пишет: On Mon, Aug 31, 2015 at 07:18:02PM +, Kevin Grittner wrote: David Fetter <da...@fetter.org> wrote: In a failed attempt to send the output of \pset to a pipe, I noticed that for reasons I find difficult to explain, not every output gets redirected with \o. At first blush, I'd consider this inconsistency as a bug. What have I missed? The documentation says: | Arranges to save future query results to the file filename or | pipe future results to the shell command command. If no argument | is specified, the query output is reset to the standard output. | | "Query results" includes all tables, command responses, and | notices obtained from the database server, as well as output of | various backslash commands that query the database (such as \d), | but not error messages. Are you seeing anything inconsistent with the documentation? If so, what? Perhaps an example would help clarify... postgres=# \o | perl -pE 's/^/PREFIXED!/' postgres=# \dt postgres=# PREFIXED!No relations found. postgres=# \set AUTOCOMMIT = 'on' ON_ERROR_STOP = '' PROMPT1 = '%/%R%# ' PROMPT2 = '%/%R%# ' PROMPT3 = '>> ' VERBOSITY = 'default' VERSION = 'PostgreSQL 9.4.4 on x86_64-unknown-linux-gnu, compiled by gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2, 64-bit' DBNAME = 'postgres' USER = 'postgres' HOST = '/var/run/postgresql' PORT = '5432' ENCODING = 'UTF8' PSQL_EDITOR = '"/usr/local/bin/vim"' Cheers, David. Thanks for your test case. It made the question clear. That's definitely not a bug. Just not use case of "\o" command. Maybe documentation is a bit vague here. | "Query results" includes <...> output of various backslash commands that query the database (such as \d), | but not error messages. As I understand, this phrase means ONLY those commands which starts with '\d' (such as \dt, \di, \des etc.) -- Anastasia Lubennikova 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
[HACKERS] [PROPOSAL] Effective storage of duplicates in B-tree index.
Hi, hackers! I'm going to begin work on effective storage of duplicate keys in B-tree index. The main idea is to implement posting lists and posting trees for B-tree index pages as it's already done for GIN. In a nutshell, effective storing of duplicates in GIN is organised as follows. Index stores single index tuple for each unique key. That index tuple points to posting list which contains pointers to heap tuples (TIDs). If too many rows having the same key, multiple pages are allocated for the TIDs and these constitute so called posting tree. You can find wonderful detailed descriptions in gin readme <https://github.com/postgres/postgres/blob/master/src/backend/access/gin/README> and articles <http://www.cybertec.at/gin-just-an-index-type/>. It also makes possible to apply compression algorithm to posting list/tree and significantly decrease index size. Read more in presentation (part 1) <http://www.pgcon.org/2014/schedule/attachments/329_PGCon2014-GIN.pdf>. Now new B-tree index tuple must be inserted for each table row that we index. It can possibly cause page split. Because of MVCC even unique index could contain duplicates. Storing duplicates in posting list/tree helps to avoid superfluous splits. So it seems to be very useful improvement. Of course it requires a lot of changes in B-tree implementation, so I need approval from community. 1. Compatibility. It's important to save compatibility with older index versions. I'm going to change BTREE_VERSION to 3. And use new (posting) features for v3, saving old implementation for v2. Any objections? 2. There are several tricks to handle non-unique keys in B-tree. More info in btree readme <https://github.com/postgres/postgres/blob/master/src/backend/access/nbtree/README> (chapter - Differences to the Lehman & Yao algorithm). In the new version they'll become useless. Am I right? 3. Microvacuum. Killed items are marked LP_DEAD and could be deleted from separate page at time of insertion. Now it's fine, because each item corresponds with separate TID. But posting list implementation requires another way. I've got two ideas: First is to mark LP_DEAD only those tuples where all TIDs are not visible. Second is to add LP_DEAD flag to each TID in posting list(tree). This way requires a bit more space, but allows to do microvacuum of posting list/tree. Which one is better? -- Anastasia Lubennikova Postgres Professional:http://www.postgrespro.com The Russian Postgres Company
Re: [HACKERS] Adding since-version tags to the docs?
31.08.2015 14:06, Shulgin, Oleksandr пишет: Hello, I often find it pity that our docs are missing any information on since when a certain GUC setting, SQL-level command or function was introduced. Clicking through the "this page in other versions" links at the top of a webpage does help, but you still need to do some guessing (binary search?) with the clicks. :-) It would be nice if we could make a script that would parse the sgml files and for every symbol it finds it would add a tag like "Since version 9.x". Such a script could start by checking out REL9_0_STABLE and looking through all symbols it can find, tagging them "Since 9.0". Then it could commit the result, check out the next version branch and apply said commit (some manual effort to merge it might be required), and repeat the process, assuming all newly found symbols must be introduced in this new version. That is for the lists, tabular representation might require adding a new column, I'm not sure what would be the best format. After this process is done once, we can have a requirement that every newly introduced symbol/command be tagged manually by the patch author. Do you think such approach will work? Is there interest in having this done? -- Alex I think that you're looking for Feature matrix <http://www.postgresql.org/about/featurematrix/>. -- Anastasia Lubennikova Postgres Professional: http://www.postgrespro.com The Russian Postgres Company
Re: [HACKERS] How to compare different datums within from a tuple?
Can someone tell me, how I can compare two datum fields, when I do not
know the data type in advance inside an executor function?
In a nutshell, there is no way to compare Datums.
Datum is an abstact data type. It's the backend internal representation of
a single value of any SQL data type.
The code using Datum has to know which type it is, since the Datum itself
doesn't contain that information.
For example, x less than y where x and y are of various types that form
intervals. I have found the method ExecTuplesMatch, but it is only for
equality comparison, I think. Another one is ApplySortComparator... maybe
that's the correct way to go?
Some code to make things clearer...
Datum x = heap_getattr(out-tts_tuple,
node-xpos,
out-tts_tupleDescriptor,
isNull1);
Datum y = slot_getattr(curr, node-ypos, isNull2);
if (compareDatumWithCorrectMethod(x,y) 0)
{
/* do something */
}
Thx,
Peter
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Maybe you can use DatumGetXXX function to extract value. For example,
DatumGetInt32.
http://doxygen.postgresql.org/postgres_8h.html#aacbc8a3ac6d52d85feaf0b7ac1b1160c
--
Best regards,
Lubennikova Anastasia
Re: [HACKERS] [PATCH] Microvacuum for gist.
On Mon, Aug 3, 2015 at 12:27 PM, Anastasia Lubennikova
a.lubennik...@postgrespro.ru mailto:a.lubennik...@postgrespro.ru
wrote:
1) Test and results are in attachments. Everything seems to work
as expected.
2) I dropped these notices. It was done only for debug purposes.
Updated patch is attached.
3) fixed
Good! Another couple of notes from me:
1) I think gistvacuumpage() and gistkillitems() need function-level
comments.
2) ItemIdIsDead() can be used in index scan like it's done
in _bt_checkkeys().
--
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
http://www.postgrespro.com/
The Russian Postgres Company
I've added some comments.
ItemIdIsDead() is used now (just skip dead tuples as not matching the
quals).
And there is one else check of LSN in gistkillitems to make sure that
page was not changed between reads.
--
Anastasia Lubennikova
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
*** a/src/backend/access/gist/gist.c
--- b/src/backend/access/gist/gist.c
***
*** 36,42 static bool gistinserttuples(GISTInsertState *state,
GISTInsertStack *stack,
bool unlockbuf, bool unlockleftchild);
static void gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
GISTSTATE *giststate, List *splitinfo, bool
releasebuf);
!
#define ROTATEDIST(d) do { \
SplitedPageLayout
*tmp=(SplitedPageLayout*)palloc(sizeof(SplitedPageLayout)); \
--- 36,42
bool unlockbuf, bool unlockleftchild);
static void gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
GISTSTATE *giststate, List *splitinfo, bool
releasebuf);
! static void gistvacuumpage(Relation rel, Page page, Buffer buffer);
#define ROTATEDIST(d) do { \
SplitedPageLayout
*tmp=(SplitedPageLayout*)palloc(sizeof(SplitedPageLayout)); \
***
*** 209,214 gistplacetopage(Relation rel, Size freespace, GISTSTATE
*giststate,
--- 209,225
* because the tuple vector passed to gistSplit won't include this
tuple.
*/
is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
+
+ /*
+* If leaf page is full, try at first to delete dead tuples. And then
+* check again.
+*/
+ if ((is_split) GistPageIsLeaf(page) GistPageHasGarbage(page))
+ {
+ gistvacuumpage(rel, page, buffer);
+ is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
+ }
+
if (is_split)
{
/* no space for insertion */
***
*** 1440,1442 freeGISTstate(GISTSTATE *giststate)
--- 1451,1522
/* It's sufficient to delete the scanCxt */
MemoryContextDelete(giststate-scanCxt);
}
+
+ /*
+ * gistvacuumpage() -- try to remove LP_DEAD items from the given page.
+ */
+ static void
+ gistvacuumpage(Relation rel, Page page, Buffer buffer)
+ {
+ OffsetNumber deletable[MaxOffsetNumber];
+ int ndeletable = 0;
+ OffsetNumber offnum,
+ minoff,
+ maxoff;
+
+ /*
+* Scan over all items to see which ones need to be deleted according to
+* LP_DEAD flags.
+*/
+ maxoff = PageGetMaxOffsetNumber(page);
+ for (offnum = FirstOffsetNumber;
+offnum = maxoff;
+offnum = OffsetNumberNext(offnum))
+ {
+ ItemId itemId = PageGetItemId(page, offnum);
+
+ if (ItemIdIsDead(itemId))
+ deletable[ndeletable++] = offnum;
+ }
+
+ if (ndeletable 0)
+ {
+ START_CRIT_SECTION();
+
+ PageIndexMultiDelete(page, deletable, ndeletable);
+
+ /*
+* Mark the page as not containing any LP_DEAD items. This is
not
+* certainly true (there might be some that have recently been
marked,
+* but weren't included in our target-item list), but it will
almost
+* always be true and it doesn't seem worth an additional page
scan to
+* check it. Remember that F_HAS_GARBAGE is only a hint anyway.
+*/
+ GistClearPageHasGarbage(page);
+
+ MarkBufferDirty(buffer);
+
+ /* XLOG stuff */
+ if (RelationNeedsWAL(rel))
+ {
+ XLogRecPtr recptr;
+
+ recptr = gistXLogUpdate(rel-rd_node, buffer,
+
deletable, ndeletable,
+ NULL,
0, InvalidBuffer);
+
+ PageSetLSN(page, recptr);
+ }
+ else
Re: [HACKERS] [PATCH] Microvacuum for gist.
30.07.2015 16:33, Alexander Korotkov пишет:
Hi!
On Thu, Jul 30, 2015 at 2:51 PM, Anastasia Lubennikova
lubennikov...@gmail.com mailto:lubennikov...@gmail.com wrote:
I have written microvacuum support for gist access method.
Briefly microvacuum includes two steps:
1. When search tells us that the tuple is invisible to all
transactions it is marked LP_DEAD and page is marked as has dead
tuples,
2. Then, when insert touches full page which has dead tuples it
calls microvacuum instead of splitting page.
You can find a kind of review here [1].
[1]
http://www.google-melange.com/gsoc/proposal/public/google/gsoc2015/ivanitskiy_ilya/5629499534213120
Patch is in attachements. Please review it.
Nice!
Some notes about this patch.
1) Could you give same test case demonstrating that microvacuum really
work with patch? Finally, we should get index less growing with
microvacuum.
2) Generating notices for every dead tuple would be too noisy. I
suggest to replace notice with one of debug levels.
+ elog(NOTICE, gistkillitems. Mark Item Dead offnum %hd, blkno %d,
offnum, BufferGetBlockNumber(buffer));
3) Please, recheck coding style. For instance, this line needs more
spaces and open brace should be on the next line.
+ if ((scan-kill_prior_tuple)(so-curPageData
0)(so-curPageData == so-nPageData)) {
--
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
http://www.postgrespro.com/
The Russian Postgres Company
1) Test and results are in attachments. Everything seems to work as
expected.
2) I dropped these notices. It was done only for debug purposes. Updated
patch is attached.
3) fixed
//
--
Anastasia Lubennikova
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
*** a/src/backend/access/gist/gist.c
--- b/src/backend/access/gist/gist.c
***
*** 36,42 static bool gistinserttuples(GISTInsertState *state,
GISTInsertStack *stack,
bool unlockbuf, bool unlockleftchild);
static void gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
GISTSTATE *giststate, List *splitinfo, bool
releasebuf);
!
#define ROTATEDIST(d) do { \
SplitedPageLayout
*tmp=(SplitedPageLayout*)palloc(sizeof(SplitedPageLayout)); \
--- 36,42
bool unlockbuf, bool unlockleftchild);
static void gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
GISTSTATE *giststate, List *splitinfo, bool
releasebuf);
! static void gistvacuumpage(Relation rel, Page page, Buffer buffer);
#define ROTATEDIST(d) do { \
SplitedPageLayout
*tmp=(SplitedPageLayout*)palloc(sizeof(SplitedPageLayout)); \
***
*** 209,214 gistplacetopage(Relation rel, Size freespace, GISTSTATE
*giststate,
--- 209,225
* because the tuple vector passed to gistSplit won't include this
tuple.
*/
is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
+
+ /*
+* If leaf page is full, try at first to delete dead tuples. And then
+* check again.
+*/
+ if ((is_split) GistPageIsLeaf(page) GistPageHasGarbage(page))
+ {
+ gistvacuumpage(rel, page, buffer);
+ is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
+ }
+
if (is_split)
{
/* no space for insertion */
***
*** 1440,1442 freeGISTstate(GISTSTATE *giststate)
--- 1451,1519
/* It's sufficient to delete the scanCxt */
MemoryContextDelete(giststate-scanCxt);
}
+
+ static void
+ gistvacuumpage(Relation rel, Page page, Buffer buffer)
+ {
+ OffsetNumber deletable[MaxOffsetNumber];
+ int ndeletable = 0;
+ OffsetNumber offnum,
+ minoff,
+ maxoff;
+
+ /*
+* Scan over all items to see which ones need to be deleted according to
+* LP_DEAD flags.
+*/
+ maxoff = PageGetMaxOffsetNumber(page);
+ for (offnum = FirstOffsetNumber;
+offnum = maxoff;
+offnum = OffsetNumberNext(offnum))
+ {
+ ItemId itemId = PageGetItemId(page, offnum);
+
+ if (ItemIdIsDead(itemId))
+ deletable[ndeletable++] = offnum;
+ }
+
+ if (ndeletable 0)
+ {
+ START_CRIT_SECTION();
+
+ PageIndexMultiDelete(page, deletable, ndeletable);
+
+ /*
+* Mark the page as not containing any LP_DEAD items. This is
not
+* certainly true (there might be some that have recently been
marked,
+* but weren't included in our target-item list), but it will
almost
+* always be true and it doesn't seem worth an additional
[HACKERS] [PATCH] Microvacuum for gist.
Hi, I have written microvacuum support for gist access method. Briefly microvacuum includes two steps: 1. When search tells us that the tuple is invisible to all transactions it is marked LP_DEAD and page is marked as has dead tuples, 2. Then, when insert touches full page which has dead tuples it calls microvacuum instead of splitting page. You can find a kind of review here [1]. [1] http://www.google-melange.com/gsoc/proposal/public/google/gsoc2015/ivanitskiy_ilya/5629499534213120 Patch is in attachements. Please review it. -- Best regards, Lubennikova Anastasia microvacuum_for_gist.patch Description: Binary data -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] Microvacuum for gist. Question about GISTPageOpaqueData flag
Hi, I'm working on microvacuum for gist access method. Briefly microvacuum includes two steps: 1. When search tells us that the tuple is invisible to all transactions it is marked LP_DEAD and page is marked as has dead tuples, 2. Then, when insert touches full page which has dead tuples it calls microvacuum instead of splitting page. You can find a kind of review here [1]. While writing patch, I found strange GISTPageOpaqueData flag - F_TUPLES_DELETED http://doxygen.postgresql.org/gist_8h.html#a23812efd70313b9b10ae61376e2594f6 . Its description looks like it is the same for BTP_HAS_GARBAGE http://doxygen.postgresql.org/nbtree_8h.html#a3b7c77849276ff8617edc1f84441c230 #define F_TUPLES_DELETED (1 2) /* some tuples on the page are dead */ #define BTP_HAS_GARBAGE (1 6) /* page has LP_DEAD tuples */ But it's definitely not the same things. I found only two mentions of this flag. Function GistMarkTuplesDeleted http://doxygen.postgresql.org/gist_8h.html#a96fc3c6bb5aecfc8d2818b7010d68aac sets the flag after dead tuples deletion. Do anyone need it at all? I found no place where this flag is checked. Is it correct using of the flag? I need an advice, what would be better: - to add new flag like F_HAS_GARBAGE, - or to delete all mentions of F_TUPLES_DELETED and use it in gist microvacuum. [1] http://www.google-melange.com/gsoc/proposal/public/google/gsoc2015/ivanitskiy_ilya/5629499534213120 -- Best regards, Lubennikova Anastasia
Re: [HACKERS] Microvacuum for gist. Question about GISTPageOpaqueData flag
2015-07-27 20:05 GMT+04:00 Heikki Linnakangas hlinn...@iki.fi: On 07/27/2015 06:46 PM, Teodor Sigaev wrote: I need an advice, what would be better: - to add new flag like F_HAS_GARBAGE, - or to delete all mentions of F_TUPLES_DELETED and use it in gist microvacuum. According to commit message: commit 2effb72e682a7dbdc9a8a60a80c22ec1fa9d8079 Author: Heikki Linnakangas heikki.linnakan...@iki.fi Date: Fri Nov 7 15:03:46 2014 +0200 .. The code that generated a record to clear the F_TUPLES_DELETED flag hasn't existed since we got rid of old-style VACUUM FULL. I kept the code that sets the flag, although it's not used for anything anymore, because it might still be interesting information for debugging purposes that some tuples have been deleted from a page. .. If Heikki doesn't change his opinion then introduce new flag. Although I don't think that we need to keep F_TUPLES_DELETED. It's certainly not needed for anything at the moment, although conceivably we might reintroduce code that needs it in the future. There are plenty of flag bits available, so let's use a new flag. If there was a shortage, I wouldn't blink reusing F_TUPLES_DELETED. - Heikki Thanks for the quick reply -- Best regards, Lubennikova Anastasia
[HACKERS] Wrong Assert in PageIndexMultiDelete?
Hi, hackers! I am trying to create new index access method. And I found strange Assert in PageIndexMultiDelete http://doxygen.postgresql.org/bufpage_8c_source.html#l00791 function. Assert http://doxygen.postgresql.org/c_8h.html#a706ac5b1a53bd04067f81924b92cb9f6(nitems MaxIndexTuplesPerPage http://doxygen.postgresql.org/itup_8h.html#adb7c94e95ce112eb47d71f7797604ddb ); Is '' sign is correct? I thougt it should be '='. Is it a bug or just my misunderstanding? -- Best regards, Lubennikova Anastasia
Re: [HACKERS] GSoC 2015 proposal. Bitmap Index-only Count
2015-03-24 18:01 GMT+04:00 Tom Lane t...@sss.pgh.pa.us: Anastasia Lubennikova lubennikov...@gmail.com writes: There is a problem of slow counting in PostgreSQL [1]. The reason why this is slow is related to the *MVCC* implementation in PostgreSQL. Index-only scans (implemented since PostgreSQL-9.2) providing some performance improvements where the *visibility map* of the table allows it. That’s good. But it works only for access methods which provide amgettuple method. Unfortunately GIN supports only BitmapIndexScan and has no implementation of index_getnext() interface [2]. Right ... As a GSoC student I will create new Node “Bitmap Index-Only Scan”, which would catch tuples from Bitmap Index Scan node and pass them to Aggregate node. Thus, new query plan will be as follow: I'm pretty hesitant about adding a whole new plan node type (which will require quite a lot of infrastructure) for such a narrow use-case. I think the odds are good that if you proceed down this path, you will end up with something that never gets committed to Postgres. Thanks a lot for reply. It was just approximate idea. I thought is wasn't very good. I wonder whether it'd be possible to teach GIN to support index_getnext instead. Initially it would probably work only for cases where the index didn't have to return any columns ... but if we did it, maybe the door would be open to cases where GIN could reconstruct actual values. Another idea is to write index_getnext() for GIN which would return some fake tuple. Since there is no difference for COUNT aggregate what the tuple contains. COUNT just wants to know whether we have tuple that satisfy the qual. Is this idea better? Is it possible for planner to use index_getnext() for GIN only with COUNT aggregate? -- Best regards, Lubennikova Anastasia
[HACKERS] GSoC 2015 proposal. Bitmap Index-only Count
Hi, hackers!
Here is the text of my proposal which I've applied to GSoC.
(and link
http://www.google-melange.com/gsoc/proposal/public/google/gsoc2015/lubennikovaav/5657382461898752
)
Any suggestions and comments are welcome.
*Project name*
Bitmap Index-only Count
*Brief review*
There is a problem of slow counting in PostgreSQL [1]. The reason why this
is slow is related to the *MVCC* implementation in PostgreSQL. Index-only
scans (implemented since PostgreSQL-9.2) providing some performance
improvements where the *visibility map* of the table allows it. That’s
good. But it works only for access methods which provide amgettuple method.
Unfortunately GIN supports only BitmapIndexScan and has no implementation
of index_getnext() interface [2]. Idea of the proposal is to implement
Bitmap Index-Only Count method that allows to count elements, without
reference to the heap.
*Benefits to the PostgreSQL Community*
Faster count(*) would be actual for GIN. Probably it would accelerate
count(*) for other access methods too, but I do not sure if it would be
significant difference.
*Quantifiable results*
Acceleration of count(*) queries with WHERE clause which use GIN.
*Project details*
Let’s look at count(*) query:
EXPLAIN SELECT count(*) from tbl_mytbl where val @ '{b:2}';
Now the query plan looks like this:
Aggregate
- Bitmap Heap Scan on tbl_mytbl
Recheck Cond: (val @ '{b: 2}'::jsonb)
- Bitmap Index Scan on idx_mytbl
Index Cond: (val @ '{b: 2}'::jsonb)
Idea of the proposal is to implement Bitmap Index-Only Count method that
allows to count elements, without reference to the heap.
Conditions:
- all tuples are visible (the same problem as for Index-only count(*));
- result TIDBitmap is not lossy. nchunks = 0;
int nchunks
http://doxygen.postgresql.org/structTIDBitmap.html#a85d5883056bad6863cb47a15446581c7;
/* number of lossy entries in pagetable */
- pages in TIDBitmap don’t require recheck
* recheck is used only on exact pages --- it indicates that although
* only the stated tuples need be checked, the full index qual condition
* must be checked for each (ie, these are candidate matches).
If all conditions are true, it’s possible to call aggregate COUNT function
for each tuple from TIDBitmap returned by Bitmap Index Scan (or
BitmapAnd/BitmapOr nodes). And there’s no necessity to call Bitmap Heap
Scan.
As a GSoC student I will create new Node “Bitmap Index-Only Scan”, which
would catch tuples from Bitmap Index Scan node and pass them to Aggregate
node. Thus, new query plan will be as follow:
Aggregate
- Bitmap Index-only Count
- Bitmap Index Scan on idx_mytbl
Index Cond: (val @ '{b: 2}'::jsonb)
*Project Schedule*
until May 25
Read documentation and source code, clarify details of implementation.
until June 30
Implement Bitmap Index-only Count node.
1 July – 31 July
Add Bitmap Index-only Count node to Planner.
1 August -15 August
Final refactoring, testing and submitting a patch.
*Links*
1. https://wiki.postgresql.org/wiki/Slow_Counting
2.
http://postgresql.nabble.com/Todo-item-Support-amgettuple-in-GIN-td5780810.html
--
Best regards,
Lubennikova Anastasia
Re: [HACKERS] Index-only scans for GiST.
I add MemoryContext listCxt to avoid memory leak. listCxt is created once in gistrescan (only for index-only scan plan ) and reseted when scan of the leaf page is finished. I do not sure if the problem was completely solved, so I wait for feedback. * What's the reason for turning GISTScanOpaqueData.pageData from an array to a List? This array is field of structure GISTScanOpaqueData. Memory for that structure allocated in function gistbeginscan(). The array is static so it's declared only one time in structure: GISTSearchHeapItem pageData [BLCKSZ/sizeof(IndexTupleData)] But how could we know size of array if we don't know what data would be returned? I mean type and amount. I asked Alexander about that and he offered me to use List instead of Array. indexonlyscan_gist_2.2.patch Description: Binary data indexonlyscan_gist_docs.patch Description: Binary data test_performance.sql Description: Binary data -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Index-only scans for GiST.
Thanks for answer.
Now it seems to be applied correctly.
2015-02-12 3:12 GMT+04:00 Thom Brown t...@linux.com:
On 11 February 2015 at 22:50, Anastasia Lubennikova
lubennikov...@gmail.com wrote:
Finally there is a new version of patch (in attachments).
It provides multicolumn index-only scan for GiST indexes.
- Memory leak is fixed.
- little code cleanup
- example of performance test in attachmens
- function OIDs have debugging values (*) just to avoid merge
conflicts while testing patch
Wiki page of the project is
https://wiki.postgresql.org/wiki/Support_for_Index-only_scans_for_GIST_GSoC_2014
Waiting for feedback.
Hi Anastasia. Thanks for the updated patch. I've just tried applying it
to head and it doesn't appear to apply cleanly.
$ patch -p1 ~/Downloads/indexonlyscan_gist_2.0.patch
(Stripping trailing CRs from patch; use --binary to disable.)
patching file src/backend/access/gist/gist.c
Hunk #1 succeeded at 1404 (offset 9 lines).
Hunk #2 succeeded at 1434 (offset 9 lines).
(Stripping trailing CRs from patch; use --binary to disable.)
patching file src/backend/access/gist/gistget.c
Hunk #1 succeeded at 227 (offset 1 line).
Hunk #2 succeeded at 243 (offset 1 line).
Hunk #3 succeeded at 293 (offset -4 lines).
Hunk #4 succeeded at 330 (offset -4 lines).
Hunk #5 succeeded at 365 (offset -5 lines).
Hunk #6 succeeded at 444 (offset -27 lines).
Hunk #7 succeeded at 474 (offset -27 lines).
Hunk #8 FAILED at 518.
Hunk #9 succeeded at 507 (offset -28 lines).
Hunk #10 succeeded at 549 with fuzz 1 (offset -28 lines).
Hunk #11 FAILED at 601.
2 out of 11 hunks FAILED -- saving rejects to file
src/backend/access/gist/gistget.c.rej
...
--
Thom
--
Best regards,
Lubennikova Anastasia
diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c
index db2a452..53750da 100644
--- a/src/backend/access/gist/gist.c
+++ b/src/backend/access/gist/gist.c
@@ -1404,6 +1404,14 @@ initGISTstate(Relation index)
else
giststate-distanceFn[i].fn_oid = InvalidOid;
+ /* opclasses are not required to provide a Fetch method */
+ if (OidIsValid(index_getprocid(index, i + 1, GIST_FETCH_PROC)))
+ fmgr_info_copy((giststate-fetchFn[i]),
+ index_getprocinfo(index, i + 1, GIST_FETCH_PROC),
+ scanCxt);
+ else
+ giststate-fetchFn[i].fn_oid = InvalidOid;
+
/*
* If the index column has a specified collation, we should honor that
* while doing comparisons. However, we may have a collatable storage
@@ -1426,6 +1434,22 @@ initGISTstate(Relation index)
return giststate;
}
+/*
+ * Gistcanreturn is supposed to be true if ANY FetchFn method is defined.
+ * If FetchFn exists it would be used in index-only scan
+ * Thus the responsibility rests with the opclass developer.
+ */
+
+Datum
+gistcanreturn(PG_FUNCTION_ARGS) {
+ Relation index = (Relation) PG_GETARG_POINTER(0);
+ int i = PG_GETARG_INT32(1);
+ if (OidIsValid(index_getprocid(index, i+1, GIST_FETCH_PROC)))
+ PG_RETURN_BOOL(true);
+ else
+ PG_RETURN_BOOL(false);
+}
+
void
freeGISTstate(GISTSTATE *giststate)
{
diff --git a/src/backend/access/gist/gistget.c b/src/backend/access/gist/gistget.c
index 717cb85..0925e56 100644
--- a/src/backend/access/gist/gistget.c
+++ b/src/backend/access/gist/gistget.c
@@ -227,8 +227,10 @@ gistindex_keytest(IndexScanDesc scan,
* If tbm/ntids aren't NULL, we are doing an amgetbitmap scan, and heap
* tuples should be reported directly into the bitmap. If they are NULL,
* we're doing a plain or ordered indexscan. For a plain indexscan, heap
- * tuple TIDs are returned into so-pageData[]. For an ordered indexscan,
+ * tuple TIDs are returned into so-pageData. For an ordered indexscan,
* heap tuple TIDs are pushed into individual search queue items.
+ * If index-only scan is possible, heap tuples themselves are returned
+ * into so-pageData or into search queue.
*
* If we detect that the index page has split since we saw its downlink
* in the parent, we push its new right sibling onto the queue so the
@@ -241,6 +243,10 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
GISTScanOpaque so = (GISTScanOpaque) scan-opaque;
Buffer buffer;
Page page;
+ GISTSTATE *giststate = so-giststate;
+ Relation r = scan-indexRelation;
+ boolisnull[INDEX_MAX_KEYS];
+ GISTSearchHeapItem *tmpListItem;
GISTPageOpaque opaque;
OffsetNumber maxoff;
OffsetNumber i;
@@ -287,8 +293,6 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
MemoryContextSwitchTo(oldcxt);
}
- so-nPageData = so-curPageData = 0;
-
/*
* check all tuples on page
*/
@@ -326,11 +330,20 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
else if (scan-numberOfOrderBys == 0 GistPageIsLeaf(page))
{
/*
- * Non-ordered scan, so report heap tuples in so-pageData[]
+ * Non-ordered scan, so report tuples in so-pageData
+ */
+
+ /* form tmpListItem
[HACKERS] Index-only scans for GiST.
Finally there is a new version of patch (in attachments). It provides multicolumn index-only scan for GiST indexes. - Memory leak is fixed. - little code cleanup - example of performance test in attachmens - function OIDs have debugging values (*) just to avoid merge conflicts while testing patch Wiki page of the project is https://wiki.postgresql.org/wiki/Support_for_Index-only_scans_for_GIST_GSoC_2014 Waiting for feedback. -- Best regards, Lubennikova Anastasia indexonlyscan_gist_2.0.patch Description: Binary data test_performance.sql Description: Binary data indexonlyscan_gist_docs.patch Description: Binary data -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] GSoC 2015 - mentors, students and admins.
I'm interested to participate as student again. -- Best regards, Lubennikova Anastasia
Re: [HACKERS] Index-only scans for GIST
Updated patch * Compiler, merge and regression fails checked * Regression tests was impoved * GiST and amcanreturn docs updated -- Best regards, Lubennikova Anastasia indexonlyscan_gist2.patch Description: Binary data indexonlyscan_gist_docs.patch Description: Binary data -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Index-only scans for GIST
2014-08-07 0:30 GMT+04:00 Heikki Linnakangas hlinnakan...@vmware.com: * I'm getting two regression failures with this (opr_sanity and join). opr_sanity failure is corrected. But there is remain question with join. I check the latest version of my github repo and there's no fail in join regression test All 145 tests passed. To tell the truth, I don't understand which changes could led to this failure. Could you show me regression diffs? I want to understand what's wrong with the patch. * The regression test queries that use LIMIT are not guaranteed to always return the same rows, hence they're not very good regression test cases. I'd suggest using more restricting WHERE clauses, so that each query only returns a handful of rows. Thank you for comment, I rewrote wrong queries. But could you explain why LIMIT queries may return different results? Is it happens because of different query optimization? * I think it's leaking memory, in GIST scan context. I tested this with a variant of the regression tests: insert into gist_tbl select box(point(0.05*i, 0.05*i), point(0.05*i, 0.05*i)), point(0.05*i, 0.05*i) FROM generate_series(0, 1000) as i; CREATE INDEX gist_tbl_point_index ON gist_tbl USING gist (p); set enable_seqscan=off; set enable_bitmapscan=off; explain analyze select p from gist_tbl where p @ box(point(0,0), point(999,999)) and length(p::text) 10; while the final query runs, 'top' shows constantly increasing memory usage. I don't think it's memory leak. After some increasing, memory using remain the same. It works similar without using indexonlyscan. -- Best regards, Lubennikova Anastasia
[HACKERS] Index-only scans for GIST
Hi, hackers! I work on a GSoC project Index-only scans for GIST https://wiki.postgresql.org/wiki/Support_for_Index-only_scans_for_GIST_GSoC_2014 Repository is https://github.com/lubennikovaav/postgres/tree/indexonlygist2 Patch is in attachments. It includes index-only scans for multicolumn GIST and new regression test. Fetch() method is realized for box and point opclasses. Documentation is not updated yet, but I'm going to do it till the end of GSoC. I've got one question about query with OR condition. It is the last query in regression test gist_indexonly. It doesn't fail but it doensn't use index-only scans. Could someone explain to me how it works? It seems to depend on build_paths_for_OR http://doxygen.postgresql.org/indxpath_8c.html#ae660d2e886355e53ed3b9ec693e4afd2 function. But I couldn't understand how. -- Best regards, Lubennikova Anastasia indexonlyscan_gist.patch Description: Binary data -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Index-only scans for GIST
Thank you for comment Patch is already added in Performance topic. 2014-08-01 20:25 GMT+04:00 Fabrízio de Royes Mello fabriziome...@gmail.com : On Fri, Aug 1, 2014 at 4:58 AM, Anastasia Lubennikova lubennikov...@gmail.com wrote: Hi, hackers! I work on a GSoC project Index-only scans for GIST https://wiki.postgresql.org/wiki/Support_for_Index-only_scans_for_GIST_GSoC_2014 Repository is https://github.com/lubennikovaav/postgres/tree/indexonlygist2 Patch is in attachments. It includes index-only scans for multicolumn GIST and new regression test. Fetch() method is realized for box and point opclasses. Documentation is not updated yet, but I'm going to do it till the end of GSoC. I've got one question about query with OR condition. It is the last query in regression test gist_indexonly. It doesn't fail but it doensn't use index-only scans. Could someone explain to me how it works? It seems to depend on build_paths_for_OR function. But I couldn't understand how. Very nice... please add your patch to the next commit fest [1]. Regards, [1] https://commitfest.postgresql.org/action/commitfest_view?id=23 -- Fabrízio de Royes Mello Consultoria/Coaching PostgreSQL Timbira: http://www.timbira.com.br Blog sobre TI: http://fabriziomello.blogspot.com Perfil Linkedin: http://br.linkedin.com/in/fabriziomello Twitter: http://twitter.com/fabriziomello -- Best regards, Lubennikova Anastasia
[HACKERS] Index-only scans for multicolumn GIST
Hi, hackers! There are new results of my work on GSoC project Index-only scans for GIST. Previous post is here: http://postgresql.1045698.n5.nabble.com/Index-only-scans-for-GIST-td5804892.html Repository is https://github.com/lubennikovaav/postgres/tree/indexonlygist2 Patch is in attachments. It includes indexonlyscan for multicolumn GiST. It works correctly - results are the same with another scan plans. Fetch() method is realized for box and circle opclasses Improvement for circle opclass is not such distinct as for box opclass, because of recheck. I remember that all elog and other bad comments must be fixed before this patch can be committed. Any comments are welcome -- Best regards, Lubennikova Anastasia indexonlygist_2.1.patch Description: Binary data -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] Changes in amcanreturn() interface to support multicolumn indexes
Changes in amcanreturn() interface to support multicolumn indexes. Hi, hackers I work on GSoC project Support_for_Index-only_scans_for_GIST_GSoC_2014 https://wiki.postgresql.org/wiki/Support_for_Index-only_scans_for_GIST_GSoC_2014 There is a question of support multicolumn index only scans for GIST. I need help with this problem. bool amcanreturn() - function to check whether index supports index-only scans. Now it's defined for - B-tree. It always returns true, so there's no questions. - SP-GIST. It doesn't support multicolumn indexes, so there's no problems in spgcanreturn too. - GIST. In first version it works only for onecolumn indexes. gistcanreturn() checks whether fetch() method is defined for column's data type. There is a question of support multicolumn index only scans for GIST. gistcanreturn() can return true if fetch is implemented for all indexed columns and false otherwise. But that's not very good case for multicolumn indexes. I think, it requires extend the interface to add separate columns checking. But I can't understand what kind of changes is required and how would it affect on previous amcanreturn interface. -- Regards, Lubennikova Anastasia
[HACKERS] Index-only scans for GIST
Hi, hackers! There are first results of my work on GSoC project Index-only scans for GIST. 1. Version of my project code is in forked repository https://github.com/lubennikovaav/postgres/tree/indexonlygist2 Patch is in attachments - This version is only for one-column indexes - fetch() method is realized only for box opclass (because it's trivial) 2. I test Index-only scans with SQL script box_test.sql and it works really faster. (results in box_test_out) I'll be glad to get your feedback about this feature. -- Best regards, Lubennikova Anastasia indexonlygist_2.0.patch Description: Binary data box_test.sql Description: Binary data box_test_out.out Description: Binary data -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] GSoC proposal. Index-only scans for GIST
2014-03-18 18:47 GMT+04:00 Robert Haas robertmh...@gmail.com If the fetch() is specified by the developer, then using it, algorithm can retrieve the data directly to output areas at this stage, without reference to the heap. This seems to be the crux of your proposal, but it seems vague: what exactly do you mean by retrieve the data directly to output areas? What data are you going to retrieve and where are you going to put it? I meant Datum that storages in Gist-tree nodes. Now gistgettuple() returns xs_ctup.t_self (item pointer). I'm going to add index-only scan functionality: gistsettuple() will return pointer and Datum itself as xs_itup . So queue will contain both the pointer and the Datum. If visibilitymap_test returns true then Datum from xs_itup would be added into queue. Otherwise page must be scanned. Another question to consider is: which operator classes do you anticipate that this will work for and which ones do you anticipate that it will not work for? Any operator class that lossifies that input data before storing it in the index is presumably doomed, but which ones do that, and which do not? about amcanreturn: I'm going to create function gistcanreturn() = If fetch() is defined for all indexed columns? And last point of my project is to implement fetch() for existing opclasses based on GIST. -- Best regards, Lubennikova Anastasia
[HACKERS] GSoC proposal. Index-only scans for GIST
Hello! Here is the text of my proposal which I've applied to GSoC. (and link http://www.google-melange.com/gsoc/proposal/public/google/gsoc2014/lubennikovaav/5629499534213120) Any suggestions and comments are welcome. *Project name* Support for index-only scans for GIST index *Brief review* Currently GiST index don't have index-only scan functionality. Index-only scans are a major performance feature added to Postgres 9.2. They allow certain types of queries to be satisfied just by retrieving data from indexes, and not from tables. This feature for B-trees (implemented since PostgreSQL-9.2) allows doing certain types of queries significantly faster. This is achieved by reduction in the amount of I/O necessary to satisfy queries. I think it will be useful to implement this feature for user defined data types that use GiST index. *Benefits to the PostgreSQL Community* Faster GiST index search would be actual for many PostgreSQL applications (for example some GIS systems). *Quantifiable results* Acceleration of GiST index search. *Project details* 1. The GiST is a balanced tree structure like a B-tree, containing key, pointer pairs. GiST key is a member of a user-defined class, and represents some property that is true of all data items reachable from the pointer associated with the key. The GiST provides a possibility to create custom data types with indexed access methods and extensible set of queries. There are seven methods that an index operator class for GiST must provide, and an eighth that is optional. -consistent -union -compress -decompress -penalty -picksplit -equal -distance (optional) I'm going to create new optional method fetch() in addition to existing. Thus user can create a method of retrieving data from the index without loss. It will be used when performing search queries to speed data retrieving. 2. gistget algorithm (several parts omitted): Check the key gistindex_keytest() - does this index tuple satisfy the scan key(s)? Scan all items on the GiST index page and insert them into the queue (or directly to output areas) plain scan Heap tuple TIDs are returned into so-pageData[] ordered scan Heap tuple TIDs are pushed into individual search queue items If the fetch() is specified by the developer, then using it, algorithm can retrieve the data directly to output areas at this stage, without reference to the heap. 3. Create function gistcanreturn to check whether fetch() is specified by user. Amcanreturn - Function to check whether index supports index-only scans, or zero if none There is the question of support index-only scans for multicolumn indexes. Probably it would require extend the interface to add separate columns checking. To solve this question I need the community's help. 4. Add details for index only scans into gistcostestimate function *Links* 1) Hellerstein J. M., Naughton J. F., Pfeffer A. Generalized search trees for database systems. - September, 1995. 2) http://www.sai.msu.su/~megera/postgres/gist/ 3) PostgreSQL 9.3.3 Documentation: chapters 11. Indexes, 55. GiST Indexes. -- Best regards, Lubennikova Anastasia
