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