Re: Optimize LISTEN/NOTIFY

On Thu, Oct 16, 2025, at 20:16, Joel Jacobson wrote:
> On Thu, Oct 16, 2025, at 04:54, Chao Li wrote:
>>> On Oct 15, 2025, at 23:36, Joel Jacobson <joel@compiler.org> wrote:
>>> The latest version gets rid of GetPendingNotifyChannels()
>>> and replaces it with the local list pendingNotifyChannels.
>>
>> Sorry for the typo, Yes, I meant to dynahash” that you have already
>> been using it.
> ...
>> My suggestion of using dynahah was for the same purpose. Because
>> list_member_ptr() iterates through all list nodes until find the
>> target, so this code is still O(n^2).
>>
>> Using a hash will make it faster. I used to work on project Concourse
>> [1]. The system is heavily using the LISTEN/NOTIFY mechanism. There
>> would be thousands of channels at runtime. In that case, hash search
>> would be much faster than linear search.
>>
>> [1] https://github.com/concourse/concourse
>
> Building pendingNotifyChannels is O(N^2) yes, but how large N is
> realistic here?
>
> Note that pendingNotifyChannels is only the unique channels for the
> notifications in the *current transaction*. At Concourse, did you really
> do thousands of NOTIFY, with unique channel names, within the same
> transaction?

I tested doing

LISTEN ch1;
LISTEN ch2;
...
LISTEN ch100000;

in one backend, and then

\timing on
BEGIN;
NOTIFY ch1;
NOTIFY ch2;
...
NOTIFY ch100000;
COMMIT;

in another backend.

Timing for the final COMMIT of the 100k NOTIFY:
2.127 ms (master)
1428.441 ms (0002-optimize_listen_notify-v19.patch)

I agree this looks like a real problem, since I guess it's not
completely unthinkable someone might have
some kind of trigger on a table, that could fire off NOTIFY
for each row, possibly causing hundreds of thousands of
notifies in the same db txn.

I tried changing pendingNotifyChannels from a list to dynahash,
which improved the timing, down to 15.169 ms.

Once we have decided which of the three alternatives to go forward with,
I will add the dynahash code for pendingNotifyChannels.

Nice catch, thanks.

/Joel