/logout becomes slow (can time out) after having refreshed refresh tokens many times

[reivilibre]

I haven't had chance to verify / investigate this, but apparently it's easily reproducible and seems to correlate with having done a lot of refreshes before logging out.

I wonder if this means that clean-up isn't happening properly? I loosely checked that there was some code present that appears to be cleaning up upon a refresh, but that's not to say it's bug-free.

It would be good to check we have some tests to ensure clean-up happens during refreshes as expected (rather than in one big bang at logout) and then investigate the cause of this report.

[reivilibre]

The access token and refresh tokens gain a net entry for each refresh, so this would explain why the logout has to perform so much clean-up work.

In a bit of limited testing, it appears logout time is proportional to the square of the number of refreshes performed beforehand.

Will figure out why the clean-up code isn't doing as promised.

[reivilibre]

Another aspect is that the refresh_tokens table bears the following foreign key constraint:

Foreign-key constraints:
    "refresh_tokens_next_token_id_fkey" FOREIGN KEY (next_token_id) REFERENCES refresh_tokens(id) ON DELETE CASCADE

I note that there is no index on next_token_id (they are not automatically added by Postgres¹). As a result, each deletion in refresh_tokens results in a table scan of refresh_tokens. If there is a referencing row, it gets deleted (and so another deletion/table scan occurs… and this keeps on happening until such time as the end of the chain is reached).

The refresh tokens form a bit of a 'linked list'-like structure in the table, except instead of being random-access pointers, a table scan is needed for each access. This might explain the quadratic-seeming time complexity of /logout with respect to the number of refreshes performed.

There are two separate problems here:

• the chain of refresh tokens is not being cleared as we go. I think we want to outright delete entries with grandchildren to prevent them building up forever until logout, whilst still allowing the queries which rely on accessing an old token and its child.
• there is no index on next_token_id so we can't find a token's parent without a table scan

Footnotes

1. A foreign key must reference columns that either are a primary key or form a unique constraint. This means that the referenced columns always have an index (the one underlying the primary key or unique constraint); so checks on whether a referencing row has a match will be efficient. Since a DELETE of a row from the referenced table or an UPDATE of a referenced column will require a scan of the referencing table for rows matching the old value, it is often a good idea to index the referencing columns too. Because this is not always needed, and there are many choices available on how to index, declaration of a foreign key constraint does not automatically create an index on the referencing columns.
   — https://www.postgresql.org/docs/current/ddl-constraints.html#DDL-CONSTRAINTS-FK

   ↩