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 294349 : pgpa_trove_entry_compare_key(pgpa_trove_entry_key a, pgpa_trove_entry_key b)
92 : {
93 294349 : if (strcmp(a.alias_name, b.alias_name) != 0)
94 39020 : return false;
95 :
96 255329 : if (!strings_equal_or_both_null(a.partition_name, b.partition_name))
97 5178 : return false;
98 :
99 250151 : if (!strings_equal_or_both_null(a.plan_name, b.plan_name))
100 690 : return false;
101 :
102 249461 : 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 43600 : pgpa_build_trove(List *advice_items)
134 : {
135 43600 : pgpa_trove *trove = palloc_object(pgpa_trove);
136 :
137 43600 : pgpa_init_trove_slice(&trove->join);
138 43600 : pgpa_init_trove_slice(&trove->rel);
139 43600 : pgpa_init_trove_slice(&trove->scan);
140 :
141 182567 : foreach_ptr(pgpa_advice_item, item, advice_items)
142 : {
143 95367 : switch (item->tag)
144 : {
145 11149 : 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 11149 : target = palloc0_object(pgpa_advice_target);
157 11149 : target->ttype = PGPA_TARGET_ORDERED_LIST;
158 11149 : target->children = item->targets;
159 :
160 11149 : pgpa_trove_add_to_slice(&trove->join,
161 : item->tag, target);
162 : }
163 11149 : break;
164 :
165 28359 : 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 100862 : 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 44144 : pgpa_trove_add_to_slice(&trove->scan,
184 : item->tag, target);
185 : }
186 28359 : break;
187 :
188 10663 : 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 36844 : foreach_ptr(pgpa_advice_target, target, item->targets)
202 : {
203 15518 : pgpa_trove_add_to_slice(&trove->join,
204 : item->tag, target);
205 : }
206 10663 : break;
207 :
208 45196 : 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 163907 : foreach_ptr(pgpa_advice_target, target, item->targets)
217 : {
218 73515 : pgpa_trove_add_to_slice(&trove->rel,
219 : item->tag, target);
220 : }
221 45196 : break;
222 : }
223 : }
224 :
225 43600 : 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 205256 : 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 205256 : if (type == PGPA_TROVE_LOOKUP_SCAN)
244 77467 : tslice = &trove->scan;
245 127789 : else if (type == PGPA_TROVE_LOOKUP_JOIN)
246 25161 : tslice = &trove->join;
247 : else
248 102628 : tslice = &trove->rel;
249 :
250 205256 : indexes = pgpa_trove_slice_lookup(tslice, &rids[0]);
251 274258 : 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 69002 : other_indexes = pgpa_trove_slice_lookup(tslice, &rids[i]);
263 69002 : indexes = bms_union(indexes, other_indexes);
264 : }
265 :
266 205256 : result->entries = tslice->entries;
267 205256 : result->indexes = indexes;
268 205256 : }
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 130797 : 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 130797 : if (type == PGPA_TROVE_LOOKUP_SCAN)
283 43599 : tslice = &trove->scan;
284 87198 : else if (type == PGPA_TROVE_LOOKUP_JOIN)
285 43599 : tslice = &trove->join;
286 : else
287 43599 : tslice = &trove->rel;
288 :
289 130797 : *entries = tslice->entries;
290 130797 : *nentries = tslice->nused;
291 130797 : }
292 :
293 : /*
294 : * Convert a trove entry to an item of plan advice that would produce it.
295 : */
296 : char *
297 144325 : pgpa_cstring_trove_entry(pgpa_trove_entry *entry)
298 : {
299 : StringInfoData buf;
300 :
301 144325 : initStringInfo(&buf);
302 144325 : appendStringInfoString(&buf, pgpa_cstring_advice_tag(entry->tag));
303 :
304 : /* JOIN_ORDER tags are transformed by pgpa_build_trove; undo that here */
305 144325 : if (entry->tag != PGPA_TAG_JOIN_ORDER)
306 133176 : appendStringInfoChar(&buf, '(');
307 : else
308 : Assert(entry->target->ttype == PGPA_TARGET_ORDERED_LIST);
309 :
310 144325 : pgpa_format_advice_target(&buf, entry->target);
311 :
312 144325 : if (entry->target->itarget != NULL)
313 : {
314 13729 : appendStringInfoChar(&buf, ' ');
315 13729 : pgpa_format_index_target(&buf, entry->target->itarget);
316 : }
317 :
318 144325 : if (entry->tag != PGPA_TAG_JOIN_ORDER)
319 133176 : appendStringInfoChar(&buf, ')');
320 :
321 144325 : return buf.data;
322 : }
323 :
324 : /*
325 : * Set PGPA_FB_* flags on a set of trove entries.
326 : */
327 : void
328 395009 : pgpa_trove_set_flags(pgpa_trove_entry *entries, Bitmapset *indexes, int flags)
329 : {
330 395009 : int i = -1;
331 :
332 568101 : while ((i = bms_next_member(indexes, i)) >= 0)
333 : {
334 173092 : pgpa_trove_entry *entry = &entries[i];
335 :
336 173092 : entry->flags |= flags;
337 : }
338 395009 : }
339 :
340 : /*
341 : * Append a string representation of the specified PGPA_FB_* flags to the
342 : * given StringInfo.
343 : */
344 : void
345 149 : pgpa_trove_append_flags(StringInfo buf, int flags)
346 : {
347 149 : if ((flags & PGPA_FB_MATCH_FULL) != 0)
348 : {
349 : Assert((flags & PGPA_FB_MATCH_PARTIAL) != 0);
350 125 : appendStringInfoString(buf, "matched");
351 : }
352 24 : else if ((flags & PGPA_FB_MATCH_PARTIAL) != 0)
353 4 : appendStringInfoString(buf, "partially matched");
354 : else
355 20 : appendStringInfoString(buf, "not matched");
356 149 : if ((flags & PGPA_FB_INAPPLICABLE) != 0)
357 4 : appendStringInfoString(buf, ", inapplicable");
358 149 : if ((flags & PGPA_FB_CONFLICTING) != 0)
359 14 : appendStringInfoString(buf, ", conflicting");
360 149 : if ((flags & PGPA_FB_FAILED) != 0)
361 31 : appendStringInfoString(buf, ", failed");
362 149 : }
363 :
364 : /*
365 : * Add a new advice target to an existing pgpa_trove_slice object.
366 : */
367 : static void
368 144326 : 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 144326 : 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 144326 : entry = &tslice->entries[tslice->nused];
385 144326 : entry->tag = tag;
386 144326 : entry->target = target;
387 144326 : entry->flags = 0;
388 :
389 144326 : pgpa_trove_add_to_hash(tslice->hash, target, tslice->nused);
390 :
391 144326 : tslice->nused++;
392 144326 : }
393 :
394 : /*
395 : * Update the hash table for a newly-added advice target.
396 : */
397 : static void
398 172760 : 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 172760 : if (target->ttype != PGPA_TARGET_IDENTIFIER)
407 : {
408 53498 : foreach_ptr(pgpa_advice_target, child_target, target->children)
409 : {
410 28434 : pgpa_trove_add_to_hash(hash, child_target, index);
411 : }
412 12532 : 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 160228 : key.alias_name = target->rid.alias_name;
421 160228 : key.partition_name = target->rid.partrel;
422 160228 : key.plan_name = target->rid.plan_name;
423 160228 : element = pgpa_trove_entry_insert(hash, key, &found);
424 160228 : if (!found)
425 141854 : element->indexes = NULL;
426 160228 : 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 130800 : 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 130800 : tslice->nallocated = 16;
445 130800 : tslice->nused = 0;
446 130800 : tslice->entries = palloc_array(pgpa_trove_entry, tslice->nallocated);
447 130800 : tslice->hash = pgpa_trove_entry_create(CurrentMemoryContext,
448 : tslice->nallocated, NULL);
449 130800 : }
450 :
451 : /*
452 : * Fast hash function for a key consisting of alias_name, partition_name,
453 : * and plan_name.
454 : */
455 : static uint32
456 447089 : pgpa_trove_entry_hash_key(pgpa_trove_entry_key key)
457 : {
458 : fasthash_state hs;
459 : int sp_len;
460 :
461 447089 : fasthash_init(&hs, 0);
462 :
463 : /* alias_name may not be NULL */
464 447089 : sp_len = fasthash_accum_cstring(&hs, key.alias_name);
465 :
466 : /* partition_name and plan_name, however, can be NULL */
467 447089 : if (key.partition_name != NULL)
468 42514 : sp_len += fasthash_accum_cstring(&hs, key.partition_name);
469 447089 : if (key.plan_name != NULL)
470 112913 : 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 447089 : return fasthash_final32(&hs, sp_len);
478 : }
479 :
480 : /*
481 : * Look for matching entries.
482 : */
483 : static Bitmapset *
484 274258 : 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 274258 : Bitmapset *result = NULL;
489 :
490 : Assert(rid->occurrence >= 1);
491 :
492 274258 : key.alias_name = rid->alias_name;
493 274258 : key.partition_name = rid->partrel;
494 274258 : key.plan_name = rid->plan_name;
495 :
496 274258 : element = pgpa_trove_entry_lookup(tslice->hash, key);
497 :
498 274258 : if (element != NULL)
499 : {
500 231087 : int i = -1;
501 :
502 513378 : while ((i = bms_next_member(element->indexes, i)) >= 0)
503 : {
504 282291 : 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 282291 : if (pgpa_identifier_matches_target(rid, entry->target))
513 272623 : result = bms_add_member(result, i);
514 : }
515 : }
516 :
517 274258 : return result;
518 : }
|
