Skip to content

Commit 0ff2733

Browse files
bmomjianbmomjian
committed
Update pathkeys comparison function.
1 parent 148ec3b commit 0ff2733

File tree

3 files changed

+57
-49
lines changed

3 files changed

+57
-49
lines changed

‎src/backend/optimizer/path/pathkeys.c

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
*
88
*
99
* IDENTIFICATION
10-
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.3 1999/02/20 16:32:35 momjian Exp $
10+
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.4 1999/02/20 18:01:01 momjian Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -54,7 +54,7 @@ static List *new_matching_subkeys(Var *subkey, List *considered_subkeys,
5454
* { {tab1.col1, tab2.col1} }. This allows future joins to use either Var
5555
* as a pre-sorted key to prevent Mergejoins from having to re-sort the Path.
5656
* They are equal, so they are both primary sort keys. This is why pathkeys
57-
* is a List of Lists.
57+
* is a List of Lists. -- bjm
5858
*/
5959

6060
/****************************************************************************

‎src/backend/optimizer/util/keys.c

Lines changed: 42 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
*
88
*
99
* IDENTIFICATION
10-
* $Header: /cvsroot/pgsql/src/backend/optimizer/util/Attic/keys.c,v 1.18 1999/02/19 02:05:16 momjian Exp $
10+
* $Header: /cvsroot/pgsql/src/backend/optimizer/util/Attic/keys.c,v 1.19 1999/02/20 18:01:02 momjian Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -110,62 +110,70 @@ extract_join_key(JoinKey *jk, int outer_or_inner)
110110
* Returns t iff two sets of path keys are equivalent. They are
111111
* equivalent if the first Var nodes match the second Var nodes.
112112
*
113-
* XXX It isn't necessary to check that each sublist exactly contain
114-
* the same elements because if the routine that built these
115-
* sublists together is correct, having one element in common
116-
* implies having all elements in common.
117-
* Huh? bjm
113+
* See the top of optimizer/path/pathkeys.c for a description of pathkeys.
114+
* Each pathkey is ordered by its join order, so they not pre-ordered to
115+
* match. We must search them ourselves.
118116
*
117+
* This gets called a lot, so it is optimized.
119118
*/
120119
bool
121120
pathkeys_match(List *keys1, List *keys2, int *better_key)
122121
{
123122
List *key1,
124-
*key2,
125-
*key1a,
126-
*key2a;
123+
*key2;
124+
bool key1_subsetof_key2 = true,
125+
key2_subsetof_key1 = true;
127126

128127
for (key1 = keys1, key2 = keys2;
129128
key1 != NIL && key2 != NIL;
130129
key1 = lnext(key1), key2 = lnext(key2))
131130
{
132-
for (key1a = lfirst(key1), key2a = lfirst(key2);
133-
key1a != NIL && key2a != NIL;
134-
key1a = lnext(key1a), key2a = lnext(key2a))
135-
if (!equal(lfirst(key1a), lfirst(key2a)))
131+
List *i;
132+
133+
if (key1_subsetof_key2)
134+
foreach(i, lfirst(key1))
136135
{
137-
*better_key = 0;
138-
return false;
136+
Var *subkey = lfirst(i);
137+
if (!member(subkey, lfirst(key2)))
138+
{
139+
key1_subsetof_key2 = false;
140+
break;
141+
}
139142
}
140-
if (key1a != NIL && key2a == NIL)
141-
{
142-
*better_key = 1;
143-
return true;
144-
}
145-
if (key1a == NIL && key2a != NIL)
146-
{
147-
*better_key = 2;
148-
return true;
149-
}
143+
144+
if (key2_subsetof_key1)
145+
foreach(i, lfirst(key2))
146+
{
147+
Var *subkey = lfirst(i);
148+
if (!member(subkey, lfirst(key1)))
149+
{
150+
key2_subsetof_key1 = false;
151+
break;
152+
}
153+
}
154+
if (!key1_subsetof_key2 && !key2_subsetof_key1)
155+
break; /* no need to continue comparisons. */
150156
}
151157

152-
/* Now the result should be true if list keys2 has at least as many
153-
* entries as keys1, ie, we did not fall off the end of keys2 first.
154-
* If key1 is now NIL then we hit the end of keys1 before or at the
155-
* same time as the end of keys2.
156-
*/
157-
if (key1 != NIL && key2 == NIL)
158+
if (!key1_subsetof_key2 && !key2_subsetof_key1)
158159
{
159-
*better_key = 1;
160-
return true;
160+
*better_key = 0;
161+
return false;
161162
}
162-
if (key1 == NIL && key2 != NIL)
163+
if (key1_subsetof_key2 && !key2_subsetof_key1)
163164
{
164165
*better_key = 2;
165166
return true;
166167
}
168+
if (!key1_subsetof_key2 && key2_subsetof_key1)
169+
{
170+
*better_key = 1;
171+
return true;
172+
}
173+
167174
*better_key = 0;
168175
return true;
176+
169177
}
170178

171179
/*

‎src/backend/optimizer/util/pathnode.c

Lines changed: 13 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
*
88
*
99
* IDENTIFICATION
10-
* $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.37 1999/02/18 00:49:38 momjian Exp $
10+
* $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.38 1999/02/20 18:01:02 momjian Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -172,15 +172,15 @@ better_path(Path *new_path, List *unique_paths, bool *is_new)
172172
{
173173
path = (Path *) lfirst(temp);
174174

175-
#if 0
176-
/*def OPTDUP_DEBUG*/
175+
#ifdef OPTDUP_DEBUG
177176
if (!pathkeys_match(new_path->pathkeys, path->pathkeys, &better_key) ||
178177
better_key != 0)
179178
{
180-
printf("oldpath\n");
181-
pprint(path->pathkeys);
179+
printf("betterkey = %d\n", better_key);
182180
printf("newpath\n");
183181
pprint(new_path->pathkeys);
182+
printf("oldpath\n");
183+
pprint(path->pathkeys);
184184
if (path->pathkeys && new_path->pathkeys &&
185185
length(lfirst(path->pathkeys)) >= 2/* &&
186186
length(lfirst(path->pathkeys)) <
@@ -191,10 +191,10 @@ better_path(Path *new_path, List *unique_paths, bool *is_new)
191191
&better_sort) ||
192192
better_sort != 0)
193193
{
194-
printf("oldord\n");
195-
pprint(path->pathorder);
196194
printf("neword\n");
197195
pprint(new_path->pathorder);
196+
printf("oldord\n");
197+
pprint(path->pathorder);
198198
}
199199
#endif
200200

@@ -204,8 +204,8 @@ better_path(Path *new_path, List *unique_paths, bool *is_new)
204204
&better_sort))
205205
{
206206
/*
207-
* Replace pathkeys that match exactly, (1,2), (1,2).
208-
* Replace pathkeys (1,2) with (1,2,3) if the latter is not
207+
* Replace pathkeys that match exactly, {{1,2}}, {{1,2}}
208+
* Replace pathkeys {{1,2}}with {{1,2,3}}} if the latter is not
209209
* more expensive and replace unordered path with ordered
210210
* path if it is not more expensive. Favor sorted keys
211211
* over unsorted keys in the same way.
@@ -221,10 +221,10 @@ better_path(Path *new_path, List *unique_paths, bool *is_new)
221221
{
222222
#ifdef OPTDUP_DEBUG
223223
printf("replace with new %p old %p better key %d better sort %d\n", &new_path, &path, better_key, better_sort);
224-
printf("old\n");
225-
pprint(path);
226224
printf("new\n");
227225
pprint(new_path);
226+
printf("old\n");
227+
pprint(path);
228228
#endif
229229
*is_new = false;
230230
return path;
@@ -241,10 +241,10 @@ better_path(Path *new_path, List *unique_paths, bool *is_new)
241241
{
242242
#ifdef OPTDUP_DEBUG
243243
printf("skip new %p old %p better key %d better sort %d\n", &new_path, &path, better_key, better_sort);
244-
printf("old\n");
245-
pprint(path);
246244
printf("new\n");
247245
pprint(new_path);
246+
printf("old\n");
247+
pprint(path);
248248
#endif
249249
*is_new = false;
250250
return NULL;

0 commit comments

Comments
 (0)