public inbox for [email protected]help / color / mirror / Atom feed
[PATCH v38 09/11] Add support for min/max aggregates for IVM 13+ messages / 5 participants [nested] [flat]
* [PATCH v38 09/11] Add support for min/max aggregates for IVM @ 2023-05-31 11:58 Yugo Nagata <[email protected]> 0 siblings, 0 replies; 13+ messages in thread From: Yugo Nagata @ 2023-05-31 11:58 UTC (permalink / raw) Supporting min and max is more complicated than count, sum, or avg. For an example of min, when tuples are inserted, the current min value in the view and the min value in the inseteted tuples are compared, then the smaller one is used as the latest min value. On the other hand, when tuples are deleted, if the current min value in the view equals to the min in the deleted tuples, we need re-computation the latest min value from base tables. Otherwise, the current value in the view remains. --- src/backend/commands/createas.c | 45 +++ src/backend/commands/matview.c | 644 +++++++++++++++++++++++++++++++- 2 files changed, 680 insertions(+), 9 deletions(-) diff --git a/src/backend/commands/createas.c b/src/backend/commands/createas.c index 35e124694ab..540d9e3d5c8 100644 --- a/src/backend/commands/createas.c +++ b/src/backend/commands/createas.c @@ -1341,6 +1341,51 @@ check_aggregate_supports_ivm(Oid aggfnoid) case F_AVG_FLOAT8: case F_AVG_INTERVAL: + /* min */ + case F_MIN_ANYARRAY: + case F_MIN_INT8: + case F_MIN_INT4: + case F_MIN_INT2: + case F_MIN_OID: + case F_MIN_FLOAT4: + case F_MIN_FLOAT8: + case F_MIN_DATE: + case F_MIN_TIME: + case F_MIN_TIMETZ: + case F_MIN_MONEY: + case F_MIN_TIMESTAMP: + case F_MIN_TIMESTAMPTZ: + case F_MIN_INTERVAL: + case F_MIN_TEXT: + case F_MIN_NUMERIC: + case F_MIN_BPCHAR: + case F_MIN_TID: + case F_MIN_ANYENUM: + case F_MIN_INET: + case F_MIN_PG_LSN: + + /* max */ + case F_MAX_ANYARRAY: + case F_MAX_INT8: + case F_MAX_INT4: + case F_MAX_INT2: + case F_MAX_OID: + case F_MAX_FLOAT4: + case F_MAX_FLOAT8: + case F_MAX_DATE: + case F_MAX_TIME: + case F_MAX_TIMETZ: + case F_MAX_MONEY: + case F_MAX_TIMESTAMP: + case F_MAX_TIMESTAMPTZ: + case F_MAX_INTERVAL: + case F_MAX_TEXT: + case F_MAX_NUMERIC: + case F_MAX_BPCHAR: + case F_MAX_TID: + case F_MAX_ANYENUM: + case F_MAX_INET: + case F_MAX_PG_LSN: return true; default: diff --git a/src/backend/commands/matview.c b/src/backend/commands/matview.c index 710224aa994..3b3871c49e2 100644 --- a/src/backend/commands/matview.c +++ b/src/backend/commands/matview.c @@ -69,6 +69,34 @@ typedef struct #define MV_INIT_QUERYHASHSIZE 16 +/* MV query type codes */ +#define MV_PLAN_RECALC 1 +#define MV_PLAN_SET_VALUE 2 + +/* + * MI_QueryKey + * + * The key identifying a prepared SPI plan in our query hashtable + */ +typedef struct MV_QueryKey +{ + Oid matview_id; /* OID of materialized view */ + int32 query_type; /* query type ID, see MV_PLAN_XXX above */ +} MV_QueryKey; + +/* + * MV_QueryHashEntry + * + * Hash entry for cached plans used to maintain materialized views. + */ +typedef struct MV_QueryHashEntry +{ + MV_QueryKey key; + SPIPlanPtr plan; + SearchPathMatcher *search_path; /* search_path used for parsing + * and planning */ +} MV_QueryHashEntry; + /* * MV_TriggerHashEntry * @@ -121,6 +149,7 @@ typedef struct DroppedImmvInfo } DroppedImmvInfo; static HTAB *mv_trigger_info = NULL; +static HTAB *mv_query_cache = NULL; static HTAB *dropped_immv = NULL; static HTAB *LastIvmUpdateHash; @@ -210,6 +239,9 @@ static void append_set_clause_for_sum(const char *resname, StringInfo buf_old, static void append_set_clause_for_avg(const char *resname, StringInfo buf_old, StringInfo buf_new, StringInfo aggs_list, const char *aggtype); +static void append_set_clause_for_minmax(const char *resname, StringInfo buf_old, + StringInfo buf_new, StringInfo aggs_list, + bool is_min); static char *get_operation_string(IvmOp op, const char *col, const char *arg1, const char *arg2, const char* count_col, const char *castType); static char *get_null_condition_string(IvmOp op, const char *arg1, const char *arg2, @@ -218,17 +250,30 @@ static void apply_old_delta(const char *matviewname, const char *deltaname_old, List *keys); static void apply_old_delta_with_count(const char *matviewname, const char *deltaname_old, List *keys, StringInfo aggs_list, StringInfo aggs_set, - const char *count_colname); + List *minmax_list, List *is_min_list, + const char *count_colname, + SPITupleTable **tuptable_recalc, uint64 *num_recalc); static void apply_new_delta(const char *matviewname, const char *deltaname_new, StringInfo target_list); static void apply_new_delta_with_count(const char *matviewname, const char* deltaname_new, List *keys, StringInfo target_list, StringInfo aggs_set, const char* count_colname); static char *get_matching_condition_string(List *keys); +static char *get_returning_string(List *minmax_list, List *is_min_list, List *keys); +static char *get_minmax_recalc_condition_string(List *minmax_list, List *is_min_list); +static char *get_select_for_recalc_string(List *keys); +static void recalc_and_set_values(SPITupleTable *tuptable_recalc, int64 num_tuples, + List *namelist, List *keys, Relation matviewRel); +static SPIPlanPtr get_plan_for_recalc(Oid matviewOid, List *namelist, List *keys, Oid *keyTypes); +static SPIPlanPtr get_plan_for_set_values(Oid matviewOid, char *matviewname, List *namelist, + Oid *valTypes); static void generate_equal(StringInfo querybuf, Oid opttype, const char *leftop, const char *rightop); static void mv_InitHashTables(void); +static SPIPlanPtr mv_FetchPreparedPlan(MV_QueryKey *key); +static void mv_HashPreparedPlan(MV_QueryKey *key, SPIPlanPtr plan); +static void mv_BuildQueryKey(MV_QueryKey *key, Oid matview_id, int32 query_type); static void clean_up_IVM_hash_entry(MV_TriggerHashEntry *entry, bool is_abort, SubTransactionId subxid); static void setLastUpdateXid(Oid immv_oid, FullTransactionId xid); @@ -2343,6 +2388,8 @@ apply_delta(Oid matviewOid, Tuplestorestate *old_tuplestores, Tuplestorestate *n ListCell *lc; int i; List *keys = NIL; + List *minmax_list = NIL; + List *is_min_list = NIL; /* @@ -2424,6 +2471,17 @@ apply_delta(Oid matviewOid, Tuplestorestate *old_tuplestores, Tuplestorestate *n append_set_clause_for_avg(resname, aggs_set_old, aggs_set_new, aggs_list_buf, format_type_be(aggref->aggtype)); + /* min/max */ + else if (!strcmp(aggname, "min") || !strcmp(aggname, "max")) + { + bool is_min = (!strcmp(aggname, "min")); + + append_set_clause_for_minmax(resname, aggs_set_old, aggs_set_new, aggs_list_buf, is_min); + + /* make a resname list of min and max aggregates */ + minmax_list = lappend(minmax_list, resname); + is_min_list = lappend_int(is_min_list, is_min); + } else elog(ERROR, "unsupported aggregate function: %s", aggname); } @@ -2453,6 +2511,8 @@ apply_delta(Oid matviewOid, Tuplestorestate *old_tuplestores, Tuplestorestate *n if (old_tuplestores && tuplestore_tuple_count(old_tuplestores) > 0) { EphemeralNamedRelation enr = palloc(sizeof(EphemeralNamedRelationData)); + SPITupleTable *tuptable_recalc = NULL; + uint64 num_recalc; int rc; /* convert tuplestores to ENR, and register for SPI */ @@ -2471,10 +2531,18 @@ apply_delta(Oid matviewOid, Tuplestorestate *old_tuplestores, Tuplestorestate *n /* apply old delta and get rows to be recalculated */ apply_old_delta_with_count(matviewname, OLD_DELTA_ENRNAME, keys, aggs_list_buf, aggs_set_old, - count_colname); + minmax_list, is_min_list, + count_colname, &tuptable_recalc, &num_recalc); else apply_old_delta(matviewname, OLD_DELTA_ENRNAME, keys); + /* + * If we have min or max, we might have to recalculate aggregate values from base tables + * on some tuples. TIDs and keys such tuples are returned as a result of the above query. + */ + if (minmax_list && tuptable_recalc) + recalc_and_set_values(tuptable_recalc, num_recalc, minmax_list, keys, matviewRel); + } /* For tuple insertion */ if (new_tuplestores && tuplestore_tuple_count(new_tuplestores) > 0) @@ -2666,6 +2734,70 @@ append_set_clause_for_avg(const char *resname, StringInfo buf_old, ); } +/* + * append_set_clause_for_minmax + * + * Append SET clause string for min or max aggregation to given buffers. + * Also, append resnames required for calculating the aggregate value. + * is_min is true if this is min, false if not. + */ +static void +append_set_clause_for_minmax(const char *resname, StringInfo buf_old, + StringInfo buf_new, StringInfo aggs_list, + bool is_min) +{ + char *count_col = IVM_colname("count", resname); + + /* For tuple deletion */ + if (buf_old) + { + /* + * If the new value doesn't became NULL then use the value remaining + * in the view although this will be recomputated afterwords. + */ + appendStringInfo(buf_old, + ", %s = CASE WHEN %s THEN NULL ELSE %s END", + quote_qualified_identifier(NULL, resname), + get_null_condition_string(IVM_SUB, "mv", "t", count_col), + quote_qualified_identifier("mv", resname) + ); + /* count = mv.count - t.count */ + appendStringInfo(buf_old, + ", %s = %s", + quote_qualified_identifier(NULL, count_col), + get_operation_string(IVM_SUB, count_col, "mv", "t", NULL, NULL) + ); + } + /* For tuple insertion */ + if (buf_new) + { + /* + * min = LEAST(mv.min, diff.min) + * max = GREATEST(mv.max, diff.max) + */ + appendStringInfo(buf_new, + ", %s = CASE WHEN %s THEN NULL ELSE %s(%s,%s) END", + quote_qualified_identifier(NULL, resname), + get_null_condition_string(IVM_ADD, "mv", "diff", count_col), + + is_min ? "LEAST" : "GREATEST", + quote_qualified_identifier("mv", resname), + quote_qualified_identifier("diff", resname) + ); + /* count = mv.count + diff.count */ + appendStringInfo(buf_new, + ", %s = %s", + quote_qualified_identifier(NULL, count_col), + get_operation_string(IVM_ADD, count_col, "mv", "diff", NULL, NULL) + ); + } + + appendStringInfo(aggs_list, ", %s, %s", + quote_qualified_identifier("diff", resname), + quote_qualified_identifier("diff", IVM_colname("count", resname)) + ); +} + /* * get_operation_string * @@ -2768,19 +2900,44 @@ get_null_condition_string(IvmOp op, const char *arg1, const char *arg2, * list to identify a tuple in the view. If the view has aggregates, this * requires strings representing resnames of aggregates and SET clause for * updating aggregate values. + * + * If the view has min or max aggregate, this requires a list of resnames of + * min/max aggregates and a list of boolean which represents which entries in + * minmax_list is min. These are necessary to check if we need to recalculate + * min or max aggregate values. In this case, this query returns TID and keys + * of tuples which need to be recalculated. This result and the number of rows + * are stored in tuptables and num_recalc repectedly. + * */ static void apply_old_delta_with_count(const char *matviewname, const char *deltaname_old, List *keys, StringInfo aggs_list, StringInfo aggs_set, - const char *count_colname) + List *minmax_list, List *is_min_list, + const char *count_colname, + SPITupleTable **tuptable_recalc, uint64 *num_recalc) { StringInfoData querybuf; char *match_cond; + char *updt_returning = ""; + char *select_for_recalc = "SELECT"; bool agg_without_groupby = (list_length(keys) == 0); + Assert(tuptable_recalc != NULL); + Assert(num_recalc != NULL); + /* build WHERE condition for searching tuples to be deleted */ match_cond = get_matching_condition_string(keys); + /* + * We need a special RETURNING clause and SELECT statement for min/max to + * check which tuple needs re-calculation from base tables. + */ + if (minmax_list) + { + updt_returning = get_returning_string(minmax_list, is_min_list, keys); + select_for_recalc = get_select_for_recalc_string(keys); + } + /* Search for matching tuples from the view and update or delete if found. */ initStringInfo(&querybuf); appendStringInfo(&querybuf, @@ -2795,10 +2952,11 @@ apply_old_delta_with_count(const char *matviewname, const char *deltaname_old, "UPDATE %s AS mv SET %s = mv.%s OPERATOR(pg_catalog.-) t.%s " "%s" /* SET clauses for aggregates */ "FROM t WHERE mv.ctid OPERATOR(pg_catalog.=) t.ctid AND NOT for_dlt " - ")" - /* delete a tuple if this is to be deleted */ - "DELETE FROM %s AS mv USING t " - "WHERE mv.ctid OPERATOR(pg_catalog.=) t.ctid AND for_dlt", + "%s" /* RETURNING clause for recalc infomation */ + "), dlt AS (" /* delete a tuple if this is to be deleted */ + "DELETE FROM %s AS mv USING t " + "WHERE mv.ctid OPERATOR(pg_catalog.=) t.ctid AND for_dlt" + ") %s", /* SELECT returning which tuples need to be recalculated */ count_colname, count_colname, count_colname, (agg_without_groupby ? "false" : "true"), (aggs_list != NULL ? aggs_list->data : ""), @@ -2806,10 +2964,25 @@ apply_old_delta_with_count(const char *matviewname, const char *deltaname_old, match_cond, matviewname, count_colname, count_colname, count_colname, (aggs_set != NULL ? aggs_set->data : ""), - matviewname); + updt_returning, + matviewname, + select_for_recalc); - if (SPI_exec(querybuf.data, 0) != SPI_OK_DELETE) + if (SPI_exec(querybuf.data, 0) != SPI_OK_SELECT) elog(ERROR, "SPI_exec failed: %s", querybuf.data); + + + /* Return tuples to be recalculated. */ + if (minmax_list) + { + *tuptable_recalc = SPI_tuptable; + *num_recalc = SPI_processed; + } + else + { + *tuptable_recalc = NULL; + *num_recalc = 0; + } } /* @@ -2992,6 +3165,349 @@ get_matching_condition_string(List *keys) return match_cond.data; } +/* + * get_returning_string + * + * Build a string for RETURNING clause of UPDATE used in apply_old_delta_with_count. + * This clause returns ctid and a boolean value that indicates if we need to + * recalculate min or max value, for each updated row. + */ +static char * +get_returning_string(List *minmax_list, List *is_min_list, List *keys) +{ + StringInfoData returning; + char *recalc_cond; + ListCell *lc; + + Assert(minmax_list != NIL && is_min_list != NIL); + recalc_cond = get_minmax_recalc_condition_string(minmax_list, is_min_list); + + initStringInfo(&returning); + + appendStringInfo(&returning, "RETURNING mv.ctid AS tid, (%s) AS recalc", recalc_cond); + foreach (lc, keys) + { + Form_pg_attribute attr = (Form_pg_attribute) lfirst(lc); + char *resname = NameStr(attr->attname); + appendStringInfo(&returning, ", %s", quote_qualified_identifier("mv", resname)); + } + + return returning.data; +} + +/* + * get_minmax_recalc_condition_string + * + * Build a predicate string for checking if any min/max aggregate + * value needs to be recalculated. + */ +static char * +get_minmax_recalc_condition_string(List *minmax_list, List *is_min_list) +{ + StringInfoData recalc_cond; + ListCell *lc1, *lc2; + + initStringInfo(&recalc_cond); + + Assert (list_length(minmax_list) == list_length(is_min_list)); + + forboth (lc1, minmax_list, lc2, is_min_list) + { + char *resname = (char *) lfirst(lc1); + bool is_min = (bool) lfirst_int(lc2); + char *op_str = (is_min ? ">=" : "<="); + + appendStringInfo(&recalc_cond, "%s OPERATOR(pg_catalog.%s) %s", + quote_qualified_identifier("mv", resname), + op_str, + quote_qualified_identifier("t", resname) + ); + + if (lnext(minmax_list, lc1)) + appendStringInfo(&recalc_cond, " OR "); + } + + return recalc_cond.data; +} + +/* + * get_select_for_recalc_string + * + * Build a query to return tid and keys of tuples which need + * recalculation. This is used as the result of the query + * built by apply_old_delta. + */ +static char * +get_select_for_recalc_string(List *keys) +{ + StringInfoData qry; + ListCell *lc; + + initStringInfo(&qry); + + appendStringInfo(&qry, "SELECT tid"); + foreach (lc, keys) + { + Form_pg_attribute attr = (Form_pg_attribute) lfirst(lc); + appendStringInfo(&qry, ", %s", NameStr(attr->attname)); + } + + appendStringInfo(&qry, " FROM updt WHERE recalc"); + + return qry.data; +} + +/* + * recalc_and_set_values + * + * Recalculate tuples in a materialized from base tables and update these. + * The tuples which needs recalculation are specified by keys, and resnames + * of columns to be updated are specified by namelist. TIDs and key values + * are given by tuples in tuptable_recalc. Its first attribute must be TID + * and key values must be following this. + */ +static void +recalc_and_set_values(SPITupleTable *tuptable_recalc, int64 num_tuples, + List *namelist, List *keys, Relation matviewRel) +{ + TupleDesc tupdesc_recalc = tuptable_recalc->tupdesc; + Oid *keyTypes = NULL, *types = NULL; + char *keyNulls = NULL, *nulls = NULL; + Datum *keyVals = NULL, *vals = NULL; + int num_vals = list_length(namelist); + int num_keys = list_length(keys); + uint64 i; + Oid matviewOid; + char *matviewname; + + matviewOid = RelationGetRelid(matviewRel); + matviewname = quote_qualified_identifier(get_namespace_name(RelationGetNamespace(matviewRel)), + RelationGetRelationName(matviewRel)); + + /* If we have keys, initialize arrays for them. */ + if (keys) + { + keyTypes = palloc(sizeof(Oid) * num_keys); + keyNulls = palloc(sizeof(char) * num_keys); + keyVals = palloc(sizeof(Datum) * num_keys); + /* a tuple contains keys to be recalculated and ctid to be updated*/ + Assert(tupdesc_recalc->natts == num_keys + 1); + + /* Types of key attributes */ + for (i = 0; i < num_keys; i++) + keyTypes[i] = TupleDescAttr(tupdesc_recalc, i + 1)->atttypid; + } + + /* allocate memory for all attribute names and tid */ + types = palloc(sizeof(Oid) * (num_vals + 1)); + nulls = palloc(sizeof(char) * (num_vals + 1)); + vals = palloc(sizeof(Datum) * (num_vals + 1)); + + /* For each tuple which needs recalculation */ + for (i = 0; i < num_tuples; i++) + { + int j; + bool isnull; + SPIPlanPtr plan; + SPITupleTable *tuptable_newvals; + TupleDesc tupdesc_newvals; + + /* Set group key values as parameters if needed. */ + if (keys) + { + for (j = 0; j < num_keys; j++) + { + keyVals[j] = SPI_getbinval(tuptable_recalc->vals[i], tupdesc_recalc, j + 2, &isnull); + if (isnull) + keyNulls[j] = 'n'; + else + keyNulls[j] = ' '; + } + } + + /* + * Get recalculated values from base tables. The result must be + * only one tuple thich contains the new values for specified keys. + */ + plan = get_plan_for_recalc(matviewOid, namelist, keys, keyTypes); + if (SPI_execute_plan(plan, keyVals, keyNulls, false, 0) != SPI_OK_SELECT) + elog(ERROR, "SPI_execute_plan"); + if (SPI_processed != 1) + elog(ERROR, "SPI_execute_plan returned zero or more than one rows"); + + tuptable_newvals = SPI_tuptable; + tupdesc_newvals = tuptable_newvals->tupdesc; + + Assert(tupdesc_newvals->natts == num_vals); + + /* Set the new values as parameters */ + for (j = 0; j < tupdesc_newvals->natts; j++) + { + if (i == 0) + types[j] = TupleDescAttr(tupdesc_newvals, j)->atttypid; + + vals[j] = SPI_getbinval(tuptable_newvals->vals[0], tupdesc_newvals, j + 1, &isnull); + if (isnull) + nulls[j] = 'n'; + else + nulls[j] = ' '; + } + /* Set TID of the view tuple to be updated as a parameter */ + types[j] = TIDOID; + vals[j] = SPI_getbinval(tuptable_recalc->vals[i], tupdesc_recalc, 1, &isnull); + nulls[j] = ' '; + + /* Update the view tuple to the new values */ + plan = get_plan_for_set_values(matviewOid, matviewname, namelist, types); + if (SPI_execute_plan(plan, vals, nulls, false, 0) != SPI_OK_UPDATE) + elog(ERROR, "SPI_execute_plan"); + } +} + + +/* + * get_plan_for_recalc + * + * Create or fetch a plan for recalculating value in the view's target list + * from base tables using the definition query of materialized view specified + * by matviewOid. namelist is a list of resnames of values to be recalculated. + * + * keys is a list of keys to identify tuples to be recalculated if this is not + * empty. KeyTypes is an array of types of keys. + */ +static SPIPlanPtr +get_plan_for_recalc(Oid matviewOid, List *namelist, List *keys, Oid *keyTypes) +{ + MV_QueryKey hash_key; + SPIPlanPtr plan; + + /* Fetch or prepare a saved plan for the recalculation */ + mv_BuildQueryKey(&hash_key, matviewOid, MV_PLAN_RECALC); + if ((plan = mv_FetchPreparedPlan(&hash_key)) == NULL) + { + ListCell *lc; + StringInfoData str; + char *viewdef; + + /* get view definition of matview */ + viewdef = text_to_cstring((text *) DatumGetPointer( + DirectFunctionCall1(pg_get_viewdef, ObjectIdGetDatum(matviewOid)))); + /* get rid of trailing semi-colon */ + viewdef[strlen(viewdef)-1] = '\0'; + + /* + * Build a query string for recalculating values. This is like + * + * SELECT x1, x2, x3, ... FROM ( ... view definition query ...) mv + * WHERE (key1, key2, ...) = ($1, $2, ...); + */ + + initStringInfo(&str); + appendStringInfo(&str, "SELECT "); + foreach (lc, namelist) + { + appendStringInfo(&str, "%s", (char *) lfirst(lc)); + if (lnext(namelist, lc)) + appendStringInfoString(&str, ", "); + } + appendStringInfo(&str, " FROM (%s) mv", viewdef); + + if (keys) + { + int i = 1; + char paramname[16]; + + appendStringInfo(&str, " WHERE ("); + foreach (lc, keys) + { + Form_pg_attribute attr = (Form_pg_attribute) lfirst(lc); + char *resname = NameStr(attr->attname); + Oid typid = attr->atttypid; + + sprintf(paramname, "$%d", i); + appendStringInfo(&str, "("); + generate_equal(&str, typid, resname, paramname); + appendStringInfo(&str, " OR (%s IS NULL AND %s IS NULL))", + resname, paramname); + + if (lnext(keys, lc)) + appendStringInfoString(&str, " AND "); + i++; + } + appendStringInfo(&str, ")"); + } + else + keyTypes = NULL; + + plan = SPI_prepare(str.data, list_length(keys), keyTypes); + if (plan == NULL) + elog(ERROR, "SPI_prepare returned %s for %s", SPI_result_code_string(SPI_result), str.data); + + SPI_keepplan(plan); + mv_HashPreparedPlan(&hash_key, plan); + } + + return plan; +} + +/* + * get_plan_for_set_values + * + * Create or fetch a plan for applying new values calculated by + * get_plan_for_recalc to a materialized view specified by matviewOid. + * matviewname is the name of the view. namelist is a list of resnames + * of attributes to be updated, and valTypes is an array of types of the + * values. + */ +static SPIPlanPtr +get_plan_for_set_values(Oid matviewOid, char *matviewname, List *namelist, + Oid *valTypes) +{ + MV_QueryKey key; + SPIPlanPtr plan; + + /* Fetch or prepare a saved plan for the real check */ + mv_BuildQueryKey(&key, matviewOid, MV_PLAN_SET_VALUE); + if ((plan = mv_FetchPreparedPlan(&key)) == NULL) + { + ListCell *lc; + StringInfoData str; + int i; + + /* + * Build a query string for applying min/max values. This is like + * + * UPDATE matviewname AS mv + * SET (x1, x2, x3, x4) = ($1, $2, $3, $4) + * WHERE ctid = $5; + */ + + initStringInfo(&str); + appendStringInfo(&str, "UPDATE %s AS mv SET (", matviewname); + foreach (lc, namelist) + { + appendStringInfo(&str, "%s", (char *) lfirst(lc)); + if (lnext(namelist, lc)) + appendStringInfoString(&str, ", "); + } + appendStringInfo(&str, ") = ROW("); + + for (i = 1; i <= list_length(namelist); i++) + appendStringInfo(&str, "%s$%d", (i==1 ? "" : ", "), i); + + appendStringInfo(&str, ") WHERE ctid OPERATOR(pg_catalog.=) $%d", i); + + plan = SPI_prepare(str.data, list_length(namelist) + 1, valTypes); + if (plan == NULL) + elog(ERROR, "SPI_prepare returned %s for %s", SPI_result_code_string(SPI_result), str.data); + + SPI_keepplan(plan); + mv_HashPreparedPlan(&key, plan); + } + + return plan; +} + /* * generate_equals * @@ -3025,6 +3541,13 @@ mv_InitHashTables(void) { HASHCTL ctl; + memset(&ctl, 0, sizeof(ctl)); + ctl.keysize = sizeof(MV_QueryKey); + ctl.entrysize = sizeof(MV_QueryHashEntry); + mv_query_cache = hash_create("MV query cache", + MV_INIT_QUERYHASHSIZE, + &ctl, HASH_ELEM | HASH_BLOBS); + memset(&ctl, 0, sizeof(ctl)); ctl.keysize = sizeof(Oid); ctl.entrysize = sizeof(MV_TriggerHashEntry); @@ -3039,6 +3562,109 @@ mv_InitHashTables(void) &ctl, HASH_ELEM | HASH_BLOBS); } +/* + * mv_FetchPreparedPlan + */ +static SPIPlanPtr +mv_FetchPreparedPlan(MV_QueryKey *key) +{ + MV_QueryHashEntry *entry; + SPIPlanPtr plan; + + /* + * On the first call initialize the hashtable + */ + if (!mv_query_cache) + mv_InitHashTables(); + + /* + * Lookup for the key + */ + entry = (MV_QueryHashEntry *) hash_search(mv_query_cache, + (void *) key, + HASH_FIND, NULL); + if (entry == NULL) + return NULL; + + /* + * Check whether the plan is still valid. If it isn't, we don't want to + * simply rely on plancache.c to regenerate it; rather we should start + * from scratch and rebuild the query text too. This is to cover cases + * such as table/column renames. We depend on the plancache machinery to + * detect possible invalidations, though. + * + * CAUTION: this check is only trustworthy if the caller has already + * locked both materialized views and base tables. + * + * Also, check whether the search_path is still the same as when we made it. + * If it isn't, we need to rebuild the query text because the result of + * pg_ivm_get_viewdef() will change. + */ + plan = entry->plan; + if (plan && SPI_plan_is_valid(plan) && + SearchPathMatchesCurrentEnvironment(entry->search_path)) + return plan; + + /* + * Otherwise we might as well flush the cached plan now, to free a little + * memory space before we make a new one. + */ + if (plan) + SPI_freeplan(plan); + if (entry->search_path) + pfree(entry->search_path); + + entry->plan = NULL; + entry->search_path = NULL; + + return NULL; +} + +/* + * mv_HashPreparedPlan + * + * Add another plan to our private SPI query plan hashtable. + */ +static void +mv_HashPreparedPlan(MV_QueryKey *key, SPIPlanPtr plan) +{ + MV_QueryHashEntry *entry; + bool found; + + /* + * On the first call initialize the hashtable + */ + if (!mv_query_cache) + mv_InitHashTables(); + + /* + * Add the new plan. We might be overwriting an entry previously found + * invalid by mv_FetchPreparedPlan. + */ + entry = (MV_QueryHashEntry *) hash_search(mv_query_cache, + (void *) key, + HASH_ENTER, &found); + Assert(!found || entry->plan == NULL); + entry->plan = plan; + entry->search_path = GetSearchPathMatcher(TopMemoryContext); +} + +/* + * mv_BuildQueryKey + * + * Construct a hashtable key for a prepared SPI plan for IVM. + */ +static void +mv_BuildQueryKey(MV_QueryKey *key, Oid matview_id, int32 query_type) +{ + /* + * We assume struct MV_QueryKey contains no padding bytes, else we'd need + * to use memset to clear them. + */ + key->matview_id = matview_id; + key->query_type = query_type; +} + /* * AtAbort_IVM * -- 2.43.0 --Multipart=_Wed__1_Jul_2026_00_04_01_+0900_OVSy2WWK_9aByzDJ Content-Type: text/x-diff; name="v38-0008-Add-aggregates-support-in-IVM.patch" Content-Disposition: attachment; filename="v38-0008-Add-aggregates-support-in-IVM.patch" Content-Transfer-Encoding: quoted-printable ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: POC: GROUP BY optimization @ 2023-12-27 02:48 Alexander Korotkov <[email protected]> 0 siblings, 1 reply; 13+ messages in thread From: Alexander Korotkov @ 2023-12-27 02:48 UTC (permalink / raw) To: Andrei Lepikhov <[email protected]>; +Cc: PostgreSQL Developers <[email protected]>; Tomas Vondra <[email protected]>; Teodor Sigaev <[email protected]>; David Rowley <[email protected]>; a.rybakina <[email protected]>; Белялов Дамир Наилевич <[email protected]>; Tom Lane <[email protected]> On Tue, Dec 26, 2023 at 1:37 PM Andrei Lepikhov <[email protected]> wrote: > On 21/12/2023 17:53, Alexander Korotkov wrote: > > On Sun, Oct 1, 2023 at 11:45 AM Andrei Lepikhov > > <[email protected]> wrote: > >> New version of the patch. Fixed minor inconsistencies and rebased onto > >> current master. > > Thank you (and other authors) for working on this subject. Indeed to > > GROUP BY clauses are order-agnostic. Reordering them in the most > > suitable order could give up significant query planning benefits. I > > went through the thread: I see significant work has been already made > > on this patch, the code is quite polished. > Maybe, but issues, mentioned in [1], still not resolved. It is the only > reason, why this thread hasn't been active. Yes, this makes sense. I have a couple of points from me on this subject. 1) The patch reorders GROUP BY items not only to make comparison cheaper but also to match the ordering of input paths and to match the ORDER BY clause. Thus, even if we leave aside for now sorting GROUP BY items by their cost, the patch will remain valuable. 2) An accurate estimate of the sorting cost is quite a difficult task. What if we make a simple rule of thumb that sorting integers and floats is cheaper than sorting numerics and strings with collation C, in turn, that is cheaper than sorting collation-aware strings (probably more groups)? Within the group, we could keep the original order of items. ------ Regards, Alexander Korotkov ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: POC: GROUP BY optimization @ 2023-12-27 03:23 Tom Lane <[email protected]> parent: Alexander Korotkov <[email protected]> 0 siblings, 2 replies; 13+ messages in thread From: Tom Lane @ 2023-12-27 03:23 UTC (permalink / raw) To: Alexander Korotkov <[email protected]>; +Cc: Andrei Lepikhov <[email protected]>; PostgreSQL Developers <[email protected]>; Tomas Vondra <[email protected]>; Teodor Sigaev <[email protected]>; David Rowley <[email protected]>; a.rybakina <[email protected]>; Белялов Дамир Наилевич <[email protected]> Alexander Korotkov <[email protected]> writes: > 2) An accurate estimate of the sorting cost is quite a difficult task. Indeed. > What if we make a simple rule of thumb that sorting integers and > floats is cheaper than sorting numerics and strings with collation C, > in turn, that is cheaper than sorting collation-aware strings > (probably more groups)? Within the group, we could keep the original > order of items. I think it's a fool's errand to even try to separate different sort column orderings by cost. We simply do not have sufficiently accurate cost information. The previous patch in this thread got reverted because of that (well, also some implementation issues, but mostly that), and nothing has happened to make me think that another try will fare any better. regards, tom lane ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: POC: GROUP BY optimization @ 2023-12-27 04:15 Alexander Korotkov <[email protected]> parent: Tom Lane <[email protected]> 1 sibling, 3 replies; 13+ messages in thread From: Alexander Korotkov @ 2023-12-27 04:15 UTC (permalink / raw) To: Tom Lane <[email protected]>; +Cc: Andrei Lepikhov <[email protected]>; PostgreSQL Developers <[email protected]>; Tomas Vondra <[email protected]>; Teodor Sigaev <[email protected]>; David Rowley <[email protected]>; a.rybakina <[email protected]>; Белялов Дамир Наилевич <[email protected]> On Wed, Dec 27, 2023 at 5:23 AM Tom Lane <[email protected]> wrote: > Alexander Korotkov <[email protected]> writes: > > 2) An accurate estimate of the sorting cost is quite a difficult task. > > Indeed. > > > What if we make a simple rule of thumb that sorting integers and > > floats is cheaper than sorting numerics and strings with collation C, > > in turn, that is cheaper than sorting collation-aware strings > > (probably more groups)? Within the group, we could keep the original > > order of items. > > I think it's a fool's errand to even try to separate different sort > column orderings by cost. We simply do not have sufficiently accurate > cost information. The previous patch in this thread got reverted because > of that (well, also some implementation issues, but mostly that), and > nothing has happened to make me think that another try will fare any > better. If there is a choice of what to compare first: 8-bytes integers or collation-aware texts possibly toasted, then the answer is pretty evident for me. For sure, there are cases then this choice is wrong. But even if all the integers appear to be the same, the penalty isn't that much. Besides sorting column orderings by cost, this patch also tries to match GROUP BY pathkeys to input pathkeys and ORDER BY pathkeys. Do you think there is a chance for the second part if we leave the cost part aside? ------ Regards, Alexander Korotkov ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: POC: GROUP BY optimization @ 2023-12-27 04:27 Tom Lane <[email protected]> parent: Alexander Korotkov <[email protected]> 2 siblings, 0 replies; 13+ messages in thread From: Tom Lane @ 2023-12-27 04:27 UTC (permalink / raw) To: Alexander Korotkov <[email protected]>; +Cc: Andrei Lepikhov <[email protected]>; PostgreSQL Developers <[email protected]>; Tomas Vondra <[email protected]>; Teodor Sigaev <[email protected]>; David Rowley <[email protected]>; a.rybakina <[email protected]>; Белялов Дамир Наилевич <[email protected]> Alexander Korotkov <[email protected]> writes: > On Wed, Dec 27, 2023 at 5:23 AM Tom Lane <[email protected]> wrote: >> I think it's a fool's errand to even try to separate different sort >> column orderings by cost. > Besides sorting column orderings by cost, this patch also tries to > match GROUP BY pathkeys to input pathkeys and ORDER BY pathkeys. Do > you think there is a chance for the second part if we leave the cost > part aside? I think it's definitely reasonable to try to match up available orderings, because that doesn't really require fine distinctions of cost: either it matches or it doesn't. Eliminating a sort step entirely is clearly a win. (Incremental sort complicates this though. I doubt our cost model for incremental sorts is any good either, so I am not eager to rely on that more heavily.) regards, tom lane ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: POC: GROUP BY optimization @ 2023-12-27 04:35 Andrei Lepikhov <[email protected]> parent: Alexander Korotkov <[email protected]> 2 siblings, 0 replies; 13+ messages in thread From: Andrei Lepikhov @ 2023-12-27 04:35 UTC (permalink / raw) To: Alexander Korotkov <[email protected]>; Tom Lane <[email protected]>; +Cc: PostgreSQL Developers <[email protected]>; Tomas Vondra <[email protected]>; Teodor Sigaev <[email protected]>; David Rowley <[email protected]>; a.rybakina <[email protected]>; Белялов Дамир Наилевич <[email protected]> On 27/12/2023 11:15, Alexander Korotkov wrote: > On Wed, Dec 27, 2023 at 5:23 AM Tom Lane <[email protected]> wrote: >> Alexander Korotkov <[email protected]> writes: >>> 2) An accurate estimate of the sorting cost is quite a difficult task. >> >> Indeed. >> >>> What if we make a simple rule of thumb that sorting integers and >>> floats is cheaper than sorting numerics and strings with collation C, >>> in turn, that is cheaper than sorting collation-aware strings >>> (probably more groups)? Within the group, we could keep the original >>> order of items. >> >> I think it's a fool's errand to even try to separate different sort >> column orderings by cost. We simply do not have sufficiently accurate >> cost information. The previous patch in this thread got reverted because >> of that (well, also some implementation issues, but mostly that), and >> nothing has happened to make me think that another try will fare any >> better. To be clear. In [1], I mentioned we can perform micro-benchmarks and structure costs of operators. At least for fixed-length operators, it is relatively easy. So, the main block here is an accurate prediction of ndistincts for different combinations of columns. Does it make sense to continue to design the feature in the direction of turning on choosing between different sort column orderings if we have extended statistics on the columns? [1] https://www.postgresql.org/message-id/[email protected] -- regards, Andrei Lepikhov Postgres Professional ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: POC: GROUP BY optimization @ 2023-12-27 05:07 Tom Lane <[email protected]> parent: Alexander Korotkov <[email protected]> 2 siblings, 1 reply; 13+ messages in thread From: Tom Lane @ 2023-12-27 05:07 UTC (permalink / raw) To: Andrei Lepikhov <[email protected]>; +Cc: Alexander Korotkov <[email protected]>; PostgreSQL Developers <[email protected]>; Tomas Vondra <[email protected]>; Teodor Sigaev <[email protected]>; David Rowley <[email protected]>; a.rybakina <[email protected]>; Белялов Дамир Наилевич <[email protected]> Andrei Lepikhov <[email protected]> writes: > To be clear. In [1], I mentioned we can perform micro-benchmarks and > structure costs of operators. At least for fixed-length operators, it is > relatively easy. I repeat what I said: this is a fool's errand. You will not get trustworthy results even for the cases you measured, let alone all the rest. I'd go as far as to say I would not believe your microbenchmarks, because they would only apply for one platform, compiler, backend build, phase of the moon, etc. regards, tom lane ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: POC: GROUP BY optimization @ 2023-12-28 08:22 Andrei Lepikhov <[email protected]> parent: Tom Lane <[email protected]> 0 siblings, 1 reply; 13+ messages in thread From: Andrei Lepikhov @ 2023-12-28 08:22 UTC (permalink / raw) To: Tom Lane <[email protected]>; Alexander Korotkov <[email protected]>; +Cc: PostgreSQL Developers <[email protected]>; Tomas Vondra <[email protected]>; Teodor Sigaev <[email protected]>; David Rowley <[email protected]>; a.rybakina <[email protected]>; Белялов Дамир Наилевич <[email protected]> On 27/12/2023 12:07, Tom Lane wrote: > Andrei Lepikhov <[email protected]> writes: >> To be clear. In [1], I mentioned we can perform micro-benchmarks and >> structure costs of operators. At least for fixed-length operators, it is >> relatively easy. > > I repeat what I said: this is a fool's errand. You will not get > trustworthy results even for the cases you measured, let alone > all the rest. I'd go as far as to say I would not believe your > microbenchmarks, because they would only apply for one platform, > compiler, backend build, phase of the moon, etc. Thanks for the explanation. I removed all cost-related codes. It still needs to be finished; I will smooth the code further and rewrite regression tests - many of them without cost-dependent reorderings look silly. Also, remember Alexander's remarks, which must be implemented, too. But already here, it works well. Look: Preliminaries: CREATE TABLE t(x int, y int, z text, w int); INSERT INTO t SELECT gs%100,gs%100, 'abc' || gs%10, gs FROM generate_series(1,10000) AS gs; CREATE INDEX abc ON t(x,y); ANALYZE t; SET enable_hashagg = 'off'; This patch eliminates unneeded Sort operation: explain SELECT x,y FROM t GROUP BY (x,y); explain SELECT x,y FROM t GROUP BY (y,x); Engages incremental sort: explain SELECT x,y FROM t GROUP BY (x,y,z,w); explain SELECT x,y FROM t GROUP BY (z,y,w,x); explain SELECT x,y FROM t GROUP BY (w,z,x,y); explain SELECT x,y FROM t GROUP BY (w,x,z,y); Works with subqueries: explain SELECT x,y FROM (SELECT * FROM t ORDER BY x,y,w,z) AS q1 GROUP BY (w,x,z,y); explain SELECT x,y FROM (SELECT * FROM t ORDER BY x,y,w,z LIMIT 100) AS q1 GROUP BY (w,x,z,y); But arrangement with an ORDER BY clause doesn't work: DROP INDEX abc; explain SELECT x,w,z FROM t GROUP BY (w,x,z) ORDER BY (x,z,w); I think the reason is that the sort_pathkeys and group_pathkeys are physically different structures, and we can't just compare pointers here. -- regards, Andrei Lepikhov Postgres Professional From 6183555c2c56d7cbbc44f213f6c5bc4cbcaef1ec Mon Sep 17 00:00:00 2001 From: "Andrey V. Lepikhov" <[email protected]> Date: Wed, 13 Sep 2023 11:20:03 +0700 Subject: [PATCH] Explore alternative orderings of group-by pathkeys during optimization. When evaluating a query with a multi-column GROUP BY clause, we can minimize sort operations or avoid them if we synchronize the order of GROUP BY clauses with the ORDER BY sort clause or sort order, which comes from the underlying query tree. Grouping does not imply any ordering, so we can compare the keys in arbitrary order, and a Hash Agg leverages this. But for Group Agg, we simply compared keys in the order specified in the query. This commit explores alternative ordering of the keys, trying to find a cheaper one. The ordering of group keys may interact with other parts of the query, some of which may not be known while planning the grouping. For example, there may be an explicit ORDER BY clause or some other ordering-dependent operation higher up in the query, and using the same ordering may allow using either incremental sort or even eliminating the sort entirely. The patch always keeps the ordering specified in the query, assuming the user might have additional insights. This introduces a new GUC enable_group_by_reordering so that the optimization may be disabled if needed. --- src/backend/optimizer/path/equivclass.c | 13 +- src/backend/optimizer/path/pathkeys.c | 224 +++++++++ src/backend/optimizer/plan/planner.c | 464 ++++++++++-------- src/backend/utils/adt/selfuncs.c | 38 +- src/backend/utils/misc/guc_tables.c | 10 + src/backend/utils/misc/postgresql.conf.sample | 1 + src/include/nodes/pathnodes.h | 10 + src/include/optimizer/paths.h | 3 + src/test/regress/expected/aggregates.out | 235 +++++++++ .../regress/expected/incremental_sort.out | 20 +- src/test/regress/expected/sysviews.out | 3 +- src/test/regress/sql/aggregates.sql | 99 ++++ src/test/regress/sql/incremental_sort.sql | 2 +- 13 files changed, 912 insertions(+), 210 deletions(-) diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c index 7fa502d6e2..07edd4f38e 100644 --- a/src/backend/optimizer/path/equivclass.c +++ b/src/backend/optimizer/path/equivclass.c @@ -652,7 +652,18 @@ get_eclass_for_sort_expr(PlannerInfo *root, if (opcintype == cur_em->em_datatype && equal(expr, cur_em->em_expr)) - return cur_ec; /* Match! */ + { + /* + * Match! + * + * Copy the sortref if it wasn't set yet. That may happen if + * the ec was constructed from WHERE clause, i.e. it doesn't + * have a target reference at all. + */ + if (cur_ec->ec_sortref == 0 && sortref > 0) + cur_ec->ec_sortref = sortref; + return cur_ec; + } } } diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index fdb60aaa8d..38c1c85472 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -28,6 +28,8 @@ #include "partitioning/partbounds.h" #include "utils/lsyscache.h" +/* Consider reordering of GROUP BY keys? */ +bool enable_group_by_reordering = true; static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys); static bool matches_boolean_partition_clause(RestrictInfo *rinfo, @@ -350,6 +352,175 @@ pathkeys_contained_in(List *keys1, List *keys2) return false; } +/* + * group_keys_reorder_by_pathkeys + * Reorder GROUP BY keys to match pathkeys of input path. + * + * Function returns new lists (pathkeys and clauses), original GROUP BY lists + * stay untouched. + * + * Returns the number of GROUP BY keys with a matching pathkey. + */ +static int +group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys, + List **group_clauses, + int num_groupby_pathkeys) +{ + List *new_group_pathkeys = NIL, + *new_group_clauses = NIL; + ListCell *lc; + int n; + + if (pathkeys == NIL || *group_pathkeys == NIL) + return 0; + + /* + * Walk the pathkeys (determining ordering of the input path) and see if + * there's a matching GROUP BY key. If we find one, we append it to the + * list, and do the same for the clauses. + * + * Once we find the first pathkey without a matching GROUP BY key, the + * rest of the pathkeys are useless and can't be used to evaluate the + * grouping, so we abort the loop and ignore the remaining pathkeys. + * + * XXX Pathkeys are built in a way to allow simply comparing pointers. + */ + foreach(lc, pathkeys) + { + PathKey *pathkey = (PathKey *) lfirst(lc); + SortGroupClause *sgc; + + if (foreach_current_index(lc) >= num_groupby_pathkeys || + !list_member_ptr(*group_pathkeys, pathkey)) + /* */ + break; + + /* abort on first mismatch */ + sgc = get_sortgroupref_clause_noerr(pathkey->pk_eclass->ec_sortref, + *group_clauses); + if (!sgc) + /* The grouping clause is not cover this pathkey */ + break; + + new_group_pathkeys = lappend(new_group_pathkeys, pathkey); + new_group_clauses = lappend(new_group_clauses, sgc); + } + + /* remember the number of pathkeys with a matching GROUP BY key */ + n = list_length(new_group_pathkeys); + + /* append the remaining group pathkeys (will be treated as not sorted) */ + *group_pathkeys = list_concat_unique_ptr(new_group_pathkeys, + *group_pathkeys); + *group_clauses = list_concat_unique_ptr(new_group_clauses, + *group_clauses); + + return n; +} + +/* + * get_useful_group_keys_orderings + * Determine which orderings of GROUP BY keys are potentially interesting. + * + * Returns list of PathKeyInfo items, each representing an interesting ordering + * of GROUP BY keys. Each item stores pathkeys and clauses in matching order. + * + * The function considers (and keeps) multiple group by orderings: + * + * - the original ordering, as specified by the GROUP BY clause + * + * - GROUP BY keys reordered to minimize the sort cost + * + * - GROUP BY keys reordered to match path ordering (as much as possible), with + * the tail reordered to minimize the sort cost + * + * - GROUP BY keys to match target ORDER BY clause (as much as possible), with + * the tail reordered to minimize the sort cost + * + * There are other potentially interesting orderings (e.g. it might be best to + * match the first ORDER BY key, order the remaining keys differently and then + * rely on the incremental sort to fix this), but we ignore those for now. To + * make this work we'd have to pretty much generate all possible permutations. + */ +List * +get_useful_group_keys_orderings(PlannerInfo *root, double nrows, + List *path_pathkeys) +{ + Query *parse = root->parse; + List *infos = NIL; + PathKeyInfo *info; + + List *pathkeys = root->group_pathkeys; + List *clauses = root->processed_groupClause; + + /* always return at least the original pathkeys/clauses */ + info = makeNode(PathKeyInfo); + info->pathkeys = pathkeys; + info->clauses = clauses; + infos = lappend(infos, info); + + /* + * Should we try generating alternative orderings of the group keys? If + * not, we produce only the order specified in the query, i.e. the + * optimization is effectively disabled. + */ + if (!enable_group_by_reordering) + return infos; + + /* for grouping sets we can't do any reordering */ + if (parse->groupingSets) + return infos; + + /* + * If the path is sorted in some way, try reordering the group keys to + * match as much of the ordering as possible - we get this sort for free + * (mostly). + * + * We must not do this when there are no grouping sets, because those use + * more complex logic to decide the ordering. + * + * XXX Isn't this somewhat redundant with presorted_keys? Actually, it's + * more a complement, because it allows benefiting from incremental sort + * as much as possible. + */ + if (path_pathkeys) + { + group_keys_reorder_by_pathkeys(path_pathkeys, &pathkeys, &clauses, + root->num_groupby_pathkeys); + + /* + * reorder the tail to minimize sort cost + * + * XXX Ignore the return value - there may be nothing to reorder, But we + * still want to keep the keys reordered to path_pathkeys. + */ + info = makeNode(PathKeyInfo); + info->pathkeys = pathkeys; + info->clauses = clauses; + + infos = lappend(infos, info); + } + + /* + * Try reordering pathkeys to minimize the sort cost (this time consider + * the ORDER BY clause, but only if set debug_group_by_match_order_by). + */ + if (root->sort_pathkeys) + { + group_keys_reorder_by_pathkeys(root->sort_pathkeys, &pathkeys, &clauses, + root->num_groupby_pathkeys); + + /* keep the group keys reordered to match ordering of input path */ + info = makeNode(PathKeyInfo); + info->pathkeys = pathkeys; + info->clauses = clauses; + + infos = lappend(infos, info); + } + + return infos; +} + /* * pathkeys_count_contained_in * Same as pathkeys_contained_in, but also sets length of longest @@ -1939,6 +2110,54 @@ pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys) return n_common_pathkeys; } +/* + * pathkeys_useful_for_grouping + * Count the number of pathkeys that are useful for grouping (instead of + * explicit sort) + * + * Group pathkeys could be reordered to benefit from the ordering. The + * ordering may not be "complete" and may require incremental sort, but that's + * fine. So we simply count prefix pathkeys with a matching group key, and + * stop once we find the first pathkey without a match. + * + * So e.g. with pathkeys (a,b,c) and group keys (a,b,e) this determines (a,b) + * pathkeys are useful for grouping, and we might do incremental sort to get + * path ordered by (a,b,e). + * + * This logic is necessary to retain paths with ordering not matching grouping + * keys directly, without the reordering. + * + * Returns the length of pathkey prefix with matching group keys. + */ +static int +pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys) +{ + ListCell *key; + int n = 0; + + /* no special ordering requested for grouping */ + if (root->group_pathkeys == NIL) + return 0; + + /* unordered path */ + if (pathkeys == NIL) + return 0; + + /* walk the pathkeys and search for matching group key */ + foreach(key, pathkeys) + { + PathKey *pathkey = (PathKey *) lfirst(key); + + /* no matching group key, we're done */ + if (!list_member_ptr(root->group_pathkeys, pathkey)) + break; + + n++; + } + + return n; +} + /* * truncate_useless_pathkeys * Shorten the given pathkey list to just the useful pathkeys. @@ -1953,6 +2172,9 @@ truncate_useless_pathkeys(PlannerInfo *root, nuseful = pathkeys_useful_for_merging(root, rel, pathkeys); nuseful2 = pathkeys_useful_for_ordering(root, pathkeys); + if (nuseful2 > nuseful) + nuseful = nuseful2; + nuseful2 = pathkeys_useful_for_grouping(root, pathkeys); if (nuseful2 > nuseful) nuseful = nuseful2; @@ -1988,6 +2210,8 @@ has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel) { if (rel->joininfo != NIL || rel->has_eclass_joins) return true; /* might be able to use pathkeys for merging */ + if (root->group_pathkeys != NIL) + return true; /* might be able to use pathkeys for grouping */ if (root->query_pathkeys != NIL) return true; /* might be able to use them for ordering */ return false; /* definitely useless */ diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index 6f45efde21..fc774bfce6 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -2805,8 +2805,9 @@ remove_useless_groupby_columns(PlannerInfo *root) * * In principle it might be interesting to consider other orderings of the * GROUP BY elements, which could match the sort ordering of other - * possible plans (eg an indexscan) and thereby reduce cost. We don't - * bother with that, though. Hashed grouping will frequently win anyway. + * possible plans (eg an indexscan) and thereby reduce cost. However, we + * don't yet have sufficient information to do that here, so that's left until + * later in planning. See get_useful_group_keys_orderings(). * * Note: we need no comparable processing of the distinctClause because * the parser already enforced that that matches ORDER BY. @@ -6839,90 +6840,108 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel, */ foreach(lc, input_rel->pathlist) { + ListCell *lc2; Path *path = (Path *) lfirst(lc); - bool is_sorted; - int presorted_keys; + Path *path_save = path; + List *pathkey_orderings = NIL; - is_sorted = pathkeys_count_contained_in(root->group_pathkeys, - path->pathkeys, - &presorted_keys); + /* generate alternative group orderings that might be useful */ + pathkey_orderings = get_useful_group_keys_orderings(root, + path->rows, + path->pathkeys); - if (!is_sorted) + Assert(list_length(pathkey_orderings) > 0); + + foreach(lc2, pathkey_orderings) { - /* - * Try at least sorting the cheapest path and also try - * incrementally sorting any path which is partially sorted - * already (no need to deal with paths which have presorted - * keys when incremental sort is disabled unless it's the - * cheapest input path). - */ - if (path != cheapest_path && - (presorted_keys == 0 || !enable_incremental_sort)) - continue; + bool is_sorted; + int presorted_keys; + PathKeyInfo *info = (PathKeyInfo *) lfirst(lc2); - /* - * We've no need to consider both a sort and incremental sort. - * We'll just do a sort if there are no presorted keys and an - * incremental sort when there are presorted keys. - */ - if (presorted_keys == 0 || !enable_incremental_sort) - path = (Path *) create_sort_path(root, - grouped_rel, - path, - root->group_pathkeys, - -1.0); - else - path = (Path *) create_incremental_sort_path(root, - grouped_rel, - path, - root->group_pathkeys, - presorted_keys, - -1.0); - } + /* restore the path (we replace it in the loop) */ + path = path_save; - /* Now decide what to stick atop it */ - if (parse->groupingSets) - { - consider_groupingsets_paths(root, grouped_rel, - path, true, can_hash, - gd, agg_costs, dNumGroups); - } - else if (parse->hasAggs) - { - /* - * We have aggregation, possibly with plain GROUP BY. Make an - * AggPath. - */ - add_path(grouped_rel, (Path *) + is_sorted = pathkeys_count_contained_in(info->pathkeys, + path->pathkeys, + &presorted_keys); + + if (!is_sorted) + { + /* + * Try at least sorting the cheapest path and also try + * incrementally sorting any path which is partially sorted + * already (no need to deal with paths which have presorted + * keys when incremental sort is disabled unless it's the + * cheapest input path). + */ + if (path != cheapest_path && + (presorted_keys == 0 || !enable_incremental_sort)) + continue; + + /* + * We've no need to consider both a sort and incremental sort. + * We'll just do a sort if there are no presorted keys and an + * incremental sort when there are presorted keys. + */ + if (presorted_keys == 0 || !enable_incremental_sort) + path = (Path *) create_sort_path(root, + grouped_rel, + path, + info->pathkeys, + -1.0); + else + path = (Path *) create_incremental_sort_path(root, + grouped_rel, + path, + info->pathkeys, + presorted_keys, + -1.0); + } + + /* Now decide what to stick atop it */ + if (parse->groupingSets) + { + consider_groupingsets_paths(root, grouped_rel, + path, true, can_hash, + gd, agg_costs, dNumGroups); + } + else if (parse->hasAggs) + { + /* + * We have aggregation, possibly with plain GROUP BY. Make an + * AggPath. + */ + add_path(grouped_rel, (Path *) create_agg_path(root, grouped_rel, path, grouped_rel->reltarget, parse->groupClause ? AGG_SORTED : AGG_PLAIN, AGGSPLIT_SIMPLE, - root->processed_groupClause, + info->clauses, havingQual, agg_costs, dNumGroups)); - } - else if (parse->groupClause) - { - /* - * We have GROUP BY without aggregation or grouping sets. Make - * a GroupPath. - */ - add_path(grouped_rel, (Path *) + } + else if (parse->groupClause) + { + /* + * We have GROUP BY without aggregation or grouping sets. Make + * a GroupPath. + */ + add_path(grouped_rel, (Path *) create_group_path(root, grouped_rel, path, - root->processed_groupClause, + info->clauses, havingQual, dNumGroups)); - } - else - { - /* Other cases should have been handled above */ - Assert(false); + } + else + { + /* Other cases should have been handled above */ + Assert(false); + } } } @@ -6934,69 +6953,84 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel, { foreach(lc, partially_grouped_rel->pathlist) { + ListCell *lc2; Path *path = (Path *) lfirst(lc); - bool is_sorted; - int presorted_keys; + List *pathkey_orderings = NIL; - is_sorted = pathkeys_count_contained_in(root->group_pathkeys, - path->pathkeys, - &presorted_keys); + /* generate alternative group orderings that might be useful */ + pathkey_orderings = get_useful_group_keys_orderings(root, + path->rows, + path->pathkeys); - if (!is_sorted) + Assert(list_length(pathkey_orderings) > 0); + + /* process all potentially interesting grouping reorderings */ + foreach(lc2, pathkey_orderings) { - /* - * Try at least sorting the cheapest path and also try - * incrementally sorting any path which is partially - * sorted already (no need to deal with paths which have - * presorted keys when incremental sort is disabled unless - * it's the cheapest input path). - */ - if (path != partially_grouped_rel->cheapest_total_path && - (presorted_keys == 0 || !enable_incremental_sort)) - continue; + bool is_sorted; + int presorted_keys; + PathKeyInfo *info = (PathKeyInfo *) lfirst(lc2); - /* - * We've no need to consider both a sort and incremental - * sort. We'll just do a sort if there are no pre-sorted - * keys and an incremental sort when there are presorted - * keys. - */ - if (presorted_keys == 0 || !enable_incremental_sort) - path = (Path *) create_sort_path(root, - grouped_rel, - path, - root->group_pathkeys, - -1.0); - else - path = (Path *) create_incremental_sort_path(root, - grouped_rel, - path, - root->group_pathkeys, - presorted_keys, - -1.0); - } + is_sorted = pathkeys_count_contained_in(root->group_pathkeys, + path->pathkeys, + &presorted_keys); - if (parse->hasAggs) - add_path(grouped_rel, (Path *) + if (!is_sorted) + { + /* + * Try at least sorting the cheapest path and also try + * incrementally sorting any path which is partially + * sorted already (no need to deal with paths which have + * presorted keys when incremental sort is disabled unless + * it's the cheapest input path). + */ + if (path != partially_grouped_rel->cheapest_total_path && + (presorted_keys == 0 || !enable_incremental_sort)) + continue; + + /* + * We've no need to consider both a sort and incremental + * sort. We'll just do a sort if there are no pre-sorted + * keys and an incremental sort when there are presorted + * keys. + */ + if (presorted_keys == 0 || !enable_incremental_sort) + path = (Path *) create_sort_path(root, + grouped_rel, + path, + info->pathkeys, + -1.0); + else + path = (Path *) create_incremental_sort_path(root, + grouped_rel, + path, + info->pathkeys, + presorted_keys, + -1.0); + } + + if (parse->hasAggs) + add_path(grouped_rel, (Path *) create_agg_path(root, grouped_rel, path, grouped_rel->reltarget, parse->groupClause ? AGG_SORTED : AGG_PLAIN, AGGSPLIT_FINAL_DESERIAL, - root->processed_groupClause, + info->clauses, havingQual, agg_final_costs, dNumGroups)); - else - add_path(grouped_rel, (Path *) + else + add_path(grouped_rel, (Path *) create_group_path(root, grouped_rel, path, - root->processed_groupClause, + info->clauses, havingQual, dNumGroups)); + } } } } @@ -7199,66 +7233,85 @@ create_partial_grouping_paths(PlannerInfo *root, */ foreach(lc, input_rel->pathlist) { + ListCell *lc2; Path *path = (Path *) lfirst(lc); - bool is_sorted; - int presorted_keys; + Path *path_save = path; + List *pathkey_orderings = NIL; - is_sorted = pathkeys_count_contained_in(root->group_pathkeys, - path->pathkeys, - &presorted_keys); - if (!is_sorted) + /* generate alternative group orderings that might be useful */ + pathkey_orderings = get_useful_group_keys_orderings(root, + path->rows, + path->pathkeys); + + Assert(list_length(pathkey_orderings) > 0); + + /* process all potentially interesting grouping reorderings */ + foreach(lc2, pathkey_orderings) { - /* - * Try at least sorting the cheapest path and also try - * incrementally sorting any path which is partially sorted - * already (no need to deal with paths which have presorted - * keys when incremental sort is disabled unless it's the - * cheapest input path). - */ - if (path != cheapest_total_path && - (presorted_keys == 0 || !enable_incremental_sort)) - continue; + bool is_sorted; + int presorted_keys; + PathKeyInfo *info = (PathKeyInfo *) lfirst(lc2); - /* - * We've no need to consider both a sort and incremental sort. - * We'll just do a sort if there are no presorted keys and an - * incremental sort when there are presorted keys. - */ - if (presorted_keys == 0 || !enable_incremental_sort) - path = (Path *) create_sort_path(root, - partially_grouped_rel, - path, - root->group_pathkeys, - -1.0); - else - path = (Path *) create_incremental_sort_path(root, - partially_grouped_rel, - path, - root->group_pathkeys, - presorted_keys, - -1.0); - } + /* restore the path (we replace it in the loop) */ + path = path_save; - if (parse->hasAggs) - add_path(partially_grouped_rel, (Path *) + is_sorted = pathkeys_count_contained_in(info->pathkeys, + path->pathkeys, + &presorted_keys); + if (!is_sorted) + { + /* + * Try at least sorting the cheapest path and also try + * incrementally sorting any path which is partially sorted + * already (no need to deal with paths which have presorted + * keys when incremental sort is disabled unless it's the + * cheapest input path). + */ + if (path != cheapest_total_path && + (presorted_keys == 0 || !enable_incremental_sort)) + continue; + + /* + * We've no need to consider both a sort and incremental sort. + * We'll just do a sort if there are no presorted keys and an + * incremental sort when there are presorted keys. + */ + if (presorted_keys == 0 || !enable_incremental_sort) + path = (Path *) create_sort_path(root, + partially_grouped_rel, + path, + info->pathkeys, + -1.0); + else + path = (Path *) create_incremental_sort_path(root, + partially_grouped_rel, + path, + info->pathkeys, + presorted_keys, + -1.0); + } + + if (parse->hasAggs) + add_path(partially_grouped_rel, (Path *) create_agg_path(root, partially_grouped_rel, path, partially_grouped_rel->reltarget, parse->groupClause ? AGG_SORTED : AGG_PLAIN, AGGSPLIT_INITIAL_SERIAL, - root->processed_groupClause, + info->clauses, NIL, agg_partial_costs, dNumPartialGroups)); - else - add_path(partially_grouped_rel, (Path *) - create_group_path(root, - partially_grouped_rel, - path, - root->processed_groupClause, - NIL, - dNumPartialGroups)); + else + add_path(partially_grouped_rel, (Path *) + create_group_path(root, + partially_grouped_rel, + path, + info->clauses, + NIL, + dNumPartialGroups)); + } } } @@ -7267,67 +7320,86 @@ create_partial_grouping_paths(PlannerInfo *root, /* Similar to above logic, but for partial paths. */ foreach(lc, input_rel->partial_pathlist) { + ListCell *lc2; Path *path = (Path *) lfirst(lc); - bool is_sorted; - int presorted_keys; + Path *path_save = path; + List *pathkey_orderings = NIL; - is_sorted = pathkeys_count_contained_in(root->group_pathkeys, - path->pathkeys, - &presorted_keys); + /* generate alternative group orderings that might be useful */ + pathkey_orderings = get_useful_group_keys_orderings(root, + path->rows, + path->pathkeys); + + Assert(list_length(pathkey_orderings) > 0); - if (!is_sorted) + /* process all potentially interesting grouping reorderings */ + foreach(lc2, pathkey_orderings) { - /* - * Try at least sorting the cheapest path and also try - * incrementally sorting any path which is partially sorted - * already (no need to deal with paths which have presorted - * keys when incremental sort is disabled unless it's the - * cheapest input path). - */ - if (path != cheapest_partial_path && - (presorted_keys == 0 || !enable_incremental_sort)) - continue; + bool is_sorted; + int presorted_keys; + PathKeyInfo *info = (PathKeyInfo *) lfirst(lc2); - /* - * We've no need to consider both a sort and incremental sort. - * We'll just do a sort if there are no presorted keys and an - * incremental sort when there are presorted keys. - */ - if (presorted_keys == 0 || !enable_incremental_sort) - path = (Path *) create_sort_path(root, - partially_grouped_rel, - path, - root->group_pathkeys, - -1.0); - else - path = (Path *) create_incremental_sort_path(root, - partially_grouped_rel, - path, - root->group_pathkeys, - presorted_keys, - -1.0); - } + /* restore the path (we replace it in the loop) */ + path = path_save; - if (parse->hasAggs) - add_partial_path(partially_grouped_rel, (Path *) + is_sorted = pathkeys_count_contained_in(info->pathkeys, + path->pathkeys, + &presorted_keys); + + if (!is_sorted) + { + /* + * Try at least sorting the cheapest path and also try + * incrementally sorting any path which is partially sorted + * already (no need to deal with paths which have presorted + * keys when incremental sort is disabled unless it's the + * cheapest input path). + */ + if (path != cheapest_partial_path && + (presorted_keys == 0 || !enable_incremental_sort)) + continue; + + /* + * We've no need to consider both a sort and incremental sort. + * We'll just do a sort if there are no presorted keys and an + * incremental sort when there are presorted keys. + */ + if (presorted_keys == 0 || !enable_incremental_sort) + path = (Path *) create_sort_path(root, + partially_grouped_rel, + path, + info->pathkeys, + -1.0); + else + path = (Path *) create_incremental_sort_path(root, + partially_grouped_rel, + path, + info->pathkeys, + presorted_keys, + -1.0); + } + + if (parse->hasAggs) + add_partial_path(partially_grouped_rel, (Path *) create_agg_path(root, partially_grouped_rel, path, partially_grouped_rel->reltarget, parse->groupClause ? AGG_SORTED : AGG_PLAIN, AGGSPLIT_INITIAL_SERIAL, - root->processed_groupClause, + info->clauses, NIL, agg_partial_costs, dNumPartialPartialGroups)); - else - add_partial_path(partially_grouped_rel, (Path *) + else + add_partial_path(partially_grouped_rel, (Path *) create_group_path(root, partially_grouped_rel, path, - root->processed_groupClause, + info->clauses, NIL, dNumPartialPartialGroups)); + } } } @@ -7441,6 +7513,8 @@ gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel) * We can also skip the entire loop when we only have a single-item * group_pathkeys because then we can't possibly have a presorted prefix * of the list without having the list be fully sorted. + * + * XXX Shouldn't this also consider the group-key-reordering? */ if (!enable_incremental_sort || list_length(root->group_pathkeys) == 1) return; diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c index e11d022827..661c5554f0 100644 --- a/src/backend/utils/adt/selfuncs.c +++ b/src/backend/utils/adt/selfuncs.c @@ -3386,11 +3386,28 @@ double estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows, List **pgset, EstimationInfo *estinfo) { - List *varinfos = NIL; + return estimate_num_groups_incremental(root, groupExprs, + input_rows, pgset, estinfo, + NULL, 0); +} + +/* + * estimate_num_groups_incremental + * An estimate_num_groups variant, optimized for cases that are adding the + * expressions incrementally (e.g. one by one). + */ +double +estimate_num_groups_incremental(PlannerInfo *root, List *groupExprs, + double input_rows, + List **pgset, EstimationInfo *estinfo, + List **cache_varinfos, int prevNExprs) +{ + List *varinfos = (cache_varinfos) ? *cache_varinfos : NIL; double srf_multiplier = 1.0; double numdistinct; ListCell *l; - int i; + int i, + j; /* Zero the estinfo output parameter, if non-NULL */ if (estinfo != NULL) @@ -3421,7 +3438,7 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows, */ numdistinct = 1.0; - i = 0; + i = j = 0; foreach(l, groupExprs) { Node *groupexpr = (Node *) lfirst(l); @@ -3430,6 +3447,14 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows, List *varshere; ListCell *l2; + /* was done on previous call */ + if (cache_varinfos && j++ < prevNExprs) + { + if (pgset) + i++; /* to keep in sync with lines below */ + continue; + } + /* is expression in this grouping set? */ if (pgset && !list_member_int(*pgset, i++)) continue; @@ -3499,7 +3524,11 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows, if (varshere == NIL) { if (contain_volatile_functions(groupexpr)) + { + if (cache_varinfos) + *cache_varinfos = varinfos; return input_rows; + } continue; } @@ -3516,6 +3545,9 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows, } } + if (cache_varinfos) + *cache_varinfos = varinfos; + /* * If now no Vars, we must have an all-constant or all-boolean GROUP BY * list. diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c index 9f59440526..c0db58757a 100644 --- a/src/backend/utils/misc/guc_tables.c +++ b/src/backend/utils/misc/guc_tables.c @@ -1039,6 +1039,16 @@ struct config_bool ConfigureNamesBool[] = true, NULL, NULL, NULL }, + { + {"enable_group_by_reordering", PGC_USERSET, QUERY_TUNING_METHOD, + gettext_noop("Enables reordering of GROUP BY keys."), + NULL, + GUC_EXPLAIN + }, + &enable_group_by_reordering, + true, + NULL, NULL, NULL + }, { {"geqo", PGC_USERSET, QUERY_TUNING_GEQO, gettext_noop("Enables genetic query optimization."), diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample index b2809c711a..dc82fceb05 100644 --- a/src/backend/utils/misc/postgresql.conf.sample +++ b/src/backend/utils/misc/postgresql.conf.sample @@ -399,6 +399,7 @@ #enable_seqscan = on #enable_sort = on #enable_tidscan = on +#enable_group_by_reordering = on # - Planner Cost Constants - diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index ed85dc7414..6e639c0494 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -1456,6 +1456,16 @@ typedef struct PathKey bool pk_nulls_first; /* do NULLs come before normal values? */ } PathKey; +/* + * Combines information about pathkeys and the associated clauses. + */ +typedef struct PathKeyInfo +{ + NodeTag type; + List *pathkeys; + List *clauses; +} PathKeyInfo; + /* * VolatileFunctionStatus -- allows nodes to cache their * contain_volatile_functions properties. VOLATILITY_UNKNOWN means not yet diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index 9e7408c7ec..cbc17a082f 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -24,6 +24,7 @@ extern PGDLLIMPORT bool enable_geqo; extern PGDLLIMPORT int geqo_threshold; extern PGDLLIMPORT int min_parallel_table_scan_size; extern PGDLLIMPORT int min_parallel_index_scan_size; +extern PGDLLIMPORT bool enable_group_by_reordering; /* Hook for plugins to get control in set_rel_pathlist() */ typedef void (*set_rel_pathlist_hook_type) (PlannerInfo *root, @@ -204,6 +205,8 @@ typedef enum extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2); extern bool pathkeys_contained_in(List *keys1, List *keys2); extern bool pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common); +extern List *get_useful_group_keys_orderings(PlannerInfo *root, double nrows, + List *path_pathkeys); extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out index d8271da4d1..268f38fa42 100644 --- a/src/test/regress/expected/aggregates.out +++ b/src/test/regress/expected/aggregates.out @@ -2715,6 +2715,241 @@ SELECT balk(hundred) FROM tenk1; (1 row) ROLLBACK; +-- GROUP BY optimization by reorder columns +SELECT + i AS id, + i/2 AS p, + format('%60s', i%2) AS v, + i/4 AS c, + i/8 AS d, + (random() * (10000/8))::int as e --the same as d but no correlation with p + INTO btg +FROM + generate_series(1, 10000) i; +VACUUM btg; +ANALYZE btg; +-- GROUP BY optimization by reorder columns by frequency +SET enable_hashagg=off; +SET max_parallel_workers= 0; +SET max_parallel_workers_per_gather = 0; +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, v; + QUERY PLAN +----------------------------- + GroupAggregate + Group Key: p, v + -> Sort + Sort Key: p, v + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p; + QUERY PLAN +----------------------------- + GroupAggregate + Group Key: v, p + -> Sort + Sort Key: v, p + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, c; + QUERY PLAN +----------------------------- + GroupAggregate + Group Key: v, p, c + -> Sort + Sort Key: v, p, c + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, c ORDER BY v, p, c; + QUERY PLAN +----------------------------- + GroupAggregate + Group Key: v, p, c + -> Sort + Sort Key: v, p, c + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, d, c; + QUERY PLAN +------------------------------ + GroupAggregate + Group Key: v, p, d, c + -> Sort + Sort Key: v, p, d, c + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, d, c ORDER BY v, p, d ,c; + QUERY PLAN +------------------------------ + GroupAggregate + Group Key: v, p, d, c + -> Sort + Sort Key: v, p, d, c + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, d, c ORDER BY p, v, d ,c; + QUERY PLAN +------------------------------ + GroupAggregate + Group Key: p, v, d, c + -> Sort + Sort Key: p, v, d, c + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, d, e; + QUERY PLAN +----------------------------- + GroupAggregate + Group Key: p, d, e + -> Sort + Sort Key: p, d, e + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, e, d; + QUERY PLAN +----------------------------- + GroupAggregate + Group Key: p, e, d + -> Sort + Sort Key: p, e, d + -> Seq Scan on btg +(5 rows) + +CREATE STATISTICS btg_dep ON d, e, p FROM btg; +ANALYZE btg; +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, d, e; + QUERY PLAN +----------------------------- + GroupAggregate + Group Key: p, d, e + -> Sort + Sort Key: p, d, e + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, e, d; + QUERY PLAN +----------------------------- + GroupAggregate + Group Key: p, e, d + -> Sort + Sort Key: p, e, d + -> Seq Scan on btg +(5 rows) + +-- GROUP BY optimization by reorder columns by index scan +CREATE INDEX ON btg(p, v); +SET enable_seqscan=off; +SET enable_bitmapscan=off; +VACUUM btg; +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, v; + QUERY PLAN +------------------------------------------------ + GroupAggregate + Group Key: p, v + -> Index Only Scan using btg_p_v_idx on btg +(3 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, v ORDER BY p, v; + QUERY PLAN +------------------------------------------------ + GroupAggregate + Group Key: p, v + -> Index Only Scan using btg_p_v_idx on btg +(3 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p; + QUERY PLAN +------------------------------------------------ + GroupAggregate + Group Key: p, v + -> Index Only Scan using btg_p_v_idx on btg +(3 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p ORDER BY p, v; + QUERY PLAN +------------------------------------------------ + GroupAggregate + Group Key: p, v + -> Index Only Scan using btg_p_v_idx on btg +(3 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, c; + QUERY PLAN +------------------------------------------------- + GroupAggregate + Group Key: p, v, c + -> Incremental Sort + Sort Key: p, v, c + Presorted Key: p, v + -> Index Scan using btg_p_v_idx on btg +(6 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, c ORDER BY p, v; + QUERY PLAN +------------------------------------------------- + GroupAggregate + Group Key: p, v, c + -> Incremental Sort + Sort Key: p, v, c + Presorted Key: p, v + -> Index Scan using btg_p_v_idx on btg +(6 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, c, p, d; + QUERY PLAN +------------------------------------------------- + GroupAggregate + Group Key: p, v, c, d + -> Incremental Sort + Sort Key: p, v, c, d + Presorted Key: p, v + -> Index Scan using btg_p_v_idx on btg +(6 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, c, p, d ORDER BY p, v; + QUERY PLAN +------------------------------------------------- + GroupAggregate + Group Key: p, v, c, d + -> Incremental Sort + Sort Key: p, v, c, d + Presorted Key: p, v + -> Index Scan using btg_p_v_idx on btg +(6 rows) + +DROP TABLE btg; +RESET enable_hashagg; +RESET max_parallel_workers; +RESET max_parallel_workers_per_gather; +RESET enable_seqscan; +RESET enable_bitmapscan; -- Secondly test the case of a parallel aggregate combiner function -- returning NULL. For that use normal transition function, but a -- combiner function returning NULL. diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out index 7fdb685313..35d697ec29 100644 --- a/src/test/regress/expected/incremental_sort.out +++ b/src/test/regress/expected/incremental_sort.out @@ -1426,24 +1426,26 @@ set parallel_setup_cost = 0; set parallel_tuple_cost = 0; set max_parallel_workers_per_gather = 2; create table t (a int, b int, c int); -insert into t select mod(i,10),mod(i,10),i from generate_series(1,10000) s(i); +insert into t select mod(i,10),mod(i,10),i from generate_series(1,60000) s(i); create index on t (a); analyze t; set enable_incremental_sort = off; explain (costs off) select a,b,sum(c) from t group by 1,2 order by 1,2,3 limit 1; - QUERY PLAN ------------------------------------------------------- + QUERY PLAN +------------------------------------------------------------ Limit -> Sort Sort Key: a, b, (sum(c)) - -> Finalize HashAggregate + -> Finalize GroupAggregate Group Key: a, b - -> Gather + -> Gather Merge Workers Planned: 2 - -> Partial HashAggregate - Group Key: a, b - -> Parallel Seq Scan on t -(10 rows) + -> Sort + Sort Key: a, b + -> Partial HashAggregate + Group Key: a, b + -> Parallel Seq Scan on t +(12 rows) set enable_incremental_sort = on; explain (costs off) select a,b,sum(c) from t group by 1,2 order by 1,2,3 limit 1; diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out index 271313ebf8..9be7aca2b8 100644 --- a/src/test/regress/expected/sysviews.out +++ b/src/test/regress/expected/sysviews.out @@ -114,6 +114,7 @@ select name, setting from pg_settings where name like 'enable%'; enable_async_append | on enable_bitmapscan | on enable_gathermerge | on + enable_group_by_reordering | on enable_hashagg | on enable_hashjoin | on enable_incremental_sort | on @@ -133,7 +134,7 @@ select name, setting from pg_settings where name like 'enable%'; enable_seqscan | on enable_sort | on enable_tidscan | on -(22 rows) +(23 rows) -- There are always wait event descriptions for various types. select type, count(*) > 0 as ok FROM pg_wait_events diff --git a/src/test/regress/sql/aggregates.sql b/src/test/regress/sql/aggregates.sql index 75c78be640..5c4e768825 100644 --- a/src/test/regress/sql/aggregates.sql +++ b/src/test/regress/sql/aggregates.sql @@ -1172,6 +1172,105 @@ SELECT balk(hundred) FROM tenk1; ROLLBACK; +-- GROUP BY optimization by reorder columns + +SELECT + i AS id, + i/2 AS p, + format('%60s', i%2) AS v, + i/4 AS c, + i/8 AS d, + (random() * (10000/8))::int as e --the same as d but no correlation with p + INTO btg +FROM + generate_series(1, 10000) i; + +VACUUM btg; +ANALYZE btg; + +-- GROUP BY optimization by reorder columns by frequency + +SET enable_hashagg=off; +SET max_parallel_workers= 0; +SET max_parallel_workers_per_gather = 0; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, v; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, c; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, c ORDER BY v, p, c; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, d, c; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, d, c ORDER BY v, p, d ,c; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, d, c ORDER BY p, v, d ,c; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, d, e; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, e, d; + +CREATE STATISTICS btg_dep ON d, e, p FROM btg; +ANALYZE btg; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, d, e; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, e, d; + + +-- GROUP BY optimization by reorder columns by index scan + +CREATE INDEX ON btg(p, v); +SET enable_seqscan=off; +SET enable_bitmapscan=off; +VACUUM btg; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, v; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, v ORDER BY p, v; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p ORDER BY p, v; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, c; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, c ORDER BY p, v; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, c, p, d; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, c, p, d ORDER BY p, v; + +DROP TABLE btg; + +RESET enable_hashagg; +RESET max_parallel_workers; +RESET max_parallel_workers_per_gather; +RESET enable_seqscan; +RESET enable_bitmapscan; + + -- Secondly test the case of a parallel aggregate combiner function -- returning NULL. For that use normal transition function, but a -- combiner function returning NULL. diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql index ab471bdfff..70f311a6f2 100644 --- a/src/test/regress/sql/incremental_sort.sql +++ b/src/test/regress/sql/incremental_sort.sql @@ -208,7 +208,7 @@ set parallel_tuple_cost = 0; set max_parallel_workers_per_gather = 2; create table t (a int, b int, c int); -insert into t select mod(i,10),mod(i,10),i from generate_series(1,10000) s(i); +insert into t select mod(i,10),mod(i,10),i from generate_series(1,60000) s(i); create index on t (a); analyze t; -- 2.43.0 Attachments: [text/plain] 0001-Explore-alternative-orderings-of-group-by-pathkeys-d-20231228.patch (47.3K, ../../[email protected]/2-0001-Explore-alternative-orderings-of-group-by-pathkeys-d-20231228.patch) download | inline diff: From 6183555c2c56d7cbbc44f213f6c5bc4cbcaef1ec Mon Sep 17 00:00:00 2001 From: "Andrey V. Lepikhov" <[email protected]> Date: Wed, 13 Sep 2023 11:20:03 +0700 Subject: [PATCH] Explore alternative orderings of group-by pathkeys during optimization. When evaluating a query with a multi-column GROUP BY clause, we can minimize sort operations or avoid them if we synchronize the order of GROUP BY clauses with the ORDER BY sort clause or sort order, which comes from the underlying query tree. Grouping does not imply any ordering, so we can compare the keys in arbitrary order, and a Hash Agg leverages this. But for Group Agg, we simply compared keys in the order specified in the query. This commit explores alternative ordering of the keys, trying to find a cheaper one. The ordering of group keys may interact with other parts of the query, some of which may not be known while planning the grouping. For example, there may be an explicit ORDER BY clause or some other ordering-dependent operation higher up in the query, and using the same ordering may allow using either incremental sort or even eliminating the sort entirely. The patch always keeps the ordering specified in the query, assuming the user might have additional insights. This introduces a new GUC enable_group_by_reordering so that the optimization may be disabled if needed. --- src/backend/optimizer/path/equivclass.c | 13 +- src/backend/optimizer/path/pathkeys.c | 224 +++++++++ src/backend/optimizer/plan/planner.c | 464 ++++++++++-------- src/backend/utils/adt/selfuncs.c | 38 +- src/backend/utils/misc/guc_tables.c | 10 + src/backend/utils/misc/postgresql.conf.sample | 1 + src/include/nodes/pathnodes.h | 10 + src/include/optimizer/paths.h | 3 + src/test/regress/expected/aggregates.out | 235 +++++++++ .../regress/expected/incremental_sort.out | 20 +- src/test/regress/expected/sysviews.out | 3 +- src/test/regress/sql/aggregates.sql | 99 ++++ src/test/regress/sql/incremental_sort.sql | 2 +- 13 files changed, 912 insertions(+), 210 deletions(-) diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c index 7fa502d6e2..07edd4f38e 100644 --- a/src/backend/optimizer/path/equivclass.c +++ b/src/backend/optimizer/path/equivclass.c @@ -652,7 +652,18 @@ get_eclass_for_sort_expr(PlannerInfo *root, if (opcintype == cur_em->em_datatype && equal(expr, cur_em->em_expr)) - return cur_ec; /* Match! */ + { + /* + * Match! + * + * Copy the sortref if it wasn't set yet. That may happen if + * the ec was constructed from WHERE clause, i.e. it doesn't + * have a target reference at all. + */ + if (cur_ec->ec_sortref == 0 && sortref > 0) + cur_ec->ec_sortref = sortref; + return cur_ec; + } } } diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index fdb60aaa8d..38c1c85472 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -28,6 +28,8 @@ #include "partitioning/partbounds.h" #include "utils/lsyscache.h" +/* Consider reordering of GROUP BY keys? */ +bool enable_group_by_reordering = true; static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys); static bool matches_boolean_partition_clause(RestrictInfo *rinfo, @@ -350,6 +352,175 @@ pathkeys_contained_in(List *keys1, List *keys2) return false; } +/* + * group_keys_reorder_by_pathkeys + * Reorder GROUP BY keys to match pathkeys of input path. + * + * Function returns new lists (pathkeys and clauses), original GROUP BY lists + * stay untouched. + * + * Returns the number of GROUP BY keys with a matching pathkey. + */ +static int +group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys, + List **group_clauses, + int num_groupby_pathkeys) +{ + List *new_group_pathkeys = NIL, + *new_group_clauses = NIL; + ListCell *lc; + int n; + + if (pathkeys == NIL || *group_pathkeys == NIL) + return 0; + + /* + * Walk the pathkeys (determining ordering of the input path) and see if + * there's a matching GROUP BY key. If we find one, we append it to the + * list, and do the same for the clauses. + * + * Once we find the first pathkey without a matching GROUP BY key, the + * rest of the pathkeys are useless and can't be used to evaluate the + * grouping, so we abort the loop and ignore the remaining pathkeys. + * + * XXX Pathkeys are built in a way to allow simply comparing pointers. + */ + foreach(lc, pathkeys) + { + PathKey *pathkey = (PathKey *) lfirst(lc); + SortGroupClause *sgc; + + if (foreach_current_index(lc) >= num_groupby_pathkeys || + !list_member_ptr(*group_pathkeys, pathkey)) + /* */ + break; + + /* abort on first mismatch */ + sgc = get_sortgroupref_clause_noerr(pathkey->pk_eclass->ec_sortref, + *group_clauses); + if (!sgc) + /* The grouping clause is not cover this pathkey */ + break; + + new_group_pathkeys = lappend(new_group_pathkeys, pathkey); + new_group_clauses = lappend(new_group_clauses, sgc); + } + + /* remember the number of pathkeys with a matching GROUP BY key */ + n = list_length(new_group_pathkeys); + + /* append the remaining group pathkeys (will be treated as not sorted) */ + *group_pathkeys = list_concat_unique_ptr(new_group_pathkeys, + *group_pathkeys); + *group_clauses = list_concat_unique_ptr(new_group_clauses, + *group_clauses); + + return n; +} + +/* + * get_useful_group_keys_orderings + * Determine which orderings of GROUP BY keys are potentially interesting. + * + * Returns list of PathKeyInfo items, each representing an interesting ordering + * of GROUP BY keys. Each item stores pathkeys and clauses in matching order. + * + * The function considers (and keeps) multiple group by orderings: + * + * - the original ordering, as specified by the GROUP BY clause + * + * - GROUP BY keys reordered to minimize the sort cost + * + * - GROUP BY keys reordered to match path ordering (as much as possible), with + * the tail reordered to minimize the sort cost + * + * - GROUP BY keys to match target ORDER BY clause (as much as possible), with + * the tail reordered to minimize the sort cost + * + * There are other potentially interesting orderings (e.g. it might be best to + * match the first ORDER BY key, order the remaining keys differently and then + * rely on the incremental sort to fix this), but we ignore those for now. To + * make this work we'd have to pretty much generate all possible permutations. + */ +List * +get_useful_group_keys_orderings(PlannerInfo *root, double nrows, + List *path_pathkeys) +{ + Query *parse = root->parse; + List *infos = NIL; + PathKeyInfo *info; + + List *pathkeys = root->group_pathkeys; + List *clauses = root->processed_groupClause; + + /* always return at least the original pathkeys/clauses */ + info = makeNode(PathKeyInfo); + info->pathkeys = pathkeys; + info->clauses = clauses; + infos = lappend(infos, info); + + /* + * Should we try generating alternative orderings of the group keys? If + * not, we produce only the order specified in the query, i.e. the + * optimization is effectively disabled. + */ + if (!enable_group_by_reordering) + return infos; + + /* for grouping sets we can't do any reordering */ + if (parse->groupingSets) + return infos; + + /* + * If the path is sorted in some way, try reordering the group keys to + * match as much of the ordering as possible - we get this sort for free + * (mostly). + * + * We must not do this when there are no grouping sets, because those use + * more complex logic to decide the ordering. + * + * XXX Isn't this somewhat redundant with presorted_keys? Actually, it's + * more a complement, because it allows benefiting from incremental sort + * as much as possible. + */ + if (path_pathkeys) + { + group_keys_reorder_by_pathkeys(path_pathkeys, &pathkeys, &clauses, + root->num_groupby_pathkeys); + + /* + * reorder the tail to minimize sort cost + * + * XXX Ignore the return value - there may be nothing to reorder, But we + * still want to keep the keys reordered to path_pathkeys. + */ + info = makeNode(PathKeyInfo); + info->pathkeys = pathkeys; + info->clauses = clauses; + + infos = lappend(infos, info); + } + + /* + * Try reordering pathkeys to minimize the sort cost (this time consider + * the ORDER BY clause, but only if set debug_group_by_match_order_by). + */ + if (root->sort_pathkeys) + { + group_keys_reorder_by_pathkeys(root->sort_pathkeys, &pathkeys, &clauses, + root->num_groupby_pathkeys); + + /* keep the group keys reordered to match ordering of input path */ + info = makeNode(PathKeyInfo); + info->pathkeys = pathkeys; + info->clauses = clauses; + + infos = lappend(infos, info); + } + + return infos; +} + /* * pathkeys_count_contained_in * Same as pathkeys_contained_in, but also sets length of longest @@ -1939,6 +2110,54 @@ pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys) return n_common_pathkeys; } +/* + * pathkeys_useful_for_grouping + * Count the number of pathkeys that are useful for grouping (instead of + * explicit sort) + * + * Group pathkeys could be reordered to benefit from the ordering. The + * ordering may not be "complete" and may require incremental sort, but that's + * fine. So we simply count prefix pathkeys with a matching group key, and + * stop once we find the first pathkey without a match. + * + * So e.g. with pathkeys (a,b,c) and group keys (a,b,e) this determines (a,b) + * pathkeys are useful for grouping, and we might do incremental sort to get + * path ordered by (a,b,e). + * + * This logic is necessary to retain paths with ordering not matching grouping + * keys directly, without the reordering. + * + * Returns the length of pathkey prefix with matching group keys. + */ +static int +pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys) +{ + ListCell *key; + int n = 0; + + /* no special ordering requested for grouping */ + if (root->group_pathkeys == NIL) + return 0; + + /* unordered path */ + if (pathkeys == NIL) + return 0; + + /* walk the pathkeys and search for matching group key */ + foreach(key, pathkeys) + { + PathKey *pathkey = (PathKey *) lfirst(key); + + /* no matching group key, we're done */ + if (!list_member_ptr(root->group_pathkeys, pathkey)) + break; + + n++; + } + + return n; +} + /* * truncate_useless_pathkeys * Shorten the given pathkey list to just the useful pathkeys. @@ -1953,6 +2172,9 @@ truncate_useless_pathkeys(PlannerInfo *root, nuseful = pathkeys_useful_for_merging(root, rel, pathkeys); nuseful2 = pathkeys_useful_for_ordering(root, pathkeys); + if (nuseful2 > nuseful) + nuseful = nuseful2; + nuseful2 = pathkeys_useful_for_grouping(root, pathkeys); if (nuseful2 > nuseful) nuseful = nuseful2; @@ -1988,6 +2210,8 @@ has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel) { if (rel->joininfo != NIL || rel->has_eclass_joins) return true; /* might be able to use pathkeys for merging */ + if (root->group_pathkeys != NIL) + return true; /* might be able to use pathkeys for grouping */ if (root->query_pathkeys != NIL) return true; /* might be able to use them for ordering */ return false; /* definitely useless */ diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index 6f45efde21..fc774bfce6 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -2805,8 +2805,9 @@ remove_useless_groupby_columns(PlannerInfo *root) * * In principle it might be interesting to consider other orderings of the * GROUP BY elements, which could match the sort ordering of other - * possible plans (eg an indexscan) and thereby reduce cost. We don't - * bother with that, though. Hashed grouping will frequently win anyway. + * possible plans (eg an indexscan) and thereby reduce cost. However, we + * don't yet have sufficient information to do that here, so that's left until + * later in planning. See get_useful_group_keys_orderings(). * * Note: we need no comparable processing of the distinctClause because * the parser already enforced that that matches ORDER BY. @@ -6839,90 +6840,108 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel, */ foreach(lc, input_rel->pathlist) { + ListCell *lc2; Path *path = (Path *) lfirst(lc); - bool is_sorted; - int presorted_keys; + Path *path_save = path; + List *pathkey_orderings = NIL; - is_sorted = pathkeys_count_contained_in(root->group_pathkeys, - path->pathkeys, - &presorted_keys); + /* generate alternative group orderings that might be useful */ + pathkey_orderings = get_useful_group_keys_orderings(root, + path->rows, + path->pathkeys); - if (!is_sorted) + Assert(list_length(pathkey_orderings) > 0); + + foreach(lc2, pathkey_orderings) { - /* - * Try at least sorting the cheapest path and also try - * incrementally sorting any path which is partially sorted - * already (no need to deal with paths which have presorted - * keys when incremental sort is disabled unless it's the - * cheapest input path). - */ - if (path != cheapest_path && - (presorted_keys == 0 || !enable_incremental_sort)) - continue; + bool is_sorted; + int presorted_keys; + PathKeyInfo *info = (PathKeyInfo *) lfirst(lc2); - /* - * We've no need to consider both a sort and incremental sort. - * We'll just do a sort if there are no presorted keys and an - * incremental sort when there are presorted keys. - */ - if (presorted_keys == 0 || !enable_incremental_sort) - path = (Path *) create_sort_path(root, - grouped_rel, - path, - root->group_pathkeys, - -1.0); - else - path = (Path *) create_incremental_sort_path(root, - grouped_rel, - path, - root->group_pathkeys, - presorted_keys, - -1.0); - } + /* restore the path (we replace it in the loop) */ + path = path_save; - /* Now decide what to stick atop it */ - if (parse->groupingSets) - { - consider_groupingsets_paths(root, grouped_rel, - path, true, can_hash, - gd, agg_costs, dNumGroups); - } - else if (parse->hasAggs) - { - /* - * We have aggregation, possibly with plain GROUP BY. Make an - * AggPath. - */ - add_path(grouped_rel, (Path *) + is_sorted = pathkeys_count_contained_in(info->pathkeys, + path->pathkeys, + &presorted_keys); + + if (!is_sorted) + { + /* + * Try at least sorting the cheapest path and also try + * incrementally sorting any path which is partially sorted + * already (no need to deal with paths which have presorted + * keys when incremental sort is disabled unless it's the + * cheapest input path). + */ + if (path != cheapest_path && + (presorted_keys == 0 || !enable_incremental_sort)) + continue; + + /* + * We've no need to consider both a sort and incremental sort. + * We'll just do a sort if there are no presorted keys and an + * incremental sort when there are presorted keys. + */ + if (presorted_keys == 0 || !enable_incremental_sort) + path = (Path *) create_sort_path(root, + grouped_rel, + path, + info->pathkeys, + -1.0); + else + path = (Path *) create_incremental_sort_path(root, + grouped_rel, + path, + info->pathkeys, + presorted_keys, + -1.0); + } + + /* Now decide what to stick atop it */ + if (parse->groupingSets) + { + consider_groupingsets_paths(root, grouped_rel, + path, true, can_hash, + gd, agg_costs, dNumGroups); + } + else if (parse->hasAggs) + { + /* + * We have aggregation, possibly with plain GROUP BY. Make an + * AggPath. + */ + add_path(grouped_rel, (Path *) create_agg_path(root, grouped_rel, path, grouped_rel->reltarget, parse->groupClause ? AGG_SORTED : AGG_PLAIN, AGGSPLIT_SIMPLE, - root->processed_groupClause, + info->clauses, havingQual, agg_costs, dNumGroups)); - } - else if (parse->groupClause) - { - /* - * We have GROUP BY without aggregation or grouping sets. Make - * a GroupPath. - */ - add_path(grouped_rel, (Path *) + } + else if (parse->groupClause) + { + /* + * We have GROUP BY without aggregation or grouping sets. Make + * a GroupPath. + */ + add_path(grouped_rel, (Path *) create_group_path(root, grouped_rel, path, - root->processed_groupClause, + info->clauses, havingQual, dNumGroups)); - } - else - { - /* Other cases should have been handled above */ - Assert(false); + } + else + { + /* Other cases should have been handled above */ + Assert(false); + } } } @@ -6934,69 +6953,84 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel, { foreach(lc, partially_grouped_rel->pathlist) { + ListCell *lc2; Path *path = (Path *) lfirst(lc); - bool is_sorted; - int presorted_keys; + List *pathkey_orderings = NIL; - is_sorted = pathkeys_count_contained_in(root->group_pathkeys, - path->pathkeys, - &presorted_keys); + /* generate alternative group orderings that might be useful */ + pathkey_orderings = get_useful_group_keys_orderings(root, + path->rows, + path->pathkeys); - if (!is_sorted) + Assert(list_length(pathkey_orderings) > 0); + + /* process all potentially interesting grouping reorderings */ + foreach(lc2, pathkey_orderings) { - /* - * Try at least sorting the cheapest path and also try - * incrementally sorting any path which is partially - * sorted already (no need to deal with paths which have - * presorted keys when incremental sort is disabled unless - * it's the cheapest input path). - */ - if (path != partially_grouped_rel->cheapest_total_path && - (presorted_keys == 0 || !enable_incremental_sort)) - continue; + bool is_sorted; + int presorted_keys; + PathKeyInfo *info = (PathKeyInfo *) lfirst(lc2); - /* - * We've no need to consider both a sort and incremental - * sort. We'll just do a sort if there are no pre-sorted - * keys and an incremental sort when there are presorted - * keys. - */ - if (presorted_keys == 0 || !enable_incremental_sort) - path = (Path *) create_sort_path(root, - grouped_rel, - path, - root->group_pathkeys, - -1.0); - else - path = (Path *) create_incremental_sort_path(root, - grouped_rel, - path, - root->group_pathkeys, - presorted_keys, - -1.0); - } + is_sorted = pathkeys_count_contained_in(root->group_pathkeys, + path->pathkeys, + &presorted_keys); - if (parse->hasAggs) - add_path(grouped_rel, (Path *) + if (!is_sorted) + { + /* + * Try at least sorting the cheapest path and also try + * incrementally sorting any path which is partially + * sorted already (no need to deal with paths which have + * presorted keys when incremental sort is disabled unless + * it's the cheapest input path). + */ + if (path != partially_grouped_rel->cheapest_total_path && + (presorted_keys == 0 || !enable_incremental_sort)) + continue; + + /* + * We've no need to consider both a sort and incremental + * sort. We'll just do a sort if there are no pre-sorted + * keys and an incremental sort when there are presorted + * keys. + */ + if (presorted_keys == 0 || !enable_incremental_sort) + path = (Path *) create_sort_path(root, + grouped_rel, + path, + info->pathkeys, + -1.0); + else + path = (Path *) create_incremental_sort_path(root, + grouped_rel, + path, + info->pathkeys, + presorted_keys, + -1.0); + } + + if (parse->hasAggs) + add_path(grouped_rel, (Path *) create_agg_path(root, grouped_rel, path, grouped_rel->reltarget, parse->groupClause ? AGG_SORTED : AGG_PLAIN, AGGSPLIT_FINAL_DESERIAL, - root->processed_groupClause, + info->clauses, havingQual, agg_final_costs, dNumGroups)); - else - add_path(grouped_rel, (Path *) + else + add_path(grouped_rel, (Path *) create_group_path(root, grouped_rel, path, - root->processed_groupClause, + info->clauses, havingQual, dNumGroups)); + } } } } @@ -7199,66 +7233,85 @@ create_partial_grouping_paths(PlannerInfo *root, */ foreach(lc, input_rel->pathlist) { + ListCell *lc2; Path *path = (Path *) lfirst(lc); - bool is_sorted; - int presorted_keys; + Path *path_save = path; + List *pathkey_orderings = NIL; - is_sorted = pathkeys_count_contained_in(root->group_pathkeys, - path->pathkeys, - &presorted_keys); - if (!is_sorted) + /* generate alternative group orderings that might be useful */ + pathkey_orderings = get_useful_group_keys_orderings(root, + path->rows, + path->pathkeys); + + Assert(list_length(pathkey_orderings) > 0); + + /* process all potentially interesting grouping reorderings */ + foreach(lc2, pathkey_orderings) { - /* - * Try at least sorting the cheapest path and also try - * incrementally sorting any path which is partially sorted - * already (no need to deal with paths which have presorted - * keys when incremental sort is disabled unless it's the - * cheapest input path). - */ - if (path != cheapest_total_path && - (presorted_keys == 0 || !enable_incremental_sort)) - continue; + bool is_sorted; + int presorted_keys; + PathKeyInfo *info = (PathKeyInfo *) lfirst(lc2); - /* - * We've no need to consider both a sort and incremental sort. - * We'll just do a sort if there are no presorted keys and an - * incremental sort when there are presorted keys. - */ - if (presorted_keys == 0 || !enable_incremental_sort) - path = (Path *) create_sort_path(root, - partially_grouped_rel, - path, - root->group_pathkeys, - -1.0); - else - path = (Path *) create_incremental_sort_path(root, - partially_grouped_rel, - path, - root->group_pathkeys, - presorted_keys, - -1.0); - } + /* restore the path (we replace it in the loop) */ + path = path_save; - if (parse->hasAggs) - add_path(partially_grouped_rel, (Path *) + is_sorted = pathkeys_count_contained_in(info->pathkeys, + path->pathkeys, + &presorted_keys); + if (!is_sorted) + { + /* + * Try at least sorting the cheapest path and also try + * incrementally sorting any path which is partially sorted + * already (no need to deal with paths which have presorted + * keys when incremental sort is disabled unless it's the + * cheapest input path). + */ + if (path != cheapest_total_path && + (presorted_keys == 0 || !enable_incremental_sort)) + continue; + + /* + * We've no need to consider both a sort and incremental sort. + * We'll just do a sort if there are no presorted keys and an + * incremental sort when there are presorted keys. + */ + if (presorted_keys == 0 || !enable_incremental_sort) + path = (Path *) create_sort_path(root, + partially_grouped_rel, + path, + info->pathkeys, + -1.0); + else + path = (Path *) create_incremental_sort_path(root, + partially_grouped_rel, + path, + info->pathkeys, + presorted_keys, + -1.0); + } + + if (parse->hasAggs) + add_path(partially_grouped_rel, (Path *) create_agg_path(root, partially_grouped_rel, path, partially_grouped_rel->reltarget, parse->groupClause ? AGG_SORTED : AGG_PLAIN, AGGSPLIT_INITIAL_SERIAL, - root->processed_groupClause, + info->clauses, NIL, agg_partial_costs, dNumPartialGroups)); - else - add_path(partially_grouped_rel, (Path *) - create_group_path(root, - partially_grouped_rel, - path, - root->processed_groupClause, - NIL, - dNumPartialGroups)); + else + add_path(partially_grouped_rel, (Path *) + create_group_path(root, + partially_grouped_rel, + path, + info->clauses, + NIL, + dNumPartialGroups)); + } } } @@ -7267,67 +7320,86 @@ create_partial_grouping_paths(PlannerInfo *root, /* Similar to above logic, but for partial paths. */ foreach(lc, input_rel->partial_pathlist) { + ListCell *lc2; Path *path = (Path *) lfirst(lc); - bool is_sorted; - int presorted_keys; + Path *path_save = path; + List *pathkey_orderings = NIL; - is_sorted = pathkeys_count_contained_in(root->group_pathkeys, - path->pathkeys, - &presorted_keys); + /* generate alternative group orderings that might be useful */ + pathkey_orderings = get_useful_group_keys_orderings(root, + path->rows, + path->pathkeys); + + Assert(list_length(pathkey_orderings) > 0); - if (!is_sorted) + /* process all potentially interesting grouping reorderings */ + foreach(lc2, pathkey_orderings) { - /* - * Try at least sorting the cheapest path and also try - * incrementally sorting any path which is partially sorted - * already (no need to deal with paths which have presorted - * keys when incremental sort is disabled unless it's the - * cheapest input path). - */ - if (path != cheapest_partial_path && - (presorted_keys == 0 || !enable_incremental_sort)) - continue; + bool is_sorted; + int presorted_keys; + PathKeyInfo *info = (PathKeyInfo *) lfirst(lc2); - /* - * We've no need to consider both a sort and incremental sort. - * We'll just do a sort if there are no presorted keys and an - * incremental sort when there are presorted keys. - */ - if (presorted_keys == 0 || !enable_incremental_sort) - path = (Path *) create_sort_path(root, - partially_grouped_rel, - path, - root->group_pathkeys, - -1.0); - else - path = (Path *) create_incremental_sort_path(root, - partially_grouped_rel, - path, - root->group_pathkeys, - presorted_keys, - -1.0); - } + /* restore the path (we replace it in the loop) */ + path = path_save; - if (parse->hasAggs) - add_partial_path(partially_grouped_rel, (Path *) + is_sorted = pathkeys_count_contained_in(info->pathkeys, + path->pathkeys, + &presorted_keys); + + if (!is_sorted) + { + /* + * Try at least sorting the cheapest path and also try + * incrementally sorting any path which is partially sorted + * already (no need to deal with paths which have presorted + * keys when incremental sort is disabled unless it's the + * cheapest input path). + */ + if (path != cheapest_partial_path && + (presorted_keys == 0 || !enable_incremental_sort)) + continue; + + /* + * We've no need to consider both a sort and incremental sort. + * We'll just do a sort if there are no presorted keys and an + * incremental sort when there are presorted keys. + */ + if (presorted_keys == 0 || !enable_incremental_sort) + path = (Path *) create_sort_path(root, + partially_grouped_rel, + path, + info->pathkeys, + -1.0); + else + path = (Path *) create_incremental_sort_path(root, + partially_grouped_rel, + path, + info->pathkeys, + presorted_keys, + -1.0); + } + + if (parse->hasAggs) + add_partial_path(partially_grouped_rel, (Path *) create_agg_path(root, partially_grouped_rel, path, partially_grouped_rel->reltarget, parse->groupClause ? AGG_SORTED : AGG_PLAIN, AGGSPLIT_INITIAL_SERIAL, - root->processed_groupClause, + info->clauses, NIL, agg_partial_costs, dNumPartialPartialGroups)); - else - add_partial_path(partially_grouped_rel, (Path *) + else + add_partial_path(partially_grouped_rel, (Path *) create_group_path(root, partially_grouped_rel, path, - root->processed_groupClause, + info->clauses, NIL, dNumPartialPartialGroups)); + } } } @@ -7441,6 +7513,8 @@ gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel) * We can also skip the entire loop when we only have a single-item * group_pathkeys because then we can't possibly have a presorted prefix * of the list without having the list be fully sorted. + * + * XXX Shouldn't this also consider the group-key-reordering? */ if (!enable_incremental_sort || list_length(root->group_pathkeys) == 1) return; diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c index e11d022827..661c5554f0 100644 --- a/src/backend/utils/adt/selfuncs.c +++ b/src/backend/utils/adt/selfuncs.c @@ -3386,11 +3386,28 @@ double estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows, List **pgset, EstimationInfo *estinfo) { - List *varinfos = NIL; + return estimate_num_groups_incremental(root, groupExprs, + input_rows, pgset, estinfo, + NULL, 0); +} + +/* + * estimate_num_groups_incremental + * An estimate_num_groups variant, optimized for cases that are adding the + * expressions incrementally (e.g. one by one). + */ +double +estimate_num_groups_incremental(PlannerInfo *root, List *groupExprs, + double input_rows, + List **pgset, EstimationInfo *estinfo, + List **cache_varinfos, int prevNExprs) +{ + List *varinfos = (cache_varinfos) ? *cache_varinfos : NIL; double srf_multiplier = 1.0; double numdistinct; ListCell *l; - int i; + int i, + j; /* Zero the estinfo output parameter, if non-NULL */ if (estinfo != NULL) @@ -3421,7 +3438,7 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows, */ numdistinct = 1.0; - i = 0; + i = j = 0; foreach(l, groupExprs) { Node *groupexpr = (Node *) lfirst(l); @@ -3430,6 +3447,14 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows, List *varshere; ListCell *l2; + /* was done on previous call */ + if (cache_varinfos && j++ < prevNExprs) + { + if (pgset) + i++; /* to keep in sync with lines below */ + continue; + } + /* is expression in this grouping set? */ if (pgset && !list_member_int(*pgset, i++)) continue; @@ -3499,7 +3524,11 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows, if (varshere == NIL) { if (contain_volatile_functions(groupexpr)) + { + if (cache_varinfos) + *cache_varinfos = varinfos; return input_rows; + } continue; } @@ -3516,6 +3545,9 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows, } } + if (cache_varinfos) + *cache_varinfos = varinfos; + /* * If now no Vars, we must have an all-constant or all-boolean GROUP BY * list. diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c index 9f59440526..c0db58757a 100644 --- a/src/backend/utils/misc/guc_tables.c +++ b/src/backend/utils/misc/guc_tables.c @@ -1039,6 +1039,16 @@ struct config_bool ConfigureNamesBool[] = true, NULL, NULL, NULL }, + { + {"enable_group_by_reordering", PGC_USERSET, QUERY_TUNING_METHOD, + gettext_noop("Enables reordering of GROUP BY keys."), + NULL, + GUC_EXPLAIN + }, + &enable_group_by_reordering, + true, + NULL, NULL, NULL + }, { {"geqo", PGC_USERSET, QUERY_TUNING_GEQO, gettext_noop("Enables genetic query optimization."), diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample index b2809c711a..dc82fceb05 100644 --- a/src/backend/utils/misc/postgresql.conf.sample +++ b/src/backend/utils/misc/postgresql.conf.sample @@ -399,6 +399,7 @@ #enable_seqscan = on #enable_sort = on #enable_tidscan = on +#enable_group_by_reordering = on # - Planner Cost Constants - diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index ed85dc7414..6e639c0494 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -1456,6 +1456,16 @@ typedef struct PathKey bool pk_nulls_first; /* do NULLs come before normal values? */ } PathKey; +/* + * Combines information about pathkeys and the associated clauses. + */ +typedef struct PathKeyInfo +{ + NodeTag type; + List *pathkeys; + List *clauses; +} PathKeyInfo; + /* * VolatileFunctionStatus -- allows nodes to cache their * contain_volatile_functions properties. VOLATILITY_UNKNOWN means not yet diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index 9e7408c7ec..cbc17a082f 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -24,6 +24,7 @@ extern PGDLLIMPORT bool enable_geqo; extern PGDLLIMPORT int geqo_threshold; extern PGDLLIMPORT int min_parallel_table_scan_size; extern PGDLLIMPORT int min_parallel_index_scan_size; +extern PGDLLIMPORT bool enable_group_by_reordering; /* Hook for plugins to get control in set_rel_pathlist() */ typedef void (*set_rel_pathlist_hook_type) (PlannerInfo *root, @@ -204,6 +205,8 @@ typedef enum extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2); extern bool pathkeys_contained_in(List *keys1, List *keys2); extern bool pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common); +extern List *get_useful_group_keys_orderings(PlannerInfo *root, double nrows, + List *path_pathkeys); extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out index d8271da4d1..268f38fa42 100644 --- a/src/test/regress/expected/aggregates.out +++ b/src/test/regress/expected/aggregates.out @@ -2715,6 +2715,241 @@ SELECT balk(hundred) FROM tenk1; (1 row) ROLLBACK; +-- GROUP BY optimization by reorder columns +SELECT + i AS id, + i/2 AS p, + format('%60s', i%2) AS v, + i/4 AS c, + i/8 AS d, + (random() * (10000/8))::int as e --the same as d but no correlation with p + INTO btg +FROM + generate_series(1, 10000) i; +VACUUM btg; +ANALYZE btg; +-- GROUP BY optimization by reorder columns by frequency +SET enable_hashagg=off; +SET max_parallel_workers= 0; +SET max_parallel_workers_per_gather = 0; +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, v; + QUERY PLAN +----------------------------- + GroupAggregate + Group Key: p, v + -> Sort + Sort Key: p, v + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p; + QUERY PLAN +----------------------------- + GroupAggregate + Group Key: v, p + -> Sort + Sort Key: v, p + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, c; + QUERY PLAN +----------------------------- + GroupAggregate + Group Key: v, p, c + -> Sort + Sort Key: v, p, c + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, c ORDER BY v, p, c; + QUERY PLAN +----------------------------- + GroupAggregate + Group Key: v, p, c + -> Sort + Sort Key: v, p, c + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, d, c; + QUERY PLAN +------------------------------ + GroupAggregate + Group Key: v, p, d, c + -> Sort + Sort Key: v, p, d, c + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, d, c ORDER BY v, p, d ,c; + QUERY PLAN +------------------------------ + GroupAggregate + Group Key: v, p, d, c + -> Sort + Sort Key: v, p, d, c + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, d, c ORDER BY p, v, d ,c; + QUERY PLAN +------------------------------ + GroupAggregate + Group Key: p, v, d, c + -> Sort + Sort Key: p, v, d, c + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, d, e; + QUERY PLAN +----------------------------- + GroupAggregate + Group Key: p, d, e + -> Sort + Sort Key: p, d, e + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, e, d; + QUERY PLAN +----------------------------- + GroupAggregate + Group Key: p, e, d + -> Sort + Sort Key: p, e, d + -> Seq Scan on btg +(5 rows) + +CREATE STATISTICS btg_dep ON d, e, p FROM btg; +ANALYZE btg; +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, d, e; + QUERY PLAN +----------------------------- + GroupAggregate + Group Key: p, d, e + -> Sort + Sort Key: p, d, e + -> Seq Scan on btg +(5 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, e, d; + QUERY PLAN +----------------------------- + GroupAggregate + Group Key: p, e, d + -> Sort + Sort Key: p, e, d + -> Seq Scan on btg +(5 rows) + +-- GROUP BY optimization by reorder columns by index scan +CREATE INDEX ON btg(p, v); +SET enable_seqscan=off; +SET enable_bitmapscan=off; +VACUUM btg; +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, v; + QUERY PLAN +------------------------------------------------ + GroupAggregate + Group Key: p, v + -> Index Only Scan using btg_p_v_idx on btg +(3 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, v ORDER BY p, v; + QUERY PLAN +------------------------------------------------ + GroupAggregate + Group Key: p, v + -> Index Only Scan using btg_p_v_idx on btg +(3 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p; + QUERY PLAN +------------------------------------------------ + GroupAggregate + Group Key: p, v + -> Index Only Scan using btg_p_v_idx on btg +(3 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p ORDER BY p, v; + QUERY PLAN +------------------------------------------------ + GroupAggregate + Group Key: p, v + -> Index Only Scan using btg_p_v_idx on btg +(3 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, c; + QUERY PLAN +------------------------------------------------- + GroupAggregate + Group Key: p, v, c + -> Incremental Sort + Sort Key: p, v, c + Presorted Key: p, v + -> Index Scan using btg_p_v_idx on btg +(6 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, c ORDER BY p, v; + QUERY PLAN +------------------------------------------------- + GroupAggregate + Group Key: p, v, c + -> Incremental Sort + Sort Key: p, v, c + Presorted Key: p, v + -> Index Scan using btg_p_v_idx on btg +(6 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, c, p, d; + QUERY PLAN +------------------------------------------------- + GroupAggregate + Group Key: p, v, c, d + -> Incremental Sort + Sort Key: p, v, c, d + Presorted Key: p, v + -> Index Scan using btg_p_v_idx on btg +(6 rows) + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, c, p, d ORDER BY p, v; + QUERY PLAN +------------------------------------------------- + GroupAggregate + Group Key: p, v, c, d + -> Incremental Sort + Sort Key: p, v, c, d + Presorted Key: p, v + -> Index Scan using btg_p_v_idx on btg +(6 rows) + +DROP TABLE btg; +RESET enable_hashagg; +RESET max_parallel_workers; +RESET max_parallel_workers_per_gather; +RESET enable_seqscan; +RESET enable_bitmapscan; -- Secondly test the case of a parallel aggregate combiner function -- returning NULL. For that use normal transition function, but a -- combiner function returning NULL. diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out index 7fdb685313..35d697ec29 100644 --- a/src/test/regress/expected/incremental_sort.out +++ b/src/test/regress/expected/incremental_sort.out @@ -1426,24 +1426,26 @@ set parallel_setup_cost = 0; set parallel_tuple_cost = 0; set max_parallel_workers_per_gather = 2; create table t (a int, b int, c int); -insert into t select mod(i,10),mod(i,10),i from generate_series(1,10000) s(i); +insert into t select mod(i,10),mod(i,10),i from generate_series(1,60000) s(i); create index on t (a); analyze t; set enable_incremental_sort = off; explain (costs off) select a,b,sum(c) from t group by 1,2 order by 1,2,3 limit 1; - QUERY PLAN ------------------------------------------------------- + QUERY PLAN +------------------------------------------------------------ Limit -> Sort Sort Key: a, b, (sum(c)) - -> Finalize HashAggregate + -> Finalize GroupAggregate Group Key: a, b - -> Gather + -> Gather Merge Workers Planned: 2 - -> Partial HashAggregate - Group Key: a, b - -> Parallel Seq Scan on t -(10 rows) + -> Sort + Sort Key: a, b + -> Partial HashAggregate + Group Key: a, b + -> Parallel Seq Scan on t +(12 rows) set enable_incremental_sort = on; explain (costs off) select a,b,sum(c) from t group by 1,2 order by 1,2,3 limit 1; diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out index 271313ebf8..9be7aca2b8 100644 --- a/src/test/regress/expected/sysviews.out +++ b/src/test/regress/expected/sysviews.out @@ -114,6 +114,7 @@ select name, setting from pg_settings where name like 'enable%'; enable_async_append | on enable_bitmapscan | on enable_gathermerge | on + enable_group_by_reordering | on enable_hashagg | on enable_hashjoin | on enable_incremental_sort | on @@ -133,7 +134,7 @@ select name, setting from pg_settings where name like 'enable%'; enable_seqscan | on enable_sort | on enable_tidscan | on -(22 rows) +(23 rows) -- There are always wait event descriptions for various types. select type, count(*) > 0 as ok FROM pg_wait_events diff --git a/src/test/regress/sql/aggregates.sql b/src/test/regress/sql/aggregates.sql index 75c78be640..5c4e768825 100644 --- a/src/test/regress/sql/aggregates.sql +++ b/src/test/regress/sql/aggregates.sql @@ -1172,6 +1172,105 @@ SELECT balk(hundred) FROM tenk1; ROLLBACK; +-- GROUP BY optimization by reorder columns + +SELECT + i AS id, + i/2 AS p, + format('%60s', i%2) AS v, + i/4 AS c, + i/8 AS d, + (random() * (10000/8))::int as e --the same as d but no correlation with p + INTO btg +FROM + generate_series(1, 10000) i; + +VACUUM btg; +ANALYZE btg; + +-- GROUP BY optimization by reorder columns by frequency + +SET enable_hashagg=off; +SET max_parallel_workers= 0; +SET max_parallel_workers_per_gather = 0; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, v; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, c; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, c ORDER BY v, p, c; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, d, c; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, d, c ORDER BY v, p, d ,c; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, d, c ORDER BY p, v, d ,c; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, d, e; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, e, d; + +CREATE STATISTICS btg_dep ON d, e, p FROM btg; +ANALYZE btg; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, d, e; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, e, d; + + +-- GROUP BY optimization by reorder columns by index scan + +CREATE INDEX ON btg(p, v); +SET enable_seqscan=off; +SET enable_bitmapscan=off; +VACUUM btg; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, v; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY p, v ORDER BY p, v; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p ORDER BY p, v; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, c; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, p, c ORDER BY p, v; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, c, p, d; + +EXPLAIN (COSTS off) +SELECT count(*) FROM btg GROUP BY v, c, p, d ORDER BY p, v; + +DROP TABLE btg; + +RESET enable_hashagg; +RESET max_parallel_workers; +RESET max_parallel_workers_per_gather; +RESET enable_seqscan; +RESET enable_bitmapscan; + + -- Secondly test the case of a parallel aggregate combiner function -- returning NULL. For that use normal transition function, but a -- combiner function returning NULL. diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql index ab471bdfff..70f311a6f2 100644 --- a/src/test/regress/sql/incremental_sort.sql +++ b/src/test/regress/sql/incremental_sort.sql @@ -208,7 +208,7 @@ set parallel_tuple_cost = 0; set max_parallel_workers_per_gather = 2; create table t (a int, b int, c int); -insert into t select mod(i,10),mod(i,10),i from generate_series(1,10000) s(i); +insert into t select mod(i,10),mod(i,10),i from generate_series(1,60000) s(i); create index on t (a); analyze t; -- 2.43.0 ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: POC: GROUP BY optimization @ 2023-12-28 11:29 Alexander Korotkov <[email protected]> parent: Andrei Lepikhov <[email protected]> 0 siblings, 1 reply; 13+ messages in thread From: Alexander Korotkov @ 2023-12-28 11:29 UTC (permalink / raw) To: Andrei Lepikhov <[email protected]>; +Cc: Tom Lane <[email protected]>; PostgreSQL Developers <[email protected]>; Tomas Vondra <[email protected]>; Teodor Sigaev <[email protected]>; David Rowley <[email protected]>; a.rybakina <[email protected]>; Белялов Дамир Наилевич <[email protected]> On Thu, Dec 28, 2023 at 10:22 AM Andrei Lepikhov <[email protected]> wrote: > But arrangement with an ORDER BY clause doesn't work: > > DROP INDEX abc; > explain SELECT x,w,z FROM t GROUP BY (w,x,z) ORDER BY (x,z,w); > > I think the reason is that the sort_pathkeys and group_pathkeys are > physically different structures, and we can't just compare pointers here. I haven't yet looked into the code. But this looks strange to me. Somehow, optimizer currently matches index pathkeys to ORDER BY pathkeys. If GROUP BY pathkeys could be matched to index pathkeys, then it should be possible to match them to ORDER BY pathkeys too. ------ Regards, Alexander Korotkov ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: POC: GROUP BY optimization @ 2023-12-29 03:23 Andrei Lepikhov <[email protected]> parent: Alexander Korotkov <[email protected]> 0 siblings, 0 replies; 13+ messages in thread From: Andrei Lepikhov @ 2023-12-29 03:23 UTC (permalink / raw) To: Alexander Korotkov <[email protected]>; +Cc: Tom Lane <[email protected]>; PostgreSQL Developers <[email protected]>; Tomas Vondra <[email protected]>; Teodor Sigaev <[email protected]>; David Rowley <[email protected]>; a.rybakina <[email protected]>; Белялов Дамир Наилевич <[email protected]> On 28/12/2023 18:29, Alexander Korotkov wrote: > On Thu, Dec 28, 2023 at 10:22 AM Andrei Lepikhov > <[email protected]> wrote: >> But arrangement with an ORDER BY clause doesn't work: >> >> DROP INDEX abc; >> explain SELECT x,w,z FROM t GROUP BY (w,x,z) ORDER BY (x,z,w); >> >> I think the reason is that the sort_pathkeys and group_pathkeys are >> physically different structures, and we can't just compare pointers here. > > I haven't yet looked into the code. But this looks strange to me. > Somehow, optimizer currently matches index pathkeys to ORDER BY > pathkeys. If GROUP BY pathkeys could be matched to index pathkeys, > then it should be possible to match them to ORDER BY pathkeys too. Oh, I found the mistake: I got used to using GROUP BY and ORDER BY on many columns with round brackets. In the case of the grouping list, it doesn't change anything. But ordering treats it as a WholeRowVar and breaks group-by arrangement. Look: explain (COSTS OFF) SELECT relname,reltuples FROM pg_class GROUP BY relname,reltuples ORDER BY reltuples,relname; Group Group Key: reltuples, relname -> Sort Sort Key: reltuples, relname -> Seq Scan on pg_class But: explain (COSTS OFF) SELECT relname,reltuples FROM pg_class GROUP BY relname,reltuples ORDER BY (reltuples,relname); Sort Sort Key: (ROW(reltuples, relname)) -> Group Group Key: relname, reltuples -> Sort Sort Key: relname, reltuples -> Seq Scan on pg_class So, let's continue to work. -- regards, Andrei Lepikhov Postgres Professional ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: POC: GROUP BY optimization @ 2024-01-26 15:09 Robert Haas <[email protected]> parent: Tom Lane <[email protected]> 1 sibling, 1 reply; 13+ messages in thread From: Robert Haas @ 2024-01-26 15:09 UTC (permalink / raw) To: Tom Lane <[email protected]>; +Cc: Alexander Korotkov <[email protected]>; Andrei Lepikhov <[email protected]>; PostgreSQL Developers <[email protected]>; Tomas Vondra <[email protected]>; Teodor Sigaev <[email protected]>; David Rowley <[email protected]>; a.rybakina <[email protected]>; Белялов Дамир Наилевич <[email protected]> On Tue, Dec 26, 2023 at 10:23 PM Tom Lane <[email protected]> wrote: > I think it's a fool's errand to even try to separate different sort > column orderings by cost. We simply do not have sufficiently accurate > cost information. The previous patch in this thread got reverted because > of that (well, also some implementation issues, but mostly that), and > nothing has happened to make me think that another try will fare any > better. I'm late to the party, but I'd like to better understand what's being argued here. If you're saying that, for some particular planner problem, we should prefer a solution that doesn't need to know about the relative cost of various sorts over one that does, I agree, for exactly the reason that you state: our knowledge of sort costs won't be reliable, and we will make mistakes. That's true in lots of situations, not just related to sorts, because estimation is a hard problem. Heuristics not based on cost are going to be, in many cases, more accurate than heuristics based on cost. They're also often cheaper, since they often let us reject possible approaches very early, without all the bother of a cost comparison. But if you're saying that it's utterly impossible to know whether sorting text will be cheaper or more expensive than sorting 4-byte integers, and that if a particular problem can be solved only by knowing which one is cheaper we should just give up, then I disagree. In the absence of any other information, it must be right, at the very least, to bank on varlena data types being more expensive to sort than fixed-length data types. How much more expensive is hard to know, because toasted blobs are going to be more expensive to sort than short varlenas. But even before you reach the comparison function, a pass-by-value datum has a significantly lower access cost than a pass-by-reference datum. The fact that the pass-by-reference value might be huge only compounds the problem. -- Robert Haas EDB: http://www.enterprisedb.com ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: POC: GROUP BY optimization @ 2024-01-26 15:38 Tom Lane <[email protected]> parent: Robert Haas <[email protected]> 0 siblings, 1 reply; 13+ messages in thread From: Tom Lane @ 2024-01-26 15:38 UTC (permalink / raw) To: Robert Haas <[email protected]>; +Cc: Alexander Korotkov <[email protected]>; Andrei Lepikhov <[email protected]>; PostgreSQL Developers <[email protected]>; Tomas Vondra <[email protected]>; Teodor Sigaev <[email protected]>; David Rowley <[email protected]>; a.rybakina <[email protected]>; Белялов Дамир Наилевич <[email protected]> Robert Haas <[email protected]> writes: > On Tue, Dec 26, 2023 at 10:23 PM Tom Lane <[email protected]> wrote: >> I think it's a fool's errand to even try to separate different sort >> column orderings by cost. We simply do not have sufficiently accurate >> cost information. The previous patch in this thread got reverted because >> of that (well, also some implementation issues, but mostly that), and >> nothing has happened to make me think that another try will fare any >> better. > I'm late to the party, but I'd like to better understand what's being > argued here. What I am saying is that we don't have sufficiently accurate cost information to support the sort of logic that got committed and reverted before. I did not mean to imply that it's not possible to have such info, only that it is not present today. IOW, what I'm saying is that if you want to write code that tries to make a cost-based preference of one sorting over another, you *first* need to put in a bunch of legwork to create more accurate cost numbers. Trying to make such logic depend on the numbers we have today is just going to result in garbage in, garbage out. Sadly, that's not a small task: * We'd need to put effort into assigning more realistic procost values --- preferably across the board, not just comparison functions. As long as all the comparison functions have procost 1.0, you're just flying blind. * As you mentioned, there'd need to be some accounting for the likely size of varlena inputs, and especially whether they might be toasted. * cost_sort knows nothing of the low-level sort algorithm improvements we've made in recent years, such as abbreviated keys. That's a lot of work, and I think it has to be done before we try to build infrastructure on top, not afterwards. regards, tom lane ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: POC: GROUP BY optimization @ 2024-01-26 15:41 Robert Haas <[email protected]> parent: Tom Lane <[email protected]> 0 siblings, 0 replies; 13+ messages in thread From: Robert Haas @ 2024-01-26 15:41 UTC (permalink / raw) To: Tom Lane <[email protected]>; +Cc: Alexander Korotkov <[email protected]>; Andrei Lepikhov <[email protected]>; PostgreSQL Developers <[email protected]>; Tomas Vondra <[email protected]>; Teodor Sigaev <[email protected]>; David Rowley <[email protected]>; a.rybakina <[email protected]>; Белялов Дамир Наилевич <[email protected]> On Fri, Jan 26, 2024 at 10:38 AM Tom Lane <[email protected]> wrote: > Sadly, that's not a small task: > > * We'd need to put effort into assigning more realistic procost > values --- preferably across the board, not just comparison functions. > As long as all the comparison functions have procost 1.0, you're > just flying blind. > > * As you mentioned, there'd need to be some accounting for the > likely size of varlena inputs, and especially whether they might > be toasted. > > * cost_sort knows nothing of the low-level sort algorithm improvements > we've made in recent years, such as abbreviated keys. > > That's a lot of work, and I think it has to be done before we try > to build infrastructure on top, not afterwards. OK, that makes sense to me. Thanks. -- Robert Haas EDB: http://www.enterprisedb.com ^ permalink raw reply [nested|flat] 13+ messages in thread
end of thread, other threads:[~2024-01-26 15:41 UTC | newest] Thread overview: 13+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2023-05-31 11:58 [PATCH v38 09/11] Add support for min/max aggregates for IVM Yugo Nagata <[email protected]> 2023-12-27 02:48 Re: POC: GROUP BY optimization Alexander Korotkov <[email protected]> 2023-12-27 03:23 ` Re: POC: GROUP BY optimization Tom Lane <[email protected]> 2023-12-27 04:15 ` Re: POC: GROUP BY optimization Alexander Korotkov <[email protected]> 2023-12-27 04:27 ` Re: POC: GROUP BY optimization Tom Lane <[email protected]> 2023-12-27 04:35 ` Re: POC: GROUP BY optimization Andrei Lepikhov <[email protected]> 2023-12-27 05:07 ` Re: POC: GROUP BY optimization Tom Lane <[email protected]> 2023-12-28 08:22 ` Re: POC: GROUP BY optimization Andrei Lepikhov <[email protected]> 2023-12-28 11:29 ` Re: POC: GROUP BY optimization Alexander Korotkov <[email protected]> 2023-12-29 03:23 ` Re: POC: GROUP BY optimization Andrei Lepikhov <[email protected]> 2024-01-26 15:09 ` Re: POC: GROUP BY optimization Robert Haas <[email protected]> 2024-01-26 15:38 ` Re: POC: GROUP BY optimization Tom Lane <[email protected]> 2024-01-26 15:41 ` Re: POC: GROUP BY optimization Robert Haas <[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