Bad inner join performance on one-to-many relationship

Question

I have a question regarding the postgres planner that I can't wrap my head around. I am trying to get the planner to look up a project ID by its unique key before running the other side of the query joining permitted users.

The Issue

There is a significant performance difference between these two queries. I would like to make the inner join to perform better than it currently does, preferably without changing the schema.

Subquery

This query is fast, but it is pretty ugly and would require major refactoring in code.

SELECT *
FROM users
  INNER JOIN permissions ON permissions.user_id = users.id
WHERE
  permissions.project_id = (SELECT id FROM projects WHERE key = 'test')

Inner Join

This is nice, but super slow. For some reason, the planner uses a hashed or nested join between projects (one row) and the permissions (many rows) instead of running them synchronously - in a more efficient matter.

SELECT *
FROM users
  INNER JOIN permissions ON permissions.user_id = users.id
  INNER JOIN projects ON projects.id = permissions.project_id
WHERE
  projects.key = 'test'

Why is this so slow? Is there a way I can make the planner find the project before finding its users instead of running them both simultaneously in the inner join?

Live Example

See the setup and performance here: Fiddle

I have the following tables and indexes (stripped down for the example):

# \d users;
 Column    | Type | Nullable 
-----------+------+----------
 id        | int8 | not null 
 name      | text | not null 
Indexes:
"id_pkey" PRIMARY KEY, btree (id)

# \d projects;
 Column    | Type | Nullable 
-----------+------+----------
 id        | int8 | not null 
 key       | text | not null
 name      | text | not null 
Indexes:
"id_pkey" PRIMARY KEY, btree (id)
"key_unique" UNIQUE CONSTRAINT, btree (key)

# \d permissions;
 Column     | Type | Nullable 
------------+------+----------
 id         | int8 | not null 
 user_id    | int8 | not null 
 project_id | int8 | not null 
Indexes:
"id_pkey" PRIMARY KEY, btree (id)
"user_id_fk" btree (user_id)
"project_id_fk" btree (project_id)
"user_id_project_id_idx" btree (user_id, project_id)
Foreign-key constraints:
"fk_user" FOREIGN KEY (user_id) REFERENCES users (id)
"fk_project" FOREIGN KEY (project_id) REFERENCES projects (id)

Update

Changing the index order on the permission table and only selecting necessary columns does speed up the example above, but I may have oversimplified the queries for the example.

In the real-world problem, there is a recursive permissions hierarchy that still has way worse performance when using project key for lookup instead of project ID. See the updated Fiddle.

I would like to understand if there is a way for the optimizer to know that running one part of the query before the other would be faster than doing it in parallel.

Answer 1

Select just the columns you need, not *. Do you really need the primary key column from "permissions"? Doing this, combined, with Andrea's suggestion and a VACUUM, will allow a much faster index-only scan, see https://dbfiddle.uk/ddyTvGts