Построение дерева плана однотабличного запроса PostgreSQL
Поскольку процесс работы планировщика достаточно сложен, в этом разделе описан самый простой процесс - создание дерева плана однотабличного запроса. Более сложный процесс, а именно создание дерева плана многотабличного запроса, описан в разделе 3.6.
Планировщик в PostgreSQL выполняет три этапа:
- предварительная обработка;
- определение самого недорого пути доступа с помощью оценки стоимости всех возможных путей доступа;
- создание дерева плана на основе самого недорого пути.
Путь доступа - это единица обработки для оценки стоимости. Пути доступа используются внутри планировщика для создания дерева планов.
Наиболее фундаментальной структурой путей доступа является структура Path, определенная в pathnodes.h и соответствующая последовательному сканированию. Все остальные пути доступа основаны именно на ней. Более подробная информация предоставлена ниже.
Path
typedef struct PathKey
{
pg_node_attr(no_read, no_query_jumble)
NodeTag type;
/* the value that is ordered */
EquivalenceClass *pk_eclass pg_node_attr(copy_as_scalar, equal_as_scalar);
Oid pk_opfamily; /* btree opfamily defining the ordering */
int pk_strategy; /* sort direction (ASC or DESC) */
bool pk_nulls_first; /* do NULLs come before normal values? */
} PathKey;
typedef struct Path
{
pg_node_attr(no_copy_equal, no_read, no_query_jumble)
NodeTag type;
/* tag identifying scan/join method */
NodeTag pathtype;
/*
* the relation this path can build
*
* We do NOT print the parent, else we'd be in infinite recursion. We can
* print the parent's relids for identification purposes, though.
*/
RelOptInfo *parent pg_node_attr(write_only_relids);
/*
* list of Vars/Exprs, cost, width
*
* We print the pathtarget only if it's not the default one for the rel.
*/
PathTarget *pathtarget pg_node_attr(write_only_nondefault_pathtarget);
/*
* parameterization info, or NULL if none
*
* We do not print the whole of param_info, since it's printed via
* RelOptInfo; it's sufficient and less cluttering to print just the
* required outer relids.
*/
ParamPathInfo *param_info pg_node_attr(write_only_req_outer);
/* engage parallel-aware logic? */
bool parallel_aware;
/* OK to use as part of parallel plan? */
bool parallel_safe;
/* desired # of workers; 0 = not parallel */
int parallel_workers;
/* estimated size/costs for path (see costsize.c for more info) */
Cardinality rows; /* estimated number of result tuples */
Cost startup_cost; /* cost expended before fetching any tuples */
Cost total_cost; /* total cost (assuming all tuples fetched) */
/* sort ordering of path's output; a List of PathKey nodes; see above */
List *pathkeys;
} Path;
Для выполнения вышеописанных действий планировщик создает структуру PlannerInfo, в которой хранится дерево запроса, информация об отношениях, содержащихся в запросе, пути доступа и так далее.
PlannerInfo
/*----------
* PlannerInfo
* Per-query information for planning/optimization
*
* This struct is conventionally called "root" in all the planner routines.
* It holds links to all of the planner's working state, in addition to the
* original Query. Note that at present the planner extensively modifies
* the passed-in Query data structure; someday that should stop.
*
* For reasons explained in optimizer/optimizer.h, we define the typedef
* either here or in that header, whichever is read first.
*
* Not all fields are printed. (In some cases, there is no print support for
* the field type; in others, doing so would lead to infinite recursion or
* bloat dump output more than seems useful.)
*----------
*/
#ifndef HAVE_PLANNERINFO_TYPEDEF
typedef struct PlannerInfo PlannerInfo;
#define HAVE_PLANNERINFO_TYPEDEF 1
#endif
struct PlannerInfo
{
pg_node_attr(no_copy_equal, no_read, no_query_jumble)
NodeTag type;
/* the Query being planned */
Query *parse;
/* global info for current planner run */
PlannerGlobal *glob;
/* 1 at the outermost Query */
Index query_level;
/* NULL at outermost Query */
PlannerInfo *parent_root pg_node_attr(read_write_ignore);
/*
* plan_params contains the expressions that this query level needs to
* make available to a lower query level that is currently being planned.
* outer_params contains the paramIds of PARAM_EXEC Params that outer
* query levels will make available to this query level.
*/
/* list of PlannerParamItems, see below */
List *plan_params;
Bitmapset *outer_params;
/*
* simple_rel_array holds pointers to "base rels" and "other rels" (see
* comments for RelOptInfo for more info). It is indexed by rangetable
* index (so entry 0 is always wasted). Entries can be NULL when an RTE
* does not correspond to a base relation, such as a join RTE or an
* unreferenced view RTE; or if the RelOptInfo hasn't been made yet.
*/
struct RelOptInfo **simple_rel_array pg_node_attr(array_size(simple_rel_array_size));
/* allocated size of array */
int simple_rel_array_size;
/*
* simple_rte_array is the same length as simple_rel_array and holds
* pointers to the associated rangetable entries. Using this is a shade
* faster than using rt_fetch(), mostly due to fewer indirections. (Not
* printed because it'd be redundant with parse->rtable.)
*/
RangeTblEntry **simple_rte_array pg_node_attr(read_write_ignore);
/*
* append_rel_array is the same length as the above arrays, and holds
* pointers to the corresponding AppendRelInfo entry indexed by
* child_relid, or NULL if the rel is not an appendrel child. The array
* itself is not allocated if append_rel_list is empty. (Not printed
* because it'd be redundant with append_rel_list.)
*/
struct AppendRelInfo **append_rel_array pg_node_attr(read_write_ignore);
/*
* all_baserels is a Relids set of all base relids (but not joins or
* "other" rels) in the query. This is computed in deconstruct_jointree.
*/
Relids all_baserels;
/*
* outer_join_rels is a Relids set of all outer-join relids in the query.
* This is computed in deconstruct_jointree.
*/
Relids outer_join_rels;
/*
* all_query_rels is a Relids set of all base relids and outer join relids
* (but not "other" relids) in the query. This is the Relids identifier
* of the final join we need to form. This is computed in
* deconstruct_jointree.
*/
Relids all_query_rels;
/*
* join_rel_list is a list of all join-relation RelOptInfos we have
* considered in this planning run. For small problems we just scan the
* list to do lookups, but when there are many join relations we build a
* hash table for faster lookups. The hash table is present and valid
* when join_rel_hash is not NULL. Note that we still maintain the list
* even when using the hash table for lookups; this simplifies life for
* GEQO.
*/
List *join_rel_list;
struct HTAB *join_rel_hash pg_node_attr(read_write_ignore);
/*
* When doing a dynamic-programming-style join search, join_rel_level[k]
* is a list of all join-relation RelOptInfos of level k, and
* join_cur_level is the current level. New join-relation RelOptInfos are
* automatically added to the join_rel_level[join_cur_level] list.
* join_rel_level is NULL if not in use.
*
* Note: we've already printed all baserel and joinrel RelOptInfos above,
* so we don't dump join_rel_level or other lists of RelOptInfos.
*/
/* lists of join-relation RelOptInfos */
List **join_rel_level pg_node_attr(read_write_ignore);
/* index of list being extended */
int join_cur_level;
/* init SubPlans for query */
List *init_plans;
/*
* per-CTE-item list of subplan IDs (or -1 if no subplan was made for that
* CTE)
*/
List *cte_plan_ids;
/* List of Lists of Params for MULTIEXPR subquery outputs */
List *multiexpr_params;
/* list of JoinDomains used in the query (higher ones first) */
List *join_domains;
/* list of active EquivalenceClasses */
List *eq_classes;
/* set true once ECs are canonical */
bool ec_merging_done;
/* list of "canonical" PathKeys */
List *canon_pathkeys;
/*
* list of OuterJoinClauseInfos for mergejoinable outer join clauses
* w/nonnullable var on left
*/
List *left_join_clauses;
/*
* list of OuterJoinClauseInfos for mergejoinable outer join clauses
* w/nonnullable var on right
*/
List *right_join_clauses;
/*
* list of OuterJoinClauseInfos for mergejoinable full join clauses
*/
List *full_join_clauses;
/* list of SpecialJoinInfos */
List *join_info_list;
/* counter for assigning RestrictInfo serial numbers */
int last_rinfo_serial;
/*
* all_result_relids is empty for SELECT, otherwise it contains at least
* parse->resultRelation. For UPDATE/DELETE/MERGE across an inheritance
* or partitioning tree, the result rel's child relids are added. When
* using multi-level partitioning, intermediate partitioned rels are
* included. leaf_result_relids is similar except that only actual result
* tables, not partitioned tables, are included in it.
*/
/* set of all result relids */
Relids all_result_relids;
/* set of all leaf relids */
Relids leaf_result_relids;
/*
* list of AppendRelInfos
*
* Note: for AppendRelInfos describing partitions of a partitioned table,
* we guarantee that partitions that come earlier in the partitioned
* table's PartitionDesc will appear earlier in append_rel_list.
*/
List *append_rel_list;
/* list of RowIdentityVarInfos */
List *row_identity_vars;
/* list of PlanRowMarks */
List *rowMarks;
/* list of PlaceHolderInfos */
List *placeholder_list;
/* array of PlaceHolderInfos indexed by phid */
struct PlaceHolderInfo **placeholder_array pg_node_attr(read_write_ignore, array_size(placeholder_array_size));
/* allocated size of array */
int placeholder_array_size pg_node_attr(read_write_ignore);
/* list of ForeignKeyOptInfos */
List *fkey_list;
/* desired pathkeys for query_planner() */
List *query_pathkeys;
/* groupClause pathkeys, if any */
List *group_pathkeys;
/*
* The number of elements in the group_pathkeys list which belong to the
* GROUP BY clause. Additional ones belong to ORDER BY / DISTINCT
* aggregates.
*/
int num_groupby_pathkeys;
/* pathkeys of bottom window, if any */
List *window_pathkeys;
/* distinctClause pathkeys, if any */
List *distinct_pathkeys;
/* sortClause pathkeys, if any */
List *sort_pathkeys;
/* Canonicalised partition schemes used in the query. */
List *part_schemes pg_node_attr(read_write_ignore);
/* RelOptInfos we are now trying to join */
List *initial_rels pg_node_attr(read_write_ignore);
/*
* Upper-rel RelOptInfos. Use fetch_upper_rel() to get any particular
* upper rel.
*/
List *upper_rels[UPPERREL_FINAL + 1] pg_node_attr(read_write_ignore);
/* Result tlists chosen by grouping_planner for upper-stage processing */
struct PathTarget *upper_targets[UPPERREL_FINAL + 1] pg_node_attr(read_write_ignore);
/*
* The fully-processed groupClause is kept here. It differs from
* parse->groupClause in that we remove any items that we can prove
* redundant, so that only the columns named here actually need to be
* compared to determine grouping. Note that it's possible for *all* the
* items to be proven redundant, implying that there is only one group
* containing all the query's rows. Hence, if you want to check whether
* GROUP BY was specified, test for nonempty parse->groupClause, not for
* nonempty processed_groupClause.
*
* Currently, when grouping sets are specified we do not attempt to
* optimize the groupClause, so that processed_groupClause will be
* identical to parse->groupClause.
*/
List *processed_groupClause;
/*
* The fully-processed distinctClause is kept here. It differs from
* parse->distinctClause in that we remove any items that we can prove
* redundant, so that only the columns named here actually need to be
* compared to determine uniqueness. Note that it's possible for *all*
* the items to be proven redundant, implying that there should be only
* one output row. Hence, if you want to check whether DISTINCT was
* specified, test for nonempty parse->distinctClause, not for nonempty
* processed_distinctClause.
*/
List *processed_distinctClause;
/*
* The fully-processed targetlist is kept here. It differs from
* parse->targetList in that (for INSERT) it's been reordered to match the
* target table, and defaults have been filled in. Also, additional
* resjunk targets may be present. preprocess_targetlist() does most of
* that work, but note that more resjunk targets can get added during
* appendrel expansion. (Hence, upper_targets mustn't get set up till
* after that.)
*/
List *processed_tlist;
/*
* For UPDATE, this list contains the target table's attribute numbers to
* which the first N entries of processed_tlist are to be assigned. (Any
* additional entries in processed_tlist must be resjunk.) DO NOT use the
* resnos in processed_tlist to identify the UPDATE target columns.
*/
List *update_colnos;
/*
* Fields filled during create_plan() for use in setrefs.c
*/
/* for GroupingFunc fixup (can't print: array length not known here) */
AttrNumber *grouping_map pg_node_attr(read_write_ignore);
/* List of MinMaxAggInfos */
List *minmax_aggs;
/* context holding PlannerInfo */
MemoryContext planner_cxt pg_node_attr(read_write_ignore);
/* # of pages in all non-dummy tables of query */
Cardinality total_table_pages;
/* tuple_fraction passed to query_planner */
Selectivity tuple_fraction;
/* limit_tuples passed to query_planner */
Cardinality limit_tuples;
/*
* Minimum security_level for quals. Note: qual_security_level is zero if
* there are no securityQuals.
*/
Index qual_security_level;
/* true if any RTEs are RTE_JOIN kind */
bool hasJoinRTEs;
/* true if any RTEs are marked LATERAL */
bool hasLateralRTEs;
/* true if havingQual was non-null */
bool hasHavingQual;
/* true if any RestrictInfo has pseudoconstant = true */
bool hasPseudoConstantQuals;
/* true if we've made any of those */
bool hasAlternativeSubPlans;
/* true once we're no longer allowed to add PlaceHolderInfos */
bool placeholdersFrozen;
/* true if planning a recursive WITH item */
bool hasRecursion;
/*
* Information about aggregates. Filled by preprocess_aggrefs().
*/
/* AggInfo structs */
List *agginfos;
/* AggTransInfo structs */
List *aggtransinfos;
/* number of aggs with DISTINCT/ORDER BY/WITHIN GROUP */
int numOrderedAggs;
/* does any agg not support partial mode? */
bool hasNonPartialAggs;
/* is any partial agg non-serializable? */
bool hasNonSerialAggs;
/*
* These fields are used only when hasRecursion is true:
*/
/* PARAM_EXEC ID for the work table */
int wt_param_id;
/* a path for non-recursive term */
struct Path *non_recursive_path;
/*
* These fields are workspace for createplan.c
*/
/* outer rels above current node */
Relids curOuterRels;
/* not-yet-assigned NestLoopParams */
List *curOuterParams;
/*
* These fields are workspace for setrefs.c. Each is an array
* corresponding to glob->subplans. (We could probably teach
* gen_node_support.pl how to determine the array length, but it doesn't
* seem worth the trouble, so just mark them read_write_ignore.)
*/
bool *isAltSubplan pg_node_attr(read_write_ignore);
bool *isUsedSubplan pg_node_attr(read_write_ignore);
/* optional private data for join_search_hook, e.g., GEQO */
void *join_search_private pg_node_attr(read_write_ignore);
/* Does this query modify any partition key columns? */
bool partColsUpdated;
};
Предварительная обработка
Перед созданием дерева планов планировщик выполняет некоторую предварительную обработку дерева запросов, хранящегося в структуре PlannerInfo.
Хотя предварительная обработка включает в себя несколько этапов, в этом подразделе мы рассматриваем только основную предварительную обработку однотабличного запроса. Остальные этапы предварительной обработки описаны в разделе 3.6.
Этапы предварительной обработки:
- Упрощение целевых списков, ограничительных условий и так далее.
Например, функция eval_const_expressions(), определенная в clauses.c, преобразовывает '2 + 2' в '4'.
- Оптимизация выражений Boolean.
Например, ‘NOT (NOT a)’ преобразовывается в ‘a’.
- Преобразование выражений AND/OR.
В PostgreSQL AND и OR называются конъюнктивными операторами, планировщик всегда сглаживает эти выражения.
Приведем конкретный пример. Рассмотрим выражение Boolean '(id = 1) OR (id = 2) OR (id = 3)'. На рисунке 17 (a) показана часть дерева запросов при использовании бинарного оператора. Планировщик упростил это дерево – смотрите рисунок 17(b).
Определение оптимального пути доступа
Для того, чтобы получить самый недорогой путь доступа, планировщик оценивает стоимость всех возможных путей доступа и выбирает из них самый недорогой. Для этого планировщик выполняет следующие операции:
- Создает структуру RelOptInfo, необходимую для хранения путей доступа и соответствующих затрат.
Структура RelOptInfo создается с помощью функции make_one_rel() и хранится в массиве simple_rel_array структуры PlannerInfo. Смотрите рисунок 18. В исходном состоянии RelOptInfo содержит базовую информацию об ограничениях и список индексов. В baserestrictinfo хранятся пункты WHERE запроса, а в indexlist - связанные индексы целевой таблицы.
RelOptInfo
typedef enum RelOptKind
{
RELOPT_BASEREL,
RELOPT_JOINREL,
RELOPT_OTHER_MEMBER_REL,
RELOPT_OTHER_JOINREL,
RELOPT_UPPER_REL,
RELOPT_OTHER_UPPER_REL
} RelOptKind;
/*
* Is the given relation a simple relation i.e a base or "other" member
* relation?
*/
#define IS_SIMPLE_REL(rel) \
((rel)->reloptkind == RELOPT_BASEREL || \
(rel)->reloptkind == RELOPT_OTHER_MEMBER_REL)
/* Is the given relation a join relation? */
#define IS_JOIN_REL(rel) \
((rel)->reloptkind == RELOPT_JOINREL || \
(rel)->reloptkind == RELOPT_OTHER_JOINREL)
/* Is the given relation an upper relation? */
#define IS_UPPER_REL(rel) \
((rel)->reloptkind == RELOPT_UPPER_REL || \
(rel)->reloptkind == RELOPT_OTHER_UPPER_REL)
/* Is the given relation an "other" relation? */
#define IS_OTHER_REL(rel) \
((rel)->reloptkind == RELOPT_OTHER_MEMBER_REL || \
(rel)->reloptkind == RELOPT_OTHER_JOINREL || \
(rel)->reloptkind == RELOPT_OTHER_UPPER_REL)
typedef struct RelOptInfo
{
pg_node_attr(no_copy_equal, no_read, no_query_jumble)
NodeTag type;
RelOptKind reloptkind;
/*
* all relations included in this RelOptInfo; set of base + OJ relids
* (rangetable indexes)
*/
Relids relids;
/*
* size estimates generated by planner
*/
/* estimated number of result tuples */
Cardinality rows;
/*
* per-relation planner control flags
*/
/* keep cheap-startup-cost paths? */
bool consider_startup;
/* ditto, for parameterized paths? */
bool consider_param_startup;
/* consider parallel paths? */
bool consider_parallel;
/*
* default result targetlist for Paths scanning this relation; list of
* Vars/Exprs, cost, width
*/
struct PathTarget *reltarget;
/*
* materialization information
*/
List *pathlist; /* Path structures */
List *ppilist; /* ParamPathInfos used in pathlist */
List *partial_pathlist; /* partial Paths */
struct Path *cheapest_startup_path;
struct Path *cheapest_total_path;
struct Path *cheapest_unique_path;
List *cheapest_parameterized_paths;
/*
* parameterization information needed for both base rels and join rels
* (see also lateral_vars and lateral_referencers)
*/
/* rels directly laterally referenced */
Relids direct_lateral_relids;
/* minimum parameterization of rel */
Relids lateral_relids;
/*
* information about a base rel (not set for join rels!)
*/
Index relid;
/* containing tablespace */
Oid reltablespace;
/* RELATION, SUBQUERY, FUNCTION, etc */
RTEKind rtekind;
/* smallest attrno of rel (often <0) */
AttrNumber min_attr;
/* largest attrno of rel */
AttrNumber max_attr;
/* array indexed [min_attr .. max_attr] */
Relids *attr_needed pg_node_attr(read_write_ignore);
/* array indexed [min_attr .. max_attr] */
int32 *attr_widths pg_node_attr(read_write_ignore);
/* relids of outer joins that can null this baserel */
Relids nulling_relids;
/* LATERAL Vars and PHVs referenced by rel */
List *lateral_vars;
/* rels that reference this baserel laterally */
Relids lateral_referencers;
/* list of IndexOptInfo */
List *indexlist;
/* list of StatisticExtInfo */
List *statlist;
/* size estimates derived from pg_class */
BlockNumber pages;
Cardinality tuples;
double allvisfrac;
/* indexes in PlannerInfo's eq_classes list of ECs that mention this rel */
Bitmapset *eclass_indexes;
PlannerInfo *subroot; /* if subquery */
List *subplan_params; /* if subquery */
/* wanted number of parallel workers */
int rel_parallel_workers;
/* Bitmask of optional features supported by the table AM */
uint32 amflags;
/*
* Information about foreign tables and foreign joins
*/
/* identifies server for the table or join */
Oid serverid;
/* identifies user to check access as; 0 means to check as current user */
Oid userid;
/* join is only valid for current user */
bool useridiscurrent;
/* use "struct FdwRoutine" to avoid including fdwapi.h here */
struct FdwRoutine *fdwroutine pg_node_attr(read_write_ignore);
void *fdw_private pg_node_attr(read_write_ignore);
/*
* cache space for remembering if we have proven this relation unique
*/
/* known unique for these other relid set(s) */
List *unique_for_rels;
/* known not unique for these set(s) */
List *non_unique_for_rels;
/*
* used by various scans and joins:
*/
/* RestrictInfo structures (if base rel) */
List *baserestrictinfo;
/* cost of evaluating the above */
QualCost baserestrictcost;
/* min security_level found in baserestrictinfo */
Index baserestrict_min_security;
/* RestrictInfo structures for join clauses involving this rel */
List *joininfo;
/* T means joininfo is incomplete */
bool has_eclass_joins;
/*
* used by partitionwise joins:
*/
/* consider partitionwise join paths? (if partitioned rel) */
bool consider_partitionwise_join;
/*
* inheritance links, if this is an otherrel (otherwise NULL):
*/
/* Immediate parent relation (dumping it would be too verbose) */
struct RelOptInfo *parent pg_node_attr(read_write_ignore);
/* Topmost parent relation (dumping it would be too verbose) */
struct RelOptInfo *top_parent pg_node_attr(read_write_ignore);
/* Relids of topmost parent (redundant, but handy) */
Relids top_parent_relids;
/*
* used for partitioned relations:
*/
/* Partitioning scheme */
PartitionScheme part_scheme pg_node_attr(read_write_ignore);
/*
* Number of partitions; -1 if not yet set; in case of a join relation 0
* means it's considered unpartitioned
*/
int nparts;
/* Partition bounds */
struct PartitionBoundInfoData *boundinfo pg_node_attr(read_write_ignore);
/* True if partition bounds were created by partition_bounds_merge() */
bool partbounds_merged;
/* Partition constraint, if not the root */
List *partition_qual;
/*
* Array of RelOptInfos of partitions, stored in the same order as bounds
* (don't print, too bulky and duplicative)
*/
struct RelOptInfo **part_rels pg_node_attr(read_write_ignore);
/*
* Bitmap with members acting as indexes into the part_rels[] array to
* indicate which partitions survived partition pruning.
*/
Bitmapset *live_parts;
/* Relids set of all partition relids */
Relids all_partrels;
/*
* These arrays are of length partkey->partnatts, which we don't have at
* hand, so don't try to print
*/
/* Non-nullable partition key expressions */
List **partexprs pg_node_attr(read_write_ignore);
/* Nullable partition key expressions */
List **nullable_partexprs pg_node_attr(read_write_ignore);
} RelOptInfo;
-
Оценивает стоимость всех возможных путей доступа и добавляет их в структуру RelOptInfo:
- Создает путь, оценивает стоимость последовательного сканирования. Затем путь добавляется в pathlist структуры RelOptInfo.
- В случае, если существуют индексы, связанные с целевой таблицей, создаются пути доступа к индексам, оцениваются все затраты на сканирование индексов. Затем пути доступа к индексам добавляются в pathlist.
- Если можно выполнить bitmap scan, создаются соответствующие пути, оцениваются затраты. Затим эти пути добавляются в pathlist.
- Определяет самый недорогой путь доступа в pathlist структуры RelOptInfo.
- При необходимости оценивает затраты на LIMIT, ORDER BY и ARREGISFDD.
Для того, чтобы понять, как именно действует планировщик, рассмотрим два примера, приведенные ниже.
Пример 1
Для начала рассмотрим простой однотабличный запрос без индексов, содержащий WHERE и ORDER BY.
testdb=# \d tbl_1
Table "public.tbl_1"Column | Type | Modifiers --------+---------+----------- id | integer | data | integer | testdb=# SELECT * FROM tbl_1 WHERE id < 300 ORDER BY data;
Рисунки описывают процесс работы планировщика в данном случае.
(1) Создает структуру RelOptInfo и сохраняет ее в массиве simple_rel_array файла PlannerInfo.
(2) В поле baserestrictinfo RelOptInfo добавляет условие WHERE.
Условие WHERE 'id<300' добавляется к baserestrictinfo при помощи функции distribute_restrictinfo_to_rels(), определенной в initsplan.c. Индексный список RelOptInfo равен NULL, поскольку целевая таблица не содержит связанных индексов.
(3) Добавляет ключ пути для сортировки в sort_pathkeys PlannerInfo с помощью функции standard_qp_callback(), определенной в planner.c.
Pathkey - это структура данных, представляющая порядок сортировки. В данном примере столбец 'data' добавлен в sort_pathkeys в качестве ключа пути, поскольку этот запрос содержит предложение ORDER BY.
(4) Создает структуру пути, оценивает стоимость последовательного сканирования с помощью функции cost_seqscan и записывает затраты в путь. После этого добавляет путь в RelOptInfo с помощью функции add_path(), определенной в pathnode.c.
Напомним, что структура Path содержит начальные и общие затраты, которые оцениваются при помощи функции cost_seqscan.
В данном примере планировщик оценивает только стоимость последовательного сканирования (так как индексы целевой таблицы отсутствуют). В связи с этим самый недорогойй путь доступа определяется автоматически.
- (5) Создает новую структуру RelOptInfo для обработки ORDER BY.
Обратите внимание, что новая структура RelOptInfo не содержит информации о предложении WHERE.
- (6) Создает путь сортировки и добавляет его в RelOptInfo.
Структура SortPath состоит из двух структур путей: path и subpath; path хранит информацию о самой операции сортировки, а subpath - самый недорогой путь.
Обратите внимание, что элемент 'parent' пути последовательного сканирования содержит ссылку на старую RelOptInfo, которая хранит предложение WHERE в baserestrictinfo. Поэтому на следующем этапе, то есть при создании дерева плана, планировщик может создать узел последовательного сканирования, содержащий условие WHERE в качестве 'фильтра', даже если новая RelOptInfo не содержит базовую ограничительную информацию.
SortPath
typedef struct SortPath
{
Path path;
Path *subpath; /* path representing input source */
} SortPath;
На основе самого недорогого пути доступаформируется дерево плана. Подробности описаны в разделе 3.3.3.
Пример 2
Теперь рассмотрим другой запрос с одной таблицей и двумя индексами, содержащий предложение WHERE.
testdb=# \d tbl_2
Table "public.tbl_2"Column | Type | Modifiers --------+---------+----------- id | integer | not null
data | integer |
Indexes:
"tbl_2_pkey" PRIMARY KEY, btree (id)
"tbl_2_data_idx" btree (data)
testdb=# SELECT * FROM tbl_2 WHERE id < 240;
Рисунки описывает действия планировщика в данном случае.
(1) Создает структуру RelOptInfo.
(2) В baserestrictinfo добавляет условие WHERE, в indexlist – индексы целевой таблицы.
В данном случае, в baserestrictinfo добавлено условие WHERE ‘id<240’, а в indexlist RelOptInfo добавлены два индекса - tbl_2_pkey и tbl_2_data_idx.
(3) Создает путь, оценивает стоимость последовательного сканирования, добавляет путь в pathlist RelOptInfo.
(4) Создает IndexPath, оценивает стоимость индексного сканирования, добавляет IndexPath в pathlist RelOptInfo с помощью функции add_path().
Поскольку в данном примере есть два индекса, tbl_2_pkey и tbl_2_data_idx, они обрабатываются по очереди. В первую очередь обрабатывается tbl_2_pkey.
Для tbl_2_pkey создается IndexPath, определяются начальная и общая стоимость. В данном случае tbl_2_pkey относится к столбцу ‘id’, предложение WHERE также содержит ‘id’; поэтому условие WHERE сохраняется в indexclauses IndexPath.
Отметим, что при добавлении путей доступа в pathlist функция add_path() добавляет пути в порядке возрастания общей стоимости. В данном случае общая стоимость индексного сканирования меньше, чем общая стоимость последовательного сканирования, поэтому путь индексного сканирования добавляется перед путем последовательного сканирования.
IndexPath
typedef struct IndexPath
{
Path path;
IndexOptInfo *indexinfo;
List *indexclauses;
List *indexorderbys;
List *indexorderbycols;
ScanDirection indexscandir;
Cost indextotalcost;
Selectivity indexselectivity;
} IndexPath;
/*
* IndexOptInfo
* Per-index information for planning/optimization
*
* indexkeys[], indexcollations[] each have ncolumns entries.
* opfamily[], and opcintype[] each have nkeycolumns entries. They do
* not contain any information about included attributes.
*
* sortopfamily[], reverse_sort[], and nulls_first[] have
* nkeycolumns entries, if the index is ordered; but if it is unordered,
* those pointers are NULL.
*
* Zeroes in the indexkeys[] array indicate index columns that are
* expressions; there is one element in indexprs for each such column.
*
* For an ordered index, reverse_sort[] and nulls_first[] describe the
* sort ordering of a forward indexscan; we can also consider a backward
* indexscan, which will generate the reverse ordering.
*
* The indexprs and indpred expressions have been run through
* prepqual.c and eval_const_expressions() for ease of matching to
* WHERE clauses. indpred is in implicit-AND form.
*
* indextlist is a TargetEntry list representing the index columns.
* It provides an equivalent base-relation Var for each simple column,
* and links to the matching indexprs element for each expression column.
*
* While most of these fields are filled when the IndexOptInfo is created
* (by plancat.c), indrestrictinfo and predOK are set later, in
* check_index_predicates().
*/
#ifndef HAVE_INDEXOPTINFO_TYPEDEF
typedef struct IndexOptInfo IndexOptInfo;
#define HAVE_INDEXOPTINFO_TYPEDEF 1
#endif
struct IndexOptInfo
{
pg_node_attr(no_copy_equal, no_read, no_query_jumble)
NodeTag type;
/* OID of the index relation */
Oid indexoid;
/* tablespace of index (not table) */
Oid reltablespace;
/* back-link to index's table; don't print, else infinite recursion */
RelOptInfo *rel pg_node_attr(read_write_ignore);
/*
* index-size statistics (from pg_class and elsewhere)
*/
/* number of disk pages in index */
BlockNumber pages;
/* number of index tuples in index */
Cardinality tuples;
/* index tree height, or -1 if unknown */
int tree_height;
/*
* index descriptor information
*/
/* number of columns in index */
int ncolumns;
/* number of key columns in index */
int nkeycolumns;
/*
* table column numbers of index's columns (both key and included
* columns), or 0 for expression columns
*/
int *indexkeys pg_node_attr(array_size(ncolumns));
/* OIDs of collations of index columns */
Oid *indexcollations pg_node_attr(array_size(nkeycolumns));
/* OIDs of operator families for columns */
Oid *opfamily pg_node_attr(array_size(nkeycolumns));
/* OIDs of opclass declared input data types */
Oid *opcintype pg_node_attr(array_size(nkeycolumns));
/* OIDs of btree opfamilies, if orderable. NULL if partitioned index */
Oid *sortopfamily pg_node_attr(array_size(nkeycolumns));
/* is sort order descending? or NULL if partitioned index */
bool *reverse_sort pg_node_attr(array_size(nkeycolumns));
/* do NULLs come first in the sort order? or NULL if partitioned index */
bool *nulls_first pg_node_attr(array_size(nkeycolumns));
/* opclass-specific options for columns */
bytea **opclassoptions pg_node_attr(read_write_ignore);
/* which index cols can be returned in an index-only scan? */
bool *canreturn pg_node_attr(array_size(ncolumns));
/* OID of the access method (in pg_am) */
Oid relam;
/*
* expressions for non-simple index columns; redundant to print since we
* print indextlist
*/
List *indexprs pg_node_attr(read_write_ignore);
/* predicate if a partial index, else NIL */
List *indpred;
/* targetlist representing index columns */
List *indextlist;
/*
* parent relation's baserestrictinfo list, less any conditions implied by
* the index's predicate (unless it's a target rel, see comments in
* check_index_predicates())
*/
List *indrestrictinfo;
/* true if index predicate matches query */
bool predOK;
/* true if a unique index */
bool unique;
/* is uniqueness enforced immediately? */
bool immediate;
/* true if index doesn't really exist */
bool hypothetical;
/*
* Remaining fields are copied from the index AM's API struct
* (IndexAmRoutine). These fields are not set for partitioned indexes.
*/
bool amcanorderbyop;
bool amoptionalkey;
bool amsearcharray;
bool amsearchnulls;
/* does AM have amgettuple interface? */
bool amhasgettuple;
/* does AM have amgetbitmap interface? */
bool amhasgetbitmap;
bool amcanparallel;
/* does AM have ammarkpos interface? */
bool amcanmarkpos;
/* AM's cost estimator */
/* Rather than include amapi.h here, we declare amcostestimate like this */
void (*amcostestimate) () pg_node_attr(read_write_ignore);
};
(5) Создает еще один IndexPath, оценивает стоимость других индексных сканирований, добавляет путь индексного сканирования в pathlist RelOptInfo.
Далее определяются затраты, и в pathlist добавляется IndexPath. В данном случае, условие WHERE, относящееся к индексу tbl_2_data_idx, отсутствует; поэтому условия индекса - NULL.
Примечание: функция add_path() не всегда добавляет путь. Не будем вдаваться в поробности проесса ввиду его сложности.
(6) Создает новую структуру RelOptInfo.
(7) Добавляет самый недорогой путь в pathlist новой RelOptInfo.
В данном случае самый недорогой путь – это путь индексного сканирования, использующий индекс tbl_2_pkey; таким образом, этот путь добавляется в pathlist новой RelOptInfo.
Формирование дерева планов
Заключительным шагом является формирование дерева планов на основе самого недорогого пути.
Корнем дерева планов является структура PlannedStmt, определенная в plannodes.h. Данная структура содердит 19 полей, самыми важными из которых являются следующие:
- commandType хранит тип операции, например, SELECT, UPDATE или INSERT.
- rtable хранит записи rangeTable.
- relationOids хранит идентификаторы объекта таблиц, связанных с запросом.
- plantree хранит дерево планов, состоящее из узлов плана, где каждый узел соответствует определенной операции (последовательное сканирование, сортировка и т.д.)
PlannedStmt
typedef struct PlannedStmt
{
pg_node_attr(no_equal, no_query_jumble)
NodeTag type;
CmdType commandType; /* select|insert|update|delete|merge|utility */
uint64 queryId; /* query identifier (copied from Query) */
bool hasReturning; /* is it insert|update|delete RETURNING? */
bool hasModifyingCTE; /* has insert|update|delete in WITH? */
bool canSetTag; /* do I set the command result tag? */
bool transientPlan; /* redo plan when TransactionXmin changes? */
bool dependsOnRole; /* is plan specific to current role? */
bool parallelModeNeeded; /* parallel mode required to execute? */
int jitFlags; /* which forms of JIT should be performed */
struct Plan *planTree; /* tree of Plan nodes */
List *rtable; /* list of RangeTblEntry nodes */
List *permInfos; /* list of RTEPermissionInfo nodes for rtable
* entries needing one */
/* rtable indexes of target relations for INSERT/UPDATE/DELETE/MERGE */
List *resultRelations; /* integer list of RT indexes, or NIL */
List *appendRelations; /* list of AppendRelInfo nodes */
List *subplans; /* Plan trees for SubPlan expressions; note
* that some could be NULL */
Bitmapset *rewindPlanIDs; /* indices of subplans that require REWIND */
List *rowMarks; /* a list of PlanRowMark's */
List *relationOids; /* OIDs of relations the plan depends on */
List *invalItems; /* other dependencies, as PlanInvalItems */
List *paramExecTypes; /* type OIDs for PARAM_EXEC Params */
Node *utilityStmt; /* non-null if this is utility stmt */
/* statement location in source string (copied from Query) */
int stmt_location; /* start location, or -1 if unknown */
int stmt_len; /* length in bytes; 0 means "rest of string" */
} PlannedStmt;
Как уже было отмечено ранее, дерево плана состоит из нескольких узлов плана. Структура PlanNode – базовый узел, входящий в состав других узлов. Например, SeqScanNode состоит из PlanNode и целочисленной переменной ‘scanrelid’. PlanNode содержит 14 полей, в том числе:
- start-up cost и total_cost – стоимость операции, соответствующей данному узлу;
- rows – количество строк, подлежащих сканированию, определенное планировщиком;
- qual – список, хранящий условия квалификации.
PlanNode
/* ----------------
* Plan node
*
* All plan nodes "derive" from the Plan structure by having the
* Plan structure as the first field. This ensures that everything works
* when nodes are cast to Plan's. (node pointers are frequently cast to Plan*
* when passed around generically in the executor)
*
* We never actually instantiate any Plan nodes; this is just the common
* abstract superclass for all Plan-type nodes.
* ----------------
*/
typedef struct Plan
{
pg_node_attr(abstract, no_equal, no_query_jumble)
NodeTag type;
/*
* estimated execution costs for plan (see costsize.c for more info)
*/
Cost startup_cost; /* cost expended before fetching any tuples */
Cost total_cost; /* total cost (assuming all tuples fetched) */
/*
* planner's estimate of result size of this plan step
*/
Cardinality plan_rows; /* number of rows plan is expected to emit */
int plan_width; /* average row width in bytes */
/*
* information needed for parallel query
*/
bool parallel_aware; /* engage parallel-aware logic? */
bool parallel_safe; /* OK to use as part of parallel plan? */
/*
* information needed for asynchronous execution
*/
bool async_capable; /* engage asynchronous-capable logic? */
/*
* Common structural data for all Plan types.
*/
int plan_node_id; /* unique across entire final plan tree */
List *targetlist; /* target list to be computed at this node */
List *qual; /* implicitly-ANDed qual conditions */
struct Plan *lefttree; /* input plan tree(s) */
struct Plan *righttree;
List *initPlan; /* Init Plan nodes (un-correlated expr
* subselects) */
/*
* Information for management of parameter-change-driven rescanning
*
* extParam includes the paramIDs of all external PARAM_EXEC params
* affecting this plan node or its children. setParam params from the
* node's initPlans are not included, but their extParams are.
*
* allParam includes all the extParam paramIDs, plus the IDs of local
* params that affect the node (i.e., the setParams of its initplans).
* These are _all_ the PARAM_EXEC params that affect this node.
*/
Bitmapset *extParam;
Bitmapset *allParam;
} Plan;ScanNode
/*
* ==========
* Scan nodes
*
* Scan is an abstract type that all relation scan plan types inherit from.
* ==========
*/
typedef struct Scan
{
pg_node_attr(abstract)
Plan plan;
Index scanrelid; /* relid is index into the range table */
} Scan;
/* ----------------
* sequential scan node
* ----------------
*/
typedef struct SeqScan
{
Scan scan;
} SeqScan;
Далее будут описаны два дерева планов, сгенерированных из самых недорогих путей, описанных выше.
Пример 1
В данном случае SortNode добавляется к plantree структуры PlannedStmt, SeqScanNode добавляется к lefttree структуры SortNode. Смотри рисунок 22.
SortNode
* ----------------
* sort node
* ----------------
*/
typedef struct Sort
{
Plan plan;
/* number of sort-key columns */
int numCols;
/* their indexes in the target list */
AttrNumber *sortColIdx pg_node_attr(array_size(numCols));
/* OIDs of operators to sort them by */
Oid *sortOperators pg_node_attr(array_size(numCols));
/* OIDs of collations */
Oid *collations pg_node_attr(array_size(numCols));
/* NULLS FIRST/LAST directions */
bool *nullsFirst pg_node_attr(array_size(numCols));
} Sort;
Пример 2
Самый недорогой путь – это путь индексного сканированя, поэтому дерево планов состоит только из структуры IndexScanNode.
IndexScanNode
/* ----------------
* index scan node
*
* indexqualorig is an implicitly-ANDed list of index qual expressions, each
* in the same form it appeared in the query WHERE condition. Each should
* be of the form (indexkey OP comparisonval) or (comparisonval OP indexkey).
* The indexkey is a Var or expression referencing column(s) of the index's
* base table. The comparisonval might be any expression, but it won't use
* any columns of the base table. The expressions are ordered by index
* column position (but items referencing the same index column can appear
* in any order). indexqualorig is used at runtime only if we have to recheck
* a lossy indexqual.
*
* indexqual has the same form, but the expressions have been commuted if
* necessary to put the indexkeys on the left, and the indexkeys are replaced
* by Var nodes identifying the index columns (their varno is INDEX_VAR and
* their varattno is the index column number).
*
* indexorderbyorig is similarly the original form of any ORDER BY expressions
* that are being implemented by the index, while indexorderby is modified to
* have index column Vars on the left-hand side. Here, multiple expressions
* must appear in exactly the ORDER BY order, and this is not necessarily the
* index column order. Only the expressions are provided, not the auxiliary
* sort-order information from the ORDER BY SortGroupClauses; it's assumed
* that the sort ordering is fully determinable from the top-level operators.
* indexorderbyorig is used at runtime to recheck the ordering, if the index
* cannot calculate an accurate ordering. It is also needed for EXPLAIN.
*
* indexorderbyops is a list of the OIDs of the operators used to sort the
* ORDER BY expressions. This is used together with indexorderbyorig to
* recheck ordering at run time. (Note that indexorderby, indexorderbyorig,
* and indexorderbyops are used for amcanorderbyop cases, not amcanorder.)
*
* indexorderdir specifies the scan ordering, for indexscans on amcanorder
* indexes (for other indexes it should be "don't care").
* ----------------
*/
typedef struct Scan
{
pg_node_attr(abstract)
Plan plan;
Index scanrelid; /* relid is index into the range table */
} Scan;
typedef struct IndexScan
{
Scan scan;
Oid indexid; /* OID of index to scan */
List *indexqual; /* list of index quals (usually OpExprs) */
List *indexqualorig; /* the same in original form */
List *indexorderby; /* list of index ORDER BY exprs */
List *indexorderbyorig; /* the same in original form */
List *indexorderbyops; /* OIDs of sort ops for ORDER BY exprs */
ScanDirection indexorderdir; /* forward or backward or don't care */
} IndexScan;
В данном случае предложение WHERE 'id<240' является предикатом доступа, поэтому оно хранится в indexqual IndexScanNode.
