Reusing abbreviated keys during second pass of ordered [set] aggregates - Mailing list pgsql-hackers

Currently, there are certain aggregates that sort some tuples before
making a second pass over their memtuples array (through the tuplesort
"gettuple" interface), calling one or more attribute equality operator
functions as they go. For example, this occurs during the execution of
the following queries:

-- Salary is a numeric column:
SELECT count(DISTINCT salary) AS distinct_compensation_levels FROM employees;
-- Get most common distinct salary in organization:
SELECT mode() WITHIN GROUP (ORDER BY salary) AS
most_common_compensation FROM employees;

Since these examples involve numeric comparisons, the equality
operator calls involved in that second pass are expensive. There is no
equality fast-path for numeric equality as there is for text; I
imagine that in practice most calls to texteq() are resolved based on
raw datum size mismatch, which is dirt cheap (while the alternative, a
memcmp(), is still very cheap). Furthermore, numeric abbreviated keys
have a good chance of capturing the entropy of the original values
more effectively than we might expect with a text attribute. That
means that in the case of numeric, even sorted, adjacent pairs of
abbreviated keys have a pretty good chance of being distinct in the
real world (if their corresponding authoritative values are themselves
distinct).

I think we can avoid this expense much of the time.

Patch, Performance
===============

Attached patch makes several cases like this try and get away with
only using the pre-existing abbreviated keys from the sort (to
determine inequality). On my laptop, it removes 15% - 25% of the run
time of cases similar to the above, with a high cardinality numeric
attribute of uniformly distributed values. As usual with my work on
sorting, multiple concurrent sorts by multiple backends are helped
most; that puts the improvements for realistic cases involving a text
attribute at about 5% (the texteq() memcmp() is cheap, but not free)
with 4 clients using pgbench.

The numeric cases above are now at about the same speed as similar
queries that use a double precision floating point number attribute.
9.5-era testing shows that sort-heavy numeric cases are often about as
fast as "equivalent" double cases, so it seems worthwhile to mostly
eliminate this additional numeric overhead that cases like the above
still incur.

I imagine citext would benefit much more here once it has abbreviation
support (which should be a TODO item).

Omissions
--------------

I haven't attempted to accelerate AGG_SORTED strategy aggregates,
which looked like it would require more invasive changes. It seemed
like more trouble than it was worth, given that crossing group
boundaries is something that won't occur very often with typical
usage, and given the fact that text is naturally pretty fast there
anyway (who groups by a numeric attribute?). Similarly, I did not
teach setop_retrieve_direct() to consider the possibility that a set
operation (like a UNION) could reuse abbreviated keys if it happens to
be fed by a sort node. Finally, I did not accelerate the merging of
spools during B-Tree index builds, even though that actually seems
quite possible -- that case just seemed marginal. We currently have no
test coverage for that case [1], so I guess its performance can't be
too important.

SortSupport contract
================

As explained in the first patch's commit message, I revised the
contract that SortSupport has with opclasses. Should this proposal be
accepted, we should backpatch the first patch to 9.5, to prevent
anyone from building abbreviation support that won't work on 9.6 (even
if that is very unlikely). In general, it seems pretty silly to me to
not make use of the abbreviated keys that the sort already went to the
trouble of building, and it seems like the revision to the SortSupport
contract is not likely to notably limit any interesting cases in the
future, so I think that this will be uncontroversial.

[1]
http://www.postgresql.org/message-id/flat/CAM3SWZTvEtVDysXeE7Py-8Ar+-+XRAPkJCZe-FH_V+zWxmuS9A@mail.gmail.com#CAM3SWZTvEtVDysXeE7Py-8Ar+-+XRAPkJCZe-FH_V+zWxmuS9A@mail.gmail.com
--
Peter Geoghegan