Query for empty relations is very slow for many-to-many relation

[vimutti77]

Bug description

I have a schema with many-to-many relation like this

model User {
  id     String  @id
  issues Issue[]
}

model Issue {
  id        String @id
  assignees User[]
}

I insert the data to database by using this SQL

INSERT INTO "User" ("id")
SELECT * FROM generate_series(1, 100) ;

INSERT INTO "Issue" ("id")
SELECT * FROM generate_series(1, 100000) ;

INSERT INTO "_IssueToUser" ("A", "B")
SELECT * FROM generate_series(1, 100000) AS A, generate_series(1, 100) AS B;

I want to count the Issue that have empty assignees by using prisma.issue.count({ where: { assignees: { none: {} } } })
But it takes about 1-2 mins to get the result.

How to reproduce

1. Create schema with many-to-many relation
2. Insert mock data
3. Count the items that relation is empty

Expected behavior

It should be fast

Prisma information

model User {
  id     String  @id
  issues Issue[]
}

model Issue {
  id        String @id
  assignees User[]
}

// Add your code using Prisma Client
prisma.issue.count({ where: { assignees: { none: {} } } })

Environment & setup

• OS: Windows, Linux
• Database: PostgreSQL
• Node.js version: 20

Prisma Version

prisma                  : 5.22.0
@prisma/client          : 5.22.0
Computed binaryTarget   : windows
Operating System        : win32
Architecture            : x64
Node.js                 : v20.13.1
Query Engine (Node-API) : libquery-engine 605197351a3c8bdd595af2d2a9bc3025bca48ea2 (at node_modules\.pnpm\@[email protected]\node_modules\@prisma\engines\query_engine-windows.dll.node)
Schema Engine           : schema-engine-cli 605197351a3c8bdd595af2d2a9bc3025bca48ea2 (at node_modules\.pnpm\@[email protected]\node_modules\@prisma\engines\schema-engine-windows.exe)  
Schema Wasm             : @prisma/prisma-schema-wasm 5.22.0-44.605197351a3c8bdd595af2d2a9bc3025bca48ea2
Default Engines Hash    : 605197351a3c8bdd595af2d2a9bc3025bca48ea2
Studio                  : 0.503.0

[vimutti77]

The SQL from prisma is using NOT IN which is very slow in this case (total time ~1.30 mins).

SELECT COUNT(*)
FROM (
  SELECT "public"."Issue"."id"
  FROM "public"."Issue"
  WHERE ("public"."Issue"."id") NOT IN (
    SELECT "t1"."A"
	FROM "public"."_IssueToUser" AS "t1"
	INNER JOIN "public"."User" AS "j1"
	ON ("j1"."id") = ("t1"."B")
	WHERE (1=1 AND "t1"."A" IS NOT NULL)
  )
) AS "sub"

I modified it to use NOT EXISTS instead, which speeds up the query significantly (total time ~0.5 secs).

SELECT COUNT(*)
FROM (
  SELECT "public"."Issue"."id"
  FROM "public"."Issue"
  WHERE NOT EXISTS (
    SELECT "t1"."A"
	FROM "public"."_IssueToUser" AS "t1"
	INNER JOIN "public"."User" AS "j1"
	ON ("j1"."id") = ("t1"."B")
	WHERE ("public"."Issue"."id" = "t1"."A")
  )
) AS "sub"

[vimutti77]

This issue may be related to #24524.
The problem is prisma using IN / NOT IN for filtering relationship which is very inefficient for large table.

[jacek-prisma]

Hi @vimutti77, @senorverde-tc and @Sjlver,
I've published a dev version which uses correlated subqueries for all relational filters, it'd be good to get some feedback on whether it performs better in typical user workloads, it's been published as:
prisma@6.3.0-integration-engines-6-3-0-1-feat-relation-exists-aff8bf73313e0df76046e671a2cb2d31491601a3.5

If you can offer some feedback on it that'd be great.

[Sjlver]

Hi @jacek-prisma, thanks so much for working on this!

I can give this a try mid next week, around Jan 15. To make sure I understand: I need to specify prisma@6.3.0-integration-engines-6-3-0-1-feat-relation-exists-aff8bf73313e0df76046e671a2cb2d31491601a3.3 in my package.json file as the prisma version? Do I need the same for @prisma/client?

[jacek-prisma]

Hi @Sjlver. yes, these are the two NPM packages:

• prisma@6.3.0-integration-engines-6-3-0-1-feat-relation-exists-aff8bf73313e0df76046e671a2cb2d31491601a3.5
@prisma/client@6.3.0-integration-engines-6-3-0-1-feat-relation-exists-aff8bf73313e0df76046e671a2cb2d31491601a3.5

[vimutti77]

@jacek-prisma I have upgraded to the version you mentioned, but it still uses IN. What else do I need to do?

Prisma Version

prisma                  : 6.3.0-integration-engines-6-3-0-2-integration-sql-nested-transactions5-9a074425ccc05b5ec12b88ec141ba5dea21472b7.2
@prisma/client          : 6.3.0-integration-engines-6-3-0-2-integration-sql-nested-transactions5-9a074425ccc05b5ec12b88ec141ba5dea21472b7.2
Computed binaryTarget   : windows
prisma                  : 6.3.0-integration-engines-6-3-0-2-integration-sql-nested-transactions5-9a074425ccc05b5ec12b88ec141ba5dea21472b7.2
@prisma/client          : 6.3.0-integration-engines-6-3-0-2-integration-sql-nested-transactions5-9a074425ccc05b5ec12b88ec141ba5dea21472b7.2
Computed binaryTarget   : windows
Operating System        : win32
Architecture            : x64
Node.js                 : v20.13.1
TypeScript              : 5.4.5
Query Engine (Node-API) : libquery-engine 9a074425ccc05b5ec12b88ec141ba5dea21472b7 (at node_modules\.pnpm\@prisma+engines@6.3.0-integration-engines-6-3-0-2-integration-sql-nested-transactions5-9a0744_kt6xdhq7jmyzsepmxwuvshgjom\node_modules\@prisma\engines\query_engine-windows.dll.node)
Schema Engine           : schema-engine-cli 9a074425ccc05b5ec12b88ec141ba5dea21472b7 (at node_modules\.pnpm\@prisma+engines@6.3.0-integration-engines-6-3-0-2-integration-sql-nested-transactions5-9a0744_kt6xdhq7jmyzsepmxwuvshgjom\node_modules\@prisma\engines\schema-engine-windows.exe)
Schema Wasm             : @prisma/prisma-schema-wasm 6.3.0-2.integration-sql-nested-transactions5-9a074425ccc05b5ec12b88ec141ba5dea21472b7
Default Engines Hash    : 9a074425ccc05b5ec12b88ec141ba5dea21472b7
Studio                  : 0.503.0

[jacek-prisma]

Sorry @vimutti77 , I've listed the wrong version, I just updated the comment with the correct one!

[vimutti77]

Thanks @jacek-prisma. I did some initial testing, and the query time was reduced to 0.5 seconds! I haven't encountered any issues yet.

[Sjlver]

@jacek-prisma you were faster than I was. If you still need me to look into this, let me know.