($INBOX_DIR/description missing)help / color / mirror / Atom feed
[PATCH 2/2] review 2+ messages / 2 participants [nested] [flat]
* [PATCH 2/2] review @ 2021-03-09 20:09 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 2+ messages in thread From: Tomas Vondra @ 2021-03-09 20:09 UTC (permalink / raw) --- src/backend/optimizer/path/costsize.c | 77 ++++++++++++++++++++------- src/backend/optimizer/path/pathkeys.c | 14 ++++- 2 files changed, 69 insertions(+), 22 deletions(-) diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index 1639258aaf..f55a4f20e5 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -1755,6 +1755,8 @@ cost_recursive_union(Path *runion, Path *nrterm, Path *rterm) * is_fake_var * Workaround for generate_append_tlist() which generates fake Vars with * varno == 0, that will cause a fail of estimate_num_group() call + * + * XXX Ummm, why would estimate_num_group fail with this? */ static bool is_fake_var(Expr *expr) @@ -1828,27 +1830,53 @@ get_width_cost_multiplier(PlannerInfo *root, Expr *expr) * compute_cpu_sort_cost * compute CPU cost of sort (i.e. in-memory) * + * The main thing we need to calculate to estimate sort CPU costs is the number + * of calls to the comparator functions. The difficulty is that for multi-column + * sorts there may be different data types involved (for some of which the calls + * may be much more expensive). Furthermore, the columns may have very different + * number of distinct values - the higher the number, the fewer comparisons will + * be needed for the following columns. + * + * The algoritm is incremental - we add pathkeys one by one, and at each step we + * estimate the number of necessary comparisons (based on the number of distinct + * groups in the current pathkey prefix and the new pathkey), and the comparison + * costs (which is data type specific). + * + * Estimation of the number of comparisons is based on ideas from two sources: + * + * 1) "Algorithms" (course), Robert Sedgewick, Kevin Wayne [https://algs4.cs.princeton.edu/home/] + * + * 2) "Quicksort Is Optimal For Many Equal Keys" (paper), Sebastian Wild, + * arXiv:1608.04906v4 [cs.DS] 1 Nov 2017. [https://arxiv.org/abs/1608.04906] + * + * In term of that paper, let N - number of tuples, Xi - number of tuples with + * key Ki, then the estimate of number of comparisons is: + * + * log(N! / (X1! * X2! * ..)) ~ sum(Xi * log(N/Xi)) + * + * In our case all Xi are the same because now we don't have any estimation of + * group sizes, we have only know the estimate of number of groups (distinct + * values). In that case, formula becomes: + * + * N * log(NumberOfGroups) + * + * For multi-column sorts we need to estimate the number of comparisons for + * each individual column - for example with columns (c1, c2, ..., ck) we + * can estimate that number of comparions on ck is roughly + * + * ncomparisons(c1, c2, ..., ck) / ncomparisons(c1, c2, ..., c(k-1)) + * + * Let k be a column number, Gk - number of groups defined by k columns, and Fk + * the cost of the comparison is + * + * N * sum( Fk * log(Gk) ) + * + * Note: We also consider column witdth, not just the comparator cost. + * * NOTE: some callers currently pass NIL for pathkeys because they * can't conveniently supply the sort keys. In this case, it will fallback to * simple comparison cost estimate. - * - * Estimation algorithm is based on ideas from course Algorithms, - * Robert Sedgewick, Kevin Wayne, https://algs4.cs.princeton.edu/home/ and paper - * "Quicksort Is Optimal For Many Equal Keys", Sebastian Wild, - * arXiv:1608.04906v4 [cs.DS] 1 Nov 2017. - * - * In term of that papers, let N - number of tuples, Xi - number of tuples with - * key Ki, then estimation is: - * log(N! / (X1! * X2! * ..)) ~ sum(Xi * log(N/Xi)) - * In our case all Xi are the same because now we don't have an estimation of - * group sizes, we have only estimation of number of groups. In this case, - * formula becomes: N * log(NumberOfGroups). Next, to support correct estimation - * of multi-column sort we need separately compute each column, so, let k is a - * column number, Gk - number of groups defined by k columns: - * N * sum( Fk * log(Gk) ) - * Fk is a function costs (including width) for k columns. */ - static Cost compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, Cost comparison_cost, double tuples, double output_tuples, @@ -1862,7 +1890,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, bool has_fake_var = false; int i = 0; Oid prev_datatype = InvalidOid; - Cost funcCost = 0.; + Cost funcCost = 0.0; List *cache_varinfos = NIL; /* fallback if pathkeys is unknown */ @@ -1873,6 +1901,10 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, * a total number of tuple comparisons of N log2 K; but the constant * factor is a bit higher than for quicksort. Tweak it so that the * cost curve is continuous at the crossover point. + * + * XXX I suppose the "quicksort factor" references to 1.5 at the end + * of this function, but I'm not sure. I suggest we introduce some simple + * constants for that, instead of magic values. */ output_tuples = (heapSort) ? 2.0 * output_tuples : tuples; per_tuple_cost += 2.0 * cpu_operator_cost * LOG2(output_tuples); @@ -1888,7 +1920,6 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, * - per column comparison function cost * - we try to compute needed number of comparison per column */ - foreach(lc, pathkeys) { PathKey *pathkey = (PathKey*)lfirst(lc); @@ -1952,6 +1983,11 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, * Don't use DEFAULT_NUM_DISTINCT because it used for only one * column while here we try to estimate number of groups over * set of columns. + * + * XXX Perhaps this should use DEFAULT_NUM_DISTINCT at least to + * limit the calculated values, somehow? + * + * XXX What's the logic of the following formula? */ nGroups = ceil(2.0 + sqrt(tuples) * list_length(pathkeyExprs) / list_length(pathkeys)); @@ -1968,6 +2004,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, { if (tuplesPerPrevGroup < output_tuples) /* comparing only inside output_tuples */ + /* XXX why not to use the same multiplier (1.5)? */ correctedNGroups = ceil(2.0 * output_tuples / (tuplesPerPrevGroup / nGroups)); else @@ -1993,7 +2030,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, tuplesPerPrevGroup = ceil(1.5 * tuplesPerPrevGroup / nGroups); /* - * We could skip all followed columns for cost estimation, because we + * We could skip all following columns for cost estimation, because we * believe that tuples are unique by set ot previous columns */ if (tuplesPerPrevGroup <= 1.0) diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index 7beb32488a..b092c3e055 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -515,10 +515,19 @@ pathkey_sort_cost_comparator(const void *_a, const void *_b) return 0; return 1; } + /* * Order tail of list of group pathkeys by uniqueness descendetly. It allows to * speedup sorting. Returns newly allocated lists, old ones stay untouched. * n_preordered defines a head of list which order should be prevented. + * + * XXX But we're not generating this only based on uniqueness (that's a bad + * term anyway, because we're using ndistinct estimates, not uniqueness). + * We're also using the comparator cost to calculate the expected sort cost, + * and optimize that. + * + * XXX This should explain how we generate the values - all permutations for + * up to 4 values, etc. */ void get_cheapest_group_keys_order(PlannerInfo *root, double nrows, @@ -597,8 +606,9 @@ get_cheapest_group_keys_order(PlannerInfo *root, double nrows, else { /* - * Since v13 list_free() can clean list elements so for original list not to be modified it should be copied to - * a new one which can then be cleaned safely if needed. + * Since v13 list_free() can clean list elements so for original list + * not to be modified it should be copied to a new one which can then + * be cleaned safely if needed. */ new_group_pathkeys = list_copy(*group_pathkeys); nToPermute = nFreeKeys; -- 2.29.2 --------------A955BFDEDE369DCD57A45C5A-- ^ permalink raw reply [nested|flat] 2+ messages in thread
* [PATCH 3/5] Move conversion of a "historic" to MVCC snapshot to a separate function. @ 2025-12-09 18:44 Antonin Houska <[email protected]> 0 siblings, 0 replies; 2+ messages in thread From: Antonin Houska @ 2025-12-09 18:44 UTC (permalink / raw) The conversion is now handled by SnapBuildMVCCFromHistoric(). REPACK CONCURRENTLY will also need it. --- src/backend/commands/cluster.c | 8 ++- src/backend/replication/logical/snapbuild.c | 57 +++++++++++++++++---- src/backend/utils/time/snapmgr.c | 3 +- src/include/replication/snapbuild.h | 1 + src/include/utils/snapmgr.h | 1 + 5 files changed, 53 insertions(+), 17 deletions(-) diff --git a/src/backend/commands/cluster.c b/src/backend/commands/cluster.c index 3afab656cd9..89f0b03a31c 100644 --- a/src/backend/commands/cluster.c +++ b/src/backend/commands/cluster.c @@ -70,8 +70,7 @@ typedef struct static bool cluster_rel_recheck(RepackCommand cmd, Relation OldHeap, Oid indexOid, Oid userid, int options); -static void rebuild_relation(RepackCommand cmd, - Relation OldHeap, Relation index, bool verbose); +static void rebuild_relation(Relation OldHeap, Relation index, bool verbose); static void copy_table_data(Relation NewHeap, Relation OldHeap, Relation OldIndex, bool verbose, bool *pSwapToastByContent, TransactionId *pFreezeXid, MultiXactId *pCutoffMulti); @@ -415,7 +414,7 @@ cluster_rel(RepackCommand cmd, Relation OldHeap, Oid indexOid, TransferPredicateLocksToHeapRelation(OldHeap); /* rebuild_relation does all the dirty work */ - rebuild_relation(cmd, OldHeap, index, verbose); + rebuild_relation(OldHeap, index, verbose); /* rebuild_relation closes OldHeap, and index if valid */ out: @@ -629,8 +628,7 @@ mark_index_clustered(Relation rel, Oid indexOid, bool is_internal) * On exit, they are closed, but locks on them are not released. */ static void -rebuild_relation(RepackCommand cmd, - Relation OldHeap, Relation index, bool verbose) +rebuild_relation(Relation OldHeap, Relation index, bool verbose) { Oid tableOid = RelationGetRelid(OldHeap); Oid accessMethod = OldHeap->rd_rel->relam; diff --git a/src/backend/replication/logical/snapbuild.c b/src/backend/replication/logical/snapbuild.c index 6e18baa33cb..34bdd987478 100644 --- a/src/backend/replication/logical/snapbuild.c +++ b/src/backend/replication/logical/snapbuild.c @@ -440,10 +440,7 @@ Snapshot SnapBuildInitialSnapshot(SnapBuild *builder) { Snapshot snap; - TransactionId xid; TransactionId safeXid; - TransactionId *newxip; - int newxcnt = 0; Assert(XactIsoLevel == XACT_REPEATABLE_READ); Assert(builder->building_full_snapshot); @@ -485,7 +482,33 @@ SnapBuildInitialSnapshot(SnapBuild *builder) MyProc->xmin = snap->xmin; - /* allocate in transaction context */ + /* Convert the historic snapshot to MVCC snapshot. */ + return SnapBuildMVCCFromHistoric(snap, true); +} + +/* + * Turn a historic MVCC snapshot into an ordinary MVCC snapshot. + * + * Unlike a regular (non-historic) MVCC snapshot, the 'xip' array of this + * snapshot contains not only running main transactions, but also their + * subtransactions. On the other hand, 'subxip' will usually be empty. This + * difference does not affect the result of XidInMVCCSnapshot() because it + * searches both in 'xip' and 'subxip'. + * + * Pass true for 'in_place' if you don't care about modifying the source + * snapshot. If you need a new instance, and one that was allocated as a + * single chunk of memory, pass false. + */ +Snapshot +SnapBuildMVCCFromHistoric(Snapshot snapshot, bool in_place) +{ + TransactionId xid; + TransactionId *oldxip = snapshot->xip; + uint32 oldxcnt = snapshot->xcnt; + TransactionId *newxip; + int newxcnt = 0; + Snapshot result; + newxip = (TransactionId *) palloc(sizeof(TransactionId) * GetMaxSnapshotXidCount()); @@ -495,7 +518,7 @@ SnapBuildInitialSnapshot(SnapBuild *builder) * classical snapshot by marking all non-committed transactions as * in-progress. This can be expensive. */ - for (xid = snap->xmin; NormalTransactionIdPrecedes(xid, snap->xmax);) + for (xid = snapshot->xmin; NormalTransactionIdPrecedes(xid, snapshot->xmax);) { void *test; @@ -503,7 +526,7 @@ SnapBuildInitialSnapshot(SnapBuild *builder) * Check whether transaction committed using the decoding snapshot * meaning of ->xip. */ - test = bsearch(&xid, snap->xip, snap->xcnt, + test = bsearch(&xid, snapshot->xip, snapshot->xcnt, sizeof(TransactionId), xidComparator); if (test == NULL) @@ -520,11 +543,25 @@ SnapBuildInitialSnapshot(SnapBuild *builder) } /* adjust remaining snapshot fields as needed */ - snap->snapshot_type = SNAPSHOT_MVCC; - snap->xcnt = newxcnt; - snap->xip = newxip; + snapshot->xcnt = newxcnt; + snapshot->xip = newxip; + + if (in_place) + result = snapshot; + else + { + result = CopySnapshot(snapshot); + + /* Restore the original values so the source is intact. */ + snapshot->xip = oldxip; + snapshot->xcnt = oldxcnt; + + /* newxip has been copied */ + pfree(newxip); + } + result->snapshot_type = SNAPSHOT_MVCC; - return snap; + return result; } /* diff --git a/src/backend/utils/time/snapmgr.c b/src/backend/utils/time/snapmgr.c index 24f73a49d27..886060305f5 100644 --- a/src/backend/utils/time/snapmgr.c +++ b/src/backend/utils/time/snapmgr.c @@ -213,7 +213,6 @@ typedef struct ExportedSnapshot static List *exportedSnapshots = NIL; /* Prototypes for local functions */ -static Snapshot CopySnapshot(Snapshot snapshot); static void UnregisterSnapshotNoOwner(Snapshot snapshot); static void FreeSnapshot(Snapshot snapshot); static void SnapshotResetXmin(void); @@ -604,7 +603,7 @@ SetTransactionSnapshot(Snapshot sourcesnap, VirtualTransactionId *sourcevxid, * The copy is palloc'd in TopTransactionContext and has initial refcounts set * to 0. The returned snapshot has the copied flag set. */ -static Snapshot +Snapshot CopySnapshot(Snapshot snapshot) { Snapshot newsnap; diff --git a/src/include/replication/snapbuild.h b/src/include/replication/snapbuild.h index 44031dcf6e3..6d4d2d1814c 100644 --- a/src/include/replication/snapbuild.h +++ b/src/include/replication/snapbuild.h @@ -73,6 +73,7 @@ extern void FreeSnapshotBuilder(SnapBuild *builder); extern void SnapBuildSnapDecRefcount(Snapshot snap); extern Snapshot SnapBuildInitialSnapshot(SnapBuild *builder); +extern Snapshot SnapBuildMVCCFromHistoric(Snapshot snapshot, bool in_place); extern const char *SnapBuildExportSnapshot(SnapBuild *builder); extern void SnapBuildClearExportedSnapshot(void); extern void SnapBuildResetExportedSnapshotState(void); diff --git a/src/include/utils/snapmgr.h b/src/include/utils/snapmgr.h index 604c1f90216..f65f83c85cd 100644 --- a/src/include/utils/snapmgr.h +++ b/src/include/utils/snapmgr.h @@ -63,6 +63,7 @@ extern Snapshot GetTransactionSnapshot(void); extern Snapshot GetLatestSnapshot(void); extern void SnapshotSetCommandId(CommandId curcid); +extern Snapshot CopySnapshot(Snapshot snapshot); extern Snapshot GetCatalogSnapshot(Oid relid); extern Snapshot GetNonHistoricCatalogSnapshot(Oid relid); extern void InvalidateCatalogSnapshot(void); -- 2.47.3 --=-=-= Content-Type: text/plain Content-Disposition: attachment; filename=v27-0004-Add-CONCURRENTLY-option-to-REPACK-command.patch ^ permalink raw reply [nested|flat] 2+ messages in thread
end of thread, other threads:[~2025-12-09 18:44 UTC | newest] Thread overview: 2+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2021-03-09 20:09 [PATCH 2/2] review Tomas Vondra <[email protected]> 2025-12-09 18:44 [PATCH 3/5] Move conversion of a "historic" to MVCC snapshot to a separate function. Antonin Houska <[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