From 1fb207b7dfdba7265b2a7806416b9cf384931f4d Mon Sep 17 00:00:00 2001 From: Peter Geoghegan Date: Thu, 9 Jul 2015 15:59:07 -0700 Subject: [PATCH 1/2] Tighten SortSupport abbreviated key contract Revise the contract that SortSupport has with its clients to forbid an abbreviated comparator ever returning 0 ("indeterminate") in the event of two abbreviated keys not being bitwise equal. This gives certain cases the leeway to inexpensively determine tuple inequality from afar, by comparing abbreviated keys using simple unsigned integer (Datum) comparisons, and trusting that bitwise inequality amounts to leading attribute inequality (and, therefore, tuple inequality). Direct access to SortSupport state is consequently not required, which will be convenient for tuplesort clients (that only have an opaque state pointer), while also saving us a few additional cycles. Cheap inequality checks of this nature might otherwise give wrong answers due (for example) to some opclass abbreviated comparator interpreting non-identical abbreviated keys with respect to some state built during memtuple copying (although that is probably still safe, depending on the exact details). Pass-by-reference abbreviated keys could similarly cause problems, and so are now forbidden. No existing opclass with abbreviation support does anything like this, so no change in any opclass SortSupport routine. Finally, move code that handles the "one initial run" external sort optimization in mergeruns() to occur immediately after (not immediately before) SortSupport state has been set to be consistent with abbreviation not being in play (this is needed because abbreviated keys are never stored on tape). The existing order of those two things is not significant, but only because the question of further tuple comparisons never arises with the "one initial run" external sort optimization. The question of cheap inequality tests can be expected to arise in a future commit, though. This is also tidier. Backpatch to 9.5, where abbreviated keys were introduced. --- src/backend/utils/sort/tuplesort.c | 52 +++++++++++++++++++++++--------------- src/include/utils/sortsupport.h | 16 +++++++++++- 2 files changed, 46 insertions(+), 22 deletions(-) diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c index 6572af8..5e12c0b 100644 --- a/src/backend/utils/sort/tuplesort.c +++ b/src/backend/utils/sort/tuplesort.c @@ -930,7 +930,17 @@ tuplesort_begin_datum(Oid datumType, Oid sortOperator, Oid sortCollation, state->sortKeys->ssup_collation = sortCollation; state->sortKeys->ssup_nulls_first = nullsFirstFlag; - /* abbreviation is possible here only for by-reference types */ + /* + * Abbreviation is possible here only for by-reference types. Note that a + * pass-by-value representation for abbreviated values is forbidden, but + * that's a distinct, generic restriction imposed by the SortSupport + * contract. + * + * It's possible for a pass-by-value type to have a pass-by-value + * abbreviated key representation, presumably with cheaper comparisons, but + * that could never be used here. Abbreviated keys are mostly about cache + * performance, so this doesn't seem like a serious restriction. + */ state->sortKeys->abbreviate = !typbyval; PrepareSortSupportFromOrderingOp(sortOperator, state->sortKeys); @@ -1271,7 +1281,7 @@ tuplesort_putindextuplevalues(Tuplesortstate *state, Relation rel, * Store ordinary Datum representation, or NULL value. If there is a * converter it won't expect NULL values, and cost model is not * required to account for NULL, so in that case we avoid calling - * converter and just set datum1 to "void" representation (to be + * converter and just set datum1 to zeroed representation (to be * consistent). */ stup.datum1 = original; @@ -2224,6 +2234,22 @@ mergeruns(Tuplesortstate *state) Assert(state->status == TSS_BUILDRUNS); Assert(state->memtupcount == 0); + if (state->sortKeys != NULL && state->sortKeys->abbrev_converter != NULL) + { + /* + * If there are multiple runs to be merged, when we go to read back + * tuples from disk, abbreviated keys will not have been stored, and + * we don't care to regenerate them. Disable abbreviation from this + * point on. + */ + state->sortKeys->abbrev_converter = NULL; + state->sortKeys->comparator = state->sortKeys->abbrev_full_comparator; + + /* Not strictly necessary, but be tidy */ + state->sortKeys->abbrev_abort = NULL; + state->sortKeys->abbrev_full_comparator = NULL; + } + /* * If we produced only one initial run (quite likely if the total data * volume is between 1X and 2X workMem), we can just use that tape as the @@ -2239,22 +2265,6 @@ mergeruns(Tuplesortstate *state) return; } - if (state->sortKeys != NULL && state->sortKeys->abbrev_converter != NULL) - { - /* - * If there are multiple runs to be merged, when we go to read back - * tuples from disk, abbreviated keys will not have been stored, and - * we don't care to regenerate them. Disable abbreviation from this - * point on. - */ - state->sortKeys->abbrev_converter = NULL; - state->sortKeys->comparator = state->sortKeys->abbrev_full_comparator; - - /* Not strictly necessary, but be tidy */ - state->sortKeys->abbrev_abort = NULL; - state->sortKeys->abbrev_full_comparator = NULL; - } - /* End of step D2: rewind all output tapes to prepare for merging */ for (tapenum = 0; tapenum < state->tapeRange; tapenum++) LogicalTapeRewind(state->tapeset, tapenum, false); @@ -3155,7 +3165,7 @@ copytup_heap(Tuplesortstate *state, SortTuple *stup, void *tup) * Store ordinary Datum representation, or NULL value. If there is a * converter it won't expect NULL values, and cost model is not * required to account for NULL, so in that case we avoid calling - * converter and just set datum1 to "void" representation (to be + * converter and just set datum1 to zeroed representation (to be * consistent). */ stup->datum1 = original; @@ -3397,7 +3407,7 @@ copytup_cluster(Tuplesortstate *state, SortTuple *stup, void *tup) * Store ordinary Datum representation, or NULL value. If there is a * converter it won't expect NULL values, and cost model is not * required to account for NULL, so in that case we avoid calling - * converter and just set datum1 to "void" representation (to be + * converter and just set datum1 to zeroed representation (to be * consistent). */ stup->datum1 = original; @@ -3701,7 +3711,7 @@ copytup_index(Tuplesortstate *state, SortTuple *stup, void *tup) * Store ordinary Datum representation, or NULL value. If there is a * converter it won't expect NULL values, and cost model is not * required to account for NULL, so in that case we avoid calling - * converter and just set datum1 to "void" representation (to be + * converter and just set datum1 to zeroed representation (to be * consistent). */ stup->datum1 = original; diff --git a/src/include/utils/sortsupport.h b/src/include/utils/sortsupport.h index 4258630..5a110f1 100644 --- a/src/include/utils/sortsupport.h +++ b/src/include/utils/sortsupport.h @@ -116,7 +116,7 @@ typedef struct SortSupportData * * This allows opclass authors to supply a conversion routine, used to * create an alternative representation of the underlying type (an - * "abbreviated key"). Typically, this representation is an ad-hoc, + * "abbreviated key"). This representation must have an ad-hoc, * pass-by-value Datum format that only the opclass has knowledge of. An * alternative comparator, used only with this alternative representation * must also be provided (which is assigned to "comparator"). This @@ -135,6 +135,20 @@ typedef struct SortSupportData * cache miss penalties are expensive; to get good overall performance, * sort infrastructure must heavily weigh cache performance. * + * There is one limited way in which the core code has knowledge of any + * abbreviated key format: it uses it directly for inequality. + * Specifically, it assumes that two non-bitwise-identical abbreviated keys + * could never have their abbreviated comparator return a 0 or + * "inconclusive" result; in other words, it assumes that abbreviated + * bitwise inequality is a reliable proxy for authoritative value + * inequality. This restriction enables cheap inequality tests made from a + * distance, without opclass involvement. Furthermore, it implies that + * abbreviated keys themselves must always be pass-by-value, since this + * won't work with pointers. Note that it is still permitted for the + * abbreviated comparator to use state generated during calls to + * abbrev_converter -- for example, a lookup table could be used, provided + * any identifier baked into the abbreviated representation is canonical. + * * Opclass authors must consider the final cardinality of abbreviated keys * when devising an encoding scheme. It's possible for a strategy to work * better than an alternative strategy with one usage pattern, while the -- 1.9.1