[PATCH] sort leaf pages by ctid for gist indexes built using sorted method

Started by Aliaksandr Kalenikabout 4 years ago3 messages

akalenik@kontur.io

about 4 years ago

1 attachment(s)

Hi!

With the current implementation, for GiST indexes created by doing multiple
inserts, index tuples match heap tuples order, but it doesn't work that way
for sorted method where index tuples on all levels are ordered using
comparator provided in sortsupport (z-order for geometry type, for
example). This means two tuples that are on the same heap page can be far
apart from one another on an index page, and the heap page may be read
twice and prefetch performance will degrade.

I've created a patch intended to improve that by sorting index tuples by
heap tuples TID order on leaf pages.

Attachments:

gist_sortsupport_sort_leaf_pages_by_ctid.patchapplication/octet-stream; name=gist_sortsupport_sort_leaf_pages_by_ctid.patchDownload

diff --git a/src/backend/access/gist/gistbuild.c b/src/backend/access/gist/gistbuild.c
index baad28c09f..58ef045d4c 100644
--- a/src/backend/access/gist/gistbuild.c
+++ b/src/backend/access/gist/gistbuild.c
@@ -480,6 +480,15 @@ gist_indexsortbuild_pagestate_add(GISTBuildState *state,
 	gistfillbuffer(pagestate->page, &itup, 1, InvalidOffsetNumber);
 }
 
+static int32
+it_cmp(const void *a, const void *b)
+{
+	IndexTuple it1 = *((const IndexTuple *) a);
+	IndexTuple it2 = *((const IndexTuple *) b);
+
+	return ItemPointerCompare(&(it1->t_tid), &(it2->t_tid));
+}
+
 static void
 gist_indexsortbuild_pagestate_flush(GISTBuildState *state,
 									GistSortedBuildPageState *pagestate)
@@ -518,6 +527,18 @@ gist_indexsortbuild_pagestate_flush(GISTBuildState *state,
 	union_tuple = gistunion(state->indexrel, itvec, vect_len,
 							state->giststate);
 	ItemPointerSetBlockNumber(&(union_tuple->t_tid), blkno);
+
+	/*
+	 * Sort index tuples by heap tuple TID within leaf pages
+	 */
+	if (isleaf)
+	{
+		Page sorted_page = PageGetTempPageCopySpecial(pagestate->page);
+		qsort(itvec, vect_len, sizeof(IndexTuple), it_cmp);
+		gistfillbuffer(sorted_page, itvec, vect_len, InvalidOffsetNumber);
+		PageRestoreTempPage(sorted_page, pagestate->page);
+	}
+
 	MemoryContextSwitchTo(oldCtx);
 
 	/*

Andrey Borodin

x4mmm@yandex-team.ru

about 4 years ago

In reply to: Aliaksandr Kalenik (#1)

Re: [PATCH] sort leaf pages by ctid for gist indexes built using sorted method

With the current implementation, for GiST indexes created by doing multiple inserts, index tuples match heap tuples order, but it doesn't work that way for sorted method where index tuples on all levels are ordered using comparator provided in sortsupport (z-order for geometry type, for example). This means two tuples that are on the same heap page can be far apart from one another on an index page, and the heap page may be read twice and prefetch performance will degrade.

I've created a patch intended to improve that by sorting index tuples by heap tuples TID order on leaf pages.

Hi!
Thanks you for the patch. The code looks nice and clean.
From my POV this optimization certainly makes sense.

But can we have some benchmarks showing that this optimization really helps?

I've tried it on my laptop extra build efforts cost us about 5% or CREATE INDEX performance. How big would be benefit for scans that we get?

before patch

postgres=# create table x as select point (random(),random()) from generate_series(1,3000000,1);
SELECT 3000000
postgres=# \timing
Timing is on.
postgres=# create index ON x using gist (point );
CREATE INDEX
Time: 1872,503 ms (00:01,873)
postgres=# create index ON x using gist (point );
CREATE INDEX
Time: 1797,329 ms (00:01,797)
postgres=# create index ON x using gist (point );
CREATE INDEX
Time: 1787,362 ms (00:01,787)
postgres=# create index ON x using gist (point );
CREATE INDEX
Time: 1793,545 ms (00:01,794)
postgres=# create index ON x using gist (point );
CREATE INDEX
Time: 1805,572 ms (00:01,806)

After patch

postgres=# create table x as select point (random(),random()) from generate_series(1,3000000,1);
SELECT 3000000
postgres=# \timing
Timing is on.
postgres=# create index ON x using gist (point );
CREATE INDEX
Time: 2134,448 ms (00:02,134)
postgres=# create index ON x using gist (point );
CREATE INDEX
Time: 1945,978 ms (00:01,946)
postgres=# create index ON x using gist (point );
CREATE INDEX
Time: 1965,045 ms (00:01,965)
postgres=# create index ON x using gist (point );
CREATE INDEX
Time: 1973,248 ms (00:01,973)
postgres=# create index ON x using gist (point );
CREATE INDEX
Time: 1970,578 ms (00:01,971)

Thanks!

Best regards, Andrey Borodin.

Andres Freund

andres@anarazel.de

almost 4 years ago

In reply to: Andrey Borodin (#2)

Re: [PATCH] sort leaf pages by ctid for gist indexes built using sorted method

Hi,

On 2021-12-16 14:49:25 +0500, Andrey Borodin wrote:

With the current implementation, for GiST indexes created by doing multiple inserts, index tuples match heap tuples order, but it doesn't work that way for sorted method where index tuples on all levels are ordered using comparator provided in sortsupport (z-order for geometry type, for example). This means two tuples that are on the same heap page can be far apart from one another on an index page, and the heap page may be read twice and prefetch performance will degrade.

I've created a patch intended to improve that by sorting index tuples by heap tuples TID order on leaf pages.

Thanks you for the patch. The code looks nice and clean.

The patch fails currently doesn't apply: http://cfbot.cputube.org/patch_37_3454.log

But can we have some benchmarks showing that this optimization really helps?

As there hasn't been a response to this even in the last CF, I'm going to mark
this entry as returned with feedback (IMO shouldn't even have been moved to
this CF).

Greetings,

Andres Freund