public inbox for [email protected]help / color / mirror / Atom feed
[PATCH v24 03/10] Add default_toast_compression GUC 3+ messages / 3 participants [nested] [flat]
* [PATCH v24 03/10] Add default_toast_compression GUC @ 2021-01-30 03:37 Justin Pryzby <[email protected]> 0 siblings, 0 replies; 3+ messages in thread From: Justin Pryzby @ 2021-01-30 03:37 UTC (permalink / raw) --- src/backend/access/common/tupdesc.c | 2 +- src/backend/bootstrap/bootstrap.c | 3 +- src/backend/commands/amcmds.c | 143 +++++++++++++++++++++++++++- src/backend/commands/tablecmds.c | 4 +- src/backend/utils/init/postinit.c | 4 + src/backend/utils/misc/guc.c | 12 +++ src/include/access/amapi.h | 2 + src/include/access/compressamapi.h | 12 ++- 8 files changed, 176 insertions(+), 6 deletions(-) diff --git a/src/backend/access/common/tupdesc.c b/src/backend/access/common/tupdesc.c index ca26fab487..7afaea000b 100644 --- a/src/backend/access/common/tupdesc.c +++ b/src/backend/access/common/tupdesc.c @@ -668,7 +668,7 @@ TupleDescInitEntry(TupleDesc desc, att->attcollation = typeForm->typcollation; if (IsStorageCompressible(typeForm->typstorage)) - att->attcompression = DefaultCompressionOid; + att->attcompression = GetDefaultToastCompression(); else att->attcompression = InvalidOid; diff --git a/src/backend/bootstrap/bootstrap.c b/src/backend/bootstrap/bootstrap.c index 9b451eaa71..ec3376cf8a 100644 --- a/src/backend/bootstrap/bootstrap.c +++ b/src/backend/bootstrap/bootstrap.c @@ -732,8 +732,9 @@ DefineAttr(char *name, char *type, int attnum, int nullness) attrtypes[attnum]->attcacheoff = -1; attrtypes[attnum]->atttypmod = -1; attrtypes[attnum]->attislocal = true; + if (IsStorageCompressible(attrtypes[attnum]->attstorage)) - attrtypes[attnum]->attcompression = DefaultCompressionOid; + attrtypes[attnum]->attcompression = GetDefaultToastCompression(); else attrtypes[attnum]->attcompression = InvalidOid; diff --git a/src/backend/commands/amcmds.c b/src/backend/commands/amcmds.c index 3ad4a61739..1682afd2a4 100644 --- a/src/backend/commands/amcmds.c +++ b/src/backend/commands/amcmds.c @@ -13,8 +13,11 @@ */ #include "postgres.h" +#include "access/amapi.h" +#include "access/compressamapi.h" #include "access/htup_details.h" #include "access/table.h" +#include "access/xact.h" #include "catalog/catalog.h" #include "catalog/dependency.h" #include "catalog/indexing.h" @@ -27,13 +30,20 @@ #include "parser/parse_func.h" #include "utils/builtins.h" #include "utils/lsyscache.h" +#include "utils/guc.h" +#include "utils/inval.h" #include "utils/rel.h" #include "utils/syscache.h" - static Oid lookup_am_handler_func(List *handler_name, char amtype); static const char *get_am_type_string(char amtype); +/* Compile-time default */ +char *default_toast_compression = DEFAULT_TOAST_COMPRESSION; // maybe needs pg_dump support ? +/* Invalid means need to lookup the text value in the catalog */ +static Oid default_toast_compression_oid = InvalidOid; + +static void AccessMethodCallback(Datum arg, int cacheid, uint32 hashvalue); /* * CreateAccessMethod @@ -277,3 +287,134 @@ lookup_am_handler_func(List *handler_name, char amtype) return handlerOid; } + +/* check_hook: validate new default_toast_compression */ +bool +check_default_toast_compression(char **newval, void **extra, GucSource source) +{ + if (**newval == '\0') + { + GUC_check_errdetail("%s cannot be empty.", + "default_toast_compression"); + return false; + } + + if (strlen(*newval) >= NAMEDATALEN) + { + GUC_check_errdetail("%s is too long (maximum %d characters).", + "default_toast_compression", NAMEDATALEN - 1); + return false; + } + + /* + * If we aren't inside a transaction, or not connected to a database, we + * cannot do the catalog access necessary to verify the method. Must + * accept the value on faith. + */ + if (IsTransactionState() && MyDatabaseId != InvalidOid) + { + if (!OidIsValid(get_compression_am_oid(*newval, true))) + { + /* + * When source == PGC_S_TEST, don't throw a hard error for a + * nonexistent table access method, only a NOTICE. See comments in + * guc.h. + */ + if (source == PGC_S_TEST) + { + ereport(NOTICE, + (errcode(ERRCODE_UNDEFINED_OBJECT), + errmsg("compression access method \"%s\" does not exist", + *newval))); + } + else + { + GUC_check_errdetail("Compression access method \"%s\" does not exist.", + *newval); + return false; + } + } + } + + return true; +} + +/* + * assign_default_toast_compression: GUC assign_hook for default_toast_compression + */ +void +assign_default_toast_compression(const char *newval, void *extra) +{ + /* + * Invalidate setting, forcing it to be looked up as needed. + * This avoids trying to do database access during GUC initialization, + * or outside a transaction. + */ + + default_toast_compression = NULL; +fprintf(stderr, "set to null\n"); +} + + +/* + * GetDefaultToastCompression -- get the OID of the current toast compression + * + * This exists to hide and optimize the use of the default_toast_compression + * GUC variable. + */ +Oid +GetDefaultToastCompression(void) +{ + /* Avoid catalog access during bootstrap, and for default compression */ + if (strcmp(default_toast_compression, DEFAULT_TOAST_COMPRESSION) == 0) + return PGLZ_COMPRESSION_AM_OID; + + /* Cannot call get_compression_am_oid this early */ + // if (IsBootstrapProcessingMode()) + // return PGLZ_COMPRESSION_AM_OID; + Assert(!IsBootstrapProcessingMode()); + + /* + * If cached value isn't valid, look up the current default value, caching + * the result + */ + if (!OidIsValid(default_toast_compression_oid)) + default_toast_compression_oid = + get_am_type_oid(default_toast_compression, AMTYPE_COMPRESSION, + false); + + return default_toast_compression_oid; +} + +/* + * InitializeAccessMethods: initialize module during InitPostgres. + * + * This is called after we are up enough to be able to do catalog lookups. + */ +void +InitializeAccessMethods(void) +{ + if (IsBootstrapProcessingMode()) + return; + + /* + * In normal mode, arrange for a callback on any syscache invalidation + * of pg_am rows. + */ + CacheRegisterSyscacheCallback(AMOID, + AccessMethodCallback, + (Datum) 0); + /* Force cached default access method to be recomputed on next use */ + // default_toast_compression_oid = InvalidOid; +} + +/* + * AccessMethodCallback + * Syscache inval callback function + */ +static void +AccessMethodCallback(Datum arg, int cacheid, uint32 hashvalue) +{ + /* Force look up of compression oid on next use */ + default_toast_compression_oid = false; +} diff --git a/src/backend/commands/tablecmds.c b/src/backend/commands/tablecmds.c index dd81d5bf4e..72ba017814 100644 --- a/src/backend/commands/tablecmds.c +++ b/src/backend/commands/tablecmds.c @@ -11925,7 +11925,7 @@ ATExecAlterColumnType(AlteredTableInfo *tab, Relation rel, if (!IsStorageCompressible(tform->typstorage)) attTup->attcompression = InvalidOid; else if (!OidIsValid(attTup->attcompression)) - attTup->attcompression = DefaultCompressionOid; + attTup->attcompression = GetDefaultToastCompression(); } else attTup->attcompression = InvalidOid; @@ -17762,7 +17762,7 @@ GetAttributeCompression(Form_pg_attribute att, char *compression) /* fallback to default compression if it's not specified */ if (compression == NULL) - return DefaultCompressionOid; + return GetDefaultToastCompression(); amoid = get_compression_am_oid(compression, false); diff --git a/src/backend/utils/init/postinit.c b/src/backend/utils/init/postinit.c index e5965bc517..6a02bbd377 100644 --- a/src/backend/utils/init/postinit.c +++ b/src/backend/utils/init/postinit.c @@ -25,6 +25,7 @@ #include "access/session.h" #include "access/sysattr.h" #include "access/tableam.h" +#include "access/amapi.h" #include "access/xact.h" #include "access/xlog.h" #include "catalog/catalog.h" @@ -1060,6 +1061,9 @@ InitPostgres(const char *in_dbname, Oid dboid, const char *username, /* set default namespace search path */ InitializeSearchPath(); + /* set callback for changes to pg_am */ + InitializeAccessMethods(); + /* initialize client encoding */ InitializeClientEncoding(); diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c index eafdb1118e..3a2b33fcd1 100644 --- a/src/backend/utils/misc/guc.c +++ b/src/backend/utils/misc/guc.c @@ -30,6 +30,7 @@ #include <unistd.h> #include "access/commit_ts.h" +#include "access/compressamapi.h" #include "access/gin.h" #include "access/rmgr.h" #include "access/tableam.h" @@ -3915,6 +3916,17 @@ static struct config_string ConfigureNamesString[] = check_default_table_access_method, NULL, NULL }, + { + {"default_toast_compression", PGC_USERSET, CLIENT_CONN_STATEMENT, + gettext_noop("Sets the default compression for new columns."), + NULL, + GUC_IS_NAME + }, + &default_toast_compression, + DEFAULT_TOAST_COMPRESSION, + check_default_toast_compression, assign_default_toast_compression, NULL, NULL + }, + { {"default_tablespace", PGC_USERSET, CLIENT_CONN_STATEMENT, gettext_noop("Sets the default tablespace to create tables and indexes in."), diff --git a/src/include/access/amapi.h b/src/include/access/amapi.h index d357ebb559..1513cafcf4 100644 --- a/src/include/access/amapi.h +++ b/src/include/access/amapi.h @@ -287,4 +287,6 @@ typedef struct IndexAmRoutine extern IndexAmRoutine *GetIndexAmRoutine(Oid amhandler); extern IndexAmRoutine *GetIndexAmRoutineByAmId(Oid amoid, bool noerror); +void InitializeAccessMethods(void); + #endif /* AMAPI_H */ diff --git a/src/include/access/compressamapi.h b/src/include/access/compressamapi.h index 5a8e23d926..d75a8e9df2 100644 --- a/src/include/access/compressamapi.h +++ b/src/include/access/compressamapi.h @@ -17,6 +17,7 @@ #include "catalog/pg_am_d.h" #include "nodes/nodes.h" +#include "utils/guc.h" /* * Built-in compression method-id. The toast compression header will store @@ -29,8 +30,17 @@ typedef enum CompressionId LZ4_COMPRESSION_ID = 1 } CompressionId; -/* Use default compression method if it is not specified. */ +/* Default compression method if not specified. */ +#define DEFAULT_TOAST_COMPRESSION "pglz" #define DefaultCompressionOid PGLZ_COMPRESSION_AM_OID + +/* GUC */ +extern char *default_toast_compression; +extern void assign_default_toast_compression(const char *newval, void *extra); +extern bool check_default_toast_compression(char **newval, void **extra, GucSource source); + +extern Oid GetDefaultToastCompression(void); + #define IsStorageCompressible(storage) ((storage) != TYPSTORAGE_PLAIN && \ (storage) != TYPSTORAGE_EXTERNAL) /* compression handler routines */ -- 2.17.0 --m51xatjYGsM+13rf Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v24-0004-default-to-with-lz4.patch" ^ permalink raw reply [nested|flat] 3+ messages in thread
* Optimization outcome depends on the index order @ 2023-12-22 06:53 Andrei Lepikhov <[email protected]> 0 siblings, 1 reply; 3+ messages in thread From: Andrei Lepikhov @ 2023-12-22 06:53 UTC (permalink / raw) To: PostgreSQL Hackers <[email protected]>; Alexander Korotkov <[email protected]> On 21/12/2023 12:10, Alexander Korotkov wrote: > I took a closer look at the patch in [9]. I should drop my argument > about breaking the model, because add_path() already considers other > aspects than just costs. But I have two more note about that patch: > > 1) It seems that you're determining the fact that the index path > should return strictly one row by checking path->rows <= 1.0 and > indexinfo->unique. Is it really guaranteed that in this case quals > are matching unique constraint? path->rows <= 1.0 could be just an > estimation error. Or one row could be correctly estimated, but it's > going to be selected by some quals matching unique constraint and > other quals in recheck. So, it seems there is a risk to select > suboptimal index due to this condition. Operating inside the optimizer, we consider all estimations to be the sooth. This patch modifies only one place: having two equal assumptions, we just choose one that generally looks more stable. Filtered tuples should be calculated and included in the cost of the path. The decision on the equality of paths has been made in view of the estimation of these filtered tuples. > 2) Even for non-unique indexes this patch is putting new logic on top > of the subsequent code. How we can prove it's going to be a win? > That could lead, for instance, to dropping parallel-safe paths in > cases we didn't do so before. Because we must trust all predictions made by the planner, we just choose the most trustworthy path. According to the planner logic, it is a path with a smaller selectivity. We can make mistakes anyway just because of the nature of estimation. > Anyway, please start a separate thread if you're willing to put more > work into this. Done > 9. https://www.postgresql.org/message-id/154f786a-06a0-4fb1- > b8a4-16c66149731b%40postgrespro.ru -- regards, Andrei Lepikhov Postgres Professional From 7b044de1449a5fdc450cb629caafb4e15ded7a93 Mon Sep 17 00:00:00 2001 From: "Andrey V. Lepikhov" <[email protected]> Date: Mon, 27 Nov 2023 11:23:48 +0700 Subject: [PATCH] Choose an index path with the best selectivity estimation. In the case when optimizer predicts only one row prefer choosing UNIQUE indexes In other cases, if optimizer treats indexes as equal, make a last attempt selecting the index with less selectivity - this decision takes away dependency on the order of indexes in an index list (good for reproduction of some issues) and proposes one more objective argument to choose specific index. --- src/backend/optimizer/util/pathnode.c | 42 +++++++++++++++++++ .../expected/drop-index-concurrently-1.out | 16 +++---- src/test/regress/expected/functional_deps.out | 39 +++++++++++++++++ src/test/regress/expected/join.out | 40 +++++++++--------- src/test/regress/sql/functional_deps.sql | 32 ++++++++++++++ 5 files changed, 143 insertions(+), 26 deletions(-) diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index 0b1d17b9d3..4b5aedd579 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -454,6 +454,48 @@ add_path(RelOptInfo *parent_rel, Path *new_path) costcmp = compare_path_costs_fuzzily(new_path, old_path, STD_FUZZ_FACTOR); + /* + * Apply some heuristics on index paths. + */ + if (IsA(new_path, IndexPath) && IsA(old_path, IndexPath)) + { + IndexPath *inp = (IndexPath *) new_path; + IndexPath *iop = (IndexPath *) old_path; + + if (new_path->rows <= 1.0 && old_path->rows <= 1.0) + { + /* + * When both paths are predicted to produce only one tuple, + * the optimiser should prefer choosing a unique index scan + * in all cases. + */ + if (inp->indexinfo->unique && !iop->indexinfo->unique) + costcmp = COSTS_BETTER1; + else if (!inp->indexinfo->unique && iop->indexinfo->unique) + costcmp = COSTS_BETTER2; + else if (costcmp != COSTS_DIFFERENT) + /* + * If the optimiser doesn't have an obviously stable choice + * of unique index, increase the chance of avoiding mistakes + * by choosing an index with smaller selectivity. + * This option makes decision more conservative and looks + * debatable. + */ + costcmp = (inp->indexselectivity < iop->indexselectivity) ? + COSTS_BETTER1 : COSTS_BETTER2; + } + else if (costcmp == COSTS_EQUAL) + /* + * The optimizer can't differ the value of two index paths. + * To avoid making a decision that is based on only an index + * order in the list, use some rational strategy based on + * selectivity: prefer touching fewer tuples on the disk to + * filtering them after. + */ + costcmp = (inp->indexselectivity < iop->indexselectivity) ? + COSTS_BETTER1 : COSTS_BETTER2; + } + /* * If the two paths compare differently for startup and total cost, * then we want to keep both, and we can skip comparing pathkeys and diff --git a/src/test/isolation/expected/drop-index-concurrently-1.out b/src/test/isolation/expected/drop-index-concurrently-1.out index 1cb2250891..2392cdb033 100644 --- a/src/test/isolation/expected/drop-index-concurrently-1.out +++ b/src/test/isolation/expected/drop-index-concurrently-1.out @@ -12,13 +12,15 @@ step preps: PREPARE getrow_seqscan AS SELECT * FROM test_dc WHERE data = 34 ORDE step begin: BEGIN; step disableseq: SET enable_seqscan = false; step explaini: EXPLAIN (COSTS OFF) EXECUTE getrow_idxscan; -QUERY PLAN ----------------------------------------------- -Sort - Sort Key: id - -> Index Scan using test_dc_data on test_dc - Index Cond: (data = 34) -(4 rows) +QUERY PLAN +--------------------------------------------- +Sort + Sort Key: id + -> Bitmap Heap Scan on test_dc + Recheck Cond: (data = 34) + -> Bitmap Index Scan on test_dc_data + Index Cond: (data = 34) +(6 rows) step enableseq: SET enable_seqscan = true; step explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seqscan; diff --git a/src/test/regress/expected/functional_deps.out b/src/test/regress/expected/functional_deps.out index 32381b8ae7..7057254278 100644 --- a/src/test/regress/expected/functional_deps.out +++ b/src/test/regress/expected/functional_deps.out @@ -230,3 +230,42 @@ EXECUTE foo; ALTER TABLE articles DROP CONSTRAINT articles_pkey RESTRICT; EXECUTE foo; -- fail ERROR: column "articles.keywords" must appear in the GROUP BY clause or be used in an aggregate function +/* + * Corner case of the PostgreSQL optimizer: + * + * ANDed clauses selectivity multiplication increases total selectivity error. + * If such non-true selectivity is so tiny that row estimation predicts the + * absolute minimum number of tuples (1), the optimizer can't choose between + * different indexes and picks a first from the index list (last created). + */ +CREATE TABLE t AS ( -- selectivity(c1)*selectivity(c2)*nrows <= 1 + SELECT gs AS c1, + gs AS c2, + (gs % 10) AS c3, -- not in the good index. + (gs % 100) AS c4 -- not in the bad index. + FROM generate_series(1,1000) AS gs +); +CREATE INDEX bad ON t (c1,c2,c3); +CREATE INDEX good ON t (c1,c2,c4); +ANALYZE t; +EXPLAIN (COSTS OFF) SELECT * FROM t WHERE c1=1 AND c2=1 AND c3=1 AND c4=1; + QUERY PLAN +---------------------------------------------------- + Index Scan using good on t + Index Cond: ((c1 = 1) AND (c2 = 1) AND (c4 = 1)) + Filter: (c3 = 1) +(3 rows) + +-- Hack: set the bad index to the first position in the index list. +DROP INDEX bad; +CREATE INDEX bad ON t (c1,c2,c3); +ANALYZE t; +EXPLAIN (COSTS OFF) SELECT * FROM t WHERE c1=1 AND c2=1 AND c3=1 AND c4=1; + QUERY PLAN +---------------------------------------------------- + Index Scan using good on t + Index Cond: ((c1 = 1) AND (c2 = 1) AND (c4 = 1)) + Filter: (c3 = 1) +(3 rows) + +DROP TABLE t CASCADE; diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out index 2c73270143..32b33fabd3 100644 --- a/src/test/regress/expected/join.out +++ b/src/test/regress/expected/join.out @@ -8629,14 +8629,15 @@ analyze j2; explain (costs off) select * from j1 inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2 where j1.id1 % 1000 = 1 and j2.id1 % 1000 = 1; - QUERY PLAN ------------------------------------------ + QUERY PLAN +--------------------------------------------------------- Merge Join - Merge Cond: (j1.id1 = j2.id1) - Join Filter: (j2.id2 = j1.id2) - -> Index Scan using j1_id1_idx on j1 - -> Index Scan using j2_id1_idx on j2 -(5 rows) + Merge Cond: ((j1.id1 = j2.id1) AND (j1.id2 = j2.id2)) + -> Index Only Scan using j1_pkey on j1 + Filter: ((id1 % 1000) = 1) + -> Index Only Scan using j2_pkey on j2 + Filter: ((id1 % 1000) = 1) +(6 rows) select * from j1 inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2 @@ -8651,15 +8652,16 @@ where j1.id1 % 1000 = 1 and j2.id1 % 1000 = 1; explain (costs off) select * from j1 inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2 where j1.id1 % 1000 = 1 and j2.id1 % 1000 = 1 and j2.id1 = any (array[1]); - QUERY PLAN ----------------------------------------------------- + QUERY PLAN +--------------------------------------------------------- Merge Join - Merge Cond: (j1.id1 = j2.id1) - Join Filter: (j2.id2 = j1.id2) - -> Index Scan using j1_id1_idx on j1 - -> Index Scan using j2_id1_idx on j2 + Merge Cond: ((j1.id1 = j2.id1) AND (j1.id2 = j2.id2)) + -> Index Only Scan using j1_pkey on j1 + Filter: ((id1 % 1000) = 1) + -> Index Only Scan using j2_pkey on j2 Index Cond: (id1 = ANY ('{1}'::integer[])) -(6 rows) + Filter: ((id1 % 1000) = 1) +(7 rows) select * from j1 inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2 @@ -8674,12 +8676,12 @@ where j1.id1 % 1000 = 1 and j2.id1 % 1000 = 1 and j2.id1 = any (array[1]); explain (costs off) select * from j1 inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2 where j1.id1 % 1000 = 1 and j2.id1 % 1000 = 1 and j2.id1 >= any (array[1,5]); - QUERY PLAN -------------------------------------------------------- + QUERY PLAN +--------------------------------------------------------- Merge Join - Merge Cond: (j1.id1 = j2.id1) - Join Filter: (j2.id2 = j1.id2) - -> Index Scan using j1_id1_idx on j1 + Merge Cond: ((j1.id1 = j2.id1) AND (j1.id2 = j2.id2)) + -> Index Only Scan using j1_pkey on j1 + Filter: ((id1 % 1000) = 1) -> Index Only Scan using j2_pkey on j2 Index Cond: (id1 >= ANY ('{1,5}'::integer[])) Filter: ((id1 % 1000) = 1) diff --git a/src/test/regress/sql/functional_deps.sql b/src/test/regress/sql/functional_deps.sql index 406490b995..1be009b1ff 100644 --- a/src/test/regress/sql/functional_deps.sql +++ b/src/test/regress/sql/functional_deps.sql @@ -208,3 +208,35 @@ EXECUTE foo; ALTER TABLE articles DROP CONSTRAINT articles_pkey RESTRICT; EXECUTE foo; -- fail + +/* + * Corner case of the PostgreSQL optimizer: + * + * ANDed clauses selectivity multiplication increases total selectivity error. + * If such non-true selectivity is so tiny that row estimation predicts the + * absolute minimum number of tuples (1), the optimizer can't choose between + * different indexes and picks a first from the index list (last created). + */ + +CREATE TABLE t AS ( -- selectivity(c1)*selectivity(c2)*nrows <= 1 + SELECT gs AS c1, + gs AS c2, + (gs % 10) AS c3, -- not in the good index. + (gs % 100) AS c4 -- not in the bad index. + FROM generate_series(1,1000) AS gs +); + +CREATE INDEX bad ON t (c1,c2,c3); +CREATE INDEX good ON t (c1,c2,c4); +ANALYZE t; + +EXPLAIN (COSTS OFF) SELECT * FROM t WHERE c1=1 AND c2=1 AND c3=1 AND c4=1; + +-- Hack: set the bad index to the first position in the index list. +DROP INDEX bad; +CREATE INDEX bad ON t (c1,c2,c3); +ANALYZE t; + +EXPLAIN (COSTS OFF) SELECT * FROM t WHERE c1=1 AND c2=1 AND c3=1 AND c4=1; + +DROP TABLE t CASCADE; -- 2.43.0 Attachments: [text/plain] v3-0001-Choose-an-index-path-with-the-best-selectivity-estim.patch (10.5K, ../../[email protected]/2-v3-0001-Choose-an-index-path-with-the-best-selectivity-estim.patch) download | inline diff: From 7b044de1449a5fdc450cb629caafb4e15ded7a93 Mon Sep 17 00:00:00 2001 From: "Andrey V. Lepikhov" <[email protected]> Date: Mon, 27 Nov 2023 11:23:48 +0700 Subject: [PATCH] Choose an index path with the best selectivity estimation. In the case when optimizer predicts only one row prefer choosing UNIQUE indexes In other cases, if optimizer treats indexes as equal, make a last attempt selecting the index with less selectivity - this decision takes away dependency on the order of indexes in an index list (good for reproduction of some issues) and proposes one more objective argument to choose specific index. --- src/backend/optimizer/util/pathnode.c | 42 +++++++++++++++++++ .../expected/drop-index-concurrently-1.out | 16 +++---- src/test/regress/expected/functional_deps.out | 39 +++++++++++++++++ src/test/regress/expected/join.out | 40 +++++++++--------- src/test/regress/sql/functional_deps.sql | 32 ++++++++++++++ 5 files changed, 143 insertions(+), 26 deletions(-) diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index 0b1d17b9d3..4b5aedd579 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -454,6 +454,48 @@ add_path(RelOptInfo *parent_rel, Path *new_path) costcmp = compare_path_costs_fuzzily(new_path, old_path, STD_FUZZ_FACTOR); + /* + * Apply some heuristics on index paths. + */ + if (IsA(new_path, IndexPath) && IsA(old_path, IndexPath)) + { + IndexPath *inp = (IndexPath *) new_path; + IndexPath *iop = (IndexPath *) old_path; + + if (new_path->rows <= 1.0 && old_path->rows <= 1.0) + { + /* + * When both paths are predicted to produce only one tuple, + * the optimiser should prefer choosing a unique index scan + * in all cases. + */ + if (inp->indexinfo->unique && !iop->indexinfo->unique) + costcmp = COSTS_BETTER1; + else if (!inp->indexinfo->unique && iop->indexinfo->unique) + costcmp = COSTS_BETTER2; + else if (costcmp != COSTS_DIFFERENT) + /* + * If the optimiser doesn't have an obviously stable choice + * of unique index, increase the chance of avoiding mistakes + * by choosing an index with smaller selectivity. + * This option makes decision more conservative and looks + * debatable. + */ + costcmp = (inp->indexselectivity < iop->indexselectivity) ? + COSTS_BETTER1 : COSTS_BETTER2; + } + else if (costcmp == COSTS_EQUAL) + /* + * The optimizer can't differ the value of two index paths. + * To avoid making a decision that is based on only an index + * order in the list, use some rational strategy based on + * selectivity: prefer touching fewer tuples on the disk to + * filtering them after. + */ + costcmp = (inp->indexselectivity < iop->indexselectivity) ? + COSTS_BETTER1 : COSTS_BETTER2; + } + /* * If the two paths compare differently for startup and total cost, * then we want to keep both, and we can skip comparing pathkeys and diff --git a/src/test/isolation/expected/drop-index-concurrently-1.out b/src/test/isolation/expected/drop-index-concurrently-1.out index 1cb2250891..2392cdb033 100644 --- a/src/test/isolation/expected/drop-index-concurrently-1.out +++ b/src/test/isolation/expected/drop-index-concurrently-1.out @@ -12,13 +12,15 @@ step preps: PREPARE getrow_seqscan AS SELECT * FROM test_dc WHERE data = 34 ORDE step begin: BEGIN; step disableseq: SET enable_seqscan = false; step explaini: EXPLAIN (COSTS OFF) EXECUTE getrow_idxscan; -QUERY PLAN ----------------------------------------------- -Sort - Sort Key: id - -> Index Scan using test_dc_data on test_dc - Index Cond: (data = 34) -(4 rows) +QUERY PLAN +--------------------------------------------- +Sort + Sort Key: id + -> Bitmap Heap Scan on test_dc + Recheck Cond: (data = 34) + -> Bitmap Index Scan on test_dc_data + Index Cond: (data = 34) +(6 rows) step enableseq: SET enable_seqscan = true; step explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seqscan; diff --git a/src/test/regress/expected/functional_deps.out b/src/test/regress/expected/functional_deps.out index 32381b8ae7..7057254278 100644 --- a/src/test/regress/expected/functional_deps.out +++ b/src/test/regress/expected/functional_deps.out @@ -230,3 +230,42 @@ EXECUTE foo; ALTER TABLE articles DROP CONSTRAINT articles_pkey RESTRICT; EXECUTE foo; -- fail ERROR: column "articles.keywords" must appear in the GROUP BY clause or be used in an aggregate function +/* + * Corner case of the PostgreSQL optimizer: + * + * ANDed clauses selectivity multiplication increases total selectivity error. + * If such non-true selectivity is so tiny that row estimation predicts the + * absolute minimum number of tuples (1), the optimizer can't choose between + * different indexes and picks a first from the index list (last created). + */ +CREATE TABLE t AS ( -- selectivity(c1)*selectivity(c2)*nrows <= 1 + SELECT gs AS c1, + gs AS c2, + (gs % 10) AS c3, -- not in the good index. + (gs % 100) AS c4 -- not in the bad index. + FROM generate_series(1,1000) AS gs +); +CREATE INDEX bad ON t (c1,c2,c3); +CREATE INDEX good ON t (c1,c2,c4); +ANALYZE t; +EXPLAIN (COSTS OFF) SELECT * FROM t WHERE c1=1 AND c2=1 AND c3=1 AND c4=1; + QUERY PLAN +---------------------------------------------------- + Index Scan using good on t + Index Cond: ((c1 = 1) AND (c2 = 1) AND (c4 = 1)) + Filter: (c3 = 1) +(3 rows) + +-- Hack: set the bad index to the first position in the index list. +DROP INDEX bad; +CREATE INDEX bad ON t (c1,c2,c3); +ANALYZE t; +EXPLAIN (COSTS OFF) SELECT * FROM t WHERE c1=1 AND c2=1 AND c3=1 AND c4=1; + QUERY PLAN +---------------------------------------------------- + Index Scan using good on t + Index Cond: ((c1 = 1) AND (c2 = 1) AND (c4 = 1)) + Filter: (c3 = 1) +(3 rows) + +DROP TABLE t CASCADE; diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out index 2c73270143..32b33fabd3 100644 --- a/src/test/regress/expected/join.out +++ b/src/test/regress/expected/join.out @@ -8629,14 +8629,15 @@ analyze j2; explain (costs off) select * from j1 inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2 where j1.id1 % 1000 = 1 and j2.id1 % 1000 = 1; - QUERY PLAN ------------------------------------------ + QUERY PLAN +--------------------------------------------------------- Merge Join - Merge Cond: (j1.id1 = j2.id1) - Join Filter: (j2.id2 = j1.id2) - -> Index Scan using j1_id1_idx on j1 - -> Index Scan using j2_id1_idx on j2 -(5 rows) + Merge Cond: ((j1.id1 = j2.id1) AND (j1.id2 = j2.id2)) + -> Index Only Scan using j1_pkey on j1 + Filter: ((id1 % 1000) = 1) + -> Index Only Scan using j2_pkey on j2 + Filter: ((id1 % 1000) = 1) +(6 rows) select * from j1 inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2 @@ -8651,15 +8652,16 @@ where j1.id1 % 1000 = 1 and j2.id1 % 1000 = 1; explain (costs off) select * from j1 inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2 where j1.id1 % 1000 = 1 and j2.id1 % 1000 = 1 and j2.id1 = any (array[1]); - QUERY PLAN ----------------------------------------------------- + QUERY PLAN +--------------------------------------------------------- Merge Join - Merge Cond: (j1.id1 = j2.id1) - Join Filter: (j2.id2 = j1.id2) - -> Index Scan using j1_id1_idx on j1 - -> Index Scan using j2_id1_idx on j2 + Merge Cond: ((j1.id1 = j2.id1) AND (j1.id2 = j2.id2)) + -> Index Only Scan using j1_pkey on j1 + Filter: ((id1 % 1000) = 1) + -> Index Only Scan using j2_pkey on j2 Index Cond: (id1 = ANY ('{1}'::integer[])) -(6 rows) + Filter: ((id1 % 1000) = 1) +(7 rows) select * from j1 inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2 @@ -8674,12 +8676,12 @@ where j1.id1 % 1000 = 1 and j2.id1 % 1000 = 1 and j2.id1 = any (array[1]); explain (costs off) select * from j1 inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2 where j1.id1 % 1000 = 1 and j2.id1 % 1000 = 1 and j2.id1 >= any (array[1,5]); - QUERY PLAN -------------------------------------------------------- + QUERY PLAN +--------------------------------------------------------- Merge Join - Merge Cond: (j1.id1 = j2.id1) - Join Filter: (j2.id2 = j1.id2) - -> Index Scan using j1_id1_idx on j1 + Merge Cond: ((j1.id1 = j2.id1) AND (j1.id2 = j2.id2)) + -> Index Only Scan using j1_pkey on j1 + Filter: ((id1 % 1000) = 1) -> Index Only Scan using j2_pkey on j2 Index Cond: (id1 >= ANY ('{1,5}'::integer[])) Filter: ((id1 % 1000) = 1) diff --git a/src/test/regress/sql/functional_deps.sql b/src/test/regress/sql/functional_deps.sql index 406490b995..1be009b1ff 100644 --- a/src/test/regress/sql/functional_deps.sql +++ b/src/test/regress/sql/functional_deps.sql @@ -208,3 +208,35 @@ EXECUTE foo; ALTER TABLE articles DROP CONSTRAINT articles_pkey RESTRICT; EXECUTE foo; -- fail + +/* + * Corner case of the PostgreSQL optimizer: + * + * ANDed clauses selectivity multiplication increases total selectivity error. + * If such non-true selectivity is so tiny that row estimation predicts the + * absolute minimum number of tuples (1), the optimizer can't choose between + * different indexes and picks a first from the index list (last created). + */ + +CREATE TABLE t AS ( -- selectivity(c1)*selectivity(c2)*nrows <= 1 + SELECT gs AS c1, + gs AS c2, + (gs % 10) AS c3, -- not in the good index. + (gs % 100) AS c4 -- not in the bad index. + FROM generate_series(1,1000) AS gs +); + +CREATE INDEX bad ON t (c1,c2,c3); +CREATE INDEX good ON t (c1,c2,c4); +ANALYZE t; + +EXPLAIN (COSTS OFF) SELECT * FROM t WHERE c1=1 AND c2=1 AND c3=1 AND c4=1; + +-- Hack: set the bad index to the first position in the index list. +DROP INDEX bad; +CREATE INDEX bad ON t (c1,c2,c3); +ANALYZE t; + +EXPLAIN (COSTS OFF) SELECT * FROM t WHERE c1=1 AND c2=1 AND c3=1 AND c4=1; + +DROP TABLE t CASCADE; -- 2.43.0 ^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: Optimization outcome depends on the index order @ 2023-12-22 09:48 Alexander Korotkov <[email protected]> parent: Andrei Lepikhov <[email protected]> 0 siblings, 0 replies; 3+ messages in thread From: Alexander Korotkov @ 2023-12-22 09:48 UTC (permalink / raw) To: Andrei Lepikhov <[email protected]>; +Cc: PostgreSQL Hackers <[email protected]> On Fri, Dec 22, 2023 at 8:53 AM Andrei Lepikhov <[email protected]> wrote: > On 21/12/2023 12:10, Alexander Korotkov wrote: > > I took a closer look at the patch in [9]. I should drop my argument > > about breaking the model, because add_path() already considers other > > aspects than just costs. But I have two more note about that patch: > > > > 1) It seems that you're determining the fact that the index path > > should return strictly one row by checking path->rows <= 1.0 and > > indexinfo->unique. Is it really guaranteed that in this case quals > > are matching unique constraint? path->rows <= 1.0 could be just an > > estimation error. Or one row could be correctly estimated, but it's > > going to be selected by some quals matching unique constraint and > > other quals in recheck. So, it seems there is a risk to select > > suboptimal index due to this condition. > > Operating inside the optimizer, we consider all estimations to be the > sooth. This patch modifies only one place: having two equal assumptions, > we just choose one that generally looks more stable. > Filtered tuples should be calculated and included in the cost of the > path. The decision on the equality of paths has been made in view of the > estimation of these filtered tuples. Even if estimates are accurate the conditions in the patch doesn't guarantee there is actually a unique condition. # create table t as select i/1000 a, i % 1000 b, i % 1000 c from generate_series(1,1000000) i; # create unique index t_unique_idx on t(a,b); # create index t_another_idx on t(a,c); # \d t Table "public.t" Column | Type | Collation | Nullable | Default --------+---------+-----------+----------+--------- a | integer | | | b | integer | | | c | integer | | | Indexes: "t_another_idx" btree (a, c) "t_unique_idx" UNIQUE, btree (a, b) # set enable_bitmapscan = off; explain select * from t where a = 1 and c = 1; SET Time: 0.459 ms QUERY PLAN -------------------------------------------------------------------------- Index Scan using t_unique_idx on t (cost=0.42..1635.16 rows=1 width=12) Index Cond: (a = 1) Filter: (c = 1) (3 rows) > > 2) Even for non-unique indexes this patch is putting new logic on top > > of the subsequent code. How we can prove it's going to be a win? > > That could lead, for instance, to dropping parallel-safe paths in > > cases we didn't do so before. > Because we must trust all predictions made by the planner, we just > choose the most trustworthy path. According to the planner logic, it is > a path with a smaller selectivity. We can make mistakes anyway just > because of the nature of estimation. Even if we need to take selectivity into account here, it's still not clear why this should be on top of other logic later in add_path(). > > Anyway, please start a separate thread if you're willing to put more > > work into this. > > Done Thanks. ------ Regards, Alexander Korotkov ^ permalink raw reply [nested|flat] 3+ messages in thread
end of thread, other threads:[~2023-12-22 09:48 UTC | newest] Thread overview: 3+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2021-01-30 03:37 [PATCH v24 03/10] Add default_toast_compression GUC Justin Pryzby <[email protected]> 2023-12-22 06:53 Optimization outcome depends on the index order Andrei Lepikhov <[email protected]> 2023-12-22 09:48 ` Re: Optimization outcome depends on the index order Alexander Korotkov <[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