Speed of deleting data from the users_who_share_private_rooms table

[kosmos]

We encountered a problem with the performance of deleting records from the users_who_share_private_rooms table. The problem occurs when executing the following code:

https://github.com/element-hq/synapse/blob/develop/synapse/storage/databases/main/user_directory.py#L960

The first deletion is fast, but the second one has a problem under certain conditions. If the home server has rooms with a large number of users (for example, tens of thousands), then when a user is deleted, 2*n^2 records are deleted from this table.

The first deletion (https://github.com/element-hq/synapse/blob/develop/synapse/storage/databases/main/user_directory.py#L955) is fast and does not cause problems, but the second deletion, in which we search by other_user_id causes problems.

In this regard, the question came up: why exactly do we create a btree index for this field?

CREATE INDEX users_who_share_private_rooms_o_idx ON users_who_share_private_rooms USING btree (other_user_id);

Wouldn't this index be more optimal if it were hash?