Consider the number of columns in the sort cost model

Hi,

I would like to propose a slight elaboration of the sort cost model.
In practice, we frequently see the choice of suboptimal sortings, which
slump performance by 10-50%.

The key reason here is the optimiser's blindness to the fact that
sorting calls a comparison operator for each pair of attributes in the
tuple. Just for example:

SET work_mem = '128MB';
CREATE TABLE test (
x1 int,x2 int,x3 int,x4 int,x5 int,x6 int,x7 int,x8 int,payload text);
INSERT INTO test (x1,x2,x3,x4,x5,x6,x7,x8,payload) (
SELECT 1,2,3,4,5,6,7,(1E5-x), 'abc'||x
FROM generate_series(1,1E5) AS x);
VACUUM ANALYZE test;

Let's execute the following three queries:

EXPLAIN (ANALYZE)
SELECT * FROM test WHERE x1<9E4 ORDER BY x8;
EXPLAIN (ANALYZE)
SELECT * FROM test WHERE x1<9E4 ORDER BY x1,x2,x3,x8;
EXPLAIN (ANALYZE)
SELECT * FROM test WHERE x1<9E4 ORDER BY x1,x2,x3,x4,x5,x6,x7,x8;

My laptop executes these three queries in 100ms, 300ms, and 560ms,
respectively. At the same time, the costs of these query plans are
similar. This corner case shows that sorting matters and in the corner
case, dependence on the number of comparisons looks close to linear.

The patch in the attachment is a simplistic attempt to differentiate
these sortings by the number of columns. It is not ideal because
comparisons depend on the duplicates in each column, but it may be the
subject of further work.

Even such a trivial model allows us to resolve the case like the below:
CREATE INDEX ON test (x1,x2,x3,x8);
EXPLAIN (ANALYZE) SELECT * FROM test WHERE x1<9E4 ORDER BY x1,x2,x3,x8;

The current master will choose SeqScan for four columns as well as for a
single column. With the model, the optimiser will understand that
sorting four columns costs more than sorting a single column and switch
to IndexScan.

--
regards, Andrei Lepikhov