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 to
9 : : * avoid naming confusion; for example, "collection of advice" would
10 : : * invite confusion with pgpa_collector.c. Note that, while we don't know
11 : : * whether the provided advice is actually wise, it's not our job to
12 : : * 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-2024, 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 : 14258 : pgpa_trove_entry_compare_key(pgpa_trove_entry_key a, pgpa_trove_entry_key b)
91 : : {
92 [ + + ]: 14258 : if (strcmp(a.alias_name, b.alias_name) != 0)
93 : 13988 : return false;
94 : :
95 [ + - ]: 270 : if (!strings_equal_or_both_null(a.partition_name, b.partition_name))
96 : 0 : return false;
97 : :
98 [ + - ]: 270 : if (!strings_equal_or_both_null(a.plan_name, b.plan_name))
99 : 0 : return false;
100 : :
101 : 270 : return true;
102 : 14258 : }
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 : 42260 : pgpa_build_trove(List *advice_items)
133 : : {
134 : 42260 : pgpa_trove *trove = palloc_object(pgpa_trove);
135 : :
136 : 42260 : pgpa_init_trove_slice(&trove->join);
137 : 42260 : pgpa_init_trove_slice(&trove->rel);
138 : 42260 : pgpa_init_trove_slice(&trove->scan);
139 : :
140 [ + + + - : 211086 : foreach_ptr(pgpa_advice_item, item, advice_items)
+ + + + ]
141 : : {
142 [ + + + + : 126566 : switch (item->tag)
- ]
143 : : {
144 : : case PGPA_TAG_JOIN_ORDER:
145 : : {
146 : 19 : 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 : 19 : target = palloc0_object(pgpa_advice_target);
156 : 19 : target->ttype = PGPA_TARGET_ORDERED_LIST;
157 : 19 : target->children = item->targets;
158 : :
159 : 38 : pgpa_trove_add_to_slice(&trove->join,
160 : 19 : item->tag, target);
161 : 19 : }
162 : 19 : break;
163 : :
164 : : case PGPA_TAG_BITMAP_HEAP_SCAN:
165 : : case PGPA_TAG_INDEX_ONLY_SCAN:
166 : : case PGPA_TAG_INDEX_SCAN:
167 : : case PGPA_TAG_SEQ_SCAN:
168 : : case PGPA_TAG_TID_SCAN:
169 : :
170 : : /*
171 : : * Scan advice.
172 : : */
173 [ + + + + : 126592 : foreach_ptr(pgpa_advice_target, target, item->targets)
+ + + + ]
174 : : {
175 : : /*
176 : : * For now, all of our scan types target single relations,
177 : : * but in the future this might not be true, e.g. a custom
178 : : * scan could replace a join.
179 : : */
180 [ + - ]: 42198 : Assert(target->ttype == PGPA_TARGET_IDENTIFIER);
181 : 84396 : pgpa_trove_add_to_slice(&trove->scan,
182 : 42198 : item->tag, target);
183 : 84395 : }
184 : 42197 : break;
185 : :
186 : : case PGPA_TAG_FOREIGN_JOIN:
187 : : case PGPA_TAG_HASH_JOIN:
188 : : case PGPA_TAG_MERGE_JOIN_MATERIALIZE:
189 : : case PGPA_TAG_MERGE_JOIN_PLAIN:
190 : : case PGPA_TAG_NESTED_LOOP_MATERIALIZE:
191 : : case PGPA_TAG_NESTED_LOOP_MEMOIZE:
192 : : case PGPA_TAG_NESTED_LOOP_PLAIN:
193 : : case PGPA_TAG_SEMIJOIN_NON_UNIQUE:
194 : : case PGPA_TAG_SEMIJOIN_UNIQUE:
195 : :
196 : : /*
197 : : * Join strategy advice.
198 : : */
199 [ + + + + : 126543 : foreach_ptr(pgpa_advice_target, target, item->targets)
+ + + + ]
200 : : {
201 : 84362 : pgpa_trove_add_to_slice(&trove->join,
202 : 42181 : item->tag, target);
203 : 84362 : }
204 : 42181 : break;
205 : :
206 : : case PGPA_TAG_PARTITIONWISE:
207 : : case PGPA_TAG_GATHER:
208 : : case PGPA_TAG_GATHER_MERGE:
209 : : case PGPA_TAG_NO_GATHER:
210 : :
211 : : /*
212 : : * Advice about a RelOptInfo relevant to both scans and joins.
213 : : */
214 [ + + + - : 126514 : foreach_ptr(pgpa_advice_target, target, item->targets)
+ + + + ]
215 : : {
216 : 84352 : pgpa_trove_add_to_slice(&trove->rel,
217 : 42176 : item->tag, target);
218 : 84345 : }
219 : 42169 : break;
220 : : }
221 : 168826 : }
222 : :
223 : 84520 : return trove;
224 : 42260 : }
225 : :
226 : : /*
227 : : * Search a trove of advice for relevant entries.
228 : : *
229 : : * All parameters are input parameters except for *result, which is an output
230 : : * parameter used to return results to the caller.
231 : : */
232 : : void
233 : 134232 : pgpa_trove_lookup(pgpa_trove *trove, pgpa_trove_lookup_type type,
234 : : int nrids, pgpa_identifier *rids, pgpa_trove_result *result)
235 : : {
236 : 134232 : pgpa_trove_slice *tslice;
237 : 134232 : Bitmapset *indexes;
238 : :
239 [ + - ]: 134232 : Assert(nrids > 0);
240 : :
241 [ + + ]: 134232 : if (type == PGPA_TROVE_LOOKUP_SCAN)
242 : 45244 : tslice = &trove->scan;
243 [ + + ]: 88988 : else if (type == PGPA_TROVE_LOOKUP_JOIN)
244 : 21872 : tslice = &trove->join;
245 : : else
246 : 67116 : tslice = &trove->rel;
247 : :
248 : 134232 : indexes = pgpa_trove_slice_lookup(tslice, &rids[0]);
249 [ + + ]: 193052 : for (int i = 1; i < nrids; ++i)
250 : : {
251 : 58820 : Bitmapset *other_indexes;
252 : :
253 : : /*
254 : : * If the caller is asking about two relations that aren't part of the
255 : : * same subquery, they've messed up.
256 : : */
257 [ + - ]: 58820 : Assert(strings_equal_or_both_null(rids[0].plan_name,
258 : : rids[i].plan_name));
259 : :
260 : 58820 : other_indexes = pgpa_trove_slice_lookup(tslice, &rids[i]);
261 : 58820 : indexes = bms_union(indexes, other_indexes);
262 : 58820 : }
263 : :
264 : 134232 : result->entries = tslice->entries;
265 : 134232 : result->indexes = indexes;
266 : 134232 : }
267 : :
268 : : /*
269 : : * Return all entries in a trove slice to the caller.
270 : : *
271 : : * The first two arguments are input arguments, and the remainder are output
272 : : * arguments.
273 : : */
274 : : void
275 : 10593 : pgpa_trove_lookup_all(pgpa_trove *trove, pgpa_trove_lookup_type type,
276 : : pgpa_trove_entry **entries, int *nentries)
277 : : {
278 : 10593 : pgpa_trove_slice *tslice;
279 : :
280 [ + + ]: 10593 : if (type == PGPA_TROVE_LOOKUP_SCAN)
281 : 3531 : tslice = &trove->scan;
282 [ + + ]: 7062 : else if (type == PGPA_TROVE_LOOKUP_JOIN)
283 : 3531 : tslice = &trove->join;
284 : : else
285 : 3531 : tslice = &trove->rel;
286 : :
287 : 10593 : *entries = tslice->entries;
288 : 10593 : *nentries = tslice->nused;
289 : 10593 : }
290 : :
291 : : /*
292 : : * Convert a trove entry to an item of plan advice that would produce it.
293 : : */
294 : : char *
295 : 10387 : pgpa_cstring_trove_entry(pgpa_trove_entry *entry)
296 : : {
297 : 10387 : StringInfoData buf;
298 : :
299 : 10387 : initStringInfo(&buf);
300 : 10387 : appendStringInfo(&buf, "%s", pgpa_cstring_advice_tag(entry->tag));
301 : :
302 : : /* JOIN_ORDER tags are transformed by pgpa_build_trove; undo that here */
303 [ + + ]: 10387 : if (entry->tag != PGPA_TAG_JOIN_ORDER)
304 : 10368 : appendStringInfoChar(&buf, '(');
305 : : else
306 [ + - ]: 19 : Assert(entry->target->ttype == PGPA_TARGET_ORDERED_LIST);
307 : :
308 : 10387 : pgpa_format_advice_target(&buf, entry->target);
309 : :
310 [ + + ]: 10387 : if (entry->target->itarget != NULL)
311 : : {
312 : 24 : appendStringInfoChar(&buf, ' ');
313 : 24 : pgpa_format_index_target(&buf, entry->target->itarget);
314 : 24 : }
315 : :
316 [ + + ]: 10387 : if (entry->tag != PGPA_TAG_JOIN_ORDER)
317 : 10368 : appendStringInfoChar(&buf, ')');
318 : :
319 : 20774 : return buf.data;
320 : 10387 : }
321 : :
322 : : /*
323 : : * Set PGPA_TE_* flags on a set of trove entries.
324 : : */
325 : : void
326 : 729 : pgpa_trove_set_flags(pgpa_trove_entry *entries, Bitmapset *indexes, int flags)
327 : : {
328 : 729 : int i = -1;
329 : :
330 [ + + ]: 892 : while ((i = bms_next_member(indexes, i)) >= 0)
331 : : {
332 : 163 : pgpa_trove_entry *entry = &entries[i];
333 : :
334 : 163 : entry->flags |= flags;
335 : 163 : }
336 : 729 : }
337 : :
338 : : /*
339 : : * Add a new advice target to an existing pgpa_trove_slice object.
340 : : */
341 : : static void
342 : 126574 : pgpa_trove_add_to_slice(pgpa_trove_slice *tslice,
343 : : pgpa_advice_tag_type tag,
344 : : pgpa_advice_target *target)
345 : : {
346 : 126574 : pgpa_trove_entry *entry;
347 : :
348 [ + - ]: 126574 : if (tslice->nused >= tslice->nallocated)
349 : : {
350 : 0 : int new_allocated;
351 : :
352 : 0 : new_allocated = tslice->nallocated * 2;
353 : 0 : tslice->entries = repalloc_array(tslice->entries, pgpa_trove_entry,
354 : : new_allocated);
355 : 0 : tslice->nallocated = new_allocated;
356 : 0 : }
357 : :
358 : 126574 : entry = &tslice->entries[tslice->nused];
359 : 126574 : entry->tag = tag;
360 : 126574 : entry->target = target;
361 : 126574 : entry->flags = 0;
362 : :
363 : 126574 : pgpa_trove_add_to_hash(tslice->hash, target, tslice->nused);
364 : :
365 : 126574 : tslice->nused++;
366 : 126574 : }
367 : :
368 : : /*
369 : : * Update the hash table for a newly-added advice target.
370 : : */
371 : : static void
372 : 126643 : pgpa_trove_add_to_hash(pgpa_trove_entry_hash *hash, pgpa_advice_target *target,
373 : : int index)
374 : : {
375 : 126643 : pgpa_trove_entry_key key;
376 : 126643 : pgpa_trove_entry_element *element;
377 : 126643 : bool found;
378 : :
379 : : /* For non-identifiers, add entries for all descendents. */
380 [ + + ]: 126643 : if (target->ttype != PGPA_TARGET_IDENTIFIER)
381 : : {
382 [ + + + - : 135 : foreach_ptr(pgpa_advice_target, child_target, target->children)
+ + + + ]
383 : : {
384 : 69 : pgpa_trove_add_to_hash(hash, child_target, index);
385 : 102 : }
386 : 33 : return;
387 : : }
388 : :
389 : : /* Sanity checks. */
390 [ + - ]: 126610 : Assert(target->rid.occurrence > 0);
391 [ - + ]: 126610 : Assert(target->rid.alias_name != NULL);
392 : :
393 : : /* Add an entry for this relation identifier. */
394 : 126610 : key.alias_name = target->rid.alias_name;
395 : 126610 : key.partition_name = target->rid.partrel;
396 : 126610 : key.plan_name = target->rid.plan_name;
397 : 126610 : element = pgpa_trove_entry_insert(hash, key, &found);
398 [ + + ]: 126610 : if (!found)
399 : 126600 : element->indexes = NULL;
400 : 126610 : element->indexes = bms_add_member(element->indexes, index);
401 [ - + ]: 126643 : }
402 : :
403 : : /*
404 : : * Create and initialize a new pgpa_trove_slice object.
405 : : */
406 : : static void
407 : 126780 : pgpa_init_trove_slice(pgpa_trove_slice *tslice)
408 : : {
409 : : /*
410 : : * In an ideal world, we'll make tslice->nallocated big enough that the
411 : : * array and hash table will be large enough to contain the number of
412 : : * advice items in this trove slice, but a generous default value is not
413 : : * good for performance, because pgpa_init_trove_slice() has to zero an
414 : : * amount of memory proportional to tslice->nallocated. Hence, we keep the
415 : : * starting value quite small, on the theory that advice strings will
416 : : * often be relatively short.
417 : : */
418 : 126780 : tslice->nallocated = 16;
419 : 126780 : tslice->nused = 0;
420 : 126780 : tslice->entries = palloc_array(pgpa_trove_entry, tslice->nallocated);
421 : 253560 : tslice->hash = pgpa_trove_entry_create(CurrentMemoryContext,
422 : 126780 : tslice->nallocated, NULL);
423 : 126780 : }
424 : :
425 : : /*
426 : : * Fast hash function for a key consisting of alias_name, partition_name,
427 : : * and plan_name.
428 : : */
429 : : static uint32
430 : 319664 : pgpa_trove_entry_hash_key(pgpa_trove_entry_key key)
431 : : {
432 : 319664 : fasthash_state hs;
433 : 319664 : int sp_len;
434 : :
435 : 319664 : fasthash_init(&hs, 0);
436 : :
437 : : /* alias_name may not be NULL */
438 : 319664 : sp_len = fasthash_accum_cstring(&hs, key.alias_name);
439 : :
440 : : /* partition_name and plan_name, however, can be NULL */
441 [ + + ]: 319664 : if (key.partition_name != NULL)
442 : 25579 : sp_len += fasthash_accum_cstring(&hs, key.partition_name);
443 [ + + ]: 319664 : if (key.plan_name != NULL)
444 : 46642 : sp_len += fasthash_accum_cstring(&hs, key.plan_name);
445 : :
446 : : /*
447 : : * hashfn_unstable.h recommends using string length as tweak. It's not
448 : : * clear to me what to do if there are multiple strings, so for now I'm
449 : : * just using the total of all of the lengths.
450 : : */
451 : 639328 : return fasthash_final32(&hs, sp_len);
452 : 319664 : }
453 : :
454 : : /*
455 : : * Look for matching entries.
456 : : */
457 : : static Bitmapset *
458 : 193052 : pgpa_trove_slice_lookup(pgpa_trove_slice *tslice, pgpa_identifier *rid)
459 : : {
460 : 193052 : pgpa_trove_entry_key key;
461 : 193052 : pgpa_trove_entry_element *element;
462 : 193052 : Bitmapset *result = NULL;
463 : :
464 [ + - ]: 193052 : Assert(rid->occurrence >= 1);
465 : :
466 : 193052 : key.alias_name = rid->alias_name;
467 : 193052 : key.partition_name = rid->partrel;
468 : 193052 : key.plan_name = rid->plan_name;
469 : :
470 : 193052 : element = pgpa_trove_entry_lookup(tslice->hash, key);
471 : :
472 [ + + ]: 193052 : if (element != NULL)
473 : : {
474 : 260 : int i = -1;
475 : :
476 [ + + ]: 535 : while ((i = bms_next_member(element->indexes, i)) >= 0)
477 : : {
478 : 275 : pgpa_trove_entry *entry = &tslice->entries[i];
479 : :
480 : : /*
481 : : * We know that this target or one of its descendents matches the
482 : : * identifier on the three key fields above, but we don't know
483 : : * which descendent or whether the occurence and schema also
484 : : * match.
485 : : */
486 [ + + ]: 275 : if (pgpa_identifier_matches_target(rid, entry->target))
487 : 271 : result = bms_add_member(result, i);
488 : 275 : }
489 : 260 : }
490 : :
491 : 386104 : return result;
492 : 193052 : }
|
