partial-sort-merge-2.patch
application/octet-stream
Filename: partial-sort-merge-2.patch
Type: application/octet-stream
Part: 1
Message:
Re: PoC: Partial sort
Patch
Format: unified
| File | + | − |
|---|---|---|
| src/backend/optimizer/path/joinpath.c | 0 | 0 |
| src/backend/optimizer/path/pathkeys.c | 0 | 0 |
| src/include/optimizer/paths.h | 0 | 0 |
| src/test/regress/expected/join.out | 0 | 0 |
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
new file mode 100644
index 7bbad4f..c1590aa
*** a/src/backend/optimizer/path/joinpath.c
--- b/src/backend/optimizer/path/joinpath.c
*************** sort_inner_and_outer(PlannerInfo *root,
*** 662,668 ****
cur_mergeclauses = find_mergeclauses_for_pathkeys(root,
outerkeys,
true,
! mergeclause_list);
/* Should have used them all... */
Assert(list_length(cur_mergeclauses) == list_length(mergeclause_list));
--- 662,672 ----
cur_mergeclauses = find_mergeclauses_for_pathkeys(root,
outerkeys,
true,
! mergeclause_list,
! NULL,
! NULL,
! NULL,
! outer_path->rows);
/* Should have used them all... */
Assert(list_length(cur_mergeclauses) == list_length(mergeclause_list));
*************** match_unsorted_outer(PlannerInfo *root,
*** 832,837 ****
--- 836,842 ----
List *mergeclauses;
List *innersortkeys;
List *trialsortkeys;
+ List *outersortkeys;
Path *cheapest_startup_inner;
Path *cheapest_total_inner;
int num_sortkeys;
*************** match_unsorted_outer(PlannerInfo *root,
*** 937,943 ****
mergeclauses = find_mergeclauses_for_pathkeys(root,
outerpath->pathkeys,
true,
! mergeclause_list);
/*
* Done with this outer path if no chance for a mergejoin.
--- 942,952 ----
mergeclauses = find_mergeclauses_for_pathkeys(root,
outerpath->pathkeys,
true,
! mergeclause_list,
! joinrel,
! &outersortkeys,
! sjinfo,
! outerpath->rows);
/*
* Done with this outer path if no chance for a mergejoin.
*************** match_unsorted_outer(PlannerInfo *root,
*** 961,967 ****
/* Compute the required ordering of the inner path */
innersortkeys = make_inner_pathkeys_for_merge(root,
mergeclauses,
! outerpath->pathkeys);
/*
* Generate a mergejoin on the basis of sorting the cheapest inner.
--- 970,976 ----
/* Compute the required ordering of the inner path */
innersortkeys = make_inner_pathkeys_for_merge(root,
mergeclauses,
! outersortkeys);
/*
* Generate a mergejoin on the basis of sorting the cheapest inner.
*************** match_unsorted_outer(PlannerInfo *root,
*** 980,986 ****
restrictlist,
merge_pathkeys,
mergeclauses,
! NIL,
innersortkeys);
/* Can't do anything else if inner path needs to be unique'd */
--- 989,995 ----
restrictlist,
merge_pathkeys,
mergeclauses,
! outersortkeys,
innersortkeys);
/* Can't do anything else if inner path needs to be unique'd */
*************** match_unsorted_outer(PlannerInfo *root,
*** 1038,1044 ****
for (sortkeycnt = num_sortkeys; sortkeycnt > 0; sortkeycnt--)
{
Path *innerpath;
- List *newclauses = NIL;
/*
* Look for an inner path ordered well enough for the first
--- 1047,1052 ----
*************** match_unsorted_outer(PlannerInfo *root,
*** 1055,1073 ****
compare_path_costs(innerpath, cheapest_total_inner,
TOTAL_COST) < 0))
{
- /* Found a cheap (or even-cheaper) sorted path */
- /* Select the right mergeclauses, if we didn't already */
- if (sortkeycnt < num_sortkeys)
- {
- newclauses =
- find_mergeclauses_for_pathkeys(root,
- trialsortkeys,
- false,
- mergeclauses);
- Assert(newclauses != NIL);
- }
- else
- newclauses = mergeclauses;
try_mergejoin_path(root,
joinrel,
jointype,
--- 1063,1068 ----
*************** match_unsorted_outer(PlannerInfo *root,
*** 1078,1086 ****
innerpath,
restrictlist,
merge_pathkeys,
! newclauses,
! NIL,
! NIL);
cheapest_total_inner = innerpath;
}
/* Same on the basis of cheapest startup cost ... */
--- 1073,1081 ----
innerpath,
restrictlist,
merge_pathkeys,
! mergeclauses,
! outersortkeys,
! innersortkeys);
cheapest_total_inner = innerpath;
}
/* Same on the basis of cheapest startup cost ... */
*************** match_unsorted_outer(PlannerInfo *root,
*** 1096,1119 ****
/* Found a cheap (or even-cheaper) sorted path */
if (innerpath != cheapest_total_inner)
{
- /*
- * Avoid rebuilding clause list if we already made one;
- * saves memory in big join trees...
- */
- if (newclauses == NIL)
- {
- if (sortkeycnt < num_sortkeys)
- {
- newclauses =
- find_mergeclauses_for_pathkeys(root,
- trialsortkeys,
- false,
- mergeclauses);
- Assert(newclauses != NIL);
- }
- else
- newclauses = mergeclauses;
- }
try_mergejoin_path(root,
joinrel,
jointype,
--- 1091,1096 ----
*************** match_unsorted_outer(PlannerInfo *root,
*** 1124,1132 ****
innerpath,
restrictlist,
merge_pathkeys,
! newclauses,
! NIL,
! NIL);
}
cheapest_startup_inner = innerpath;
}
--- 1101,1109 ----
innerpath,
restrictlist,
merge_pathkeys,
! mergeclauses,
! outersortkeys,
! innersortkeys);
}
cheapest_startup_inner = innerpath;
}
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
new file mode 100644
index 6ac28c4..15daba2
*** a/src/backend/optimizer/path/pathkeys.c
--- b/src/backend/optimizer/path/pathkeys.c
*************** update_mergeclause_eclasses(PlannerInfo
*** 1055,1060 ****
--- 1055,1079 ----
restrictinfo->right_ec = restrictinfo->right_ec->ec_merged;
}
+ typedef struct
+ {
+ Selectivity selec;
+ RestrictInfo *rinfo;
+ } UnusedRestrictInfo;
+
+ static int
+ cmpUnusedRestrictInfo(const void *a1, const void *a2)
+ {
+ Selectivity s1 = ((const UnusedRestrictInfo *)a1)->selec;
+ Selectivity s2 = ((const UnusedRestrictInfo *)a2)->selec;
+
+ if (s1 < s2)
+ return 1;
+ if (s1 > s2)
+ return -1;
+ return 0;
+ }
+
/*
* find_mergeclauses_for_pathkeys
* This routine attempts to find a set of mergeclauses that can be
*************** update_mergeclause_eclasses(PlannerInfo
*** 1066,1071 ****
--- 1085,1091 ----
* FALSE if for inner.
* 'restrictinfos' is a list of mergejoinable restriction clauses for the
* join relation being formed.
+ * 'outersortkeys' is additional pathkeys proposed to fit mergeclauses.
*
* The restrictinfos must be marked (via outer_is_left) to show which side
* of each clause is associated with the current outer path. (See
*************** List *
*** 1078,1087 ****
find_mergeclauses_for_pathkeys(PlannerInfo *root,
List *pathkeys,
bool outer_keys,
! List *restrictinfos)
{
List *mergeclauses = NIL;
ListCell *i;
/* make sure we have eclasses cached in the clauses */
foreach(i, restrictinfos)
--- 1098,1115 ----
find_mergeclauses_for_pathkeys(PlannerInfo *root,
List *pathkeys,
bool outer_keys,
! List *restrictinfos,
! RelOptInfo *joinrel,
! List **outersortkeys,
! SpecialJoinInfo *sjinfo,
! double rows)
{
List *mergeclauses = NIL;
ListCell *i;
+ bool *used = (bool *)palloc0(sizeof(bool) * list_length(restrictinfos));
+ int k;
+ List *usedPathkeys = NIL;
+ Selectivity selec = 1.0, targetSelec = 2.0 / rows;
/* make sure we have eclasses cached in the clauses */
foreach(i, restrictinfos)
*************** find_mergeclauses_for_pathkeys(PlannerIn
*** 1134,1139 ****
--- 1162,1168 ----
* deal with the case in create_mergejoin_plan().
*----------
*/
+ k = 0;
foreach(j, restrictinfos)
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
*************** find_mergeclauses_for_pathkeys(PlannerIn
*** 1146,1152 ****
--- 1175,1186 ----
clause_ec = rinfo->outer_is_left ?
rinfo->right_ec : rinfo->left_ec;
if (clause_ec == pathkey_ec)
+ {
+ selec *= clause_selectivity(root, (Node *)rinfo, 0, JOIN_INNER, sjinfo);
matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
+ used[k] = true;
+ }
+ k++;
}
/*
*************** find_mergeclauses_for_pathkeys(PlannerIn
*** 1157,1162 ****
--- 1191,1198 ----
if (matched_restrictinfos == NIL)
break;
+ usedPathkeys = lappend(usedPathkeys, pathkey);
+
/*
* If we did find usable mergeclause(s) for this sort-key position,
* add them to result list.
*************** find_mergeclauses_for_pathkeys(PlannerIn
*** 1164,1169 ****
--- 1200,1272 ----
mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
}
+ /*
+ * Try to fill outersortkeys if caller requires it.
+ */
+ if (outersortkeys)
+ {
+ List *addPathkeys, *addMergeclauses, *addRestrictinfos = NIL;
+ UnusedRestrictInfo *unusedRestrictinfos;
+ int unusedRestrictinfosCount = 0, j;
+
+ *outersortkeys = pathkeys;
+
+ if (!mergeclauses || selec <= targetSelec)
+ return mergeclauses;
+
+ /*
+ * Find restrictions unused by given pathkeys.
+ */
+ unusedRestrictinfos = (UnusedRestrictInfo *)palloc(
+ sizeof(UnusedRestrictInfo) * list_length(restrictinfos));
+ k = 0;
+ foreach(i, restrictinfos)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
+ if (!used[k])
+ {
+ unusedRestrictinfos[unusedRestrictinfosCount].rinfo = rinfo;
+ unusedRestrictinfos[unusedRestrictinfosCount++].selec =
+ clause_selectivity(root, (Node *)rinfo, 0, JOIN_INNER, sjinfo);
+ }
+ k++;
+ }
+ qsort(unusedRestrictinfos, unusedRestrictinfosCount,
+ sizeof(UnusedRestrictInfo), cmpUnusedRestrictInfo);
+ for (j = 0; j < unusedRestrictinfosCount; j++)
+ {
+ selec *= unusedRestrictinfos[j].selec;
+ addRestrictinfos = lappend(addRestrictinfos,
+ unusedRestrictinfos[j].rinfo);
+ if (selec <= targetSelec)
+ break;
+ }
+
+ if (!addRestrictinfos)
+ return mergeclauses;
+
+ /*
+ * Generate pathkeys based on those restrictions.
+ */
+ addPathkeys = select_outer_pathkeys_for_merge(root,
+ addRestrictinfos, joinrel);
+
+ if (!addPathkeys)
+ return mergeclauses;
+
+ /*
+ * Do recursive call to find mergeclauses for additional proposed
+ * pathkeys. We pass NULL to outersortkeys, so there is only one level
+ * of recursion.
+ */
+ addMergeclauses = find_mergeclauses_for_pathkeys(root,
+ addPathkeys, true, addRestrictinfos, NULL, NULL, NULL, rows);
+
+ *outersortkeys = list_concat(usedPathkeys, addPathkeys);
+ mergeclauses = list_concat(mergeclauses, addMergeclauses);
+
+ }
+
return mergeclauses;
}
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
new file mode 100644
index 9179b4e..f4ccb3c
*** a/src/include/optimizer/paths.h
--- b/src/include/optimizer/paths.h
*************** extern void update_mergeclause_eclasses(
*** 179,185 ****
extern List *find_mergeclauses_for_pathkeys(PlannerInfo *root,
List *pathkeys,
bool outer_keys,
! List *restrictinfos);
extern List *select_outer_pathkeys_for_merge(PlannerInfo *root,
List *mergeclauses,
RelOptInfo *joinrel);
--- 179,189 ----
extern List *find_mergeclauses_for_pathkeys(PlannerInfo *root,
List *pathkeys,
bool outer_keys,
! List *restrictinfos,
! RelOptInfo *joinrel,
! List **outerpathkeys,
! SpecialJoinInfo *sjinfo,
! double rows);
extern List *select_outer_pathkeys_for_merge(PlannerInfo *root,
List *mergeclauses,
RelOptInfo *joinrel);
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
new file mode 100644
index 2501184..f9aed86
*** a/src/test/regress/expected/join.out
--- b/src/test/regress/expected/join.out
*************** select c.*,a.*,ss1.q1,ss2.q1,ss3.* from
*** 4198,4239 ****
lateral (select q1, coalesce(ss1.x,q2) as y from int8_tbl d) ss2
) on c.q2 = ss2.q1,
lateral (select * from int4_tbl i where ss2.y > f1) ss3;
! QUERY PLAN
! ---------------------------------------------------------------------------------------------------------
! Nested Loop
Output: c.q1, c.q2, a.q1, a.q2, b.q1, d.q1, i.f1
! Join Filter: ((COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2)) > i.f1)
! -> Hash Right Join
! Output: c.q1, c.q2, a.q1, a.q2, b.q1, d.q1, (COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2))
! Hash Cond: (d.q1 = c.q2)
! -> Nested Loop
! Output: a.q1, a.q2, b.q1, d.q1, (COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2))
! -> Hash Right Join
! Output: a.q1, a.q2, b.q1, (COALESCE(b.q2, (b2.f1)::bigint))
! Hash Cond: (b.q1 = a.q2)
! -> Nested Loop
! Output: b.q1, COALESCE(b.q2, (b2.f1)::bigint)
! Join Filter: (b.q1 < b2.f1)
! -> Seq Scan on public.int8_tbl b
! Output: b.q1, b.q2
! -> Materialize
Output: b2.f1
! -> Seq Scan on public.int4_tbl b2
! Output: b2.f1
! -> Hash
Output: a.q1, a.q2
! -> Seq Scan on public.int8_tbl a
! Output: a.q1, a.q2
! -> Seq Scan on public.int8_tbl d
! Output: d.q1, COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2)
! -> Hash
! Output: c.q1, c.q2
-> Seq Scan on public.int8_tbl c
Output: c.q1, c.q2
! -> Materialize
! Output: i.f1
! -> Seq Scan on public.int4_tbl i
! Output: i.f1
(34 rows)
-- check processing of postponed quals (bug #9041)
--- 4198,4239 ----
lateral (select q1, coalesce(ss1.x,q2) as y from int8_tbl d) ss2
) on c.q2 = ss2.q1,
lateral (select * from int4_tbl i where ss2.y > f1) ss3;
! QUERY PLAN
! ---------------------------------------------------------------------------------------------
! Hash Right Join
Output: c.q1, c.q2, a.q1, a.q2, b.q1, d.q1, i.f1
! Hash Cond: (d.q1 = c.q2)
! Filter: ((COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2)) > i.f1)
! -> Nested Loop
! Output: a.q1, a.q2, b.q1, d.q1, (COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2))
! -> Hash Right Join
! Output: a.q1, a.q2, b.q1, (COALESCE(b.q2, (b2.f1)::bigint))
! Hash Cond: (b.q1 = a.q2)
! -> Nested Loop
! Output: b.q1, COALESCE(b.q2, (b2.f1)::bigint)
! Join Filter: (b.q1 < b2.f1)
! -> Seq Scan on public.int8_tbl b
! Output: b.q1, b.q2
! -> Materialize
! Output: b2.f1
! -> Seq Scan on public.int4_tbl b2
Output: b2.f1
! -> Hash
! Output: a.q1, a.q2
! -> Seq Scan on public.int8_tbl a
Output: a.q1, a.q2
! -> Seq Scan on public.int8_tbl d
! Output: d.q1, COALESCE((COALESCE(b.q2, (b2.f1)::bigint)), d.q2)
! -> Hash
! Output: c.q1, c.q2, i.f1
! -> Nested Loop
! Output: c.q1, c.q2, i.f1
-> Seq Scan on public.int8_tbl c
Output: c.q1, c.q2
! -> Materialize
! Output: i.f1
! -> Seq Scan on public.int4_tbl i
! Output: i.f1
(34 rows)
-- check processing of postponed quals (bug #9041)