Обсуждение: Get more from indices.
Hello, This is the last episode of the 'dance with indices'?
series.
Unique indexes can sort the tuples in corresponding tables
prefectly. So this query might can use index.
> uniquetest=# create table t (a int, b int, c int, d text);
> uniquetest=# create unique index i_t_pkey on t(a, b);
> uniquetest=# insert into t
> (select a % 10, a / 10, a, 't' from generate_series(0, 100000) a);
> uniquetest=# analyze;
>
> uniquetest=# explain (costs off, analyze on) select distinct * from t;
> QUERY PLAN
> ---------------------------------------------------------------------------
> Unique (actual time=149.625..245.978 rows=100001 loops=1)
> -> Sort (actual time=149.624..199.806 rows=100001 loops=1)
> Sort Key: a, b, c, d
> Sort Method: external merge Disk: 2328kB
> -> Seq Scan on t (actual time=0.016..15.597 rows=100001 loops=1)
> Total runtime: 251.272 ms
With this patch, the plan for this query becomes as follows,
> uniquetest=# explain (costs off, analyze on) select distinct * from t;
> QUERY PLAN
> ---------------------------------------------------------------------
> Index Scan using i_t_pkey on t
> (actual time=0.019..32.457 rows=100001 loops=1)
> Total runtime: 37.488 ms
This only seems not so valuable to archive, but with my previous
MergeAppend for UNION patch, this will have more value.
> uniquetest=# create table pu1 (a int, b int, c int, d text);
> uniquetest=# create unique index pu1_pkey_idx on pu1 (a, b);
> uniquetest=# create table cu11 (like pu1 including all) inherits (pu1);
> uniquetest=# create table cu12 (like pu1 including all) inherits (pu1);
> uniquetest=# create table pu2 (like pu1 including all);
> uniquetest=# create table cu21 (like pu1 including all) inherits (pu2);
> uniquetest=# create table cu22 (like pu1 including all) inherits (pu2);
> uniquetest=# insert into cu11 (select a / 5, 4 - (a % 5), a, 'cu11'
> from generate_series(000000, 099999) a);
> uniquetest=# insert into cu12 (select a / 5, 4 - (a % 5), a, 'cu12'
> from generate_series(100000, 199999) a);
> uniquetest=# insert into cu21 (select a / 5, 4 - (a % 5), a, 'cu21'
> from generate_series(150000, 249999) a);
> uniquetest=# insert into cu22 (select a / 5, 4 - (a % 5), a, 'cu22'
> from generate_series(250000, 349999) a);
> uniquetest=# explain (analyze on, costs off)
> select * from pu1 union select * from pu2 order by a, b limit 100;
> QUERY PLAN
> --------------------------------------------------------------------------
> Limit (actual time=0.226..0.591 rows=100 loops=1)
> -> Unique (actual time=0.223..0.561 rows=100 loops=1)
> -> Merge Append (actual time=0.223..0.470 rows=100 loops=1)
> Sort Key: pu1.a, pu1.b, pu1.c, pu1.d
> -> Limit (actual time=0.125..0.326 rows=100 loops=1)
> -> Unique (actual time=0.125..0.303 rows=100 loops=1)
> -> Merge Append (actual time=0.123..0.220 rows=100 loops=1)
> Sort Key: pu1.a, pu1.b, pu1.c, pu1.d
> -> Index Scan using..on pu1 (actual time=0.005..0.005 rows=0 loops=1)
> -> Index Scan using..on cu11(actual time=0.071..0.128 rows=100 loops=1)
> -> Index Scan using..on cu12 (actual time=0.045..0.045 rows=1 loops=1)
> -> Limit (actual time=0.096..0.096 rows=1 loops=1)
> -> Unique (actual time=0.096..0.096 rows=1 loops=1)
> -> Merge Append (actual time=0.094..0.094 rows=1 loops=1)
> Sort Key: pu2.a, pu2.b, pu2.c, pu2.d
> -> Index Scan using..on pu2 (actual time=0.002..0.002 rows=0 loops=1)
> -> Index Scan using..on cu21 (actual time=0.047..0.047 rows=1 loops=1)
> -> Index Scan using..on cu22 (actual time=0.043..0.043 rows=1 loops=1)
> Total runtime: 1.987 ms
On the other hand, what we will get from the unpatched PostgreSQL is,
> uniquetest=# explain (analyze on, costs off)
> select * from pu1 union select * from pu2 order by a, b limit 100;
> QUERY PLAN
> -------------------------------------------------------------------------
> Limit (actual time=535.620..535.706 rows=100 loops=1)
> -> Unique (actual time=535.618..535.695 rows=100 loops=1)
> -> Sort (actual time=535.617..535.637 rows=100 loops=1)
> Sort Key: pu1.a, pu1.b, pu1.c, pu1.d
> Sort Method: external sort Disk: 10568kB
> -> Append (actual time=0.012..144.144 rows=400000 loops=1)
> -> Append (actual time=0.012..49.570 rows=200000 loops=1)
> -> Seq Scan on pu1 (actual time=0.001..0.001 rows=0 loops=1)
> -> Seq Scan on cu11 (actual time=0.011..16.202 rows=100000 loops=1)
> -> Seq Scan on cu12 (actual time=0.008..16.334 rows=100000 loops=1)
> -> Append (actual time=0.010..54.052 rows=200000 loops=1)
> -> Seq Scan on pu2 (actual time=0.000..0.000 rows=0 loops=1)
> -> Seq Scan on cu21 (actual time=0.009..16.444 rows=100000 loops=1)
> -> Seq Scan on cu22 (actual time=0.021..18.923 rows=100000 loops=1)
> Total runtime: 537.765 ms
What do you think about this?
This could be realized by following modifications,
- Consider a query pathekeys is useful for ordering when a index pathkey is a subset of that when the index is UNIQUE.
(build_index_paths, pathkeys_useful_for_ordering, truncate_useless_pathkeys, grouping_planner)
- Judge a path is orderd or not counting the uniqueness of the path.
- Regard IndexPath on UNIQUE index is reagarded uniquely ordered.
- Regard MergeAppendPath of which all children is uniquely orderd as (not necessarily uniquely) ordered.
(path_is_ordered)
- Judge the necessity of sorting on above premises. (grouping_planner)
Needless to say, theses patches have no effect on any other set
operations than UNION(ALL). They are, INTERSECT(ALL),
EXCEPT(ALL).
regards,
--
Kyotaro Horiguchi
NTT Open Source Software Center
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 606734a..bc1ab9a 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -953,7 +953,8 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_pathkeys =
build_index_pathkeys(root,index, ForwardScanDirection);
useful_pathkeys= truncate_useless_pathkeys(root, rel,
- index_pathkeys);
+ index_pathkeys,
+ index->unique); orderbyclauses = NIL;
orderbyclausecols= NIL; }
@@ -1015,7 +1016,8 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_pathkeys =
build_index_pathkeys(root,index, BackwardScanDirection);
useful_pathkeys= truncate_useless_pathkeys(root, rel,
- index_pathkeys);
+ index_pathkeys,
+ index->unique); if (useful_pathkeys != NIL) {
ipath = create_index_path(root, index,
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 6724996..87070e7 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -363,6 +363,68 @@ get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,}/*
+ * path_is_uniquely_ordered
+ * Return true if the path is apparently uniquely ordered on the pathkeys.
+ */
+bool
+path_is_uniquely_ordered(Path *path, List *pathkeys)
+{
+ if (pathkeys && path->pathkeys &&
+ IsA(path, IndexPath) &&
+ ((IndexPath*)path)->indexinfo->unique &&
+ (pathkeys_contained_in(path->pathkeys, pathkeys)))
+ {
+ return true;
+ }
+
+ return false;
+}
+
+
+/*
+ * path_is_ordered
+ * Return true if the path is apparently ordered on the pathkeys. The given
+ * path might be modified so that it will be recognized later as sufficiently
+ * ordered.
+ */
+bool
+path_is_ordered(Path *path, List *pathkeys)
+{
+ if (pathkeys_contained_in(pathkeys, path->pathkeys))
+ return true;
+
+ /* path is obviously ordered when uniquely ordered */
+ if (path_is_uniquely_ordered(path, pathkeys))
+ return true;
+
+ /*
+ * MergeAppendPath's pathkeys can be replaced by arbitrary pathkeys when
+ * all subpaths are uniquely ordered on the target pathkeys.
+ */
+ if (IsA(path, MergeAppendPath))
+ {
+ ListCell *lc;
+ MergeAppendPath *mpath = (MergeAppendPath *)path;
+
+ foreach (lc, mpath->subpaths)
+ {
+ Path *subpath = (Path *) lfirst(lc);
+ if (!path_is_uniquely_ordered(subpath, pathkeys)) break;
+ }
+ if (!lc)
+ {
+ /*
+ * This MergeAppendPath is sufficiently ordered on the target
+ * pathkeys. Reflect that on this path.
+ */
+ mpath->path.pathkeys = pathkeys;
+ return true;
+ }
+ }
+ return false;
+}
+
+/* * get_cheapest_fractional_path_for_pathkeys * Find the cheapest path (for retrieving a specified fraction of
all* the tuples) that satisfies the given pathkeys and parameterization.
@@ -397,7 +459,7 @@ get_cheapest_fractional_path_for_pathkeys(List *paths,
compare_fractional_path_costs(matched_path,path, fraction) <= 0) continue;
- if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
+ if (path_is_ordered(path, pathkeys) && bms_is_subset(PATH_REQ_OUTER(path), required_outer))
matched_path = path; }
@@ -733,7 +795,7 @@ build_join_pathkeys(PlannerInfo *root, * contain pathkeys that were useful for forming this
joinrelbut are * uninteresting to higher levels. */
- return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
+ return truncate_useless_pathkeys(root, joinrel, outer_pathkeys,
false);}/****************************************************************************
@@ -1378,9 +1440,12 @@ right_merge_direction(PlannerInfo *root, PathKey *pathkey) * Unlike merge pathkeys, this is an
all-or-nothingaffair: it does us * no good to order by just the first key(s) of the requested ordering. * So the result
isalways either 0 or list_length(root->query_pathkeys).
+ * pk_uniq can be true when pathkeys are unique key itself. Tuples are
+ * sufficiently ordered when the pathkeys are the subset of the
+ * query_pathkeys for the case. */static int
-pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
+pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys, bool pk_uniq){ if (root->query_pathkeys == NIL)
return 0; /* no special ordering requested */
@@ -1394,23 +1459,34 @@ pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys) return
list_length(root->query_pathkeys); }
+ /*
+ * Given that the pathkeys compose an unique key, they are useful for
+ * ordering when they are a sublist of query_pathkeys.
+ */
+ if (pk_uniq && pathkeys_contained_in(pathkeys, root->query_pathkeys))
+ return list_length(pathkeys);
+ return 0; /* path ordering not useful */}/* * truncate_useless_pathkeys * Shorten the
givenpathkey list to just the useful pathkeys.
+ *
+ * When pathkeys_unique is true, reconsider counting the uniqueness even if
+ * the pathkeys are once judged as useless by the general criteria. */List *truncate_useless_pathkeys(PlannerInfo
*root, RelOptInfo *rel,
- List *pathkeys)
+ List *pathkeys,
+ bool pathkeys_unique){ int nuseful; int nuseful2; nuseful =
pathkeys_useful_for_merging(root,rel, pathkeys);
- nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
+ nuseful2 = pathkeys_useful_for_ordering(root, pathkeys, pathkeys_unique); if (nuseful2 > nuseful)
nuseful= nuseful2;
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 9b9eb2f..7b1490f 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -809,7 +809,7 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path)
numsortkeys* sizeof(bool)) == 0); /* Now, insert a Sort node if subplan isn't sufficiently ordered */
- if (!pathkeys_contained_in(pathkeys, subpath->pathkeys))
+ if (!path_is_ordered(subpath, pathkeys)) subplan = (Plan *) make_sort(root, subplan, numsortkeys,
sortColIdx, sortOperators, collations,
nullsFirst,
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 86abdf6..1ce04ac 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -258,6 +258,31 @@ standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams) return result;}
+/*
+ * Check if a path is sufficiently ordered on target pathkeys. This function
+ * is intended to be used as a replace for pathkeys_contained_in() when the
+ * focused path might be uniquely ordered on the current_pathkeys.
+ */
+static bool
+sort_needed(List *current_pathkeys, bool path_is_unique, List *target_pathkeys)
+{
+ /*
+ * If target pathkeys are a sublist of current pathkeys, the path is
+ * ordered also on target pathkeys
+ */
+ if (pathkeys_contained_in(target_pathkeys, current_pathkeys))
+ return false;
+
+ /*
+ * If a plan is uniquely ordered on current_pathkeys, it is sufficiently
+ * ordered on any pathkeys containing it.
+ */
+ if (path_is_unique && current_pathkeys &&
+ pathkeys_contained_in(current_pathkeys, target_pathkeys))
+ return false;
+
+ return true;
+}/*-------------------- * subquery_planner
@@ -1043,6 +1068,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) double dNumGroups = 0;
bool use_hashed_distinct = false; bool tested_hashed_distinct = false;
+ bool result_plan_is_unique = false; /* Tweak caller-supplied tuple_fraction if have LIMIT/OFFSET */
if(parse->limitCount || parse->limitOffset)
@@ -1451,18 +1477,24 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) result_plan =
create_plan(root,best_path); current_pathkeys = best_path->pathkeys;
+ result_plan_is_unique =
+ path_is_uniquely_ordered(best_path, root->query_pathkeys); /* Detect if we'll need an
explicitsort for grouping */
- if (parse->groupClause && !use_hashed_grouping &&
- !pathkeys_contained_in(root->group_pathkeys, current_pathkeys))
+ if (parse->groupClause && !use_hashed_grouping) {
- need_sort_for_grouping = true;
+ if (path_is_ordered(best_path, root->group_pathkeys))
+ current_pathkeys = root->group_pathkeys;
+ else
+ {
+ need_sort_for_grouping = true;
- /*
- * Always override create_plan's tlist, so that we don't sort
- * useless data from a "physical" tlist.
- */
- need_tlist_eval = true;
+ /*
+ * Always override create_plan's tlist, so that we don't
+ * sort useless data from a "physical" tlist.
+ */
+ need_tlist_eval = true;
+ } } /*
@@ -1575,6 +1607,9 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
extract_grouping_ops(parse->groupClause), numGroups,
result_plan);
+
+ /* Aggregation might break the tuple uniqueness. */
+ result_plan_is_unique = false; } else if (parse->groupClause) {
@@ -1603,7 +1638,11 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
extract_grouping_ops(parse->groupClause), dNumGroups,
result_plan);
- /* The Group node won't change sort ordering */
+ /*
+ * The Group node won't change sort ordering, however might
+ * break the uniqueness.
+ */
+ result_plan_is_unique = false; } else if (root->hasHavingQual) {
@@ -1713,8 +1752,9 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
result_plan, window_pathkeys,
-1.0);
- if (!pathkeys_contained_in(window_pathkeys,
- current_pathkeys))
+
+ if (sort_needed(current_pathkeys, result_plan_is_unique,
+ window_pathkeys)) { /* we do indeed need
tosort */ result_plan = (Plan *) sort_plan;
@@ -1770,6 +1810,8 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
wc->startOffset, wc->endOffset, result_plan);
+ /* Aggregation might break the tuple uniqueness. */
+ result_plan_is_unique = false; } } } /* end of if
(setOperations)*/
@@ -1855,8 +1897,9 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) needed_pathkeys =
root->sort_pathkeys; else needed_pathkeys = root->distinct_pathkeys;
-
- if (!pathkeys_contained_in(needed_pathkeys, current_pathkeys))
+
+ if (sort_needed(current_pathkeys, result_plan_is_unique,
+ needed_pathkeys)) { if (list_length(root->distinct_pathkeys) >=
list_length(root->sort_pathkeys))
@@ -1875,8 +1918,9 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
-1.0); }
- result_plan = (Plan *) make_unique(result_plan,
- parse->distinctClause);
+ if (!result_plan_is_unique)
+ result_plan = (Plan *) make_unique(result_plan,
+ parse->distinctClause); result_plan->plan_rows =
dNumDistinctRows; /* The Unique node won't change sort ordering */ }
@@ -1888,7 +1932,8 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) */ if (parse->sortClause) {
- if (!pathkeys_contained_in(root->sort_pathkeys, current_pathkeys))
+ if (sort_needed(current_pathkeys, result_plan_is_unique,
+ root->sort_pathkeys)) { result_plan = (Plan *) make_sort_from_pathkeys(root,
result_plan,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 9ef93c7..8e6d0e7 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -156,6 +156,8 @@ typedef enumextern PathKeysComparison compare_pathkeys(List *keys1, List *keys2);extern bool
pathkeys_contained_in(List*keys1, List *keys2);
+extern bool path_is_ordered(Path *path, List *pathkeys);
+extern bool path_is_uniquely_ordered(Path *path, List *pathkeys);extern Path *get_cheapest_path_for_pathkeys(List
*paths,List *pathkeys, Relids required_outer, CostSelector
cost_criterion);
@@ -190,7 +192,8 @@ extern List *make_inner_pathkeys_for_merge(PlannerInfo *root, List
*outer_pathkeys);externList *truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel,
- List *pathkeys);
+ List *pathkeys,
+ bool pathkeys_unique);extern bool has_useful_pathkeys(PlannerInfo *root, RelOptInfo
*rel);#endif /* PATHS_H */
Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> writes:
> Unique indexes can sort the tuples in corresponding tables
> prefectly. So this query might can use index.
>> uniquetest=# create table t (a int, b int, c int, d text);
>> uniquetest=# create unique index i_t_pkey on t(a, b);
>> uniquetest=# insert into t
>> (select a % 10, a / 10, a, 't' from generate_series(0, 100000) a);
>> uniquetest=# analyze;
>>
>> uniquetest=# explain (costs off, analyze on) select distinct * from t;
ISTM the right way to deal with this is not what you've done here, but
just to deem the DISTINCT a no-op if there's a unique index on some subset
of the distinct-ed columns. This query is actually legally satisfied by
a simple seqscan, which would be faster than either of the plans you
mention. In any case, it seems like a bad idea to me to conflate
distinct-ness with ordering, so I don't like what you did to PathKeys.
Having said that, there is the kernel of a useful idea here, I think.
The reason you don't get an indexscan already is that the DISTINCT
assumes it needs to sort by (a,b,c,d), which an index on just (a,b)
doesn't appear to satisfy. However, if the index is unique, wouldn't
scanning the index produce data that actually satisfies the longer sort
key? It doesn't matter what the values of c,d are if there are no
duplicates in the a,b columns. So maybe as a separate patch, we could
look at claiming that a unique index satisfies the entire query_pathkeys
if it matches the first N columns of that.
regards, tom lane
On Thu, Oct 31, 2013 at 10:59 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote: > However, if the index is unique, wouldn't > scanning the index produce data that actually satisfies the longer sort > key? It doesn't matter what the values of c,d are if there are no > duplicates in the a,b columns. So maybe as a separate patch, we could > look at claiming that a unique index satisfies the entire query_pathkeys > if it matches the first N columns of that. That would be really spiffy. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
I wrote:
> Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> writes:
>> Unique indexes can sort the tuples in corresponding tables
>> prefectly. So this query might can use index.
BTW, how much of any of this is correct if the "unique" index contains
multiple NULL values? We might need to restrict the optimization(s)
to cases where the unique-ified columns are all marked NOT NULL.
regards, tom lane
On 10/31/13, 6:43 AM, Kyotaro HORIGUCHI wrote: > Hello, This is the last episode of the 'dance with indices'? > series. Your patch fails the isolation test because of changed query plans: http://pgci.eisentraut.org/jenkins/job/postgresql_commitfest_world/175/artifact/src/test/isolation/regression.diffs/*view*/
Thank you, > In any case, it seems like a bad idea to me to conflate > distinct-ness with ordering, so I don't like what you did to > PathKeys. Hmm, that sounds quite resonable in general. But the conflation is already found in grouping_planner to some extent. The name distinct_pathkey itself asserts that it is the ordering used for distinct. And actually is used for sorting if hashed-distinct is not selected. Plus, these modifications in grouping_planner is required by the patch for pathkeys.c to be effective. I suppose the main cause of nastiness of the patch for grouping_planner comes from the adheration of the usage of the variable for path uniqueness with the existent code. The additional members to Plan, say, pathkeys and ordered could help the code to look less ugly by taking in the related code currently appears nakedly in grouping_planner into make(or generate)_xxxxplan() functions. Although the new attributes somewhat look out of place.. > > However, if the index is unique, wouldn't > > scanning the index produce data that actually satisfies the longer sort > > key? It doesn't matter what the values of c,d are if there are no > > duplicates in the a,b columns. So maybe as a separate patch, we could > > look at claiming that a unique index satisfies the entire query_pathkeys > > if it matches the first N columns of that. > > That would be really spiffy. # Putting aside the trueness of the assumption for unique-index # and pathkeys. The "expanded" sufficiency check can be archieved by involving 'unique-indexed' attribute for pathkeys_contained_in(),say pathkeys_satisfies(pathkeys, pathkeys, is_uniq), but finally could have no effect without some extent of assist in the process in grouping_planner like my preveous patch to be in effect, I believe. I'll try to rewrite the path to be as following considering less conflating lookings in grouping_planner. - is_unique and pathkeys is added to the type Path. (umm...) - create function like pathkeys_satisfies(check_pathkeys, pathkeys, isuniq) or path_ordered_by(pathkeys, path) as needed. - Plan will be set ordered and pathkeys derived from source path and its process and grouping_planner consults it to deceide whether to do sort (to hide the currently naked code). - Add check for NULLuble columns :-) regards, -- Kyotaro Horiguchi NTT Open Source Software Center
Hello, > Your patch fails the isolation test because of changed query plans: > > http://pgci.eisentraut.org/jenkins/job/postgresql_commitfest_world/175/artifact/src/test/isolation/regression.diffs/*view*/ Thank you for pointing out. I wasn't aware of that.. # Because it is not launched from the top-level make check... I'll count that in next pach. -- Kyotaro Horiguchi NTT Open Source Software Center
Hello, this is the revised patch.
> Hmm, that sounds quite resonable in general. But the conflation
> is already found in grouping_planner to some extent.
Although this new patch is not split into unique-index sutff and
others, it removes current_pathkeys from grouping_planner, and
adds pathkeys and is_unique into struct Plan instead. This
eliminates independent and longstanding current_pathkeys variable
and calculus involving it from grouping_planner() so it would be
made clearer and easier to read, I expect.
> - is_unique and pathkeys is added to the type Path. (umm...)
>
> - create function like pathkeys_satisfies(check_pathkeys,
> pathkeys, isuniq) or path_ordered_by(pathkeys, path) as
> needed.
This was different from my thought. Finally I added
plan_is_ordered(plan, path) and some of make_<nodename>()
functions take pathkeys and/or uniquely_ordered as parameter and
some of others take them from given leftree plan. Plan nodes
propagate the attributes in autonomous way so explicit
current_pathkeys handling could be thrown away.
> - Plan will be set ordered and pathkeys derived from source path
> and its process and grouping_planner consults it to deceide
> whether to do sort (to hide the currently naked code).
>
> - Add check for NULLuble columns :-)
Now IndexOptInfo has new attribute full_ordered and it is set
true if the index does not cover any nullAble columns in
get_relation_info().
And expect file of isolation test is modified to fit the change
in result plan.
Finally, this version became to conflict with the another UNION
patch so I detached from it and rebased to current master.
regards,
--
Kyotaro Horiguchi
NTT Open Source Software Center
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 606734a..43be0a5 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -953,7 +953,8 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_pathkeys =
build_index_pathkeys(root,index, ForwardScanDirection);
useful_pathkeys= truncate_useless_pathkeys(root, rel,
- index_pathkeys);
+ index_pathkeys,
+ index->full_ordered); orderbyclauses = NIL;
orderbyclausecols= NIL; }
@@ -1015,7 +1016,8 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_pathkeys =
build_index_pathkeys(root,index, BackwardScanDirection);
useful_pathkeys= truncate_useless_pathkeys(root, rel,
- index_pathkeys);
+ index_pathkeys,
+ index->full_ordered); if (useful_pathkeys != NIL) {
ipath = create_index_path(root, index,
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 6724996..954d8a8 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -363,6 +363,68 @@ get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,}/*
+ * path_is_uniquely_ordered
+ * Return true if the path is apparently uniquely ordered on the pathkeys.
+ */
+bool
+path_is_uniquely_ordered(Path *path, List *pathkeys)
+{
+ if (pathkeys && path->pathkeys &&
+ IsA(path, IndexPath) &&
+ ((IndexPath*)path)->indexinfo->full_ordered &&
+ (pathkeys_contained_in(path->pathkeys, pathkeys)))
+ {
+ return true;
+ }
+
+ return false;
+}
+
+
+/*
+ * path_is_ordered
+ * Return true if the path is apparently ordered on the pathkeys. The given
+ * path might be modified so that it will be recognized later as sufficiently
+ * ordered.
+ */
+bool
+path_is_ordered(Path *path, List *pathkeys)
+{
+ if (pathkeys_contained_in(pathkeys, path->pathkeys))
+ return true;
+
+ /* path is obviously ordered when uniquely ordered */
+ if (path_is_uniquely_ordered(path, pathkeys))
+ return true;
+
+ /*
+ * MergeAppendPath's pathkeys can be replaced by arbitrary pathkeys when
+ * all subpaths are uniquely ordered on the target pathkeys.
+ */
+ if (IsA(path, MergeAppendPath))
+ {
+ ListCell *lc;
+ MergeAppendPath *mpath = (MergeAppendPath *)path;
+
+ foreach (lc, mpath->subpaths)
+ {
+ Path *subpath = (Path *) lfirst(lc);
+ if (!path_is_uniquely_ordered(subpath, pathkeys)) break;
+ }
+ if (!lc)
+ {
+ /*
+ * This MergeAppendPath is sufficiently ordered on the target
+ * pathkeys. Reflect that on this path.
+ */
+ mpath->path.pathkeys = pathkeys;
+ return true;
+ }
+ }
+ return false;
+}
+
+/* * get_cheapest_fractional_path_for_pathkeys * Find the cheapest path (for retrieving a specified fraction of
all* the tuples) that satisfies the given pathkeys and parameterization.
@@ -397,7 +459,7 @@ get_cheapest_fractional_path_for_pathkeys(List *paths,
compare_fractional_path_costs(matched_path,path, fraction) <= 0) continue;
- if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
+ if (path_is_ordered(path, pathkeys) && bms_is_subset(PATH_REQ_OUTER(path), required_outer))
matched_path = path; }
@@ -733,7 +795,7 @@ build_join_pathkeys(PlannerInfo *root, * contain pathkeys that were useful for forming this
joinrelbut are * uninteresting to higher levels. */
- return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
+ return truncate_useless_pathkeys(root, joinrel, outer_pathkeys,
false);}/****************************************************************************
@@ -1378,9 +1440,14 @@ right_merge_direction(PlannerInfo *root, PathKey *pathkey) * Unlike merge pathkeys, this is an
all-or-nothingaffair: it does us * no good to order by just the first key(s) of the requested ordering. * So the result
isalways either 0 or list_length(root->query_pathkeys).
+
+ * pk_full_ordered can be true when pathkeys are strictly unique key (which
+ * should not contain no NULLable column). Tuples are sufficiently ordered
+ * when the pathkeys are the subset of the query_pathkeys for the case. */static int
-pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
+pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys,
+ bool pk_full_ordered){ if (root->query_pathkeys == NIL) return 0;
/* no special ordering requested */
@@ -1394,23 +1461,35 @@ pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys) return
list_length(root->query_pathkeys); }
+ /*
+ * Given that the pathkeys compose an unique key, they are useful for
+ * ordering when they are a sublist of query_pathkeys.
+ */
+ if (pk_full_ordered &&
+ pathkeys_contained_in(pathkeys, root->query_pathkeys))
+ return list_length(pathkeys);
+ return 0; /* path ordering not useful */}/* * truncate_useless_pathkeys * Shorten the
givenpathkey list to just the useful pathkeys.
+ *
+ * When pk_full_ordered is true, reconsider counting the uniqueness even if
+ * the pathkeys are once judged as useless by the general criteria. */List *truncate_useless_pathkeys(PlannerInfo
*root, RelOptInfo *rel,
- List *pathkeys)
+ List *pathkeys,
+ bool pk_full_ordered){ int nuseful; int nuseful2; nuseful =
pathkeys_useful_for_merging(root,rel, pathkeys);
- nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
+ nuseful2 = pathkeys_useful_for_ordering(root, pathkeys, pk_full_ordered); if (nuseful2 > nuseful)
nuseful= nuseful2;
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 5947e5b..7755cbb 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -98,11 +98,13 @@ static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid);static IndexScan
*make_indexscan(List*qptlist, List *qpqual, Index scanrelid, Oid indexid, List *indexqual, List
*indexqualorig, List *indexorderby, List *indexorderbyorig,
+ List *pathkeys, bool uniquely_ordered, ScanDirection indexscandir);static IndexOnlyScan
*make_indexonlyscan(List*qptlist, List *qpqual, Index scanrelid, Oid indexid, List
*indexqual,List *indexorderby, List *indextlist,
+ List *pathkeys, bool uniquely_ordered, ScanDirection indexscandir);static
BitmapIndexScan*make_bitmap_indexscan(Index scanrelid, Oid indexid, List *indexqual,
@@ -150,10 +152,10 @@ static MergeJoin *make_mergejoin(List *tlist, bool *mergenullsfirst,
Plan*lefttree, Plan *righttree, JoinType jointype);
-static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
- AttrNumber *sortColIdx, Oid *sortOperators,
+static Sort *make_sort(PlannerInfo *root, Plan *lefttree, List *pathkeys,
+ int numCols, AttrNumber *sortColIdx, Oid *sortOperators, Oid *collations, bool *nullsFirst,
- double limit_tuples);
+ double limit_tuples);static Plan *prepare_sort_from_pathkeys(PlannerInfo *root,
Plan*lefttree, List *pathkeys, Relids relids,
@@ -750,6 +752,8 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path) plan->qual = NIL;
plan->lefttree= NULL; plan->righttree = NULL;
+ plan->pathkeys = pathkeys;
+ plan->is_unique = false; /* Compute sort column info, and adjust MergeAppend's tlist as needed */ (void)
prepare_sort_from_pathkeys(root,plan, pathkeys,
@@ -809,8 +813,8 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path)
numsortkeys* sizeof(bool)) == 0); /* Now, insert a Sort node if subplan isn't sufficiently ordered */
- if (!pathkeys_contained_in(pathkeys, subpath->pathkeys))
- subplan = (Plan *) make_sort(root, subplan, numsortkeys,
+ if (!path_is_ordered(subpath, pathkeys))
+ subplan = (Plan *) make_sort(root, subplan, pathkeys, numsortkeys,
sortColIdx,sortOperators, collations, nullsFirst,
best_path->limit_tuples);
@@ -1147,6 +1151,7 @@ create_indexscan_plan(PlannerInfo *root, List *fixed_indexquals; List
*fixed_indexorderbys; ListCell *l;
+ bool uniquely_ordered = false; /* it should be a base rel... */ Assert(baserelid > 0);
@@ -1254,6 +1259,9 @@ create_indexscan_plan(PlannerInfo *root, replace_nestloop_params(root, (Node *)
indexorderbys); }
+ uniquely_ordered =
+ path_is_uniquely_ordered((Path*)best_path, root->query_pathkeys);
+ /* Finally ready to build the plan node */ if (indexonly) scan_plan = (Scan *)
make_indexonlyscan(tlist,
@@ -1263,6 +1271,8 @@ create_indexscan_plan(PlannerInfo *root,
fixed_indexquals, fixed_indexorderbys,
best_path->indexinfo->indextlist,
+ best_path->path.pathkeys,
+ uniquely_ordered,
best_path->indexscandir); else scan_plan = (Scan *) make_indexscan(tlist,
@@ -1273,6 +1283,8 @@ create_indexscan_plan(PlannerInfo *root,
stripped_indexquals, fixed_indexorderbys,
indexorderbys,
+ best_path->path.pathkeys,
+ uniquely_ordered,
best_path->indexscandir); copy_path_costsize(&scan_plan->plan, &best_path->path);
@@ -3245,6 +3257,8 @@ make_indexscan(List *qptlist, List *indexqualorig, List
*indexorderby, List *indexorderbyorig,
+ List *pathkeys,
+ bool uniquely_ordered, ScanDirection indexscandir){ IndexScan *node =
makeNode(IndexScan);
@@ -3255,6 +3269,8 @@ make_indexscan(List *qptlist, plan->qual = qpqual; plan->lefttree = NULL;
plan->righttree= NULL;
+ plan->pathkeys = pathkeys;
+ plan->is_unique = uniquely_ordered; node->scan.scanrelid = scanrelid; node->indexid = indexid;
node->indexqual= indexqual;
@@ -3274,6 +3290,8 @@ make_indexonlyscan(List *qptlist, List *indexqual, List
*indexorderby, List *indextlist,
+ List *pathkeys,
+ bool uniquely_ordered, ScanDirection indexscandir){ IndexOnlyScan *node =
makeNode(IndexOnlyScan);
@@ -3284,6 +3302,8 @@ make_indexonlyscan(List *qptlist, plan->qual = qpqual; plan->lefttree = NULL;
plan->righttree= NULL;
+ plan->pathkeys = pathkeys;
+ plan->is_unique = uniquely_ordered; node->scan.scanrelid = scanrelid; node->indexid = indexid;
node->indexqual= indexqual;
@@ -3753,8 +3773,8 @@ make_mergejoin(List *tlist, * limit_tuples is as for cost_sort (in particular, pass -1 if no
limit)*/static Sort *
-make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
- AttrNumber *sortColIdx, Oid *sortOperators,
+make_sort(PlannerInfo *root, Plan *lefttree, List *pathkeys,
+ int numCols, AttrNumber *sortColIdx, Oid *sortOperators, Oid *collations, bool *nullsFirst,
double limit_tuples){
@@ -3776,6 +3796,8 @@ make_sort(PlannerInfo *root, Plan *lefttree, int numCols, plan->qual = NIL; plan->lefttree
=lefttree; plan->righttree = NULL;
+ plan->pathkeys = pathkeys;
+ plan->is_unique = false; node->numCols = numCols; node->sortColIdx = sortColIdx; node->sortOperators =
sortOperators;
@@ -4125,7 +4147,7 @@ make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
&nullsFirst); /* Now build the Sort node */
- return make_sort(root, lefttree, numsortkeys,
+ return make_sort(root, lefttree, pathkeys, numsortkeys, sortColIdx, sortOperators, collations,
nullsFirst, limit_tuples);}
@@ -4147,6 +4169,7 @@ make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree) Oid
*sortOperators; Oid *collations; bool *nullsFirst;
+ List *pathkeys; /* Convert list-ish representation to arrays wanted by executor */ numsortkeys =
list_length(sortcls);
@@ -4168,7 +4191,9 @@ make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree)
numsortkeys++; }
- return make_sort(root, lefttree, numsortkeys,
+ pathkeys = make_pathkeys_for_sortclauses(root, sortcls, sub_tlist);
+
+ return make_sort(root, lefttree, pathkeys, numsortkeys, sortColIdx, sortOperators, collations,
nullsFirst, -1.0);}
@@ -4199,6 +4224,7 @@ make_sort_from_groupcols(PlannerInfo *root, Oid *sortOperators; Oid
*collations; bool *nullsFirst;
+ List *pathkeys; /* Convert list-ish representation to arrays wanted by executor */ numsortkeys =
list_length(groupcls);
@@ -4220,10 +4246,17 @@ make_sort_from_groupcols(PlannerInfo *root, sortOperators[numsortkeys] = grpcl->sortop;
collations[numsortkeys] = exprCollation((Node *) tle->expr); nullsFirst[numsortkeys] = grpcl->nulls_first;
+
+ /* This tlist should not be bound with any other orderig clause */
+ Assert(tle->ressortgroupref == 0);
+ tle->ressortgroupref = grpcl->tleSortGroupRef;
+ numsortkeys++; }
- return make_sort(root, lefttree, numsortkeys,
+ pathkeys = make_pathkeys_for_sortclauses(root, groupcls, sub_tlist);
+
+ return make_sort(root, lefttree, pathkeys, numsortkeys, sortColIdx, sortOperators, collations,
nullsFirst, -1.0);}
@@ -4338,6 +4371,15 @@ make_agg(PlannerInfo *root, List *tlist, List *qual, plan->targetlist = tlist;
plan->lefttree= lefttree; plan->righttree = NULL;
+ /*
+ * We can safely assume that the lefttree and therefore the result is
+ * sorted on group pathkeys and unique if given aggstrategy is AGG_SORTED.
+ */
+ if (node->aggstrategy == AGG_SORTED)
+ plan->pathkeys = root->group_pathkeys;
+ else
+ plan->pathkeys = NIL;
+ plan->is_unique = true; return node;}
@@ -4447,6 +4489,12 @@ make_group(PlannerInfo *root, plan->targetlist = tlist; plan->lefttree = lefttree;
plan->righttree= NULL;
+ /*
+ * We assume that lefttree is ordered on the same pathkeys with that this
+ * group node wants.
+ */
+ plan->pathkeys = lefttree->pathkeys;
+ plan->is_unique = true; return node;}
@@ -4486,6 +4534,8 @@ make_unique(Plan *lefttree, List *distinctList) plan->qual = NIL; plan->lefttree =
lefttree; plan->righttree = NULL;
+ plan->pathkeys = lefttree->pathkeys;
+ plan->is_unique = true; /* * convert SortGroupClause list into arrays of attr indexes and equality
@@ -4717,6 +4767,10 @@ make_result(PlannerInfo *root, plan->qual = NIL; plan->lefttree = subplan;
plan->righttree= NULL;
+
+ /* this plan emits zero or one row when subplan is NULL */
+ if (subplan == NULL) plan->is_unique = true;
+ node->resconstantqual = resconstantqual; return node;
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index d8aa35d..c80556e 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -1011,6 +1011,19 @@ inheritance_planner(PlannerInfo *root)
SS_assign_special_param(root));}
+static bool
+plan_is_ordered(Plan *plan, List *pathkeys)
+{
+ if (pathkeys_contained_in(pathkeys, plan->pathkeys))
+ return true;
+
+ if (plan->pathkeys && plan->is_unique &&
+ pathkeys_contained_in(plan->pathkeys, pathkeys))
+ return true;
+
+ return false;
+}
+/*-------------------- * grouping_planner * Perform planning steps related to grouping, aggregation, etc.
@@ -1039,7 +1052,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) int64 count_est = 0;
double limit_tuples = -1.0; Plan *result_plan;
- List *current_pathkeys; double dNumGroups = 0; bool use_hashed_distinct = false; bool
tested_hashed_distinct = false;
@@ -1081,15 +1093,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
&set_sortclauses); /*
- * Calculate pathkeys representing the sort order (if any) of the set
- * operation's result. We have to do this before overwriting the sort
- * key information...
- */
- current_pathkeys = make_pathkeys_for_sortclauses(root,
- set_sortclauses,
- result_plan->targetlist);
-
- /* * We should not need to call preprocess_targetlist, since we must be * in a SELECT query
node. Instead, use the targetlist returned by * plan_set_operations (since this tells whether it returned
any
@@ -1442,15 +1445,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
tlist, &agg_costs,
best_path);
- if (result_plan != NULL)
- {
- /*
- * optimize_minmax_aggregates generated the full plan, with the
- * right tlist, and it has no sort order.
- */
- current_pathkeys = NIL;
- }
- else
+ if (result_plan == NULL) { /* * Normal case --- create a plan according to
query_planner's
@@ -1459,11 +1454,10 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) bool
need_sort_for_grouping= false; result_plan = create_plan(root, best_path);
- current_pathkeys = best_path->pathkeys; /* Detect if we'll need an explicit sort for grouping
*/ if (parse->groupClause && !use_hashed_grouping &&
- !pathkeys_contained_in(root->group_pathkeys, current_pathkeys))
+ !plan_is_ordered(result_plan, root->group_pathkeys)) {
need_sort_for_grouping= true;
@@ -1541,37 +1535,21 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
extract_grouping_ops(parse->groupClause), numGroups,
result_plan);
- /* Hashed aggregation produces randomly-ordered results */
- current_pathkeys = NIL; } else if (parse->hasAggs) {
/*Plain aggregate plan --- sort if needed */ AggStrategy aggstrategy;
- if (parse->groupClause)
- {
- if (need_sort_for_grouping)
- {
- result_plan = (Plan *)
- make_sort_from_groupcols(root,
- parse->groupClause,
- groupColIdx,
- result_plan);
- current_pathkeys = root->group_pathkeys;
- }
- aggstrategy = AGG_SORTED;
+ aggstrategy = parse->groupClause ? AGG_SORTED : AGG_PLAIN;
- /*
- * The AGG node will not change the sort ordering of its
- * groups, so current_pathkeys describes the result too.
- */
- }
- else
+ if (aggstrategy == AGG_SORTED && need_sort_for_grouping) {
- aggstrategy = AGG_PLAIN;
- /* Result will be only one row anyway; no sort order */
- current_pathkeys = NIL;
+ result_plan = (Plan *)
+ make_sort_from_groupcols(root,
+ parse->groupClause,
+ groupColIdx,
+ result_plan); } result_plan = (Plan *)
make_agg(root,
@@ -1601,7 +1579,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
parse->groupClause, groupColIdx,
result_plan);
- current_pathkeys = root->group_pathkeys; } result_plan = (Plan *)
make_group(root,
@@ -1612,7 +1589,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
extract_grouping_ops(parse->groupClause), dNumGroups,
result_plan);
- /* The Group node won't change sort ordering */ } else if (root->hasHavingQual)
{
@@ -1722,13 +1698,14 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
result_plan, window_pathkeys,
-1.0);
- if (!pathkeys_contained_in(window_pathkeys,
- current_pathkeys))
- {
- /* we do indeed need to sort */
+
+ /*
+ * we do indeed need to sort if result_plan is not ordered
+ * on window_pathkeys
+ */
+ if (!plan_is_ordered(result_plan, window_pathkeys)) result_plan = (Plan *)
sort_plan;
- current_pathkeys = window_pathkeys;
- }
+ /* In either case, extract the per-column information */
get_column_info_for_window(root,wc, tlist, sort_plan->numCols,
@@ -1792,12 +1769,12 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) long numDistinctRows;
/*
- * If there was grouping or aggregation, use the current number of
- * rows as the estimated number of DISTINCT rows (ie, assume the
- * result was already mostly unique). If not, use the number of
+ * If result_plan emits already distinct'ed rows, use the current
+ * number of rows as the estimated number of DISTINCT rows (ie, assume
+ * the result was already mostly unique). If not, use the number of * distinct-groups calculated
previously. */
- if (parse->groupClause || root->hasHavingQual || parse->hasAggs)
+ if (result_plan->is_unique) dNumDistinctRows = result_plan->plan_rows; else
dNumDistinctRows= dNumGroups;
@@ -1822,7 +1799,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
result_plan->total_cost, result_plan->startup_cost,
result_plan->total_cost,
- current_pathkeys,
+ result_plan->pathkeys, dNumDistinctRows);
}
@@ -1840,8 +1817,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
extract_grouping_ops(parse->distinctClause), numDistinctRows,
result_plan);
- /* Hashed aggregation produces randomly-ordered results */
- current_pathkeys = NIL; } else {
@@ -1864,28 +1839,23 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) needed_pathkeys =
root->sort_pathkeys; else needed_pathkeys = root->distinct_pathkeys;
-
- if (!pathkeys_contained_in(needed_pathkeys, current_pathkeys))
+
+ if (!plan_is_ordered(result_plan, needed_pathkeys)) {
- if (list_length(root->distinct_pathkeys) >=
- list_length(root->sort_pathkeys))
- current_pathkeys = root->distinct_pathkeys;
- else
- {
- current_pathkeys = root->sort_pathkeys;
- /* Assert checks that parser didn't mess up... */
- Assert(pathkeys_contained_in(root->distinct_pathkeys,
- current_pathkeys));
- }
-
+ /* Assert checks that parser didn't mess up... */
+ Assert(pathkeys_contained_in(root->distinct_pathkeys,
+ needed_pathkeys));
+ Assert(pathkeys_contained_in(root->sort_pathkeys,
+ needed_pathkeys)); result_plan = (Plan *)
make_sort_from_pathkeys(root, result_plan,
- current_pathkeys,
+ needed_pathkeys,
-1.0); }
- result_plan = (Plan *) make_unique(result_plan,
- parse->distinctClause);
+ if (!result_plan->is_unique)
+ result_plan = (Plan *) make_unique(result_plan,
+ parse->distinctClause); result_plan->plan_rows =
dNumDistinctRows; /* The Unique node won't change sort ordering */ }
@@ -1897,13 +1867,12 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) */ if (parse->sortClause)
{
- if (!pathkeys_contained_in(root->sort_pathkeys, current_pathkeys))
+ if (!plan_is_ordered(result_plan, root->sort_pathkeys)) { result_plan = (Plan *)
make_sort_from_pathkeys(root, result_plan,
root->sort_pathkeys,
limit_tuples);
- current_pathkeys = root->sort_pathkeys; } }
@@ -1919,11 +1888,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
root->rowMarks, SS_assign_special_param(root));
- /*
- * The result can no longer be assumed sorted, since locking might
- * cause the sort key columns to be replaced with new values.
- */
- current_pathkeys = NIL; } /*
@@ -1942,7 +1906,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) * Return the actual output
orderingin query_pathkeys for possible use by * an outer query level. */
- root->query_pathkeys = current_pathkeys;
+ root->query_pathkeys = result_plan->pathkeys; return result_plan;}
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 954666c..d81f9e3 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -231,6 +231,7 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent, */
if (info->relam == BTREE_AM_OID) {
+ bool has_nullable_keycol = false; /* * If it's a btree index, we can
useits opfamily OIDs * directly as the sort ordering opfamily OIDs.
@@ -244,10 +245,25 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent, for (i
=0; i < ncolumns; i++) { int16 opt = indexRelation->rd_indoption[i];
+ int16 keyattno = index->indkey.values[i]; info->reverse_sort[i] = (opt &
INDOPTION_DESC)!= 0; info->nulls_first[i] = (opt & INDOPTION_NULLS_FIRST) != 0;
+
+ if (keyattno > 0)
+ {
+ has_nullable_keycol |=
+ !relation->rd_att->attrs[keyattno - 1]->attnotnull;
+ }
+ else if (keyattno != ObjectIdAttributeNumber)
+ has_nullable_keycol = true; }
+
+ /* Check to see if it is a full-ordered index */
+ if (IndexIsValid(index) &&
+ index->indisunique && index->indimmediate &&
+ !has_nullable_keycol)
+ info->full_ordered = true; } else if (indexRelation->rd_am->amcanorder)
{
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index 44ea0b7..6f0935c 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -101,7 +101,8 @@ typedef struct Plan */ double plan_rows; /* number of rows plan is expected to
emit*/ int plan_width; /* average row width in bytes */
-
+ List *pathkeys; /* ordered on this pathkeys if any */
+ bool is_unique; /* emits unique result */ /* * Common structural data for all Plan types.
*/
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index a2853fb..e09d75a 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -515,6 +515,7 @@ typedef struct IndexOptInfo bool predOK; /* true if predicate matches query */
bool unique; /* true if a unique index */ bool immediate; /* is uniqueness
enforcedimmediately? */
+ bool full_ordered; /* is fully-ordered? */ bool hypothetical; /* true if index doesn't
reallyexist */ bool canreturn; /* can index return IndexTuples? */ bool amcanorderbyop; /*
doesAM support order by operator result? */
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 9ef93c7..9a6c8e0 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -156,6 +156,8 @@ typedef enumextern PathKeysComparison compare_pathkeys(List *keys1, List *keys2);extern bool
pathkeys_contained_in(List*keys1, List *keys2);
+extern bool path_is_ordered(Path *path, List *pathkeys);
+extern bool path_is_uniquely_ordered(Path *path, List *pathkeys);extern Path *get_cheapest_path_for_pathkeys(List
*paths,List *pathkeys, Relids required_outer, CostSelector
cost_criterion);
@@ -190,7 +192,8 @@ extern List *make_inner_pathkeys_for_merge(PlannerInfo *root, List
*outer_pathkeys);externList *truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel,
- List *pathkeys);
+ List *pathkeys,
+ bool pk_full_ordered);extern bool has_useful_pathkeys(PlannerInfo *root, RelOptInfo
*rel);#endif /* PATHS_H */
diff --git a/src/test/isolation/expected/drop-index-concurrently-1.out
b/src/test/isolation/expected/drop-index-concurrently-1.out
index 75dff56..ab96fa0 100644
--- a/src/test/isolation/expected/drop-index-concurrently-1.out
+++ b/src/test/isolation/expected/drop-index-concurrently-1.out
@@ -19,10 +19,8 @@ Sortstep explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seq;QUERY PLAN
-Sort
- Sort Key: id, data
- -> Seq Scan on test_dc
- Filter: ((data)::text = '34'::text)
+Index Scan using test_dc_pkey on test_dc
+ Filter: ((data)::text = '34'::text)step select2: SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;id
data
On Tue, 2013-11-12 at 17:48 +0900, Kyotaro HORIGUCHI wrote: > Hello, this is the revised patch. Since you're using git, please check your patch for trailing whitespace with git diff --check.
Hello, I might made insufficient explanation. Surely it is overdone for the example. >> uniquetest=# create table t (a int, b int, c int, d text); >> uniquetest=# create unique index i_t_pkey on t(a, b); >> uniquetest=# insert into t >> (select a % 10, a / 10, a, 't' from generate_series(0, 100000) a); >> uniquetest=# analyze; >> >> uniquetest=# explain (costs off, analyze on) select distinct * from t; This is the simplest example for this patch. The main intention of this patch is to widen application of my another 'Index for UNION' patch. https://commitfest.postgresql.org/action/patch_view?id=1279 > ISTM the right way to deal with this is not what you've done > here, but just to deem the DISTINCT a no-op if there's a unique > index on some subset of the distinct-ed columns. It is not sufficient only to deem DISTINCT no-op in order to get more utility of MergeAppends on IndexScans for UNION. The following example (omitting data insertion..) | create table cu11 (a int not null, b int not null, c int, d text); | create unique index i_cu11_pk on cu11 (a, b); | create table cu12 (like cu11 including all); | explain select a, b from cu11 union select a, b from cu12 | order by a, b limit 100; yields following plan without this patch. | Limit | -> Sort (Sort Key: cu11.a, cu11.b) | -> HashAggregate | -> Append | -> Limit | -> Unique | -> Index Only Scan using cu11_a_b_idx on cu11 | -> Limit | -> Unique | -> Index Only Scan using cu12_a_b_idx on cu12 But, this could be far more effecient when the plan were as follows if the rows are fully-ordered on the sort key. | Limit | -> Unique | -> Merge Append (Sort Key: cu11.a, cu11.b) | -> Index Only Scan using cu11_a_b_idx on cu11 | -> Index Only Scan using cu12_a_b_idx on cu12 Propagation of uniqueness on MergeAppend is required to do this but not for the first expample on this thread. > This query is actually legally satisfied by a simple seqscan, > which would be faster than either of the plans you mention. In > any case, it seems like a bad idea to me to conflate > distinct-ness with ordering, so I don't like what you did to > PathKeys. Umm. Reconsidering on that and the discussion of the purose above and the last patch of this thread, I've been wrong in where to split the patches. I'll repost the reorganized patches on both threads. regards, -- Kyotaro Horiguchi NTT Open Source Software Center
Hello, I've totally refactored the series of patches and cut out
the appropriate portion as 'unique (and non-nullable) index
stuff'.
As the discussion before, it got rid of path distinctness. This
patch works only on index 'full-orederedness', i.e., unique index
on non-nullable columns.
This patch itself does not so much. Will have power applied with
'Using indices for UNION' patch.
=== Making test table
create table t (a int not null, b int not null, c int, d text);
create unique index i_t_ab on t (a, b);
insert into t (select a / 5, 4 - (a % 5), a, 't' from generate_series(000000, 099999) a);
=== Example 1.
not-patched=# explain select * from t order by a, b ,c limit 1;
> QUERY PLAN
> ----------------------------------------------------------------------
> Limit (cost=2041.00..2041.00 rows=1 width=14)
> -> Sort (cost=2041.00..2291.00 rows=100000 width=14)
> Sort Key: a, b, c
> -> Seq Scan on t (cost=0.00..1541.00 rows=100000 width=14)
patched=# explain select * from t order by a, b ,c limit 1;
> QUERY PLAN
> -----------------------------------------------------------------------------
> Limit (cost=0.29..0.33 rows=1 width=14)
> -> Index Scan using i_t_ab on t (cost=0.29..3857.04 rows=100000 width=14)
=== Example 2.
not-patched=# explain select distinct * from t order by a limit 1;
> QUERY PLAN
> ---------------------------------------------------------------------------
> Limit (cost=1820.46..1820.47 rows=1 width=44)
> -> Sort (cost=1820.46..1835.34 rows=5951 width=44)
> Sort Key: a
> -> HashAggregate (cost=1731.20..1790.71 rows=5951 width=44)
> -> Seq Scan on t (cost=0.00..1136.10 rows=59510 width=44)
patched=# explain select distinct * from t order by a limit 1;
> QUERY PLAN
> ------------------------------------------------------------------------------------
> Limit (cost=0.29..1.09 rows=1 width=44)
> -> Unique (cost=0.29..4756.04 rows=5951 width=44)
> -> Index Scan using i_t_ab on t (cost=0.29..4160.94 rows=59510 width=44)
The unique node could be removed technically but it requires to
care the distinctness of path/plan. So it has been put out to
"Using indeces for UNION" patch.
Any comments?
regards,
--
Kyotaro Horiguchi
NTT Open Source Software Center
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 606734a..43be0a5 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -953,7 +953,8 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_pathkeys =
build_index_pathkeys(root,index, ForwardScanDirection);
useful_pathkeys= truncate_useless_pathkeys(root, rel,
- index_pathkeys);
+ index_pathkeys,
+ index->full_ordered); orderbyclauses = NIL;
orderbyclausecols= NIL; }
@@ -1015,7 +1016,8 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_pathkeys =
build_index_pathkeys(root,index, BackwardScanDirection);
useful_pathkeys= truncate_useless_pathkeys(root, rel,
- index_pathkeys);
+ index_pathkeys,
+ index->full_ordered); if (useful_pathkeys != NIL) {
ipath = create_index_path(root, index,
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 032b2cd..5d8ee04 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -369,6 +369,29 @@ get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,}/*
+ * path_is_ordered
+ * Return true if the path is apparently ordered on the pathkeys.
+ */
+bool
+path_is_ordered(Path *path, List *pathkeys)
+{
+ if (pathkeys_contained_in(pathkeys, path->pathkeys))
+ return true;
+
+ /*
+ * If IndexPath is fully ordered, it is sufficiently ordered if index
+ * pathkeys is a subset of target pathkeys
+ */
+ if (pathkeys && path->pathkeys &&
+ IsA(path, IndexPath) &&
+ ((IndexPath*)path)->indexinfo->full_ordered &&
+ (pathkeys_contained_in(path->pathkeys, pathkeys)))
+ return true;
+
+ return false;
+}
+
+/* * get_cheapest_fractional_path_for_pathkeys * Find the cheapest path (for retrieving a specified fraction of
all* the tuples) that satisfies the given pathkeys and parameterization.
@@ -381,6 +404,8 @@ get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, * 'pathkeys' represents a required
ordering(in canonical form!) * 'required_outer' denotes allowable outer relations for parameterized paths * 'fraction'
isthe fraction of the total tuples expected to be retrieved
+ * paths->pathkeys might be replaced with pathkeys so as to declare that the
+ * path is ordered on it. */Path *get_cheapest_fractional_path_for_pathkeys(List *paths,
@@ -403,9 +428,17 @@ get_cheapest_fractional_path_for_pathkeys(List *paths,
compare_fractional_path_costs(matched_path,path, fraction) <= 0) continue;
- if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
+ if (path_is_ordered(path, pathkeys) && bms_is_subset(PATH_REQ_OUTER(path), required_outer))
+ {
+ /*
+ * Set required pathkeys as the path's pathkeys so as to declare
+ * that this path is ordred on the pathkeys.
+ */
+ if (list_length(path->pathkeys) < list_length(pathkeys))
+ path->pathkeys = pathkeys; matched_path = path;
+ } } return matched_path;}
@@ -747,7 +780,7 @@ build_join_pathkeys(PlannerInfo *root, * contain pathkeys that were useful for forming this
joinrelbut are * uninteresting to higher levels. */
- return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
+ return truncate_useless_pathkeys(root, joinrel, outer_pathkeys,
false);}/****************************************************************************
@@ -1404,7 +1437,8 @@ right_merge_direction(PlannerInfo *root, PathKey *pathkey) * So the result is always either 0 or
list_length(root->query_pathkeys).*/static int
-pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
+pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys,
+ bool pk_full_ordered){ if (root->query_pathkeys == NIL) return 0;
/* no special ordering requested */
@@ -1418,23 +1452,35 @@ pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys) return
list_length(root->query_pathkeys); }
+ /*
+ * Given that the pathkeys compose an unique key, they are useful for
+ * ordering when they are a sublist of query_pathkeys.
+ */
+ if (pk_full_ordered &&
+ pathkeys_contained_in(pathkeys, root->query_pathkeys))
+ return list_length(pathkeys);
+ return 0; /* path ordering not useful */}/* * truncate_useless_pathkeys * Shorten the
givenpathkey list to just the useful pathkeys.
+ *
+ * When pk_full_ordered is true, reconsider counting the uniqueness even if
+ * the pathkeys are once judged as useless by the general criteria. */List *truncate_useless_pathkeys(PlannerInfo
*root, RelOptInfo *rel,
- List *pathkeys)
+ List *pathkeys,
+ bool pk_full_ordered){ int nuseful; int nuseful2; nuseful =
pathkeys_useful_for_merging(root,rel, pathkeys);
- nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
+ nuseful2 = pathkeys_useful_for_ordering(root, pathkeys, pk_full_ordered); if (nuseful2 > nuseful)
nuseful= nuseful2;
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 954666c..ee92545 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -231,6 +231,8 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent, */
if (info->relam == BTREE_AM_OID) {
+ bool has_nullable_keycol = false;
+ /* * If it's a btree index, we can use its opfamily OIDs * directly as
thesort ordering opfamily OIDs.
@@ -244,10 +246,25 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent, for (i
=0; i < ncolumns; i++) { int16 opt = indexRelation->rd_indoption[i];
+ int16 keyattno = index->indkey.values[i]; info->reverse_sort[i] = (opt &
INDOPTION_DESC)!= 0; info->nulls_first[i] = (opt & INDOPTION_NULLS_FIRST) != 0;
- }
+
+ if (keyattno > 0)
+ {
+ has_nullable_keycol |=
+ !relation->rd_att->attrs[keyattno - 1]->attnotnull;
+ }
+ else if (keyattno != ObjectIdAttributeNumber)
+ has_nullable_keycol = true;
+ }
+
+ /* Check to see if it is a full-ordered index */
+ if (IndexIsValid(index) &&
+ index->indisunique && index->indimmediate &&
+ !has_nullable_keycol)
+ info->full_ordered = true; } else if (indexRelation->rd_am->amcanorder)
{
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 6d7b594..b38c667 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -524,6 +524,7 @@ typedef struct IndexOptInfo bool predOK; /* true if predicate matches query */
bool unique; /* true if a unique index */ bool immediate; /* is uniqueness
enforcedimmediately? */
+ bool full_ordered; /* is ordered rows not duplicate ? */ bool hypothetical; /* true if
indexdoesn't really exist */ bool canreturn; /* can index return IndexTuples? */ bool
amcanorderbyop;/* does AM support order by operator result? */
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 96ffdb1..9e53b42 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -160,6 +160,7 @@ extern bool pathkeys_contained_in(List *keys1, List *keys2);extern Path
*get_cheapest_path_for_pathkeys(List*paths, List *pathkeys, Relids required_outer,
CostSelector cost_criterion);
+extern bool path_is_ordered(Path *path, List *pathkeys);extern Path *get_cheapest_fractional_path_for_pathkeys(List
*paths, List *pathkeys, Relids
required_outer,
@@ -191,7 +192,8 @@ extern List *make_inner_pathkeys_for_merge(PlannerInfo *root, List
*outer_pathkeys);externList *truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel,
- List *pathkeys);
+ List *pathkeys,
+ bool pk_full_ordered);extern bool has_useful_pathkeys(PlannerInfo *root, RelOptInfo
*rel);#endif /* PATHS_H */
diff --git a/src/test/isolation/expected/drop-index-concurrently-1.out
b/src/test/isolation/expected/drop-index-concurrently-1.out
index 75dff56..ab96fa0 100644
--- a/src/test/isolation/expected/drop-index-concurrently-1.out
+++ b/src/test/isolation/expected/drop-index-concurrently-1.out
@@ -19,10 +19,8 @@ Sortstep explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seq;QUERY PLAN
-Sort
- Sort Key: id, data
- -> Seq Scan on test_dc
- Filter: ((data)::text = '34'::text)
+Index Scan using test_dc_pkey on test_dc
+ Filter: ((data)::text = '34'::text)step select2: SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;id
data
Kyotaro HORIGUCHI wrote: > Hello, I've totally refactored the series of patches and cut out the appropriate portion as 'unique (and non-nullable) index stuff'. > As the discussion before, it got rid of path distinctness. This patch works only on index 'full-orederedness', i.e., unique index on non-nullable columns. This is interesting! I took a quick look at the patch. Here is my initial comment. I don't think it's so good to set the pathkeys of a unique-index path to query_pathkeys after the scan/join optimization because it can't exploit the full-orderedness property in implementing mergejoins, i.e., it can't skip doing an explicit sort that is considered unnecessary from the property. So, I think the path's pathkeys should be set to query_pathkeys before the scan/join optimization, i.e., at the index-path creation time. If you wouldn't mind, I'd like to rework on the patch. Thanks, Best regards, Etsuro Fujita
Hello. I found a bug(?) in thsi patch as I considered on another
patch.
In truncate_useless_pathkeys, if query_pathkeys is longer than
pathkeys made from index columns old patch picked up the latter
as IndexPath's pathkeys. But the former is more suitable
according to the context here.
the attched pathkey_and_uniqueindx_v4_20131122.patch is changed
as follows.
- Rebased to current master.
- truncate_useless_pathkeys returns root->query_pathkeys when the index is fully-ordered and query_pathkeys contains
the pathkeys made from index columns.
regards,
--
Kyotaro Horiguchi
NTT Open Source Software Center
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 606734a..43be0a5 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -953,7 +953,8 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_pathkeys =
build_index_pathkeys(root,index, ForwardScanDirection);
useful_pathkeys= truncate_useless_pathkeys(root, rel,
- index_pathkeys);
+ index_pathkeys,
+ index->full_ordered); orderbyclauses = NIL;
orderbyclausecols= NIL; }
@@ -1015,7 +1016,8 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_pathkeys =
build_index_pathkeys(root,index, BackwardScanDirection);
useful_pathkeys= truncate_useless_pathkeys(root, rel,
- index_pathkeys);
+ index_pathkeys,
+ index->full_ordered); if (useful_pathkeys != NIL) {
ipath = create_index_path(root, index,
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 9c8ede6..fd104b2 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -369,6 +369,29 @@ get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,}/*
+ * path_is_ordered
+ * Return true if the path is apparently ordered on the pathkeys.
+ */
+bool
+path_is_ordered(Path *path, List *pathkeys)
+{
+ if (pathkeys_contained_in(pathkeys, path->pathkeys))
+ return true;
+
+ /*
+ * If IndexPath is fully ordered, it is sufficiently ordered if index
+ * pathkeys is a subset of target pathkeys
+ */
+ if (pathkeys && path->pathkeys &&
+ IsA(path, IndexPath) &&
+ ((IndexPath*)path)->indexinfo->full_ordered &&
+ (pathkeys_contained_in(path->pathkeys, pathkeys)))
+ return true;
+
+ return false;
+}
+
+/* * get_cheapest_fractional_path_for_pathkeys * Find the cheapest path (for retrieving a specified fraction of
all* the tuples) that satisfies the given pathkeys and parameterization.
@@ -381,6 +404,8 @@ get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, * 'pathkeys' represents a required
ordering(in canonical form!) * 'required_outer' denotes allowable outer relations for parameterized paths * 'fraction'
isthe fraction of the total tuples expected to be retrieved
+ * paths->pathkeys might be replaced with pathkeys so as to declare that the
+ * path is ordered on it. */Path *get_cheapest_fractional_path_for_pathkeys(List *paths,
@@ -403,9 +428,17 @@ get_cheapest_fractional_path_for_pathkeys(List *paths,
compare_fractional_path_costs(matched_path,path, fraction) <= 0) continue;
- if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
+ if (path_is_ordered(path, pathkeys) && bms_is_subset(PATH_REQ_OUTER(path), required_outer))
+ {
+ /*
+ * Set required pathkeys as the path's pathkeys so as to declare
+ * that this path is ordred on the pathkeys.
+ */
+ if (length(path->pathkeys) < length(pathkeys))
+ path->pathkeys = pathkeys; matched_path = path;
+ } } return matched_path;}
@@ -798,7 +831,7 @@ build_join_pathkeys(PlannerInfo *root, * contain pathkeys that were useful for forming this
joinrelbut are * uninteresting to higher levels. */
- return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
+ return truncate_useless_pathkeys(root, joinrel, outer_pathkeys,
false);}/****************************************************************************
@@ -1455,7 +1488,8 @@ right_merge_direction(PlannerInfo *root, PathKey *pathkey) * So the result is always either 0 or
list_length(root->query_pathkeys).*/static int
-pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
+pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys,
+ bool pk_full_ordered){ if (root->query_pathkeys == NIL) return 0;
/* no special ordering requested */
@@ -1469,23 +1503,36 @@ pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys) return
list_length(root->query_pathkeys); }
+ /*
+ * Given that the pathkeys compose an unique key, they are useful for
+ * ordering when they are a sublist of query_pathkeys. Expand pathkeys to
+ * root->query_pathkeys in this case.
+ */
+ if (pk_full_ordered &&
+ pathkeys_contained_in(pathkeys, root->query_pathkeys))
+ return list_length(root->query_pathkeys);
+ return 0; /* path ordering not useful */}/* * truncate_useless_pathkeys * Shorten the
givenpathkey list to just the useful pathkeys.
+ *
+ * When pk_full_ordered is true, reconsider counting the uniqueness even if
+ * the pathkeys are once judged as useless by the general criteria. */List *truncate_useless_pathkeys(PlannerInfo
*root, RelOptInfo *rel,
- List *pathkeys)
+ List *pathkeys,
+ bool pk_full_ordered){ int nuseful; int nuseful2; nuseful =
pathkeys_useful_for_merging(root,rel, pathkeys);
- nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
+ nuseful2 = pathkeys_useful_for_ordering(root, pathkeys, pk_full_ordered); if (nuseful2 > nuseful)
nuseful= nuseful2;
@@ -1498,7 +1545,7 @@ truncate_useless_pathkeys(PlannerInfo *root, else if (nuseful == list_length(pathkeys))
returnpathkeys; else
- return list_truncate(list_copy(pathkeys), nuseful);
+ return list_truncate(list_copy(root->query_pathkeys), nuseful);}/*
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 954666c..ee92545 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -231,6 +231,8 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent, */
if (info->relam == BTREE_AM_OID) {
+ bool has_nullable_keycol = false;
+ /* * If it's a btree index, we can use its opfamily OIDs * directly as
thesort ordering opfamily OIDs.
@@ -244,10 +246,25 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent, for (i
=0; i < ncolumns; i++) { int16 opt = indexRelation->rd_indoption[i];
+ int16 keyattno = index->indkey.values[i]; info->reverse_sort[i] = (opt &
INDOPTION_DESC)!= 0; info->nulls_first[i] = (opt & INDOPTION_NULLS_FIRST) != 0;
- }
+
+ if (keyattno > 0)
+ {
+ has_nullable_keycol |=
+ !relation->rd_att->attrs[keyattno - 1]->attnotnull;
+ }
+ else if (keyattno != ObjectIdAttributeNumber)
+ has_nullable_keycol = true;
+ }
+
+ /* Check to see if it is a full-ordered index */
+ if (IndexIsValid(index) &&
+ index->indisunique && index->indimmediate &&
+ !has_nullable_keycol)
+ info->full_ordered = true; } else if (indexRelation->rd_am->amcanorder)
{
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 6d7b594..b38c667 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -524,6 +524,7 @@ typedef struct IndexOptInfo bool predOK; /* true if predicate matches query */
bool unique; /* true if a unique index */ bool immediate; /* is uniqueness
enforcedimmediately? */
+ bool full_ordered; /* is ordered rows not duplicate ? */ bool hypothetical; /* true if
indexdoesn't really exist */ bool canreturn; /* can index return IndexTuples? */ bool
amcanorderbyop;/* does AM support order by operator result? */
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 999adaa..1987659 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -194,7 +194,8 @@ extern List *make_inner_pathkeys_for_merge(PlannerInfo *root, List
*outer_pathkeys);externList *truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel,
- List *pathkeys);
+ List *pathkeys,
+ bool pk_full_ordered);extern bool has_useful_pathkeys(PlannerInfo *root, RelOptInfo
*rel);#endif /* PATHS_H */
diff --git a/src/test/isolation/expected/drop-index-concurrently-1.out
b/src/test/isolation/expected/drop-index-concurrently-1.out
index 75dff56..ab96fa0 100644
--- a/src/test/isolation/expected/drop-index-concurrently-1.out
+++ b/src/test/isolation/expected/drop-index-concurrently-1.out
@@ -19,10 +19,8 @@ Sortstep explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seq;QUERY PLAN
-Sort
- Sort Key: id, data
- -> Seq Scan on test_dc
- Filter: ((data)::text = '34'::text)
+Index Scan using test_dc_pkey on test_dc
+ Filter: ((data)::text = '34'::text)step select2: SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;id
data
Kyotaro HORIGUCHI wrote: > Hello. I found a bug(?) in thsi patch as I considered on another patch. > In truncate_useless_pathkeys, if query_pathkeys is longer than pathkeys made > from index columns old patch picked up the latter as IndexPath's pathkeys. > But the former is more suitable according to the context here. > the attched pathkey_and_uniqueindx_v4_20131122.patch is changed as follows. > - Rebased to current master. > - truncate_useless_pathkeys returns root->query_pathkeys when > the index is fully-ordered and query_pathkeys contains the > pathkeys made from index columns. OK, I'd like to look at this version of the patch more closely, then. Thanks, Best regards, Etsuro Fujita
Kyotaro HORIGUCHI wrote:
> the attched pathkey_and_uniqueindx_v4_20131122.patch is changed as
> follows.
The patch is compiled successfully and passes all regression tests. Also,
the patch works well for the tests shown in an earlier email from
Horiguchi-san. But in this version I found an incorrect behavior.
postgres=# CREATE TABLE t (a int not null, b int not null, c int, d text);
CREATE TABLE
postgres=# CREATE UNIQUE INDEX i_t_ab ON t (a, b);
CREATE INDEX
postgres=# INSERT INTO t (SELECT a / 5, 4 - (a % 5), a, 't' FROM
generate_series(000000, 099999) a);
INSERT 0 100000
postgres=# ANALYZE t;
ANALYZE
postgres=# CREATE TABLE t2 (e text, f int);
CREATE TABLE
postgres=# INSERT INTO t2 VALUES ('t', 2);
INSERT 0 1
postgres=# INSERT INTO t2 VALUES ('t', 1);
INSERT 0 1
postgres=# ANALYZE t2;
ANALYZE
postgres=# EXPLAIN SELECT * FROM t, t2 WHERE t.a < 10 AND t.d = t2.e ORDER
BY t.a, t.b, t.c, t.d, t2.f LIMIT 10; QUERY PLAN
----------------------------------------------------------------------------
----Limit (cost=0.29..9.30 rows=10 width=20) -> Nested Loop (cost=0.29..129.99 rows=144 width=20) Join
Filter:(t.d = t2.e) -> Index Scan using i_t_ab on t (cost=0.29..126.80 rows=72
width=14) Index Cond: (a < 10) -> Materialize (cost=0.00..1.03 rows=2 width=6) ->
SeqScan on t2 (cost=0.00..1.02 rows=2 width=6)
(7 rows)
postgres=# SELECT * FROM t, t2 WHERE t.a < 10 AND t.d = t2.e ORDER BY t.a,
t.b, t.c, t.d, t2.f LIMIT 10;a | b | c | d | e | f
---+---+---+---+---+---0 | 0 | 4 | t | t | 20 | 0 | 4 | t | t | 10 | 1 | 3 | t | t | 20 | 1 | 3 | t | t | 10 | 2 | 2 |
t| t | 20 | 2 | 2 | t | t | 10 | 3 | 1 | t | t | 20 | 3 | 1 | t | t | 10 | 4 | 0 | t | t | 20 | 4 | 0 | t | t | 1
(10 rows)
(Note the column f is sorted in the descending order.)
ISTM this was brought by the following change.
> In truncate_useless_pathkeys, if query_pathkeys is longer than pathkeys
> made from index columns old patch picked up the latter as IndexPath's
> pathkeys. But the former is more suitable according to the context here.
> - truncate_useless_pathkeys returns root->query_pathkeys when
> the index is fully-ordered and query_pathkeys contains the
> pathkeys made from index columns.
I think it would be required to modify the patch so that the transformation
of the pathkeys is performed only when each pathkey of query_pathkeys
references the indexed relation. (The above change might have been made
according to my comment in an earlier email I sent. But I have to admit my
explanation there was not adequate. I'm sorry for that.)
Here are random comments.
* In grouping_planner(), the patch resets the pathkeys of the cheapest
presorted index-path to query_pathkeys through
get_cheapest_fractional_path_for_pathkeys(). Is this necessary? ISTM the
transformation of the pathkeys after the scan/join optimization would be no
longer necessary once it has been done at the index-path creation time, ie,
build_index_paths(). Why does the patch do that thing?
* In get_relation_info(), the patch determines the branch condition
"keyattno != ObjectIdAttributeNumber". I fail to understand the meaning of
this branch condition. Could you explain about it?
Thanks,
Best regards,
Etsuro Fujita
Thank you for pointing out.
> > the attched pathkey_and_uniqueindx_v4_20131122.patch is changed as
> > follows.
>
> The patch is compiled successfully and passes all regression tests. Also,
> the patch works well for the tests shown in an earlier email from
> Horiguchi-san. But in this version I found an incorrect behavior.
>
> postgres=# CREATE TABLE t (a int not null, b int not null, c int, d text);
> CREATE TABLE
> postgres=# CREATE UNIQUE INDEX i_t_ab ON t (a, b);
> CREATE INDEX
> postgres=# INSERT INTO t (SELECT a / 5, 4 - (a % 5), a, 't' FROM
> generate_series(000000, 099999) a);
> INSERT 0 100000
> postgres=# ANALYZE t;
> ANALYZE
> postgres=# CREATE TABLE t2 (e text, f int);
> CREATE TABLE
> postgres=# INSERT INTO t2 VALUES ('t', 2);
> INSERT 0 1
> postgres=# INSERT INTO t2 VALUES ('t', 1);
> INSERT 0 1
> postgres=# ANALYZE t2;
> ANALYZE
> postgres=# EXPLAIN SELECT * FROM t, t2 WHERE t.a < 10 AND t.d = t2.e ORDER
> BY t.a, t.b, t.c, t.d, t2.f LIMIT 10;
> QUERY PLAN
> ----------------------------------------------------------------------------
> ----
> Limit (cost=0.29..9.30 rows=10 width=20)
- -> Sort (cost=92.33..92.57 rows=94 width=20)
- Sort Key: t.a, t.b, t.c, t.d, t2.f
> -> Nested Loop (cost=0.29..129.99 rows=144 width=20)
> Join Filter: (t.d = t2.e)
> -> Index Scan using i_t_ab on t (cost=0.29..126.80 rows=72
> width=14)
> Index Cond: (a < 10)
> -> Materialize (cost=0.00..1.03 rows=2 width=6)
> -> Seq Scan on t2 (cost=0.00..1.02 rows=2 width=6)
> (7 rows)
Auch. Outermost sort is omitted but necessary (Prefixed by '-' above).
> ISTM this was brought by the following change.
>
> > In truncate_useless_pathkeys, if query_pathkeys is longer than pathkeys
> > made from index columns old patch picked up the latter as IndexPath's
> > pathkeys. But the former is more suitable according to the context here.
>
> > - truncate_useless_pathkeys returns root->query_pathkeys when
> > the index is fully-ordered and query_pathkeys contains the
> > pathkeys made from index columns.
I implicitly put a wrong assumption that query_pathkeys is
dedicated for the relation under work, not whole subquery.
> I think it would be required to modify the patch so that the transformation
> of the pathkeys is performed only when each pathkey of query_pathkeys
> references the indexed relation.
What is wrong here is that IndexPath declares that it is ordered
in the pathkeys which includes the columns not belongs to the
table.
> (The above change might have been made according to my comment
> in an earlier email I sent. But I have to admit my explanation
> there was not adequate. I'm sorry for that.)
Nothing to be sorry for. It's my fault.
Anyway, I've put restriction on pathkeys_useful_for_ordering that
pick up longest pathkeys consists only ec members which matches
the required rel bitmap. With the new patch the planner makes
plan with the omitted sort and the query returns the following
result.
uniontest=# SELECT * FROM t, t2 WHERE t.a < 10 AND t.d = t2.e
| ORDER BY t.a, t.b, t.c, t.d, t2.f LIMIT 10;
| a | b | c | d | e | f
| ---+---+---+---+---+---
| 0 | 0 | 4 | t | t | 1 <-+-- Correct order by t2.f.
| 0 | 0 | 4 | t | t | 2 <-+
| 0 | 1 | 3 | t | t | 1
(snipped.)
> Here are random comments.
>
> * In grouping_planner(), the patch resets the pathkeys of the cheapest
> presorted index-path to query_pathkeys through
> get_cheapest_fractional_path_for_pathkeys(). Is this necessary? ISTM the
> transformation of the pathkeys after the scan/join optimization would be no
> longer necessary once it has been done at the index-path creation time, ie,
> build_index_paths(). Why does the patch do that thing?
You're appliciated for pointing out. It is utterly useless code
of older patch. ("Have you totally scrapped the older verions?" >me :-(
Removed it in this version.
> * In get_relation_info(), the patch determines the branch condition
> "keyattno != ObjectIdAttributeNumber". I fail to understand the meaning of
> this branch condition. Could you explain about it?
Literally answering, it means oid cannot be NULL (if it exists).
Precisely, it reflects that I believed (or wished) it cannot be
NULL if oid column exists. (Other sysattrs are dismissed because
they are hardly to be a unique index column:-)
Oid in a tuple is retrived using HeapTupleGetOid() in
heap_getsysattr().
| result = ObjectIdGetDatum(HeapTupleGetOid(tup));
Then HeapTupleHeaderGetOid,
| #define HeapTupleGetOid(tuple) \
| HeapTupleHeaderGetOid((tuple)->t_data)
Finally asking HeapTupleHeaderGetOid for the value.
htup_details.h:354
| #define HeapTupleHeaderGetOid(tup) \
| ( \
| ((tup)->t_infomask & HEAP_HASOID) ? \
| *((Oid *) ((char *)(tup) + (tup)->t_hoff - sizeof(Oid))) \
| : \
| InvalidOid \
| )
So oid cannot be NULL after all even though can be InvalidOid.
On the otherhand, it can be NULL according to the definition in
heap.c.
heap.c:146
| static FormData_pg_attribute a2 = {
| 0, {"oid"}, OIDOID, 0, sizeof(Oid),
| ObjectIdAttributeNumber, 0, -1, -1,
| true, 'p', 'i', true, false, false, true, 0
| }; ~~~~
Can we set this to false safely?
regards,
--
Kyotaro Horiguchi
NTT Open Source Software Center
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 606734a..43be0a5 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -953,7 +953,8 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_pathkeys =
build_index_pathkeys(root,index, ForwardScanDirection);
useful_pathkeys= truncate_useless_pathkeys(root, rel,
- index_pathkeys);
+ index_pathkeys,
+ index->full_ordered); orderbyclauses = NIL;
orderbyclausecols= NIL; }
@@ -1015,7 +1016,8 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_pathkeys =
build_index_pathkeys(root,index, BackwardScanDirection);
useful_pathkeys= truncate_useless_pathkeys(root, rel,
- index_pathkeys);
+ index_pathkeys,
+ index->full_ordered); if (useful_pathkeys != NIL) {
ipath = create_index_path(root, index,
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 9c8ede6..47d844b 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -369,6 +369,29 @@ get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,}/*
+ * path_is_ordered
+ * Return true if the path is apparently ordered on the pathkeys.
+ */
+bool
+path_is_ordered(Path *path, List *pathkeys)
+{
+ if (pathkeys_contained_in(pathkeys, path->pathkeys))
+ return true;
+
+ /*
+ * If IndexPath is fully ordered, it is sufficiently ordered if index
+ * pathkeys is a subset of target pathkeys
+ */
+ if (pathkeys && path->pathkeys &&
+ IsA(path, IndexPath) &&
+ ((IndexPath*)path)->indexinfo->full_ordered &&
+ (pathkeys_contained_in(path->pathkeys, pathkeys)))
+ return true;
+
+ return false;
+}
+
+/* * get_cheapest_fractional_path_for_pathkeys * Find the cheapest path (for retrieving a specified fraction of
all* the tuples) that satisfies the given pathkeys and parameterization.
@@ -381,6 +404,8 @@ get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, * 'pathkeys' represents a required
ordering(in canonical form!) * 'required_outer' denotes allowable outer relations for parameterized paths * 'fraction'
isthe fraction of the total tuples expected to be retrieved
+ * paths->pathkeys might be replaced with pathkeys so as to declare that the
+ * path is ordered on it. */Path *get_cheapest_fractional_path_for_pathkeys(List *paths,
@@ -403,7 +428,7 @@ get_cheapest_fractional_path_for_pathkeys(List *paths,
compare_fractional_path_costs(matched_path,path, fraction) <= 0) continue;
- if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
+ if (path_is_ordered(path, pathkeys) && bms_is_subset(PATH_REQ_OUTER(path), required_outer))
matched_path = path; }
@@ -798,7 +823,7 @@ build_join_pathkeys(PlannerInfo *root, * contain pathkeys that were useful for forming this
joinrelbut are * uninteresting to higher levels. */
- return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
+ return truncate_useless_pathkeys(root, joinrel, outer_pathkeys,
false);}/****************************************************************************
@@ -1455,7 +1480,8 @@ right_merge_direction(PlannerInfo *root, PathKey *pathkey) * So the result is always either 0 or
list_length(root->query_pathkeys).*/static int
-pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
+pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys,
+ bool pk_full_ordered, Bitmapset *rel){ if (root->query_pathkeys == NIL) return
0; /* no special ordering requested */
@@ -1469,23 +1495,71 @@ pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys) return
list_length(root->query_pathkeys); }
+ /*
+ * Given that the pathkeys compose an unique key, they are useful for
+ * ordering when they are a sublist of query_pathkeys. Expand pathkeys to
+ * root->query_pathkeys in this case.
+ */
+ if (pk_full_ordered &&
+ pathkeys_contained_in(pathkeys, root->query_pathkeys))
+ {
+ int len = list_length(pathkeys);
+ Assert(!bms_is_empty(rel));
+ if (list_length(root->query_pathkeys) > len)
+ {
+ /*
+ * Extend useful_pathkeys up to as long as relids of EC has a
+ * matche for the target relations.
+ */
+ ListCell *lcpk = list_head(root->query_pathkeys);
+ int i;
+
+ /* Skip known section, list_nth_cell is not extern'ed */
+ for (i = 0 ; i < len ; i++)
+ lcpk = lnext(lcpk);
+
+ for_each_cell(lcpk, lcpk)
+ {
+ ListCell *lcm;
+ PathKey *pk = (PathKey *) lfirst(lcpk);
+ foreach (lcm, pk->pk_eclass->ec_members)
+ {
+ EquivalenceMember *em = (EquivalenceMember *) lfirst(lcm);
+ if (bms_is_subset(em->em_relids, rel))
+ break;
+ }
+ if (!lcm)
+ break;
+
+ len++;
+ }
+ }
+
+ return len;
+ }
+ return 0; /* path ordering not useful */}/* * truncate_useless_pathkeys * Shorten the
givenpathkey list to just the useful pathkeys.
+ *
+ * When pk_full_ordered is true, reconsider counting the uniqueness even if
+ * the pathkeys are once judged as useless by the general criteria. */List *truncate_useless_pathkeys(PlannerInfo
*root, RelOptInfo *rel,
- List *pathkeys)
+ List *pathkeys,
+ bool pk_full_ordered){ int nuseful; int nuseful2; nuseful =
pathkeys_useful_for_merging(root,rel, pathkeys);
- nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
+ nuseful2 = pathkeys_useful_for_ordering(root, pathkeys,
+ pk_full_ordered, rel->relids); if (nuseful2 > nuseful) nuseful =
nuseful2;
@@ -1498,7 +1572,7 @@ truncate_useless_pathkeys(PlannerInfo *root, else if (nuseful == list_length(pathkeys))
returnpathkeys; else
- return list_truncate(list_copy(pathkeys), nuseful);
+ return list_truncate(list_copy(root->query_pathkeys), nuseful);}/*
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 954666c..c6d45e3 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -231,6 +231,8 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent, */
if (info->relam == BTREE_AM_OID) {
+ bool has_nullable_keycol = false;
+ /* * If it's a btree index, we can use its opfamily OIDs * directly as
thesort ordering opfamily OIDs.
@@ -244,10 +246,26 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent, for (i
=0; i < ncolumns; i++) { int16 opt = indexRelation->rd_indoption[i];
+ int16 keyattno = index->indkey.values[i]; info->reverse_sort[i] = (opt &
INDOPTION_DESC)!= 0; info->nulls_first[i] = (opt & INDOPTION_NULLS_FIRST) != 0;
- }
+
+ if (keyattno > 0)
+ {
+ has_nullable_keycol |=
+ !relation->rd_att->attrs[keyattno - 1]->attnotnull;
+ }
+ /* OID should be NULL if exists. */
+ else if (keyattno != ObjectIdAttributeNumber)
+ has_nullable_keycol = true;
+ }
+
+ /* Check to see if it is a full-ordered index */
+ if (IndexIsValid(index) &&
+ index->indisunique && index->indimmediate &&
+ !has_nullable_keycol)
+ info->full_ordered = true; } else if (indexRelation->rd_am->amcanorder)
{
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 6d7b594..b38c667 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -524,6 +524,7 @@ typedef struct IndexOptInfo bool predOK; /* true if predicate matches query */
bool unique; /* true if a unique index */ bool immediate; /* is uniqueness
enforcedimmediately? */
+ bool full_ordered; /* is ordered rows not duplicate ? */ bool hypothetical; /* true if
indexdoesn't really exist */ bool canreturn; /* can index return IndexTuples? */ bool
amcanorderbyop;/* does AM support order by operator result? */
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 999adaa..1987659 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -194,7 +194,8 @@ extern List *make_inner_pathkeys_for_merge(PlannerInfo *root, List
*outer_pathkeys);externList *truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel,
- List *pathkeys);
+ List *pathkeys,
+ bool pk_full_ordered);extern bool has_useful_pathkeys(PlannerInfo *root, RelOptInfo
*rel);#endif /* PATHS_H */
diff --git a/src/test/isolation/expected/drop-index-concurrently-1.out
b/src/test/isolation/expected/drop-index-concurrently-1.out
index 75dff56..ab96fa0 100644
--- a/src/test/isolation/expected/drop-index-concurrently-1.out
+++ b/src/test/isolation/expected/drop-index-concurrently-1.out
@@ -19,10 +19,8 @@ Sortstep explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seq;QUERY PLAN
-Sort
- Sort Key: id, data
- -> Seq Scan on test_dc
- Filter: ((data)::text = '34'::text)
+Index Scan using test_dc_pkey on test_dc
+ Filter: ((data)::text = '34'::text)step select2: SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;id
data
On Fri, 2013-11-22 at 16:59 +0900, Kyotaro HORIGUCHI wrote: > Hello. I found a bug(?) in thsi patch as I considered on another > patch. src/backend/optimizer/util/plancat.c:256: trailing whitespace. src/backend/optimizer/util/plancat.c:261: space before tab in indent.
Kyotaro HORIGUCHI wrote: > > * In get_relation_info(), the patch determines the branch condition > > "keyattno != ObjectIdAttributeNumber". I fail to understand the > > meaning of this branch condition. Could you explain about it? > Literally answering, it means oid cannot be NULL (if it exists). Understood. Thank you for the detailed information. But I'm not sure it's worth complicating the code. What use cases are you thinking? Thanks, Best regards, Etsuro Fujita
I wrote: > Kyotaro HORIGUCHI wrote: > > > * In get_relation_info(), the patch determines the branch condition > > > "keyattno != ObjectIdAttributeNumber". I fail to understand the > > > meaning of this branch condition. Could you explain about it? > > Literally answering, it means oid cannot be NULL (if it exists). > Understood. Thank you for the detailed information. But I'm not sure it's > worth complicating the code. What use cases are you thinking? Having said that, I've reconsidered about this, and start to think it would be better that all system attributes are processed in the same way as are user attributes because that makes the code more simple. Yes, as you mention, it's not necessarily guaranteed that system attributes have the uniqueness property in general, but that's another problem. Thanks, Best regards, Etsuro Fujita
I wrote: > I wrote: > > Kyotaro HORIGUCHI wrote: > > > > * In get_relation_info(), the patch determines the branch > > > > condition "keyattno != ObjectIdAttributeNumber". I fail to > > > > understand the meaning of this branch condition. Could you explain > about it? > > > Literally answering, it means oid cannot be NULL (if it exists). > > Understood. Thank you for the detailed information. But I'm not sure > > it's worth complicating the code. What use cases are you thinking? > Having said that, I've reconsidered about this, and start to think it would > be better that all system attributes are processed in the same way as are > user attributes because that makes the code more simple. Yes, as you > mention, it's not necessarily guaranteed that system attributes have the > uniqueness property in general, but that's another problem. I've modified the patch to work in such a way. Also, as ISTM the patch is more complicated than what the patch really does, I've simplified the patch. Attached is an updated version of the patch. Could you review the patch? Thanks, Best regards, Etsuro Fujita
I wrote: > I've modified the patch to work in such a way. Also, as ISTM the patch > is more complicated than what the patch really does, I've simplified the > patch. I've revised the patch a bit. Please find attached the patch. Thanks, Best regards, Etsuro Fujita
Hello, > > I've modified the patch to work in such a way. Also, as ISTM the patch > > is more complicated than what the patch really does, I've simplified the > > patch. > > I've revised the patch a bit. Please find attached the patch. Thank you, but it seems to me too simplified. You made two major functional changes. One is, you put the added code for getrelation_info() out of the block for the condition (info->relam == BTREE_AM_OID) (though amcanorder would be preferable..) Anyway the reason for the place is to guarantee 'full_ordered' index always to be orderable. I believe the relation between them are not obvious. So your patch has an oppotunity to make wrong assumption for possible indexes which is not orderable but unique. Going on your way some additional works would be needed to judge an index to be orderable or not on checking the extensibility of pathkeys. Another is, you changed pathkeys expantion to be all-or-nothing decision. While this change should simplify the code slightly, it also dismisses the oppotunity for partially-extended pathkeys. Could you let me know the reason why you did so. Any thoughts? regards, -- Kyotaro Horiguchi NTT Open Source Software Center
Kyotaro HORIGUCHI wrote: > Thank you, but it seems to me too simplified. You made two major functional > changes. Thank you for the comments! > One is, you put the added code for getrelation_info() out of the block for > the condition (info->relam == BTREE_AM_OID) (though amcanorder would be > preferable..) Anyway the reason for the place is to guarantee 'full_ordered' > index always to be orderable. I believe the relation between them are not > obvious. So your patch has an oppotunity to make wrong assumption for > possible indexes which is not orderable but unique. Going on your way some > additional works would be needed to judge an index to be orderable or not > on checking the extensibility of pathkeys. By checking the following equation in build_index_paths(), the updated version of the patch guarantees that the result of an index scan is ordered: index_is_ordered = (index->sortopfamily != NULL); > Another is, you changed pathkeys expantion to be all-or-nothing decision. > While this change should simplify the code slightly, it also dismisses the > oppotunity for partially-extended pathkeys. Could you let me know the reason > why you did so. At first I thought the partially-extended pathkey list that is made from query_pathkeys, as you proposed in the original versions of the patch. But I've started to doubt whether it's worth doing that because I think the partially-extended pathkey list is merely one example while the original pathkey list can be partially-extended in different ways, ie, ISTM the partially-extended pathkey list doesn't necessarily have the optimality in anything significant. We might be able to partially-extend the original pathkey list optimally in something significant, but that seems useless complexity to me. So, I modified the patch to do the all-or-nothing decision. Thanks, Best regards, Etsuro Fujita
I wrote: > Kyotaro HORIGUCHI wrote: > > Another is, you changed pathkeys expantion to be all-or-nothing decision. > > While this change should simplify the code slightly, it also dismisses > > the oppotunity for partially-extended pathkeys. Could you let me know > > the > reason > > why you did so. > At first I thought the partially-extended pathkey list that is made from > query_pathkeys, as you proposed in the original versions of the patch. But > I've started to doubt whether it's worth doing that because I think the > partially-extended pathkey list is merely one example while the original > pathkey list can be partially-extended in different ways, ie, ISTM the > partially-extended pathkey list doesn't necessarily have the optimality > in anything significant. We might be able to partially-extend the original > pathkey list optimally in something significant, but that seems useless > complexity to me. So, I modified the patch to do the all-or-nothing > decision. Here I mean the optimality for use in merge joins. Thanks, Best regards, Etsuro Fujita
Thank you, > > One is, you put the added code for getrelation_info() out of the block for > > the condition (info->relam == BTREE_AM_OID) (though amcanorder would be .. > By checking the following equation in build_index_paths(), the updated > version of the patch guarantees that the result of an index scan is ordered: > > index_is_ordered = (index->sortopfamily != NULL); Oops.. I forgot about it although many times I've seen... You're right. > > > Another is, you changed pathkeys expantion to be all-or-nothing decision. > > > While this change should simplify the code slightly, it also dismisses > > > the oppotunity for partially-extended pathkeys. Could you let me know > > > the reason why you did so. ... > > We might be able to partially-extend the original > > pathkey list optimally in something significant, but that seems useless > > complexity to me. So, I modified the patch to do the all-or-nothing > > decision. > > Here I mean the optimality for use in merge joins. Ok, I'll follow your advice. I agree on the point about merit vs complexity. I'm convinced of the validity of your patch. I'm satisfied with it. Thank you. regards, -- Kyotaro Horiguchi NTT Open Source Software Center
Kyotaro HORIGUCHI wrote: > I'm convinced of the validity of your patch. I'm satisfied with it. Thank > you. Thank you for the reply. Then, if there are no objections of others, I'll mark this as "Ready for Committer". Thanks, Best regards, Etsuro Fujita
I wrote: > Kyotaro HORIGUCHI wrote: > > I'm convinced of the validity of your patch. I'm satisfied with it. > Then, if there are no objections of others, I'll mark this as "Ready for > Committer". Done. Thanks, Best regards, Etsuro Fujita
"Etsuro Fujita" <fujita.etsuro@lab.ntt.co.jp> writes:
> [ pathkey_and_uniqueindx_v7_20131203.patch ]
I started to look at this patch. I don't understand the reason for the
foreach loop in index_pathkeys_are_extensible (and the complete lack of
comments in the patch isn't helping). Isn't it sufficient to check that
the index is unique/immediate/allnotnull and its ordering is a prefix
of query_pathkeys? If not, what's the rationale for the specific tests
being made on the pathkeys --- this code doesn't make much sense to me.
regards, tom lane
Tom Lane wrote:
> "Etsuro Fujita" <fujita.etsuro@lab.ntt.co.jp> writes:
> > [ pathkey_and_uniqueindx_v7_20131203.patch ]
> I started to look at this patch. I don't understand the reason for the
> foreach loop in index_pathkeys_are_extensible (and the complete lack of
> comments in the patch isn't helping). Isn't it sufficient to check that
> the index is unique/immediate/allnotnull and its ordering is a prefix of
> query_pathkeys? If not, what's the rationale for the specific tests being
> made on the pathkeys --- this code doesn't make much sense to me.
Thank you for taking time to look at this patch. I think it's not
sufficient to check those things. Let me explain the reason why this patch
has that code. The patch has that code in order to prevent
build_join_pathkeys() from building incorrect join pathkeys', where the
pathkeys for a join relation constructed by mergejoin or nestloop join are
built normally just by using the outer path's pathkeys. Without that code,
the patch would produce an incorrect result for such a case. An example
will be shown below. A simple approach to avoid this problem would be to
apply this idea only when each pathkey in query_pathkeys references the
indexed relation in addition to that the index is
unique/immediate/allnotnull and its ordering is a prefix of query_pathkeys.
That's the reason.
[Data]
CREATE TABLE t (a int not null, b int not null, c int, d text);
CREATE UNIQUE INDEX i_t_ab ON t (a, b);
INSERT INTO t (SELECT a / 5, 4 - (a % 5), a, 't' FROM
generate_series(000000, 099999) a);
ANALYZE t;
CREATE TABLE t2 (e text, f int);
INSERT INTO t2 VALUES ('t', 2);
INSERT INTO t2 VALUES ('t', 1);
ANALYZE t2;
[Query]
EXPLAIN SELECT * FROM t, t2 WHERE t.a < 10 AND t.d = t2.e ORDER BY t.a, t.b,
t.c, t.d, t2.f LIMIT 4; QUERY PLAN
----------------------------------------------------------------------------
----Limit (cost=0.29..3.96 rows=4 width=20) -> Nested Loop (cost=0.29..110.17 rows=120 width=20) Join
Filter:(t.d = t2.e) -> Index Scan using i_t_ab on t (cost=0.29..107.34 rows=60
width=14) Index Cond: (a < 10) -> Materialize (cost=0.00..1.03 rows=2 width=6) ->
SeqScan on t2 (cost=0.00..1.02 rows=2 width=6)
(7 rows)
SELECT * FROM t, t2 WHERE t.a < 10 AND t.d = t2.e ORDER BY t.a, t.b, t.c,
t.d, t2.f LIMIT 4;a | b | c | d | e | f
---+---+---+---+---+---0 | 0 | 4 | t | t | 20 | 0 | 4 | t | t | 10 | 1 | 3 | t | t | 20 | 1 | 3 | t | t | 1
(4 rows)
(Note the column f is sorted in the descending order.)
Sorry for the delay.
Best regards,
Etsuro Fujita
"Etsuro Fujita" <fujita.etsuro@lab.ntt.co.jp> writes:
> Thank you for taking time to look at this patch. I think it's not
> sufficient to check those things. Let me explain the reason why this patch
> has that code. The patch has that code in order to prevent
> build_join_pathkeys() from building incorrect join pathkeys', where the
> pathkeys for a join relation constructed by mergejoin or nestloop join are
> built normally just by using the outer path's pathkeys. Without that code,
> the patch would produce an incorrect result for such a case.
Ah, thanks for the example. ISTM that really the issue is that if an
originally-unique row is "expanded" into multiple rows, those rows are
sort peers so far as the unique-index column(s) are concerned, and so
now the lower-order ORDER BY columns do matter after all.
The problem is that joining isn't the only way that such expansion can
happen. Set-returning functions in the targetlist are another way,
and I'm not sure that there aren't others. Here's an example that
I'm pretty sure breaks your patch (though I didn't actually reinstall
the patch to try it):
create or replace function rev(n int) returns setof int language plpgsql
as 'begin for i in reverse n..1 loop return next i; end loop; end';
create table tt (f1 int primary key, f2 int);
insert into tt values (1,2), (2,3);
select f1, rev(f2) from tt order by 1,2;
Also, even if the row-expansion mechanism is a join, it's certainly
insufficient to check that the lower-order sort column is an expression
in variables of the index's table. Something like "f2 + random()" is
going to need an explicit sort step anyway.
These particular objections could be worked around by checking for
set-returning functions and volatile functions in the lower-order
ORDER BY expressions. But I have to say that I think I'm losing
faith in the entire idea. I have little confidence that there
aren't other cases that will break it.
regards, tom lane
Hello,
> Tom Lane wrote:
> > I started to look at this patch. I don't understand the reason for the
> > foreach loop in index_pathkeys_are_extensible (and the complete lack of
> > comments in the patch isn't helping). Isn't it sufficient to check that
> > the index is unique/immediate/allnotnull and its ordering is a prefix of
> > query_pathkeys? If not, what's the rationale for the specific tests being
> > made on the pathkeys --- this code doesn't make much sense to me.
>
> Thank you for taking time to look at this patch. I think it's not
> sufficient to check those things. Let me explain the reason why this patch
> has that code. The patch has that code in order to prevent
> build_join_pathkeys() from building incorrect join pathkeys', where the
> pathkeys for a join relation constructed by mergejoin or nestloop join are
> built normally just by using the outer path's pathkeys. Without that code,
> the patch would produce an incorrect result for such a case. An example
> will be shown below.
> A simple approach to avoid this problem would be to
> apply this idea only when each pathkey in query_pathkeys references the
> indexed relation in addition to that the index is
> unique/immediate/allnotnull and its ordering is a prefix of query_pathkeys.
> That's the reason.
Utterly disregarding the chances of joins - the patch (v7)
already does so in some extent, ignoring the possibility of
partial extension for multi-table'd pathkeys - it is also
avoidable by simply passing a boolean
'extend_pathkeys_if_possible', or splitting into two functions
regarding the boolean. The check was not a yes-or-no decision but
a how-long-it-can-be-extended measuring in the previous version
(pathkey_and_uniqueindx_v5). It has been simplified and splitted
out as individual function after.
> [Data]
> CREATE TABLE t (a int not null, b int not null, c int, d text);
> CREATE UNIQUE INDEX i_t_ab ON t (a, b);
> INSERT INTO t (SELECT a / 5, 4 - (a % 5), a, 't' FROM
> generate_series(000000, 099999) a);
> ANALYZE t;
> CREATE TABLE t2 (e text, f int);
> INSERT INTO t2 VALUES ('t', 2);
> INSERT INTO t2 VALUES ('t', 1);
> ANALYZE t2;
>
> [Query]
> EXPLAIN SELECT * FROM t, t2 WHERE t.a < 10 AND t.d = t2.e ORDER BY t.a, t.b,
> t.c, t.d, t2.f LIMIT 4;
> QUERY PLAN
> ----------------------------------------------------------------------------
> ----
> Limit (cost=0.29..3.96 rows=4 width=20)
> -> Nested Loop (cost=0.29..110.17 rows=120 width=20)
> Join Filter: (t.d = t2.e)
> -> Index Scan using i_t_ab on t (cost=0.29..107.34 rows=60
> width=14)
> Index Cond: (a < 10)
> -> Materialize (cost=0.00..1.03 rows=2 width=6)
> -> Seq Scan on t2 (cost=0.00..1.02 rows=2 width=6)
> (7 rows)
>
> SELECT * FROM t, t2 WHERE t.a < 10 AND t.d = t2.e ORDER BY t.a, t.b, t.c,
> t.d, t2.f LIMIT 4;
> a | b | c | d | e | f
> ---+---+---+---+---+---
> 0 | 0 | 4 | t | t | 2
> 0 | 0 | 4 | t | t | 1
> 0 | 1 | 3 | t | t | 2
> 0 | 1 | 3 | t | t | 1
> (4 rows)
>
> (Note the column f is sorted in the descending order.)
>
> Sorry for the delay.
>
> Best regards,
> Etsuro Fujita
With best wishes for a happy New Yaar.
--
Kyotaro Horiguchi
NTT Open Source Software Center
Hello,
tgl> The problem is that joining isn't the only way that such expansion can
tgl> happen. Set-returning functions in the targetlist are another way,
tgl> and I'm not sure that there aren't others. Here's an example that
tgl> I'm pretty sure breaks your patch (though I didn't actually reinstall
tgl> the patch to try it):
tgl>
tgl> create or replace function rev(n int) returns setof int language plpgsql
tgl> as 'begin for i in reverse n..1 loop return next i; end loop; end';
tgl>
tgl> create table tt (f1 int primary key, f2 int);
tgl>
tgl> insert into tt values (1,2), (2,3);
tgl>
tgl> select f1, rev(f2) from tt order by 1,2;
tgl>
tgl> Also, even if the row-expansion mechanism is a join, it's certainly
tgl> insufficient to check that the lower-order sort column is an expression
tgl> in variables of the index's table. Something like "f2 + random()" is
tgl> going to need an explicit sort step anyway.
tgl>
tgl> These particular objections could be worked around by checking for
tgl> set-returning functions and volatile functions in the lower-order
tgl> ORDER BY expressions. But I have to say that I think I'm losing
tgl> faith in the entire idea. I have little confidence that there
tgl> aren't other cases that will break it.
I think that the required condition for all these ordering
problems is generating multiple rows for single input (for a
value of any column of the same table).
If a prefixing set of values correspond to a unique index appears
only once in a result, the result must can be fully-ordered by
the extended pathkeys. This is what this patch stands on. It
never be broken while the precondition is satisfied... I think.
On the other hand, the precondition should be satisfied when all
extended columns are simple Vars of the target table. I believe
Vars cannot produce multiple result. More close checking for
every possibility could be done but it should be a overdone.
The following modification to v7 does this.
=========
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 380f3ba..233e21c 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -536,7 +536,8 @@ index_pathkeys_are_extensible(PlannerInfo *root, { EquivalenceMember *member =
(EquivalenceMember*) lfirst(lc2);
- if (!bms_equal(member->em_relids, index->rel->relids))
+ if (!bms_equal(member->em_relids, index->rel->relids) ||
+ !IsA(member, Var)) continue; else {
==========
The result is
postgres=# select f1, rev(f2) from tt order by 1, 2;f1 | rev
----+----- 1 | 1 1 | 2 2 | 1 2 | 2 2 | 3
==========
regards,
--
Kyotaro Horiguchi
NTT Open Source Software Center
> I think that the required condition for all these ordering Careless wording. the 'required' condition above means 'necessary (but not sufficient)' condition so I think the lack of the precondition (=multiple rows) results in prevention of the postcondition = ordering problems. > problems is generating multiple rows for single input (for a > value of any column of the same table). > > If a prefixing set of values correspond to a unique index appears > only once in a result, the result must can be fully-ordered by > the extended pathkeys. This is what this patch stands on. It > never be broken while the precondition is satisfied... I think. > > On the other hand, the precondition should be satisfied when all > extended columns are simple Vars of the target table. I believe > Vars cannot produce multiple result. More close checking for > every possibility could be done but it should be a overdone. regards, -- Kyotaro Horiguchi NTT Open Source Software Center
Kyotaro HORIGUCHI wrote: > tgl> The problem is that joining isn't the only way that such expansion > tgl> can happen. Set-returning functions in the targetlist are another > tgl> way, and I'm not sure that there aren't others. Here's an example > tgl> that I'm pretty sure breaks your patch (though I didn't actually > tgl> reinstall the patch to try it): > tgl> Also, even if the row-expansion mechanism is a join, it's certainly > tgl> insufficient to check that the lower-order sort column is an > tgl> expression in variables of the index's table. Something like "f2 + > tgl> random()" is going to need an explicit sort step anyway. > tgl> These particular objections could be worked around by checking for > tgl> set-returning functions and volatile functions in the lower-order > tgl> ORDER BY expressions. But I have to say that I think I'm losing > tgl> faith in the entire idea. I have little confidence that there > tgl> aren't other cases that will break it. > On the other hand, the precondition should be satisfied when all extended > columns are simple Vars of the target table. I believe Vars cannot produce > multiple result. More close checking for every possibility could be done > but it should be a overdone. > The following modification to v7 does this. It seems to me that this would be reasonable at least as the first step and that it would be better to leave more close checking for future work. Thanks, Best regards, Etsuro Fujita
Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> writes:
> The following modification to v7 does this.
> =========
> diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
> index 380f3ba..233e21c 100644
> --- a/src/backend/optimizer/path/pathkeys.c
> +++ b/src/backend/optimizer/path/pathkeys.c
> @@ -536,7 +536,8 @@ index_pathkeys_are_extensible(PlannerInfo *root,
> {
> EquivalenceMember *member = (EquivalenceMember *) lfirst(lc2);
> - if (!bms_equal(member->em_relids, index->rel->relids))
> + if (!bms_equal(member->em_relids, index->rel->relids) ||
> + !IsA(member, Var))
> continue;
> else
> {
> ==========
I'm pretty sure that IsA test prevents the optimization from ever firing.
But aside from hasty typos, is there enough left of this optimization to
be worth the complication?
regards, tom lane
Hello, tgl> I'm pretty sure that IsA test prevents the optimization from ever firing. Thank you. tgl> But aside from hasty typos, Oops! I've picked up wrong node. It always denies pathkeys extension. | !IsA(member, Var)) is a mistake of the following. | !IsA(member->em_expr, Var)) tgl> is there enough left of this optimization to tgl> be worth the complication? Certainly. This patch is intended to be with my another UNION-ALL optimization pathce at first. It does very much with UNION-ORDERBY-LIMIT and also with UNION_ALL(Partitioned tables)-DISTINCT-ORDERBY-LIMIT. ===== test tables create table pu1 (a int not null, b int not null, c int, d text); create unique index i_pu1_ab on pu1 (a, b); create table cu11 (like pu1 including all) inherits (pu1); create table cu12 (like pu1 including all) inherits (pu1); create table pu2 (like pu1 including all); create table cu21 (like pu2 including all) inherits (pu2); create table cu22 (like pu2 including all) inherits (pu2); insert into cu11 (select a / 5, 4 - (a % 5), a, 'cu11' from generate_series(000000, 099999) a); insert into cu12 (select a / 5, 4 - (a % 5), a, 'cu12' from generate_series(100000, 199999) a); insert into cu21 (select a / 5, 4 - (a % 5), a, 'cu21' from generate_series(200000, 299999) a); insert into cu22 (select a / 5, 4 - (a % 5), a, 'cu22' from generate_series(300000, 399999) a); ==== Following example is an implicit union derived from partitioned tables created as above. Limit is added to highlight the effect. 9.4dev with no patch, | =# explain (analyze on, costs off) select distinct * from pu1 order by a, b limit 100; | QUERY PLAN | ---------------------------------------------------------------------------- | Limit (actual time=246.653..246.730 rows=100 loops=1) | -> Unique (actual time=246.646..246.713 rows=100 loops=1) | -> Sort (actual time=246.645..246.666 rows=100 loops=1) | Sort Key: pu1.a, pu1.b, pu1.c, pu1.d | Sort Method: external sort Disk: 5280kB | -> Append (actual time=0.017..52.608 rows=200000 loops=1) | -> Seq Scan on pu1 (actual time=0.001..0.001 rows=0 loops=1) | -> Seq Scan on cu11 (actual time=0.015..17.047 rows=100000 loops=1) | -> Seq Scan on cu12 (actual time=0.007..15.474 rows=100000 loops=1) | Total runtime: 247.854 ms Fairly common query. It will get following plan with this patch. | =# explain (analyze on, costs off) select distinct * from pu1 order by a, b limit 100; | QUERY PLAN | ----------------------------------------------------------------------------- | Limit (actual time=0.108..0.350 rows=100 loops=1) | -> Unique (actual time=0.104..0.329 rows=100 loops=1) | -> Merge Append (actual time=0.103..0.214 rows=100 loops=1) | Sort Key: pu1.a, pu1.b, pu1.c, pu1.d | -> Index Scan .. on pu1 (actual time=0.003..0.003 rows=0 loops=1) | -> Index Scan .. on cu11 (actual time=0.049..0.110 rows=100 loops=1) | -> Index Scan .. on cu12 (actual time=0.044..0.044 rows=1 loops=1) | Total runtime: 0.666 ms The same could be said on union with my another union-pullup patch. We will get the following result with only the union-pullup patch. |=# explain (analyze on, costs off) select * from cu11 union select * from cu12 union select * from cu21 union select * fromcu22 order by a limit 10000; | QUERY PLAN |--------------------------------------------------------------------------- | Limit (actual time=474.825..482.326 rows=10000 loops=1) | -> Unique (actual time=474.824..481.357 rows=10000 loops=1) | -> Sort (actual time=474.823..477.101 rows=10000 loops=1) | Sort Key: cu11.a, cu11.b, cu11.c, cu11.d | Sort Method: external sort Disk: 10568kB | -> Append (actual time=0.018..99.310 rows=400000 loops=1) | -> Seq Scan on cu11 (actual time=0.017..16.263 rows=100000 loops=1) | -> Seq Scan on cu12 (actual time=0.006..14.831 rows=100000 loops=1) | -> Seq Scan on cu21 (actual time=0.006..14.766 rows=100000 loops=1) | -> Seq Scan on cu22 (actual time=0.006..14.721 rows=100000 loops=1) | Total runtime: 484.555 ms This is also a quite common operation but implicit DISTINCT prevents planner from selecting index scans. (ORDER BY is not essential but needed because planner does not consult distinct_pathkeys on planning scans and I've left it as it is.) The planner gives the following plan with this patch. | =# explain (analyze on, costs off) select * from cu11 union select * from cu12 union select * from cu21 union select *from cu22 order by a limit 10000; | QUERY PLAN | ------------------------------------------------------------------------- | Limit (actual time=0.197..14.739 rows=10000 loops=1) | -> Unique (actual time=0.191..13.527 rows=10000 loops=1) | -> Merge Append (actual time=0.191..7.894 rows=10000 loops=1) | Sort Key: cu11.a, cu11.b, cu11.c, cu11.d | -> Index Scan .. on cu11 (actual time=0.054..4.676 rows=10000 loops=1) | -> Index Scan .. on cu12 (actual time=0.045..0.045 rows=1 loops=1) | -> Index Scan .. on cu21 (actual time=0.044..0.044 rows=1 loops=1) | -> Index Scan .. on cu22 (actual time=0.043..0.043 rows=1 loops=1) | Total runtime: 15.872 ms This seems for me worth enough to do. regards, -- Kyotaro Horiguchi NTT Open Source Software Center
Hello, since CF4 is already closed but this patch ramains marked
as 'Ready for Committer', please let me re-post the latest
version for CF4 to get rid of vanishing :-p
> tgl> But aside from hasty typos,
>
> Oops! I've picked up wrong node. It always denies pathkeys extension.
>
> | !IsA(member, Var))
>
> is a mistake of the following.
>
> | !IsA(member->em_expr, Var))
regards,
--
Kyotaro Horiguchi
NTT Open Source Software Center
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 4f63906..b695e40 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -1790,6 +1790,7 @@ _outIndexOptInfo(StringInfo str, const IndexOptInfo *node) WRITE_BOOL_FIELD(predOK);
WRITE_BOOL_FIELD(unique); WRITE_BOOL_FIELD(immediate);
+ WRITE_BOOL_FIELD(allnotnull); WRITE_BOOL_FIELD(hypothetical); /* we don't bother with fields copied from the
pg_amentry */}
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 606734a..0b2f529 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -952,8 +952,11 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, { index_pathkeys =
build_index_pathkeys(root,index, ForwardScanDirection);
- useful_pathkeys = truncate_useless_pathkeys(root, rel,
- index_pathkeys);
+ if (index_pathkeys_are_extensible(root, index, index_pathkeys))
+ useful_pathkeys = root->query_pathkeys;
+ else
+ useful_pathkeys = truncate_useless_pathkeys(root, rel,
+ index_pathkeys); orderbyclauses = NIL;
orderbyclausecols= NIL; }
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 9c8ede6..ad3a8b7 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -502,6 +502,60 @@ build_index_pathkeys(PlannerInfo *root,}/*
+ * index_pathkeys_are_extensible
+ * Check whether the pathkeys are extensible to query_pathkeys.
+ */
+bool
+index_pathkeys_are_extensible(PlannerInfo *root,
+ IndexOptInfo *index,
+ List *pathkeys)
+{
+ bool result;
+ ListCell *lc1;
+
+ if (root->query_pathkeys == NIL || pathkeys == NIL)
+ return false;
+
+ if (!index->unique || !index->immediate || !index->allnotnull)
+ return false;
+
+ if (!pathkeys_contained_in(pathkeys, root->query_pathkeys))
+ return false;
+
+ if (list_length(pathkeys) == list_length(root->query_pathkeys))
+ return true;
+
+ result = true;
+ foreach(lc1, root->query_pathkeys)
+ {
+ PathKey *pathkey = (PathKey *) lfirst(lc1);
+ bool found = false;
+ ListCell *lc2;
+
+ foreach(lc2, pathkey->pk_eclass->ec_members)
+ {
+ EquivalenceMember *member = (EquivalenceMember *) lfirst(lc2);
+
+ if (!bms_equal(member->em_relids, index->rel->relids) ||
+ !IsA(member->em_expr, Var))
+ continue;
+ else
+ {
+ found = true;
+ break;
+ }
+ }
+
+ if (!found)
+ {
+ result = false;
+ break;
+ }
+ }
+ return result;
+}
+
+/* * build_expression_pathkey * Build a pathkeys list that describes an ordering by a single expression *
usingthe given sort operator.
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index de981cb..4e24220 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -333,6 +333,26 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
info->immediate= index->indimmediate; info->hypothetical = false;
+ info->allnotnull = true;
+ for (i = 0; i < ncolumns; i++)
+ {
+ int attrno = info->indexkeys[i];
+
+ if (attrno == 0)
+ {
+ info->allnotnull = false;
+ break;
+ }
+ else if (attrno > 0)
+ {
+ if (!relation->rd_att->attrs[attrno - 1]->attnotnull)
+ {
+ info->allnotnull = false;
+ break;
+ }
+ }
+ }
+ /* * Estimate the index size. If it's not a partial index, we lock * the
number-of-tuplesestimate to equal the parent table; if it
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index a9219e0..d9a3b9b 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -525,6 +525,7 @@ typedef struct IndexOptInfo bool predOK; /* true if predicate matches query */
bool unique; /* true if a unique index */ bool immediate; /* is uniqueness
enforcedimmediately? */
+ bool allnotnull; /* true if index's keys are all not null */ bool hypothetical; /* true
ifindex doesn't really exist */ bool canreturn; /* can index return IndexTuples? */ bool
amcanorderbyop;/* does AM support order by operator result? */
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 999adaa..5ee2e56 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -196,5 +196,8 @@ extern List *truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel,
List *pathkeys);extern bool has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel);
+extern bool index_pathkeys_are_extensible(PlannerInfo *root,
+ IndexOptInfo *index,
+ List *pathkeys);#endif /* PATHS_H */
diff --git a/src/test/isolation/expected/drop-index-concurrently-1.out
b/src/test/isolation/expected/drop-index-concurrently-1.out
index 75dff56..ab96fa0 100644
--- a/src/test/isolation/expected/drop-index-concurrently-1.out
+++ b/src/test/isolation/expected/drop-index-concurrently-1.out
@@ -19,10 +19,8 @@ Sortstep explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seq;QUERY PLAN
-Sort
- Sort Key: id, data
- -> Seq Scan on test_dc
- Filter: ((data)::text = '34'::text)
+Index Scan using test_dc_pkey on test_dc
+ Filter: ((data)::text = '34'::text)step select2: SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;id
data
Hello. May I mark this patch as "Ready for Committer" by myself since this was already marked so in last CF3 and have had no objection or new suggestion in this CF4 for more than a month? At Tue, 14 Jan 2014 18:08:10 +0900, Kyotaro HORIGUCHI wrote > Hello, since CF4 is already closed but this patch ramains marked CF3 > as 'Ready for Committer', please let me re-post the latest > version for CF4 to get rid of vanishing :-p > regards, -- Kyotaro Horiguchi NTT Open Source Software Center
On Tue, Feb 25, 2014 at 3:36 AM, Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> wrote: > May I mark this patch as "Ready for Committer" by myself since > this was already marked so in last CF3 and have had no objection > or new suggestion in this CF4 for more than a month? Sounds fair. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
Hello, At Tue, 25 Feb 2014 16:35:55 -0500, Robert Haas wrote > On Tue, Feb 25, 2014 at 3:36 AM, Kyotaro HORIGUCHI > <horiguchi.kyotaro@lab.ntt.co.jp> wrote: > > May I mark this patch as "Ready for Committer" by myself since > > this was already marked so in last CF3 and have had no objection > > or new suggestion in this CF4 for more than a month? > > Sounds fair. Thank you, I will send this patch to commtters after waiting another few days for more suggestions. regards, -- Kyotaro Horiguchi NTT Open Source Software Center
I marked this patch as 'Ready for Committer' by myself according to the following discussion. Thanks. > At Tue, 25 Feb 2014 16:35:55 -0500, Robert Haas wrote > > On Tue, Feb 25, 2014 at 3:36 AM, Kyotaro HORIGUCHI > > <horiguchi.kyotaro@lab.ntt.co.jp> wrote: > > > May I mark this patch as "Ready for Committer" by myself since > > > this was already marked so in last CF3 and have had no objection > > > or new suggestion in this CF4 for more than a month? > > > > Sounds fair. > > Thank you, I will send this patch to commtters after waiting > another few days for more suggestions. -- Kyotaro Horiguchi NTT Open Source Software Center
Oops! I found a bug in this patch. The previous v8 patch missed
the case that build_index_pathkeys() could build a partial
pathkeys from the index tlist.
This causes the situation follows,
=======
=# \d cu11 Table "public.cu11"Column | Type | Modifiers
--------+---------+-----------a | integer | not nullb | integer | not nullc | integer | d | text
|
Indexes: "cu11_a_b_idx" UNIQUE, btree (a, b)
s=# explain (costs off) select * from cu11 order by a, c ,d; QUERY PLAN
---------------------------------------Index Scan using cu11_a_b_idx on cu11
(1 row)
=======
Where the simple ORDER BY a, c, d on the table with index on
columns (a, b) results simple index scan which cannot perform the
order.
The attached v9 patche is fixed by adding a check for the case
into index_pathkeys_are_extensible(), and rebase to current HEAD.
regards,
--
Kyotaro Horiguchi
NTT Open Source Software Center
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index bfb4b9f..ff5c88c 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -1790,6 +1790,7 @@ _outIndexOptInfo(StringInfo str, const IndexOptInfo *node) WRITE_BOOL_FIELD(predOK);
WRITE_BOOL_FIELD(unique); WRITE_BOOL_FIELD(immediate);
+ WRITE_BOOL_FIELD(allnotnull); WRITE_BOOL_FIELD(hypothetical); /* we don't bother with fields copied from the
pg_amentry */}
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index a912174..4376e95 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -951,8 +951,11 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, { index_pathkeys =
build_index_pathkeys(root,index, ForwardScanDirection);
- useful_pathkeys = truncate_useless_pathkeys(root, rel,
- index_pathkeys);
+ if (index_pathkeys_are_extensible(root, index, index_pathkeys))
+ useful_pathkeys = root->query_pathkeys;
+ else
+ useful_pathkeys = truncate_useless_pathkeys(root, rel,
+ index_pathkeys); orderbyclauses = NIL;
orderbyclausecols= NIL; }
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 9179c61..01479f4 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -502,6 +502,65 @@ build_index_pathkeys(PlannerInfo *root,}/*
+ * index_pathkeys_are_extensible
+ * Check whether the pathkeys are extensible to query_pathkeys.
+ */
+bool
+index_pathkeys_are_extensible(PlannerInfo *root,
+ IndexOptInfo *index,
+ List *pathkeys)
+{
+ bool result;
+ ListCell *lc1;
+
+ if (root->query_pathkeys == NIL || pathkeys == NIL)
+ return false;
+
+ /* This index is not suitable for pathkey extension */
+ if (!index->unique || !index->immediate || !index->allnotnull)
+ return false;
+
+ /* pathkeys is a prefixing proper subset of index tlist */
+ if (list_length(pathkeys) < list_length(index->indextlist))
+ return false;
+
+ if (!pathkeys_contained_in(pathkeys, root->query_pathkeys))
+ return false;
+
+ if (list_length(pathkeys) == list_length(root->query_pathkeys))
+ return true;
+
+ result = true;
+ foreach(lc1, root->query_pathkeys)
+ {
+ PathKey *pathkey = (PathKey *) lfirst(lc1);
+ bool found = false;
+ ListCell *lc2;
+
+ foreach(lc2, pathkey->pk_eclass->ec_members)
+ {
+ EquivalenceMember *member = (EquivalenceMember *) lfirst(lc2);
+
+ if (!bms_equal(member->em_relids, index->rel->relids) ||
+ !IsA(member->em_expr, Var))
+ continue;
+ else
+ {
+ found = true;
+ break;
+ }
+ }
+
+ if (!found)
+ {
+ result = false;
+ break;
+ }
+ }
+ return result;
+}
+
+/* * build_expression_pathkey * Build a pathkeys list that describes an ordering by a single expression *
usingthe given sort operator.
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 73ba2f6..c61cddb 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -333,6 +333,26 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
info->immediate= index->indimmediate; info->hypothetical = false;
+ info->allnotnull = true;
+ for (i = 0; i < ncolumns; i++)
+ {
+ int attrno = info->indexkeys[i];
+
+ if (attrno == 0)
+ {
+ info->allnotnull = false;
+ break;
+ }
+ else if (attrno > 0)
+ {
+ if (!relation->rd_att->attrs[attrno - 1]->attnotnull)
+ {
+ info->allnotnull = false;
+ break;
+ }
+ }
+ }
+ /* * Estimate the index size. If it's not a partial index, we lock * the
number-of-tuplesestimate to equal the parent table; if it
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index c607b36..119bb31 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -525,6 +525,7 @@ typedef struct IndexOptInfo bool predOK; /* true if predicate matches query */
bool unique; /* true if a unique index */ bool immediate; /* is uniqueness
enforcedimmediately? */
+ bool allnotnull; /* true if index's keys are all not null */ bool hypothetical; /* true
ifindex doesn't really exist */ bool canreturn; /* can index return IndexTuples? */ bool
amcanorderbyop;/* does AM support order by operator result? */
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 9b22fda..8abdb99 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -187,5 +187,8 @@ extern List *truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel,
List *pathkeys);extern bool has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel);
+extern bool index_pathkeys_are_extensible(PlannerInfo *root,
+ IndexOptInfo *index,
+ List *pathkeys);#endif /* PATHS_H */
diff --git a/src/test/isolation/expected/drop-index-concurrently-1.out
b/src/test/isolation/expected/drop-index-concurrently-1.out
index 75dff56..ab96fa0 100644
--- a/src/test/isolation/expected/drop-index-concurrently-1.out
+++ b/src/test/isolation/expected/drop-index-concurrently-1.out
@@ -19,10 +19,8 @@ Sortstep explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seq;QUERY PLAN
-Sort
- Sort Key: id, data
- -> Seq Scan on test_dc
- Filter: ((data)::text = '34'::text)
+Index Scan using test_dc_pkey on test_dc
+ Filter: ((data)::text = '34'::text)step select2: SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;id
data
Hi Horiguchi-san, Sorry for not reviewing this patch in the last CF. (2014/03/10 16:21), Kyotaro HORIGUCHI wrote: > Oops! I found a bug in this patch. The previous v8 patch missed > the case that build_index_pathkeys() could build a partial > pathkeys from the index tlist. > > This causes the situation follows, > > ======= > =# \d cu11 > Table "public.cu11" > Column | Type | Modifiers > --------+---------+----------- > a | integer | not null > b | integer | not null > c | integer | > d | text | > Indexes: > "cu11_a_b_idx" UNIQUE, btree (a, b) > > s=# explain (costs off) select * from cu11 order by a, c ,d; > QUERY PLAN > --------------------------------------- > Index Scan using cu11_a_b_idx on cu11 > (1 row) > ======= > > Where the simple ORDER BY a, c, d on the table with index on > columns (a, b) results simple index scan which cannot perform the > order. > > The attached v9 patche is fixed by adding a check for the case > into index_pathkeys_are_extensible(), and rebase to current HEAD. Good catch! ISTM that the biggest concern about this patch would be whether it's worth complicating the code, because the range of application of the patch is not so wide as is. So, all we need to do is show important use cases that prove the effectiveness of the patch. Sorry, I can't come up with a good idea, though. Thanks, Best regards, Etsuro Fujita
Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> writes:
> Oops! I found a bug in this patch. The previous v8 patch missed
> the case that build_index_pathkeys() could build a partial
> pathkeys from the index tlist.
TBH I think that's barely the tip of the iceberg of cases where this
patch will get the wrong answer. It looks like it thinks that *any*
Var belonging to the indexed relation must be the same one indexed
by the index. Also, I don't see it doing anything to check the ordering
of multiple index columns --- for instance, an index on (a,b) and one
on (b,a) would both pass or fail identically, though surely only one
should match "ORDER BY a,b,...". Also, what's with the success return
before the loop:
+ if (list_length(pathkeys) == list_length(root->query_pathkeys))
+ return true;
At this point you haven't proven *anything at all* about whether the
index columns have something to do with the query_pathkeys.
regards, tom lane
(2014/04/10 0:08), Tom Lane wrote: > Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> writes: >> Oops! I found a bug in this patch. The previous v8 patch missed >> the case that build_index_pathkeys() could build a partial >> pathkeys from the index tlist. > > TBH I think that's barely the tip of the iceberg of cases where this > patch will get the wrong answer. > Also, I don't see it doing anything to check the ordering > of multiple index columns I think that the following code in index_pathkeys_are_extensible() would check the ordering: + if (!pathkeys_contained_in(pathkeys, root->query_pathkeys)) + return false; > Also, what's with the success return > before the loop: > > + if (list_length(pathkeys) == list_length(root->query_pathkeys)) > + return true; > > At this point you haven't proven *anything at all* about whether the > index columns have something to do with the query_pathkeys. I think that the two pathkeys would be proved to be equal, if the both conditions are satisfied. Thanks, Best regards, Etsuro Fujita
Etsuro Fujita <fujita.etsuro@lab.ntt.co.jp> writes:
> (2014/04/10 0:08), Tom Lane wrote:
>> TBH I think that's barely the tip of the iceberg of cases where this
>> patch will get the wrong answer.
>> Also, I don't see it doing anything to check the ordering
>> of multiple index columns
> I think that the following code in index_pathkeys_are_extensible() would
> check the ordering:
> + if (!pathkeys_contained_in(pathkeys, root->query_pathkeys))
> + return false;
Hm ... if you're relying on that, then what's the point of the new loop
at all?
regards, tom lane
(2014/04/10 22:25), Tom Lane wrote: > Etsuro Fujita <fujita.etsuro@lab.ntt.co.jp> writes: >> (2014/04/10 0:08), Tom Lane wrote: >>> TBH I think that's barely the tip of the iceberg of cases where this >>> patch will get the wrong answer. > >>> Also, I don't see it doing anything to check the ordering >>> of multiple index columns > >> I think that the following code in index_pathkeys_are_extensible() would >> check the ordering: >> + if (!pathkeys_contained_in(pathkeys, root->query_pathkeys)) >> + return false; > > Hm ... if you're relying on that, then what's the point of the new loop > at all? The point is that from the discussion [1], we allow the index pathkeys to be extended to query_pathkeys if each *remaining* pathkey in query_pathkey is a Var belonging to the indexed relation. The code is confusing, though. Sorry, that is my faults. Thanks, [1] http://www.postgresql.org/message-id/29637.1389064686@sss.pgh.pa.us Best regards, Etsuro Fujita
Hi, sorry for the absense. I've been back. Attached is the patch following the discussion below. > >> (2014/04/10 0:08), Tom Lane wrote: > >>> TBH I think that's barely the tip of the iceberg of cases where this > >>> patch will get the wrong answer. > > > >>> Also, I don't see it doing anything to check the ordering > >>> of multiple index columns > > > >> I think that the following code in index_pathkeys_are_extensible() would > >> check the ordering: > >> + if (!pathkeys_contained_in(pathkeys, root->query_pathkeys)) > >> + return false; > > > > Hm ... if you're relying on that, then what's the point of the new loop > > at all? > > The point is that from the discussion [1], we allow the index pathkeys > to be extended to query_pathkeys if each *remaining* pathkey in > query_pathkey is a Var belonging to the indexed relation. The code is > confusing, though. Sorry, that is my faults. Hmm, I found that the iterations for the part that already checked by pathkeys_contained_in are not only needless but a bit heavy. And the loop seems a little verbose. I did for the patch, in index_pathkeys_are_extensible, - Avoiding duplicate check with pathkeys_contained_in. I put similar code to list_nth_cell since it is not exposed outside of list.c. - Add comment to clarify the purpose of the loop. - Simplify the check for the "remaining" keycolumns > Thanks, > > [1] http://www.postgresql.org/message-id/29637.1389064686@sss.pgh.pa.us > > Best regards, > Etsuro Fujita > > > -- > Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) > To make changes to your subscription: > http://www.postgresql.org/mailpref/pgsql-hackers
# Sorry for accidentialy sending the previous mail unfinished.
## ...and I seem to have bombed uncertain files off out of my
## home directory by accident, too :(
=====
Hi, sorry for the absense. I've been back.
Thank you for continuing this discussion.
Attached is the patch following the discussion below.
> >> (2014/04/10 0:08), Tom Lane wrote:
> >>> TBH I think that's barely the tip of the iceberg of cases where this
> >>> patch will get the wrong answer.
> >
> >>> Also, I don't see it doing anything to check the ordering
> >>> of multiple index columns
> >
> >> I think that the following code in index_pathkeys_are_extensible() would
> >> check the ordering:
> >> + if (!pathkeys_contained_in(pathkeys, root->query_pathkeys))
> >> + return false;
> >
> > Hm ... if you're relying on that, then what's the point of the new loop
> > at all?
>
> The point is that from the discussion [1], we allow the index pathkeys
> to be extended to query_pathkeys if each *remaining* pathkey in
> query_pathkey is a Var belonging to the indexed relation. The code is
> confusing, though. Sorry, that is my faults.
Hmm, I found that the iterations for the part that already
checked by pathkeys_contained_in are not only useless but a bit
heavy. And the loop seems a little verbose. I did for the patch,
in index_pathkeys_are_extensible,
- Avoiding duplicate check with pathkeys_contained_in.
I put similar code to list_nth_cell since it is not exposed outside of list.c.
- Add comment to clarify the purpose of the loop.
- Simplify the check for the "remaining" keycolumns
I think this makes some things clearer.
regards,
--
Kyotaro Horiguchi
NTT Open Source Software Center
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index bfb4b9f..ff5c88c 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -1790,6 +1790,7 @@ _outIndexOptInfo(StringInfo str, const IndexOptInfo *node) WRITE_BOOL_FIELD(predOK);
WRITE_BOOL_FIELD(unique); WRITE_BOOL_FIELD(immediate);
+ WRITE_BOOL_FIELD(allnotnull); WRITE_BOOL_FIELD(hypothetical); /* we don't bother with fields copied from the
pg_amentry */}
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index a912174..4376e95 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -951,8 +951,11 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, { index_pathkeys =
build_index_pathkeys(root,index, ForwardScanDirection);
- useful_pathkeys = truncate_useless_pathkeys(root, rel,
- index_pathkeys);
+ if (index_pathkeys_are_extensible(root, index, index_pathkeys))
+ useful_pathkeys = root->query_pathkeys;
+ else
+ useful_pathkeys = truncate_useless_pathkeys(root, rel,
+ index_pathkeys); orderbyclauses = NIL;
orderbyclausecols= NIL; }
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 9179c61..5edca4f 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -502,6 +502,76 @@ build_index_pathkeys(PlannerInfo *root,}/*
+ * index_pathkeys_are_extensible
+ * Check whether the pathkeys are extensible to query_pathkeys.
+ */
+bool
+index_pathkeys_are_extensible(PlannerInfo *root,
+ IndexOptInfo *index,
+ List *pathkeys)
+{
+ bool result;
+ ListCell *lc1, *remain;
+
+ if (root->query_pathkeys == NIL || pathkeys == NIL)
+ return false;
+
+ /* This index is not suitable for pathkey extension */
+ if (!index->unique || !index->immediate || !index->allnotnull)
+ return false;
+
+ /* pathkeys is a prefixing proper subset of index tlist */
+ if (list_length(pathkeys) < list_length(index->indextlist))
+ return false;
+
+ if (!pathkeys_contained_in(pathkeys, root->query_pathkeys))
+ return false;
+
+ if (list_length(pathkeys) == list_length(root->query_pathkeys))
+ return true;
+
+ Assert(list_length(root->query_pathkeys) > list_length(pathkeys));
+
+ /*
+ * Check if all unchecked elements of query_patheys are simple Vars for
+ * the same relation.
+ */
+
+ /* list_nth_cell is not exposed publicly.. */
+ if (list_length(pathkeys) == list_length(root->query_pathkeys) - 1)
+ remain = list_tail(root->query_pathkeys);
+ else
+ {
+ int n = list_length(pathkeys);
+
+ remain = root->query_pathkeys->head;
+ while(n-- > 0) remain = remain->next;
+ }
+
+ result = true;
+ for_each_cell(lc1, remain)
+ {
+ PathKey *pathkey = (PathKey *) lfirst(lc1);
+ ListCell *lc2;
+
+ foreach(lc2, pathkey->pk_eclass->ec_members)
+ {
+ EquivalenceMember *member = (EquivalenceMember *) lfirst(lc2);
+
+ if (!bms_equal(member->em_relids, index->rel->relids) ||
+ !IsA(member->em_expr, Var))
+ {
+ result = false;
+ break;
+ }
+ }
+
+ if (!result) break;
+ }
+ return result;
+}
+
+/* * build_expression_pathkey * Build a pathkeys list that describes an ordering by a single expression *
usingthe given sort operator.
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 73ba2f6..c61cddb 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -333,6 +333,26 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
info->immediate= index->indimmediate; info->hypothetical = false;
+ info->allnotnull = true;
+ for (i = 0; i < ncolumns; i++)
+ {
+ int attrno = info->indexkeys[i];
+
+ if (attrno == 0)
+ {
+ info->allnotnull = false;
+ break;
+ }
+ else if (attrno > 0)
+ {
+ if (!relation->rd_att->attrs[attrno - 1]->attnotnull)
+ {
+ info->allnotnull = false;
+ break;
+ }
+ }
+ }
+ /* * Estimate the index size. If it's not a partial index, we lock * the
number-of-tuplesestimate to equal the parent table; if it
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index c607b36..119bb31 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -525,6 +525,7 @@ typedef struct IndexOptInfo bool predOK; /* true if predicate matches query */
bool unique; /* true if a unique index */ bool immediate; /* is uniqueness
enforcedimmediately? */
+ bool allnotnull; /* true if index's keys are all not null */ bool hypothetical; /* true
ifindex doesn't really exist */ bool canreturn; /* can index return IndexTuples? */ bool
amcanorderbyop;/* does AM support order by operator result? */
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 9b22fda..8abdb99 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -187,5 +187,8 @@ extern List *truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel,
List *pathkeys);extern bool has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel);
+extern bool index_pathkeys_are_extensible(PlannerInfo *root,
+ IndexOptInfo *index,
+ List *pathkeys);#endif /* PATHS_H */
diff --git a/src/test/isolation/expected/drop-index-concurrently-1.out
b/src/test/isolation/expected/drop-index-concurrently-1.out
index 75dff56..ab96fa0 100644
--- a/src/test/isolation/expected/drop-index-concurrently-1.out
+++ b/src/test/isolation/expected/drop-index-concurrently-1.out
@@ -19,10 +19,8 @@ Sortstep explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seq;QUERY PLAN
-Sort
- Sort Key: id, data
- -> Seq Scan on test_dc
- Filter: ((data)::text = '34'::text)
+Index Scan using test_dc_pkey on test_dc
+ Filter: ((data)::text = '34'::text)step select2: SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;id
data
Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> writes:
> [ pathkey_and_uniqueindx_v10_20130411.patch ]
I thought some more about this patch, and realized that it's more or less
morally equivalent to allowing references to ungrouped variables when the
query has a GROUP BY clause listing all the columns of the primary key.
In that case the parser is effectively pretending that the GROUP BY list
contains additional implicit entries that are functionally dependent on
the entries that are actually there. In this patch, what we want to do
is recognize that trailing entries in an ORDER BY list are semantically
no-ops and can be ignored because they are functionally dependent on
earlier entries.
Now, the reason that the parser restricts the functional dependency
deduction to a primary key is that it wants to be able to identify a
constraint OID that the query is dependent on to be semantically valid.
In this case, we don't need such an OID, so just finding any old unique
index on not-null columns is good enough. (If someone drops the index,
the optimization might become incorrect, but that would force replanning
anyway.)
However, this way of thinking about it shows that the patch is missing
possible optimizations. If we have "ORDER BY a, b, c" and (a,b) is the
primary key, then including c in the ORDER BY list is semantically
redundant, *whether or not we use an indexscan on the pkey index at all*.
More: if we have "ORDER BY a, b, c" and the primary key is (b,a), we
can still discard c from the sort requirement, even though the pkey
index as such isn't helpful for producing the required order.
So hacking up the pathkeys attributed to the indexscan is the wrong thing.
Rather, what we should be looking to do is decide that c is a useless
pathkey and remove it from the query_pathkeys, much as we'd do if we found
"c = constant" in WHERE. That would allow optimization of other query
plans besides scan-the-pkey-index plans.
regards, tom lane
Hello, > I thought some more about this patch, and realized that it's more or less > morally equivalent to allowing references to ungrouped variables when the > query has a GROUP BY clause listing all the columns of the primary key. > In that case the parser is effectively pretending that the GROUP BY list > contains additional implicit entries that are functionally dependent on > the entries that are actually there. In this patch, what we want to do > is recognize that trailing entries in an ORDER BY list are semantically > no-ops and can be ignored because they are functionally dependent on > earlier entries. Ah, that sounds smarter than extending pathekys. I feel it preferable. > Now, the reason that the parser restricts the functional dependency > deduction to a primary key is that it wants to be able to identify a > constraint OID that the query is dependent on to be semantically valid. > In this case, we don't need such an OID, so just finding any old unique > index on not-null columns is good enough. (If someone drops the index, > the optimization might become incorrect, but that would force replanning > anyway.) Agreed, > However, this way of thinking about it shows that the patch is missing > possible optimizations. If we have "ORDER BY a, b, c" and (a,b) is the > primary key, then including c in the ORDER BY list is semantically > redundant, *whether or not we use an indexscan on the pkey index at all*. > More: if we have "ORDER BY a, b, c" and the primary key is (b,a), we > can still discard c from the sort requirement, even though the pkey > index as such isn't helpful for producing the required order. Hmm yes, it really seems expectable. > So hacking up the pathkeys attributed to the indexscan is the wrong thing. > Rather, what we should be looking to do is decide that c is a useless > pathkey and remove it from the query_pathkeys, much as we'd do if we found > "c = constant" in WHERE. That would allow optimization of other query > plans besides scan-the-pkey-index plans. Ok, I am convinced that your suggestion - truncating query_pathkeys by removing eventually no-op entries - seems preferable and will have wider effect naturally - more promised. I won't persist with the way this patch currently does but the new patch of course can't come up within this CF. I will agree if you decide to make this patch 'Returned with Feedback'. (I feel a little sad for 'Rejected' but you can justly do that if you think that the patch comming up next is utterly different from this one:() regards, -- Kyotaro Horiguchi NTT Open Source Software Center
Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> writes:
> Ok, I am convinced that your suggestion - truncating
> query_pathkeys by removing eventually no-op entries - seems
> preferable and will have wider effect naturally - more promised.
> I won't persist with the way this patch currently does but the
> new patch of course can't come up within this CF. I will agree if
> you decide to make this patch 'Returned with Feedback'. (I feel a
> little sad for 'Rejected' but you can justly do that if you think
> that the patch comming up next is utterly different from this
> one:()
I marked it as "returned with feedback".
regards, tom lane