Feedback-ID: ie8b149e1:Fastmail
User-Agent: Cyrus-JMAP/3.9.0-alpha0-761-gece9e40c48-fm-20230913.001-gece9e40c
MIME-Version: 1.0
Message-Id: <db387e04-beb5-4454-8ad7-e358d3308e12@app.fastmail.com>
In-Reply-To: 
 <CAApHDvofBE-oG998LnEWO6aOrZxnh11BtSOK9uDpjoFwahZ65A@mail.gmail.com>
References: <0d3f9971e82d2d969a5f@zeyos.com>
 <379b65d3-fde4-a9b4-1ea9-4eaa3936e729@postgrespro.ru>
 <CAApHDvofBE-oG998LnEWO6aOrZxnh11BtSOK9uDpjoFwahZ65A@mail.gmail.com>
Date: Wed, 20 Sep 2023 22:17:46 +0700
From: "Lepikhov Andrei" <a.lepikhov@postgrespro.ru>
To: "David Rowley" <dgrowleyml@gmail.com>
Cc: "Benjamin Coutu" <ben.coutu@zeyos.com>,
 "PostgreSQL Hackers" <pgsql-hackers@lists.postgresql.org>,
 "Tom Lane" <tgl@sss.pgh.pa.us>, "Robert Haas" <robertmhaas@gmail.com>,
 "Peter Geoghegan" <pg@bowt.ie>
Subject: Re: disfavoring unparameterized nested loops
Content-Type: text/plain
Archived-At: <https://www.postgresql.org/message-id/db387e04-beb5-4454-8ad7-e358d3308e12%40app.fastmail.com>
Precedence: bulk


On Wed, Sep 20, 2023, at 4:49 PM, David Rowley wrote:
> On Wed, 20 Sept 2023 at 19:56, Andrey Lepikhov
> <a.lepikhov@postgrespro.ru> wrote:
>> What could you say about a different way: hybrid join? In MS SQL Server,
>> they have such a feature [1], and, according to their description, it
>> requires low overhead. They start from HashJoin and switch to NestLoop
>> if the inner input contains too small tuples. It solves the issue, Isn't it?
>
> A complexity which you may not be considering here is that Nested Loop
> joins always preserve the tuple order from the outer side of the join,
> whereas hash joins will not do this when multi-batching.

My idea here is the same as MS SQL guys did: prefetch from the HashJoin inner some predefined number of tuples and, if the planner has made a mistake and overestimated it, move hash join inner to NestLoop as an outer.
The opposite strategy, "underestimation" - starting with NestLoop and switching to HashJoin looks more difficult, but the main question is: is it worthwhile to research?

> I've no idea how the SQL Server engineers solved that.

>> [1]
>> https://techcommunity.microsoft.com/t5/sql-server-blog/introducing-batch-mode-adaptive-joins/ba-p/385411

-- 
Regards,
Andrei Lepikhov