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