Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * pgpa_trove.c
4 : : * All of the advice given for a particular query, appropriately
5 : : * organized for convenient access.
6 : : *
7 : : * This name comes from the English expression "trove of advice", which
8 : : * means a collection of wisdom. This slightly unusual term is chosen
9 : : * partly because it seems to fit and partly because it's not presently
10 : : * used for anything else, making it easy to grep. Note that, while we
11 : : * don't know whether the provided advice is actually wise, it's not our
12 : : * job to question the user's choices.
13 : : *
14 : : * The goal of this module is to make it easy to locate the specific
15 : : * bits of advice that pertain to any given part of a query, or to
16 : : * determine that there are none.
17 : : *
18 : : * Copyright (c) 2016-2026, PostgreSQL Global Development Group
19 : : *
20 : : * contrib/pg_plan_advice/pgpa_trove.c
21 : : *
22 : : *-------------------------------------------------------------------------
23 : : */
24 : : #include "postgres.h"
25 : :
26 : : #include "pg_plan_advice.h"
27 : : #include "pgpa_trove.h"
28 : :
29 : : #include "common/hashfn_unstable.h"
30 : : #include "miscadmin.h"
31 : :
32 : : /*
33 : : * An advice trove is organized into a series of "slices", each of which
34 : : * contains information about one topic e.g. scan methods. Each slice consists
35 : : * of an array of trove entries plus a hash table that we can use to determine
36 : : * which ones are relevant to a particular part of the query.
37 : : */
38 : : typedef struct pgpa_trove_slice
39 : : {
40 : : unsigned nallocated;
41 : : unsigned nused;
42 : : pgpa_trove_entry *entries;
43 : : struct pgpa_trove_entry_hash *hash;
44 : : } pgpa_trove_slice;
45 : :
46 : : /*
47 : : * Scan advice is stored into 'scan'; join advice is stored into 'join'; and
48 : : * advice that can apply to both cases is stored into 'rel'. This lets callers
49 : : * ask just for what's relevant. These slices correspond to the possible values
50 : : * of pgpa_trove_lookup_type.
51 : : */
52 : : struct pgpa_trove
53 : : {
54 : : pgpa_trove_slice join;
55 : : pgpa_trove_slice rel;
56 : : pgpa_trove_slice scan;
57 : : };
58 : :
59 : : /*
60 : : * We're going to build a hash table to allow clients of this module to find
61 : : * relevant advice for a given part of the query quickly. However, we're going
62 : : * to use only three of the five key fields as hash keys. That's because we
63 : : * expect the "occurrence" and "partition_schema" portions of the relation
64 : : * identifiers to be mostly uninteresting. Most of the time, the occurrence
65 : : * field will be 1 and the partition_schema values will all be the same. Even
66 : : * when there is some variation, the absolute number of entries that have the
67 : : * same values for all three of these key fields should be quite small.
68 : : */
69 : : typedef struct
70 : : {
71 : : const char *alias_name;
72 : : const char *partition_name;
73 : : const char *plan_name;
74 : : } pgpa_trove_entry_key;
75 : :
76 : : typedef struct
77 : : {
78 : : pgpa_trove_entry_key key;
79 : : int status;
80 : : Bitmapset *indexes;
81 : : } pgpa_trove_entry_element;
82 : :
83 : : static uint32 pgpa_trove_entry_hash_key(pgpa_trove_entry_key key);
84 : :
85 : : static inline bool
192 rhaas@postgresql.org 86 :CBC 331422 : pgpa_trove_entry_compare_key(pgpa_trove_entry_key a, pgpa_trove_entry_key b)
87 : : {
88 [ + + ]: 331422 : if (strcmp(a.alias_name, b.alias_name) != 0)
89 : 71752 : return false;
90 : :
91 [ + + ]: 259670 : if (!strings_equal_or_both_null(a.partition_name, b.partition_name))
92 : 5150 : return false;
93 : :
94 [ + + ]: 254520 : if (!strings_equal_or_both_null(a.plan_name, b.plan_name))
95 : 277 : return false;
96 : :
97 : 254243 : return true;
98 : : }
99 : :
100 : : #define SH_PREFIX pgpa_trove_entry
101 : : #define SH_ELEMENT_TYPE pgpa_trove_entry_element
102 : : #define SH_KEY_TYPE pgpa_trove_entry_key
103 : : #define SH_KEY key
104 : : #define SH_HASH_KEY(tb, key) pgpa_trove_entry_hash_key(key)
105 : : #define SH_EQUAL(tb, a, b) pgpa_trove_entry_compare_key(a, b)
106 : : #define SH_SCOPE static inline
107 : : #define SH_DECLARE
108 : : #define SH_DEFINE
109 : : #include "lib/simplehash.h"
110 : :
111 : : static void pgpa_init_trove_slice(pgpa_trove_slice *tslice);
112 : : static void pgpa_trove_add_to_slice(pgpa_trove_slice *tslice,
113 : : pgpa_advice_tag_type tag,
114 : : pgpa_advice_target *target);
115 : : static void pgpa_trove_add_to_hash(pgpa_trove_entry_hash *hash,
116 : : pgpa_advice_target *target,
117 : : int index);
118 : : static Bitmapset *pgpa_trove_slice_lookup(pgpa_trove_slice *tslice,
119 : : pgpa_identifier *rid);
120 : :
121 : : /*
122 : : * Build a trove of advice from a list of advice items.
123 : : *
124 : : * Caller can obtain a list of advice items to pass to this function by
125 : : * calling pgpa_parse().
126 : : */
127 : : pgpa_trove *
128 : 43205 : pgpa_build_trove(List *advice_items)
129 : : {
130 : 43205 : pgpa_trove *trove = palloc_object(pgpa_trove);
131 : :
132 : 43205 : pgpa_init_trove_slice(&trove->join);
133 : 43205 : pgpa_init_trove_slice(&trove->rel);
134 : 43205 : pgpa_init_trove_slice(&trove->scan);
135 : :
136 [ + - + + : 181081 : foreach_ptr(pgpa_advice_item, item, advice_items)
+ + ]
137 : : {
138 [ + + + + : 94671 : switch (item->tag)
- ]
139 : : {
140 : 10947 : case PGPA_TAG_JOIN_ORDER:
141 : : {
142 : : pgpa_advice_target *target;
143 : :
144 : : /*
145 : : * For most advice types, each element in the top-level
146 : : * list is a separate target, but it's most convenient to
147 : : * regard the entirety of a JOIN_ORDER specification as a
148 : : * single target. Since it wasn't represented that way
149 : : * during parsing, build a surrogate object now.
150 : : */
151 : 10947 : target = palloc0_object(pgpa_advice_target);
152 : 10947 : target->ttype = PGPA_TARGET_ORDERED_LIST;
153 : 10947 : target->children = item->targets;
154 : :
155 : 10947 : pgpa_trove_add_to_slice(&trove->join,
156 : : item->tag, target);
157 : : }
158 : 10947 : break;
159 : :
160 : 28464 : case PGPA_TAG_BITMAP_HEAP_SCAN:
161 : : case PGPA_TAG_DO_NOT_SCAN:
162 : : case PGPA_TAG_INDEX_ONLY_SCAN:
163 : : case PGPA_TAG_INDEX_SCAN:
164 : : case PGPA_TAG_SEQ_SCAN:
165 : : case PGPA_TAG_TID_SCAN:
166 : :
167 : : /*
168 : : * Scan advice.
169 : : */
170 [ + + + + : 100660 : foreach_ptr(pgpa_advice_target, target, item->targets)
+ + ]
171 : : {
172 : : /*
173 : : * For now, all of our scan types target single relations,
174 : : * but in the future this might not be true, e.g. a custom
175 : : * scan could replace a join.
176 : : */
177 [ - + ]: 43732 : Assert(target->ttype == PGPA_TARGET_IDENTIFIER);
178 : 43732 : pgpa_trove_add_to_slice(&trove->scan,
179 : : item->tag, target);
180 : : }
181 : 28464 : break;
182 : :
183 : 10539 : case PGPA_TAG_FOREIGN_JOIN:
184 : : case PGPA_TAG_HASH_JOIN:
185 : : case PGPA_TAG_MERGE_JOIN_MATERIALIZE:
186 : : case PGPA_TAG_MERGE_JOIN_PLAIN:
187 : : case PGPA_TAG_NESTED_LOOP_MATERIALIZE:
188 : : case PGPA_TAG_NESTED_LOOP_MEMOIZE:
189 : : case PGPA_TAG_NESTED_LOOP_PLAIN:
190 : : case PGPA_TAG_SEMIJOIN_NON_UNIQUE:
191 : : case PGPA_TAG_SEMIJOIN_UNIQUE:
192 : :
193 : : /*
194 : : * Join strategy advice.
195 : : */
196 [ + + + + : 36660 : foreach_ptr(pgpa_advice_target, target, item->targets)
+ + ]
197 : : {
198 : 15582 : pgpa_trove_add_to_slice(&trove->join,
199 : : item->tag, target);
200 : : }
201 : 10539 : break;
202 : :
203 : 44721 : case PGPA_TAG_PARTITIONWISE:
204 : : case PGPA_TAG_GATHER:
205 : : case PGPA_TAG_GATHER_MERGE:
206 : : case PGPA_TAG_NO_GATHER:
207 : :
208 : : /*
209 : : * Advice about a RelOptInfo relevant to both scans and joins.
210 : : */
211 [ + - + + : 162326 : foreach_ptr(pgpa_advice_target, target, item->targets)
+ + ]
212 : : {
213 : 72884 : pgpa_trove_add_to_slice(&trove->rel,
214 : : item->tag, target);
215 : : }
216 : 44721 : break;
217 : : }
218 : : }
219 : :
220 : 43205 : return trove;
221 : : }
222 : :
223 : : /*
224 : : * Search a trove of advice for relevant entries.
225 : : *
226 : : * All parameters are input parameters except for *result, which is an output
227 : : * parameter used to return results to the caller.
228 : : */
229 : : void
230 : 208450 : pgpa_trove_lookup(pgpa_trove *trove, pgpa_trove_lookup_type type,
231 : : int nrids, pgpa_identifier *rids, pgpa_trove_result *result)
232 : : {
233 : : pgpa_trove_slice *tslice;
234 : : Bitmapset *indexes;
235 : :
236 [ - + ]: 208450 : Assert(nrids > 0);
237 : :
238 [ + + ]: 208450 : if (type == PGPA_TROVE_LOOKUP_SCAN)
239 : 78932 : tslice = &trove->scan;
240 [ + + ]: 129518 : else if (type == PGPA_TROVE_LOOKUP_JOIN)
241 : 25293 : tslice = &trove->join;
242 : : else
243 : 104225 : tslice = &trove->rel;
244 : :
245 : 208450 : indexes = pgpa_trove_slice_lookup(tslice, &rids[0]);
246 [ + + ]: 278438 : for (int i = 1; i < nrids; ++i)
247 : : {
248 : : Bitmapset *other_indexes;
249 : :
250 : : /*
251 : : * If the caller is asking about two relations that aren't part of the
252 : : * same subquery, they've messed up.
253 : : */
254 [ - + ]: 69988 : Assert(strings_equal_or_both_null(rids[0].plan_name,
255 : : rids[i].plan_name));
256 : :
257 : 69988 : other_indexes = pgpa_trove_slice_lookup(tslice, &rids[i]);
258 : 69988 : indexes = bms_union(indexes, other_indexes);
259 : : }
260 : :
261 : 208450 : result->entries = tslice->entries;
262 : 208450 : result->indexes = indexes;
263 : 208450 : }
264 : :
265 : : /*
266 : : * Return all entries in a trove slice to the caller.
267 : : *
268 : : * The first two arguments are input arguments, and the remainder are output
269 : : * arguments.
270 : : */
271 : : void
272 : 129612 : pgpa_trove_lookup_all(pgpa_trove *trove, pgpa_trove_lookup_type type,
273 : : pgpa_trove_entry **entries, int *nentries)
274 : : {
275 : : pgpa_trove_slice *tslice;
276 : :
277 [ + + ]: 129612 : if (type == PGPA_TROVE_LOOKUP_SCAN)
278 : 43204 : tslice = &trove->scan;
279 [ + + ]: 86408 : else if (type == PGPA_TROVE_LOOKUP_JOIN)
280 : 43204 : tslice = &trove->join;
281 : : else
282 : 43204 : tslice = &trove->rel;
283 : :
284 : 129612 : *entries = tslice->entries;
285 : 129612 : *nentries = tslice->nused;
286 : 129612 : }
287 : :
288 : : /*
289 : : * Convert a trove entry to an item of plan advice that would produce it.
290 : : */
291 : : char *
292 : 143144 : pgpa_cstring_trove_entry(pgpa_trove_entry *entry)
293 : : {
294 : : StringInfoData buf;
295 : :
296 : 143144 : initStringInfo(&buf);
160 drowley@postgresql.o 297 : 143144 : appendStringInfoString(&buf, pgpa_cstring_advice_tag(entry->tag));
298 : :
299 : : /* JOIN_ORDER tags are transformed by pgpa_build_trove; undo that here */
192 rhaas@postgresql.org 300 [ + + ]: 143144 : if (entry->tag != PGPA_TAG_JOIN_ORDER)
301 : 132197 : appendStringInfoChar(&buf, '(');
302 : : else
303 [ - + ]: 10947 : Assert(entry->target->ttype == PGPA_TARGET_ORDERED_LIST);
304 : :
305 : 143144 : pgpa_format_advice_target(&buf, entry->target);
306 : :
307 [ + + ]: 143144 : if (entry->target->itarget != NULL)
308 : : {
309 : 14664 : appendStringInfoChar(&buf, ' ');
310 : 14664 : pgpa_format_index_target(&buf, entry->target->itarget);
311 : : }
312 : :
313 [ + + ]: 143144 : if (entry->tag != PGPA_TAG_JOIN_ORDER)
314 : 132197 : appendStringInfoChar(&buf, ')');
315 : :
316 : 143144 : return buf.data;
317 : : }
318 : :
319 : : /*
320 : : * Set PGPA_FB_* flags on a set of trove entries.
321 : : */
322 : : void
323 : 401393 : pgpa_trove_set_flags(pgpa_trove_entry *entries, Bitmapset *indexes, int flags)
324 : : {
325 : 401393 : int i = -1;
326 : :
327 [ + + ]: 578936 : while ((i = bms_next_member(indexes, i)) >= 0)
328 : : {
329 : 177543 : pgpa_trove_entry *entry = &entries[i];
330 : :
331 : 177543 : entry->flags |= flags;
332 : : }
333 : 401393 : }
334 : :
335 : : /*
336 : : * Append a string representation of the specified PGPA_FB_* flags to the
337 : : * given StringInfo.
338 : : */
339 : : void
340 : 157 : pgpa_trove_append_flags(StringInfo buf, int flags)
341 : : {
160 342 [ + + ]: 157 : if ((flags & PGPA_FB_MATCH_FULL) != 0)
343 : : {
344 [ - + ]: 133 : Assert((flags & PGPA_FB_MATCH_PARTIAL) != 0);
drowley@postgresql.o 345 : 133 : appendStringInfoString(buf, "matched");
346 : : }
rhaas@postgresql.org 347 [ + + ]: 24 : else if ((flags & PGPA_FB_MATCH_PARTIAL) != 0)
drowley@postgresql.o 348 : 4 : appendStringInfoString(buf, "partially matched");
349 : : else
350 : 20 : appendStringInfoString(buf, "not matched");
rhaas@postgresql.org 351 [ + + ]: 157 : if ((flags & PGPA_FB_INAPPLICABLE) != 0)
drowley@postgresql.o 352 : 4 : appendStringInfoString(buf, ", inapplicable");
rhaas@postgresql.org 353 [ + + ]: 157 : if ((flags & PGPA_FB_CONFLICTING) != 0)
drowley@postgresql.o 354 : 14 : appendStringInfoString(buf, ", conflicting");
rhaas@postgresql.org 355 [ + + ]: 157 : if ((flags & PGPA_FB_FAILED) != 0)
drowley@postgresql.o 356 : 30 : appendStringInfoString(buf, ", failed");
192 rhaas@postgresql.org 357 : 157 : }
358 : :
359 : : /*
360 : : * Add a new advice target to an existing pgpa_trove_slice object.
361 : : */
362 : : static void
363 : 143145 : pgpa_trove_add_to_slice(pgpa_trove_slice *tslice,
364 : : pgpa_advice_tag_type tag,
365 : : pgpa_advice_target *target)
366 : : {
367 : : pgpa_trove_entry *entry;
368 : :
369 [ + + ]: 143145 : if (tslice->nused >= tslice->nallocated)
370 : : {
371 : : int new_allocated;
372 : :
373 : 24 : new_allocated = tslice->nallocated * 2;
374 : 24 : tslice->entries = repalloc_array(tslice->entries, pgpa_trove_entry,
375 : : new_allocated);
376 : 24 : tslice->nallocated = new_allocated;
377 : : }
378 : :
379 : 143145 : entry = &tslice->entries[tslice->nused];
380 : 143145 : entry->tag = tag;
381 : 143145 : entry->target = target;
382 : 143145 : entry->flags = 0;
383 : :
384 : 143145 : pgpa_trove_add_to_hash(tslice->hash, target, tslice->nused);
385 : :
386 : 143145 : tslice->nused++;
387 : 143145 : }
388 : :
389 : : /*
390 : : * Update the hash table for a newly-added advice target.
391 : : */
392 : : static void
393 : 171124 : pgpa_trove_add_to_hash(pgpa_trove_entry_hash *hash, pgpa_advice_target *target,
394 : : int index)
395 : : {
396 : : pgpa_trove_entry_key key;
397 : : pgpa_trove_entry_element *element;
398 : : bool found;
399 : :
11 400 : 171124 : check_stack_depth();
401 : :
402 : : /* For non-identifiers, add entries for all descendants. */
192 403 [ + + ]: 171124 : if (target->ttype != PGPA_TARGET_IDENTIFIER)
404 : : {
405 [ + - + + : 52279 : foreach_ptr(pgpa_advice_target, child_target, target->children)
+ + ]
406 : : {
407 : 27979 : pgpa_trove_add_to_hash(hash, child_target, index);
408 : : }
409 : 12150 : return;
410 : : }
411 : :
412 : : /* Sanity checks. */
413 [ - + ]: 158974 : Assert(target->rid.occurrence > 0);
414 [ - + ]: 158974 : Assert(target->rid.alias_name != NULL);
415 : :
416 : : /* Add an entry for this relation identifier. */
417 : 158974 : key.alias_name = target->rid.alias_name;
418 : 158974 : key.partition_name = target->rid.partrel;
419 : 158974 : key.plan_name = target->rid.plan_name;
420 : 158974 : element = pgpa_trove_entry_insert(hash, key, &found);
421 [ + + ]: 158974 : if (!found)
422 : 140894 : element->indexes = NULL;
423 : 158974 : element->indexes = bms_add_member(element->indexes, index);
424 : : }
425 : :
426 : : /*
427 : : * Create and initialize a new pgpa_trove_slice object.
428 : : */
429 : : static void
430 : 129615 : pgpa_init_trove_slice(pgpa_trove_slice *tslice)
431 : : {
432 : : /*
433 : : * In an ideal world, we'll make tslice->nallocated big enough that the
434 : : * array and hash table will be large enough to contain the number of
435 : : * advice items in this trove slice, but a generous default value is not
436 : : * good for performance, because pgpa_init_trove_slice() has to zero an
437 : : * amount of memory proportional to tslice->nallocated. Hence, we keep the
438 : : * starting value quite small, on the theory that advice strings will
439 : : * often be relatively short.
440 : : */
441 : 129615 : tslice->nallocated = 16;
442 : 129615 : tslice->nused = 0;
443 : 129615 : tslice->entries = palloc_array(pgpa_trove_entry, tslice->nallocated);
444 : 129615 : tslice->hash = pgpa_trove_entry_create(CurrentMemoryContext,
445 : : tslice->nallocated, NULL);
446 : 129615 : }
447 : :
448 : : /*
449 : : * Fast hash function for a key consisting of alias_name, partition_name,
450 : : * and plan_name.
451 : : */
452 : : static uint32
453 : 457684 : pgpa_trove_entry_hash_key(pgpa_trove_entry_key key)
454 : : {
455 : : fasthash_state hs;
456 : : int sp_len;
457 : :
458 : 457684 : fasthash_init(&hs, 0);
459 : :
460 : : /* alias_name may not be NULL */
461 : 457684 : sp_len = fasthash_accum_cstring(&hs, key.alias_name);
462 : :
463 : : /* partition_name and plan_name, however, can be NULL */
464 [ + + ]: 457684 : if (key.partition_name != NULL)
465 : 41934 : sp_len += fasthash_accum_cstring(&hs, key.partition_name);
466 [ + + ]: 457684 : if (key.plan_name != NULL)
467 : 123985 : sp_len += fasthash_accum_cstring(&hs, key.plan_name);
468 : :
469 : : /*
470 : : * hashfn_unstable.h recommends using string length as tweak. It's not
471 : : * clear to me what to do if there are multiple strings, so for now I'm
472 : : * just using the total of all of the lengths.
473 : : */
474 : 457684 : return fasthash_final32(&hs, sp_len);
475 : : }
476 : :
477 : : /*
478 : : * Look for matching entries.
479 : : */
480 : : static Bitmapset *
481 : 278438 : pgpa_trove_slice_lookup(pgpa_trove_slice *tslice, pgpa_identifier *rid)
482 : : {
483 : : pgpa_trove_entry_key key;
484 : : pgpa_trove_entry_element *element;
485 : 278438 : Bitmapset *result = NULL;
486 : :
487 [ - + ]: 278438 : Assert(rid->occurrence >= 1);
488 : :
489 : 278438 : key.alias_name = rid->alias_name;
490 : 278438 : key.partition_name = rid->partrel;
491 : 278438 : key.plan_name = rid->plan_name;
492 : :
493 : 278438 : element = pgpa_trove_entry_lookup(tslice->hash, key);
494 : :
495 [ + + ]: 278438 : if (element != NULL)
496 : : {
497 : 236163 : int i = -1;
498 : :
499 [ + + ]: 520284 : while ((i = bms_next_member(element->indexes, i)) >= 0)
500 : : {
501 : 284121 : pgpa_trove_entry *entry = &tslice->entries[i];
502 : :
503 : : /*
504 : : * We know that this target or one of its descendants matches the
505 : : * identifier on the three key fields above, but we don't know
506 : : * which descendant or whether the occurrence and schema also
507 : : * match.
508 : : */
509 [ + + ]: 284121 : if (pgpa_identifier_matches_target(rid, entry->target))
510 : 276303 : result = bms_add_member(result, i);
511 : : }
512 : : }
513 : :
514 : 278438 : return result;
515 : : }
|
