public inbox for [email protected]help / color / mirror / Atom feed
[PATCH v9 4/8] Propagate changes to indisclustered to child/parents 3+ messages / 3 participants [nested] [flat]
* [PATCH v9 4/8] Propagate changes to indisclustered to child/parents @ 2020-10-07 03:11 Justin Pryzby <[email protected]> 0 siblings, 0 replies; 3+ messages in thread From: Justin Pryzby @ 2020-10-07 03:11 UTC (permalink / raw) --- src/backend/commands/cluster.c | 110 ++++++++++++++++---------- src/backend/commands/indexcmds.c | 2 + src/test/regress/expected/cluster.out | 46 +++++++++++ src/test/regress/sql/cluster.sql | 11 +++ 4 files changed, 126 insertions(+), 43 deletions(-) diff --git a/src/backend/commands/cluster.c b/src/backend/commands/cluster.c index 7d8d1d8a69..dd8014c206 100644 --- a/src/backend/commands/cluster.c +++ b/src/backend/commands/cluster.c @@ -74,6 +74,7 @@ static void rebuild_relation(Relation OldHeap, Oid indexOid, bool verbose); static void copy_table_data(Oid OIDNewHeap, Oid OIDOldHeap, Oid OIDOldIndex, bool verbose, bool *pSwapToastByContent, TransactionId *pFreezeXid, MultiXactId *pCutoffMulti); +static void set_indisclustered(Oid indexOid, bool isclustered, Relation pg_index); static List *get_tables_to_cluster(MemoryContext cluster_context); static List *get_tables_to_cluster_partitioned(MemoryContext cluster_context, Oid indexOid); @@ -513,66 +514,89 @@ check_index_is_clusterable(Relation OldHeap, Oid indexOid, bool recheck, LOCKMOD index_close(OldIndex, NoLock); } +/* + * Helper for mark_index_clustered + * Mark a single index as clustered or not. + * pg_index is passed by caller to avoid repeatedly re-opening it. + */ +static void +set_indisclustered(Oid indexOid, bool isclustered, Relation pg_index) +{ + HeapTuple indexTuple; + Form_pg_index indexForm; + + indexTuple = SearchSysCacheCopy1(INDEXRELID, + ObjectIdGetDatum(indexOid)); + if (!HeapTupleIsValid(indexTuple)) + elog(ERROR, "cache lookup failed for index %u", indexOid); + indexForm = (Form_pg_index) GETSTRUCT(indexTuple); + + /* this was checked earlier, but let's be real sure */ + if (isclustered && !indexForm->indisvalid) + elog(ERROR, "cannot cluster on invalid index %u", indexOid); + + indexForm->indisclustered = isclustered; + CatalogTupleUpdate(pg_index, &indexTuple->t_self, indexTuple); + heap_freetuple(indexTuple); +} + /* * mark_index_clustered: mark the specified index as the one clustered on * - * With indexOid == InvalidOid, will mark all indexes of rel not-clustered. + * With indexOid == InvalidOid, mark all indexes of rel not-clustered. + * Otherwise, mark children of the clustered index as clustered, and parents of + * other indexes as unclustered. + * We wish to maintain the following properties: + * 1) Only one index on a relation can be marked clustered at once + * 2) If a partitioned index is clustered, then all its children must be + * clustered. */ void mark_index_clustered(Relation rel, Oid indexOid, bool is_internal) { - HeapTuple indexTuple; - Form_pg_index indexForm; - Relation pg_index; - ListCell *index; - - /* - * If the index is already marked clustered, no need to do anything. - */ - if (OidIsValid(indexOid)) - { - if (get_index_isclustered(indexOid)) - return; - } + ListCell *lc, *lc2; + List *indexes; + Relation pg_index = table_open(IndexRelationId, RowExclusiveLock); + List *inh = find_all_inheritors(RelationGetRelid(rel), + ShareRowExclusiveLock, NULL); /* * Check each index of the relation and set/clear the bit as needed. + * Iterate over the relation's children rather than the index's children + * since we need to unset cluster for indexes on intermediate children, + * too. */ - pg_index = table_open(IndexRelationId, RowExclusiveLock); - - foreach(index, RelationGetIndexList(rel)) + foreach(lc, inh) { - Oid thisIndexOid = lfirst_oid(index); - - indexTuple = SearchSysCacheCopy1(INDEXRELID, - ObjectIdGetDatum(thisIndexOid)); - if (!HeapTupleIsValid(indexTuple)) - elog(ERROR, "cache lookup failed for index %u", thisIndexOid); - indexForm = (Form_pg_index) GETSTRUCT(indexTuple); + Oid inhrelid = lfirst_oid(lc); + Relation thisrel = table_open(inhrelid, ShareRowExclusiveLock); - /* - * Unset the bit if set. We know it's wrong because we checked this - * earlier. - */ - if (indexForm->indisclustered) + indexes = RelationGetIndexList(thisrel); + foreach (lc2, indexes) { - indexForm->indisclustered = false; - CatalogTupleUpdate(pg_index, &indexTuple->t_self, indexTuple); - } - else if (thisIndexOid == indexOid) - { - /* this was checked earlier, but let's be real sure */ - if (!indexForm->indisvalid) - elog(ERROR, "cannot cluster on invalid index %u", indexOid); - indexForm->indisclustered = true; - CatalogTupleUpdate(pg_index, &indexTuple->t_self, indexTuple); - } + bool isclustered; + Oid thisIndexOid = lfirst_oid(lc2); + List *parentoids = get_rel_relispartition(thisIndexOid) ? + get_partition_ancestors(thisIndexOid) : NIL; - InvokeObjectPostAlterHookArg(IndexRelationId, thisIndexOid, 0, - InvalidOid, is_internal); + /* + * A child of the clustered index must be set clustered; + * indexes which are not children of the clustered index are + * set unclustered + */ + isclustered = (thisIndexOid == indexOid) || + list_member_oid(parentoids, indexOid); + Assert(OidIsValid(indexOid) || !isclustered); + set_indisclustered(thisIndexOid, isclustered, pg_index); + + InvokeObjectPostAlterHookArg(IndexRelationId, thisIndexOid, 0, + InvalidOid, is_internal); + } - heap_freetuple(indexTuple); + list_free(indexes); + table_close(thisrel, ShareRowExclusiveLock); } + list_free(inh); table_close(pg_index, RowExclusiveLock); } diff --git a/src/backend/commands/indexcmds.c b/src/backend/commands/indexcmds.c index 8bc652ecd3..5f8fc2ea16 100644 --- a/src/backend/commands/indexcmds.c +++ b/src/backend/commands/indexcmds.c @@ -25,6 +25,7 @@ #include "catalog/catalog.h" #include "catalog/index.h" #include "catalog/indexing.h" +#include "catalog/partition.h" #include "catalog/pg_am.h" #include "catalog/pg_constraint.h" #include "catalog/pg_inherits.h" @@ -32,6 +33,7 @@ #include "catalog/pg_opfamily.h" #include "catalog/pg_tablespace.h" #include "catalog/pg_type.h" +#include "commands/cluster.h" #include "commands/comment.h" #include "commands/dbcommands.h" #include "commands/defrem.h" diff --git a/src/test/regress/expected/cluster.out b/src/test/regress/expected/cluster.out index c74cfa88cc..1d436dfaae 100644 --- a/src/test/regress/expected/cluster.out +++ b/src/test/regress/expected/cluster.out @@ -495,6 +495,52 @@ Indexes: "clstrpart_idx" btree (a) CLUSTER Number of partitions: 3 (Use \d+ to list them.) +-- Test that it recurses to grandchildren: +\d clstrpart33 + Table "public.clstrpart33" + Column | Type | Collation | Nullable | Default +--------+---------+-----------+----------+--------- + a | integer | | | +Partition of: clstrpart3 DEFAULT +Indexes: + "clstrpart33_a_idx" btree (a) CLUSTER + +ALTER TABLE clstrpart SET WITHOUT CLUSTER; +\d clstrpart33 + Table "public.clstrpart33" + Column | Type | Collation | Nullable | Default +--------+---------+-----------+----------+--------- + a | integer | | | +Partition of: clstrpart3 DEFAULT +Indexes: + "clstrpart33_a_idx" btree (a) + +ALTER TABLE clstrpart CLUSTER ON clstrpart_idx; +\d clstrpart33 + Table "public.clstrpart33" + Column | Type | Collation | Nullable | Default +--------+---------+-----------+----------+--------- + a | integer | | | +Partition of: clstrpart3 DEFAULT +Indexes: + "clstrpart33_a_idx" btree (a) CLUSTER + +-- Check that only one child is marked clustered after marking clustered on a different parent +CREATE INDEX clstrpart1_idx_2 ON clstrpart1(a); +ALTER TABLE clstrpart CLUSTER ON clstrpart_idx; +ALTER TABLE clstrpart1 CLUSTER ON clstrpart1_idx_2; +\d clstrpart1 + Partitioned table "public.clstrpart1" + Column | Type | Collation | Nullable | Default +--------+---------+-----------+----------+--------- + a | integer | | | +Partition of: clstrpart FOR VALUES FROM (1) TO (10) +Partition key: RANGE (a) +Indexes: + "clstrpart1_a_idx" btree (a) + "clstrpart1_idx_2" btree (a) CLUSTER +Number of partitions: 2 (Use \d+ to list them.) + -- Test CLUSTER with external tuplesorting create table clstr_4 as select * from tenk1; create index cluster_sort on clstr_4 (hundred, thousand, tenthous); diff --git a/src/test/regress/sql/cluster.sql b/src/test/regress/sql/cluster.sql index 9bcc77695c..0ded2be1ca 100644 --- a/src/test/regress/sql/cluster.sql +++ b/src/test/regress/sql/cluster.sql @@ -220,6 +220,17 @@ CLUSTER clstrpart1 USING clstrpart1_a_idx; -- partition which is itself partitio CLUSTER clstrpart12 USING clstrpart12_a_idx; -- partition which is itself partitioned, no childs CLUSTER clstrpart2 USING clstrpart2_a_idx; -- leaf \d clstrpart +-- Test that it recurses to grandchildren: +\d clstrpart33 +ALTER TABLE clstrpart SET WITHOUT CLUSTER; +\d clstrpart33 +ALTER TABLE clstrpart CLUSTER ON clstrpart_idx; +\d clstrpart33 +-- Check that only one child is marked clustered after marking clustered on a different parent +CREATE INDEX clstrpart1_idx_2 ON clstrpart1(a); +ALTER TABLE clstrpart CLUSTER ON clstrpart_idx; +ALTER TABLE clstrpart1 CLUSTER ON clstrpart1_idx_2; +\d clstrpart1 -- Test CLUSTER with external tuplesorting -- 2.17.0 --fmvA4kSBHQVZhkR6 Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v9-0005-Invalidate-parent-indexes.patch" ^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: index prefetching @ 2026-01-05 12:21 Konstantin Knizhnik <[email protected]> 0 siblings, 1 reply; 3+ messages in thread From: Konstantin Knizhnik @ 2026-01-05 12:21 UTC (permalink / raw) To: Tomas Vondra <[email protected]>; Peter Geoghegan <[email protected]>; +Cc: Andres Freund <[email protected]>; Thomas Munro <[email protected]>; Nazir Bilal Yavuz <[email protected]>; Robert Haas <[email protected]>; Melanie Plageman <[email protected]>; PostgreSQL Hackers <[email protected]>; Georgios <[email protected]>; Dilip Kumar <[email protected]> On 05/01/2026 2:21 AM, Tomas Vondra wrote: > Even a small fixes overhead can be quite visible for extremely short > queries that can't possibly benefit from prefetching (like the LIMIT 1). > > That's what we were concerned about when we invented this heuristics > (which only prefetches from the 2nd batch). I agree it's crude, no > argument there. I'm not against having something better, as long as we > can make it reliable. I completely agree that we should not create read stream from the very beginning despite to small overhead. My concern is that second batch is not good criteria: depending on key size and position of the first key on the page, it can be too short. > One of the problems with read_stream is that it may look ahead very far > ahead. Much further than the query will need. Imagine an index-only > scan, with 99.99% pages being all-visible. At some point the scan will > hit an item that requires reading the heap page. Which triggers the > look-ahead, and a search for the *next* heap page. > > But that next index entry may be many leafs ahead. And maybe the scan > never even gets to actually need that, which means the work will be > wasted. If the query only needs a couple tuples, this may cause a bad > regression. Sorry, I do not completely understand how it can happen. Read stream can only fetch heap pages which are referenced by TIDs in leave pages (leaf=batch). So read stream can not advance more than TIDs from currently processes leaf page, can it? > IIRC the same thing can happen for plain index scans. You may need to > try with correlated indexes (I think the read_stream callback skips > duplicate TIDs). Another problem is that different TIDs can refer to the same heap page (which happens with clustered index or table populated in key ascending order). But number of SMGR reads criteria also should work good in this case. > When all data is cached in shared buffers, then we do not perform IO at > all. > It means there it doesn't matter whether and when we initialize > read_stream. > We can do it after processing 10 items (current default), or immediately > - it should not affect performance. > And this is what I have tested: performance actually not depends on > `read_stream_threshold` (if data fits in shared buffers). > At least it is within few percents and may be it is just random > fluctuations. > Obviously there is no 25% degradation. > > I'm not sure it's this simple. Even if we perform no physical I/O, the > read_stream callback will need to go through the whole batch and pass > all the items to the read_stream. The data may be cached, but not in > shared buffers, in which case the read_stream will do the IPC etc. You mean that data is present in OS file cache and reading it is fast and will not benefit from AIO? It certainly can happen but it seems to be quite obvious problem of double buffering. > It definitely doesn't mean that it is not possible to find scenario > where this approach with enabling prefetch after processing N items will > show worse performance than master or v5. We just need to properly > choose cache hit rate. But the same is true IMHO for v5 itself: it is > possible to find workload where it will show the same degradation > comparing with master. > > I'm sure such "adversarial" data sets exist, even if we don't have a > good example at hand. The question is how plausible / realistic such > data sets are, though. > > I'm not sure about v5, though. The assumption was the overhead is most > visible for short queries, and once we get to the 2nd batch the query is > expensive enough to to not be affected too much. > > When you say "we just need to properly choose cache hit rate", how would > we do that? And how would we know/determine the optimal threshold? Sorry, may be I was unclear. Saying about "choosing cache hit rate" I didn't not mean to use it for determining proper threshold. I was thinking about the best/worst scenario for index prefetch. Originally in my "benchmark" I considered case when no heap pages are present in shared buffer. In your scenario - size of shared buffers is larger than size of table, so all pages are present in shared buffers. First case is certainly the best scenario for index prefetch where we can expect to get the largest improvement. In your case there is certainly no improvement, but as we can see - overhead is also not so large (just because we do not read any page). I expect that the worst result will be in some intermediate case - when some pages are present in shared buffer, some - not. It will be especially true for "second batch" criteria, because it can happen that we need to read just the single heap page for the whole batch and using read stream for it will just add extra overhead. >> More precise heuristic should IMHO take in account actual number of >> performed disk read. > I'm not sure "disk reads" is the right term. The data may be in page > cache, and we just need to copy them into shared buffers. I agree, but there seems to be no chance to determine if page was actually read from disk or cache. But as I wrote above, it is problem of double buffering. If we can avoid it (i.e. using direct IO), then there will be no such problem. >> Please notice that I do not want to predict number of disk reads - i.e. >> check if candidates for prefetch are present in shared buffers. >> It will really adds significant overhead. I think that it is better to >> use as threshold number of performed reads. >> > Not sure I understand what this says. Can you elaborate? I sent proposed patch in the previous mail. Did you have a chance to look at it? ^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: index prefetching @ 2026-01-05 13:25 Tomas Vondra <[email protected]> parent: Konstantin Knizhnik <[email protected]> 0 siblings, 0 replies; 3+ messages in thread From: Tomas Vondra @ 2026-01-05 13:25 UTC (permalink / raw) To: Konstantin Knizhnik <[email protected]>; Peter Geoghegan <[email protected]>; +Cc: Andres Freund <[email protected]>; Thomas Munro <[email protected]>; Nazir Bilal Yavuz <[email protected]>; Robert Haas <[email protected]>; Melanie Plageman <[email protected]>; PostgreSQL Hackers <[email protected]>; Georgios <[email protected]>; Dilip Kumar <[email protected]> On 1/5/26 13:21, Konstantin Knizhnik wrote: > > On 05/01/2026 2:21 AM, Tomas Vondra wrote: >> Even a small fixes overhead can be quite visible for extremely short >> queries that can't possibly benefit from prefetching (like the LIMIT 1). >> >> That's what we were concerned about when we invented this heuristics >> (which only prefetches from the 2nd batch). I agree it's crude, no >> argument there. I'm not against having something better, as long as we >> can make it reliable. > > I completely agree that we should not create read stream from the very > beginning despite to small overhead. > My concern is that second batch is not good criteria: depending on key > size and position of the first key on the page, it can be too short. > > >> One of the problems with read_stream is that it may look ahead very far >> ahead. Much further than the query will need. Imagine an index-only >> scan, with 99.99% pages being all-visible. At some point the scan will >> hit an item that requires reading the heap page. Which triggers the >> look-ahead, and a search for the *next* heap page. >> >> But that next index entry may be many leafs ahead. And maybe the scan >> never even gets to actually need that, which means the work will be >> wasted. If the query only needs a couple tuples, this may cause a bad >> regression. > > Sorry, I do not completely understand how it can happen. > Read stream can only fetch heap pages which are referenced by TIDs in > leave pages (leaf=batch). > So read stream can not advance more than TIDs from currently processes > leaf page, can it? > Sure it can. It can look multiple leaf pages ahead. Allowing that is one of the points of amgetbatch(). The read_stream is gradually increasing the look-ahead distance, do let's say it increases distance from 4 to 8. Now the callback needs to find 4 more blocks to return to the read stream. For plain index scans, we do skip duplicate blocks. If there's a sequence of index entries pointing to toples on the same heap page, the callback will skip those. This can happen with correlated indexes. The number of tuples on a heap page is limited, so there's an limit of how bad this can get. But it still adds overhead, and forces the callback to look further ahead. For index-only scans it's much worse, because there's no limit on how far the next not-allvisible page is (and maybe there is none). FWIW the "second batch" heuristics does not really fix these issues. The unbounded look-ahead can happen for the later batches, and it's just as bad. The "good" solution would be to have some feedback about how much effort was already used (and then yield control, using the WIP patch). >> IIRC the same thing can happen for plain index scans. You may need to >> try with correlated indexes (I think the read_stream callback skips >> duplicate TIDs). > > Another problem is that different TIDs can refer to the same heap page > (which happens with clustered index or table populated in key ascending > order). Sure, but master does not check that either. It's not clear to me what exactly we should do about that. Should we hold on to ping for a couple recent pages? Or should we just remember the recent blocks, assuming they're still in cache? Or something else? > But number of SMGR reads criteria also should work good in this case. > It might be one of the inputs for the heuristics. But I still don't know what should the heuristics look like exactly. >> When all data is cached in shared buffers, then we do not perform IO at >> all. >> It means there it doesn't matter whether and when we initialize >> read_stream. >> We can do it after processing 10 items (current default), or immediately >> - it should not affect performance. >> And this is what I have tested: performance actually not depends on >> `read_stream_threshold` (if data fits in shared buffers). >> At least it is within few percents and may be it is just random >> fluctuations. >> Obviously there is no 25% degradation. >> >> I'm not sure it's this simple. Even if we perform no physical I/O, the >> read_stream callback will need to go through the whole batch and pass >> all the items to the read_stream. The data may be cached, but not in >> shared buffers, in which case the read_stream will do the IPC etc. > > You mean that data is present in OS file cache and reading it is fast > and will not benefit from AIO? > It certainly can happen but it seems to be quite obvious problem of > double buffering. > Depends. It can benefit from AIO with io_method=worker, because it can parallelize the memcpy() and checksum validation. My point is that the "page cache" is pretty opaque to us. We don't know if a page was read from disk or page cache, which means we can't really calculate cache hit ratio for it. >> It definitely doesn't mean that it is not possible to find scenario >> where this approach with enabling prefetch after processing N items will >> show worse performance than master or v5. We just need to properly >> choose cache hit rate. But the same is true IMHO for v5 itself: it is >> possible to find workload where it will show the same degradation >> comparing with master. >> >> I'm sure such "adversarial" data sets exist, even if we don't have a >> good example at hand. The question is how plausible / realistic such >> data sets are, though. >> >> I'm not sure about v5, though. The assumption was the overhead is most >> visible for short queries, and once we get to the 2nd batch the query is >> expensive enough to to not be affected too much. >> >> When you say "we just need to properly choose cache hit rate", how would >> we do that? And how would we know/determine the optimal threshold? > > Sorry, may be I was unclear. > Saying about "choosing cache hit rate" I didn't not mean to use it for > determining proper threshold. > I was thinking about the best/worst scenario for index prefetch. > Originally in my "benchmark" I considered case when no heap pages are > present in shared buffer. > In your scenario - size of shared buffers is larger than size of table, > so all pages are present in shared buffers. > First case is certainly the best scenario for index prefetch where we > can expect to get the largest improvement. > In your case there is certainly no improvement, but as we can see - > overhead is also not so large (just because we do not read any page). > I expect that the worst result will be in some intermediate case - when > some pages are present in shared buffer, some - not. > It will be especially true for "second batch" criteria, because it can > happen that we need to read just the single heap page for the whole > batch and using read stream for it will just add extra overhead. > True. The case with no data in memory is definitely the best case for index prefetching. With all data in shared buffers we can measure the overhead of read_stream (because it won't really do any prefetching). The in-between cases with a mix of cached / uncached pages can trigger all kinds of weird behaviors in read_stream / AIO. We've seen cases where the distance "collapsed" to ~2.0, which maximizes the overhead with io_method=worker (doing IPC for each block). You could argue that's more an issue in read_stream, of course. And in my last round of testing I haven't seen such cases. But I don't think it got fixed, more likely I haven't generated a suitable data set. >>> More precise heuristic should IMHO take in account actual number of >>> performed disk read. >> I'm not sure "disk reads" is the right term. The data may be in page >> cache, and we just need to copy them into shared buffers. > > I agree, but there seems to be no chance to determine if page was > actually read from disk or cache. > But as I wrote above, it is problem of double buffering. If we can avoid > it (i.e. using direct IO), then there will be no such problem. > True, but most users don't use direct I/O. >>> Please notice that I do not want to predict number of disk reads - i.e. >>> check if candidates for prefetch are present in shared buffers. >>> It will really adds significant overhead. I think that it is better to >>> use as threshold number of performed reads. >>> >> Not sure I understand what this says. Can you elaborate? > > I sent proposed patch in the previous mail. > Did you have a chance to look at it? > Not yet, I'll take a look. regards -- Tomas Vondra ^ permalink raw reply [nested|flat] 3+ messages in thread
end of thread, other threads:[~2026-01-05 13:25 UTC | newest] Thread overview: 3+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2020-10-07 03:11 [PATCH v9 4/8] Propagate changes to indisclustered to child/parents Justin Pryzby <[email protected]> 2026-01-05 12:21 Re: index prefetching Konstantin Knizhnik <[email protected]> 2026-01-05 13:25 ` Re: index prefetching Tomas Vondra <[email protected]>
This inbox is served by agora; see mirroring instructions for how to clone and mirror all data and code used for this inbox