Message-ID: <e3602ccb-e643-2e79-ed2c-1175a80533a1@postgrespro.ru>
Date: Tue, 19 Sep 2023 11:42:13 +0700
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0)
 Gecko/20100101 Thunderbird/102.15.1
Subject: Re: POC: GROUP BY optimization
To: Tomas Vondra <tomas.vondra@enterprisedb.com>
Cc: Teodor Sigaev <teodor@sigaev.ru>,
 PostgreSQL Developers <pgsql-hackers@lists.postgresql.org>,
 David Rowley <dgrowleyml@gmail.com>, "a.rybakina"
 <a.rybakina@postgrespro.ru>, Tom Lane <tgl@sss.pgh.pa.us>,
 =?UTF-8?B?0JHQtdC70Y/Qu9C+0LIg0JTQsNC80LjRgCDQndCw0LjQu9C10LLQuNGH?=
 <d.belyalov@postgrespro.ru>
References: <CA+q6zcVRrd-z4YZ4M43ccst7aGL9==w5r1fionRWhP9ot6mybQ@mail.gmail.com>
 <006667af-fc50-0627-4be7-5d9cf665219f@enterprisedb.com>
 <dc933c66-41b9-8907-327e-f6361a690654@postgrespro.ru>
 <4ee5b15c-1ce0-59c7-8d4a-a1fd68ee0d12@postgrespro.ru>
 <721b3ff9-f214-f5d4-86c7-bae515bbec18@enterprisedb.com>
 <7bea462e-8c3e-0f8c-c7d5-f4daa12f3baf@postgrespro.ru>
 <9af89543-3d17-4c98-59de-1daa5bceeb06@enterprisedb.com>
 <9408e450-60c6-6fbc-d5c4-467bb0abfe67@postgrespro.ru>
 <44472925-f6c6-e8de-6f72-0451458532c4@enterprisedb.com>
 <CALNJ-vQp3WNV-kKuGsjSOhjRfdECA1Dbxa-vjAgOmQ4f4Qaw-Q@mail.gmail.com>
 <7a80a207-5e8e-b80c-476c-2d290b0526e9@enterprisedb.com>
 <65941e87-86c1-c09c-8ad5-8e102aebe8ee@enterprisedb.com>
 <CAApHDvq65=9Ro+hLX1i9ugWEiNDvHrBibAO7ARcTnf38_JE+UQ@mail.gmail.com>
 <CAApHDvoEF0GsqmBuCPXb6f12jPwz8EeLG-oYsOSc5zrJtKZHOg@mail.gmail.com>
 <7256159a-bb83-7ef3-c9c9-b2188a29aaf8@postgrespro.ru>
 <60610df1-c32f-ebdf-e58c-7a664431f452@enterprisedb.com>
Content-Language: en-US
From: Andrey Lepikhov <a.lepikhov@postgrespro.ru>
Organization: Postgres Professional
In-Reply-To: <60610df1-c32f-ebdf-e58c-7a664431f452@enterprisedb.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Archived-At: <https://www.postgresql.org/message-id/e3602ccb-e643-2e79-ed2c-1175a80533a1%40postgrespro.ru>
Precedence: bulk

On 20/7/2023 18:46, Tomas Vondra wrote:
> On 7/20/23 08:37, Andrey Lepikhov wrote:
>> On 3/10/2022 21:56, Tom Lane wrote:
>>> Revert "Optimize order of GROUP BY keys".
>>>
>>> This reverts commit db0d67db2401eb6238ccc04c6407a4fd4f985832 and
>>> several follow-on fixes.
>>> ...
>>> Since we're hard up against the release deadline for v15, let's
>>> revert these changes for now.  We can always try again later.
>>
>> It may be time to restart the project. As a first step, I rebased the
>> patch on the current master. It wasn't trivial because of some latest
>> optimizations (a29eab, 1349d27 and 8d83a5d).
>> Now, Let's repeat the review and rewrite the current path according to
>> the reasons uttered in the revert commit.
> 1) procost = 1.0 - I guess we could make this more realistic by doing
> some microbenchmarks and tuning the costs for the most expensive cases.
Ok, some thoughts on this part of the task. As I see, we have not so 
many different operators: 26 with fixed width and 16 with variable width:

SELECT o.oid,oprcode,typname,typlen FROM pg_operator o
   JOIN pg_type t ON (oprleft = t.oid)
WHERE (oprname='<') AND oprleft=oprright AND typlen>0
ORDER BY o.oid;

SELECT o.oid,oprcode,typname,typlen FROM pg_operator o
   JOIN pg_type t ON (oprleft = t.oid)
WHERE (oprname='<') AND oprleft=oprright AND typlen<0
ORDER BY o.oid;

Benchmarking procedure of types with fixed length can be something like 
below:

CREATE OR REPLACE FUNCTION pass_sort(typ regtype) RETURNS TABLE (
     nrows integer,
     exec_time float
)  AS $$
DECLARE
   data json;
   step integer;
BEGIN
   SET work_mem='1GB';

   FOR step IN 0..3 LOOP
     SELECT pow(100, step)::integer INTO nrows;
     DROP TABLE IF EXISTS test CASCADE;
     EXECUTE format('CREATE TABLE test AS SELECT gs::%s AS x
                     FROM generate_series(1,%s) AS gs;', typ, nrows);

     EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, FORMAT JSON)
       SELECT * FROM test ORDER BY (x) DESC INTO data;
     SELECT data->0->'Execution Time' INTO exec_time;
     RETURN NEXT;
   END LOOP;
END;
$$ LANGUAGE plpgsql VOLATILE;

Execution of SELECT * FROM pass_sort('integer'); shows quite linear grow 
of the execution time. So, using '2.0 * cpu_operator_cost' as a cost for 
the integer type (as a basis) we can calculate costs for other 
operators. Variable-width types, i think, could require more complex 
technique to check dependency on the length.

Does this way look worthwhile?

-- 
regards,
Andrey Lepikhov
Postgres Professional