From: jkaczman (@jkaczman) <noreply+jkaczman@github.com>
To: pgdogdev/pgdog <noreply+pgdogdev-pgdog@github.com>
Subject: [pgdogdev/pgdog] PR #2070: feat: support two-table cross-shard JOINs (JOIN, LEFT JOIN, CROSS JOIN, NATURAL JOIN)
Date: Thu, 19 Nov 2026 12:31:59 +0000
Message-ID: <gh-pgdogdev-pgdog-2070@github.com> (raw)
Building off of #2042, #2060, #2061, #2064 and #2066, this PR now executes and re-writes JOINs of two sharded tables (if subqueries are set to be rewritten in pgdog.toml)
This is the start of the foundation for cross-shard JOINs (re #94) giving partial support for `JOIN`, `LEFT JOIN`, `CROSS JOIN` and `NATURAL JOIN`
Say we have a statement such as
> `SELECT o.id, s.username FROM orders o JOIN users s ON s.id = o.seller_id`
where `orders` is sharded by `buyer_id` (the user who bought the order) and `users` by `id`.
Say order 10 is on Shard A (with the buyer of order 10), but the seller of order 10, user 3, is on Shard B.
Previously, we sent the statement to all shards as-is. Neither shard is fundamentally capable of joining order 10 with user 3 as order 10 is on Shard A but user 3 is on Shard B. Therefore, the client didn't receive `(10, 'user3')`.
Now, we first fetch **all** rows of the table after `JOIN` (`s`) from all shards with `SELECT * FROM users s` (will change; see future work). Then, we re-write the JOIN to use the fetched rows as `unnest(..)` arrays (as we do for subqueries in #2003 and #2023):
```sql
SELECT o.id, s.username FROM orders o JOIN (SELECT u.c1, u.c2, u.c3 FROM unnest($1::pg_catalog._int8, $2::pg_catalog._text, $3::pg_catalog._text) u(c1, c2, c3)) s(id, username, status) ON s.id = o.seller_id
```
Shard A now is capable of joining the forementioned order 10 with user 3 (from the fetched rows), so the client now correctly receives `(10, 'user3')`!
If JOINs are on the sharding keys of both tables (e.g., `ON s.id = o.buyer_id`) and both tables are sharded the same way, we correctly don't rewrite these as they can be run as-is (the rows that those JOINs join fundamentally align to the same shard).
Some other cases are handled:
- Tables without aliases after `JOIN` (as Rails writes JOINs) (e.g., `INNER JOIN "users" ON "users"."id" = "orders"."seller_id"`)
- `INSERT INTO .. SELECT .. JOIN ..`
- JOINs next to cross-shard subqueries in `WHERE` (e.g., `.. JOIN users u ON .. WHERE o.id IN (SELECT order_id FROM packages)`)
Planned future work (for JOINs):
- Three or more tables, `RIGHT JOIN` and `FULL JOIN` (sent as-is for now; same as before)
- `LEFT JOIN`s from tables that aren't sharded (e.g., `FROM states s LEFT JOIN users u ON ..`) (sent as-is for now; same as before)
- Fetching only the columns and rows that statements actually use instead of whole tables
- Returning errors if the fetched rows are larger than a limit (e.g., 100 MB)
Unrelated fixes:
- Errors that Postgres returns for fetches are now returned to the client instead of closing the client's connection
inline patch 1: integration/rust/tests/integration/subqueries/tests/insert.sql, integration/rust/tests/integration/subqueries/tests/select.sql, integration/rust/tests/integration/subqueries/todo.sql and 13 more (+809/-26 lines) download inline-1.patchdiff --git a/integration/rust/tests/integration/subqueries/tests/insert.sql b/integration/rust/tests/integration/subqueries/tests/insert.sqlindex becdf856b..159db89b2 100644--- a/integration/rust/tests/integration/subqueries/tests/insert.sql+++ b/integration/rust/tests/integration/subqueries/tests/insert.sql@@ -130,6 +130,17 @@ INSERT INTO subpackages (id, user_id) SELECT id, id FROM subusers ORDER BY id DE
-- verify: SELECT * FROM subpackages ORDER BY id
INSERT INTO subpackages (id, user_id, order_id) SELECT suborders.id, suborders.user_id, suborders.id FROM suborders JOIN subusers ON suborders.user_id = subusers.id
+-- case+-- what: INSERT INTO .. SELECT .. JOIN on suborders.id = subusers.id (the sharding key of suborders is user_id, not id)+-- route select: 0,1+-- sql: SELECT * FROM subusers u+-- route select: 0,1+-- sql: SELECT o.id, u.id FROM suborders o JOIN (SELECT u.c1, u.c2, u.c3, u.c4, u.c5, u.c6, ($7::pg_catalog._varchar)[u.c7 + 1:u.c7 + u.c8], ($10::pg_catalog._int8)[u.c9 + 1:u.c9 + u.c10] FROM unnest($1::pg_catalog._int8, $2::pg_catalog._text, $3::pg_catalog._text, $4::pg_catalog._jsonb, $5::pg_catalog._date, $6::pg_catalog._inet, $8::pg_catalog._int4, $9::pg_catalog._int4, $11::pg_catalog._int4, $12::pg_catalog._int4) u(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10)) u(id, username, status, profile, signed_up, last_ip, tags, media_ids) ON o.id = u.id+-- route insert: 0,1+-- sql: INSERT INTO subpackages (id, user_id) SELECT u.c1, u.c2 FROM unnest($1::pg_catalog._int8, $2::pg_catalog._int8) u(c1, c2)+-- verify: SELECT * FROM subpackages ORDER BY id+INSERT INTO subpackages (id, user_id) SELECT o.id, u.id FROM suborders o JOIN subusers u ON o.id = u.id+
-- case
-- what: WITH a AS (..), b AS (SELECT .. FROM a) INSERT .. FROM a JOIN b .., one CTE over another
-- route select: 0,1
diff --git a/integration/rust/tests/integration/subqueries/tests/select.sql b/integration/rust/tests/integration/subqueries/tests/select.sqlindex 33f600c8f..878ddfd1b 100644--- a/integration/rust/tests/integration/subqueries/tests/select.sql+++ b/integration/rust/tests/integration/subqueries/tests/select.sql@@ -248,6 +248,12 @@ SELECT COUNT(*) FROM (SELECT 1 AS one FROM subusers WHERE status = 'VIP' LIMIT 4
-- sql: SELECT count(*) FROM (SELECT 1 FROM unnest($1::pg_catalog._int4) u(c1)) subquery_for_count(one) WHERE false
SELECT COUNT(*) FROM (SELECT 1 AS one FROM subusers WHERE status = 'nobody' LIMIT 40) subquery_for_count;
+-- case+-- what: .. WHERE <col> IN (<sq>), <sq> returns an error+-- route select: 0,1+-- sql: SELECT 1 / 0 FROM subusers+SELECT * FROM subusers WHERE id IN (SELECT 1 / 0 FROM subusers);+
-- case
-- what: Derived table with an inner-table that returns an empty response.
-- Want to make sure that the OIDs returned are correct (if present)
@@ -302,3 +308,184 @@ WITH a AS (
WITH a AS (
SELECT id, status FROM subusers
) SELECT x.id, y.id FROM a x JOIN a y ON x.status = y.status ORDER BY x.id, y.id;
++-- case+-- what: .. FROM subusers u JOIN suborders o ON u.id = o.user_id (the sharding keys of both tables)+-- used by: Mastodon, which joins accounts to users with Account.joins(:user) on accounts.id = users.account_id+-- - https://github.com/mastodon/mastodon/blob/v4.3.0/app/lib/feed_manager.rb#L21+-- route select: 0,1+-- sql: SELECT u.id, u.username, o.id AS order_id FROM subusers u JOIN suborders o ON u.id = o.user_id ORDER BY o.id+SELECT u.id, u.username, o.id AS order_id FROM subusers u+JOIN suborders o ON u.id = o.user_id+ORDER BY o.id;++-- case+-- what: JOIN on suborders.id = subusers.id (the sharding key of suborders is user_id, not id)+-- used by: Mastodon, which joins notifications to the accounts that sent the notifications on accounts.id = notifications.from_account_id+-- - https://github.com/mastodon/mastodon/blob/v4.3.0/app/models/notification.rb#L108+-- route select: 0,1+-- sql: SELECT * FROM subusers u+-- route select: 0,1+-- sql: SELECT o.id, o.user_id, u.username FROM suborders o JOIN (SELECT u.c1, u.c2, u.c3, u.c4, u.c5, u.c6, ($7::pg_catalog._varchar)[u.c7 + 1:u.c7 + u.c8], ($10::pg_catalog._int8)[u.c9 + 1:u.c9 + u.c10] FROM unnest($1::pg_catalog._int8, $2::pg_catalog._text, $3::pg_catalog._text, $4::pg_catalog._jsonb, $5::pg_catalog._date, $6::pg_catalog._inet, $8::pg_catalog._int4, $9::pg_catalog._int4, $11::pg_catalog._int4, $12::pg_catalog._int4) u(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10)) u(id, username, status, profile, signed_up, last_ip, tags, media_ids) ON o.id = u.id ORDER BY o.id+SELECT o.id, o.user_id, u.username FROM suborders o+JOIN subusers u ON o.id = u.id+ORDER BY o.id;++-- case+-- what: JOIN on x.status = y.status (the sharding key of subusers is id)+-- used by: Mastodon, which joins follows to the followed accounts on follows.target_account_id = target_accounts.id to suggest accounts to follow+-- - https://github.com/mastodon/mastodon/blob/v4.3.0/app/models/account_suggestions/friends_of_friends_s...+-- route select: 0,1+-- sql: SELECT * FROM subusers y+-- route select: 0,1+-- sql: SELECT x.id, y.id, x.id AS __pgdog_order_col0, y.id AS __pgdog_order_col1 FROM subusers x JOIN (SELECT u.c1, u.c2, u.c3, u.c4, u.c5, u.c6, ($7::pg_catalog._varchar)[u.c7 + 1:u.c7 + u.c8], ($10::pg_catalog._int8)[u.c9 + 1:u.c9 + u.c10] FROM unnest($1::pg_catalog._int8, $2::pg_catalog._text, $3::pg_catalog._text, $4::pg_catalog._jsonb, $5::pg_catalog._date, $6::pg_catalog._inet, $8::pg_catalog._int4, $9::pg_catalog._int4, $11::pg_catalog._int4, $12::pg_catalog._int4) u(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10)) y(id, username, status, profile, signed_up, last_ip, tags, media_ids) ON x.status = y.status ORDER BY x.id, y.id+SELECT x.id, y.id FROM subusers x+JOIN subusers y ON x.status = y.status+ORDER BY x.id, y.id;++-- case+-- what: LEFT JOIN on x.status = y.status (the sharding key of subusers is id)+-- used by: Mastodon, which LEFT JOINs accounts to follows on follows.target_account_id = accounts.id to show admins the most followed accounts of a server+-- - https://github.com/mastodon/mastodon/blob/v4.3.0/app/lib/admin/metrics/dimension/instance_accounts_d...+-- route select: 0,1+-- sql: SELECT * FROM subusers y+-- route select: 0,1+-- sql: SELECT x.id, y.id, x.id AS __pgdog_order_col0, y.id AS __pgdog_order_col1 FROM subusers x LEFT JOIN (SELECT u.c1, u.c2, u.c3, u.c4, u.c5, u.c6, ($7::pg_catalog._varchar)[u.c7 + 1:u.c7 + u.c8], ($10::pg_catalog._int8)[u.c9 + 1:u.c9 + u.c10] FROM unnest($1::pg_catalog._int8, $2::pg_catalog._text, $3::pg_catalog._text, $4::pg_catalog._jsonb, $5::pg_catalog._date, $6::pg_catalog._inet, $8::pg_catalog._int4, $9::pg_catalog._int4, $11::pg_catalog._int4, $12::pg_catalog._int4) u(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10)) y(id, username, status, profile, signed_up, last_ip, tags, media_ids) ON x.status = y.status ORDER BY x.id, y.id+SELECT x.id, y.id FROM subusers x+LEFT JOIN subusers y ON x.status = y.status+ORDER BY x.id, y.id;++-- case+-- what: .. FROM subusers x CROSS JOIN subusers y+-- used by: not Mastodon or Rails, but CROSS JOIN was free to add, since Postgres parses CROSS JOIN as an inner JOIN without an ON clause+-- route select: 0,1+-- sql: SELECT * FROM subusers y+-- route select: 0,1+-- sql: SELECT x.id, y.id FROM subusers x CROSS JOIN (SELECT u.c1, u.c2, u.c3, u.c4, u.c5, u.c6, ($7::pg_catalog._varchar)[u.c7 + 1:u.c7 + u.c8], ($10::pg_catalog._int8)[u.c9 + 1:u.c9 + u.c10] FROM unnest($1::pg_catalog._int8, $2::pg_catalog._text, $3::pg_catalog._text, $4::pg_catalog._jsonb, $5::pg_catalog._date, $6::pg_catalog._inet, $8::pg_catalog._int4, $9::pg_catalog._int4, $11::pg_catalog._int4, $12::pg_catalog._int4) u(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10)) y(id, username, status, profile, signed_up, last_ip, tags, media_ids) ORDER BY 1, 2+SELECT x.id, y.id FROM subusers x+CROSS JOIN subusers y+ORDER BY 1, 2;++-- case+-- what: .. FROM suborders o NATURAL JOIN subusers u (id is the only shared column between the two tables)+-- used by: not Mastodon or Rails, but NATURAL JOIN was free to add, since Postgres parses NATURAL JOIN as an inner JOIN on the shared columns between the two tables+-- route select: 0,1+-- sql: SELECT * FROM subusers u+-- route select: 0,1+-- sql: SELECT o.id, u.username FROM suborders o NATURAL JOIN (SELECT u.c1, u.c2, u.c3, u.c4, u.c5, u.c6, ($7::pg_catalog._varchar)[u.c7 + 1:u.c7 + u.c8], ($10::pg_catalog._int8)[u.c9 + 1:u.c9 + u.c10] FROM unnest($1::pg_catalog._int8, $2::pg_catalog._text, $3::pg_catalog._text, $4::pg_catalog._jsonb, $5::pg_catalog._date, $6::pg_catalog._inet, $8::pg_catalog._int4, $9::pg_catalog._int4, $11::pg_catalog._int4, $12::pg_catalog._int4) u(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10)) u(id, username, status, profile, signed_up, last_ip, tags, media_ids) ORDER BY 1+SELECT o.id, u.username FROM suborders o+NATURAL JOIN subusers u+ORDER BY 1;++-- case+-- what: .. FROM suborders o JOIN substates s ON s.state = o.state (substates isn't sharded)+-- used by: Mastodon, which joins statuses to oauth_applications to find the apps that users post with the most+-- - https://github.com/mastodon/mastodon/blob/v4.3.0/app/lib/annual_report/most_used_apps.rb#L20+-- route select: 0,1+-- sql: SELECT o.id, s.shipping FROM suborders o JOIN substates s ON s.state = o.state ORDER BY o.id+SELECT o.id, s.shipping FROM suborders o+JOIN substates s ON s.state = o.state+ORDER BY o.id;++-- case+-- what: .. FROM "suborders" INNER JOIN "subusers" ON "subusers"."id" = "suborders"."id" (without an alias)+-- used by: Mastodon, which leaves out the notifications from suspended accounts with Notification.without_suspended, i.e., joins(:from_account), which Rails writes without an alias+-- - https://github.com/mastodon/mastodon/blob/v4.3.0/app/models/notification.rb#L108+-- route select: 0,1+-- sql: SELECT * FROM subusers+-- route select: 0,1+-- sql: SELECT suborders.id, subusers.username FROM suborders JOIN (SELECT u.c1, u.c2, u.c3, u.c4, u.c5, u.c6, ($7::pg_catalog._varchar)[u.c7 + 1:u.c7 + u.c8], ($10::pg_catalog._int8)[u.c9 + 1:u.c9 + u.c10] FROM unnest($1::pg_catalog._int8, $2::pg_catalog._text, $3::pg_catalog._text, $4::pg_catalog._jsonb, $5::pg_catalog._date, $6::pg_catalog._inet, $8::pg_catalog._int4, $9::pg_catalog._int4, $11::pg_catalog._int4, $12::pg_catalog._int4) u(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10)) subusers(id, username, status, profile, signed_up, last_ip, tags, media_ids) ON subusers.id = suborders.id ORDER BY suborders.id+SELECT "suborders"."id", "subusers"."username" FROM "suborders"+INNER JOIN "subusers" ON "subusers"."id" = "suborders"."id"+ORDER BY "suborders"."id";++-- case+-- what: .. FROM suborders JOIN subusers ON .. WHERE subusers.id = 3+-- We use the name subusers as the alias of the fetched rows, so subusers.id = 3 refers to the fetched rows, not to the table subusers+-- The router doesn't route by subusers.id = 3, since the fetched rows are a derived table (#2064)+-- route select: 0,1+-- sql: SELECT * FROM subusers+-- route select: 0,1+-- sql: SELECT suborders.id, subusers.id FROM suborders JOIN (SELECT u.c1, u.c2, u.c3, u.c4, u.c5, u.c6, ($7::pg_catalog._varchar)[u.c7 + 1:u.c7 + u.c8], ($10::pg_catalog._int8)[u.c9 + 1:u.c9 + u.c10] FROM unnest($1::pg_catalog._int8, $2::pg_catalog._text, $3::pg_catalog._text, $4::pg_catalog._jsonb, $5::pg_catalog._date, $6::pg_catalog._inet, $8::pg_catalog._int4, $9::pg_catalog._int4, $11::pg_catalog._int4, $12::pg_catalog._int4) u(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10)) subusers(id, username, status, profile, signed_up, last_ip, tags, media_ids) ON subusers.id = suborders.id WHERE subusers.id = 3+SELECT "suborders"."id", "subusers"."id" FROM "suborders"+INNER JOIN "subusers" ON "subusers"."id" = "suborders"."id"+WHERE "subusers"."id" = 3;++-- case+-- what: .. FROM "subusers" LEFT OUTER JOIN "suborders" ON "suborders"."id" = "subusers"."id" (without an alias)+-- used by: Mastodon, which LEFT JOINs statuses to mentions with account.statuses.left_outer_joins(:mentions) to list the posts of other accounts without boosts (exclude_reblogs=true)+-- - https://github.com/mastodon/mastodon/blob/v4.3.0/app/lib/account_statuses_filter.rb#L49+-- route select: 0,1+-- sql: SELECT * FROM suborders+-- route select: 0,1+-- sql: SELECT subusers.id, suborders.id FROM subusers LEFT JOIN (SELECT u.c1, u.c2, u.c3, u.c4 FROM unnest($1::pg_catalog._int8, $2::pg_catalog._int8, $3::pg_catalog._text, $4::pg_catalog._timestamptz) u(c1, c2, c3, c4)) suborders(id, user_id, state, created_at) ON suborders.id = subusers.id ORDER BY 1, 2+SELECT "subusers"."id", "suborders"."id" FROM "subusers"+LEFT OUTER JOIN "suborders" ON "suborders"."id" = "subusers"."id"+ORDER BY 1, 2;++-- case+-- what: .. FROM suborders JOIN subusers ON .. WHERE suborders.id IN (SELECT .. FROM subusers ..)+-- We rewrite this statement twice (first the subquery in WHERE, then the JOIN)+-- Without the `|=` in `send_query_string`, simple-protocol clients would receive ParseComplete and BindComplete before the rows+-- route select: 0,1+-- sql: SELECT subusers.id FROM subusers WHERE subusers.status = 'VIP'+-- route select: 0,1+-- sql: SELECT * FROM subusers+-- route select: 0,1+-- sql: SELECT suborders.id FROM suborders JOIN (SELECT u.c1, u.c2, u.c3, u.c4, u.c5, u.c6, ($8::pg_catalog._varchar)[u.c7 + 1:u.c7 + u.c8], ($11::pg_catalog._int8)[u.c9 + 1:u.c9 + u.c10] FROM unnest($2::pg_catalog._int8, $3::pg_catalog._text, $4::pg_catalog._text, $5::pg_catalog._jsonb, $6::pg_catalog._date, $7::pg_catalog._inet, $9::pg_catalog._int4, $10::pg_catalog._int4, $12::pg_catalog._int4, $13::pg_catalog._int4) u(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10)) subusers(id, username, status, profile, signed_up, last_ip, tags, media_ids) ON subusers.id = suborders.id WHERE suborders.id IN (SELECT u.c1 FROM unnest($1::pg_catalog._int8) u(c1)) ORDER BY 1+SELECT "suborders"."id" FROM "suborders"+INNER JOIN "subusers" ON "subusers"."id" = "suborders"."id"+WHERE "suborders"."id" IN (SELECT "subusers"."id" FROM "subusers" WHERE "subusers"."status" = 'VIP')+ORDER BY 1;++-- case+-- what: .. FROM suborders o JOIN subusers u ON .. WHERE o.user_id = 2 (o.user_id is the sharding key of suborders)+-- used by: Mastodon, which lists the notifications of the current account with current_account.notifications.without_suspended (WHERE notifications.account_id = ..)+-- - https://github.com/mastodon/mastodon/blob/v4.3.0/app/controllers/api/v1/notifications_controller.rb#...+-- route select: 0,1+-- sql: SELECT * FROM subusers u+-- route select: 0+-- sql: SELECT o.id, u.id FROM suborders o JOIN (SELECT u.c1, u.c2, u.c3, u.c4, u.c5, u.c6, ($7::pg_catalog._varchar)[u.c7 + 1:u.c7 + u.c8], ($10::pg_catalog._int8)[u.c9 + 1:u.c9 + u.c10] FROM unnest($1::pg_catalog._int8, $2::pg_catalog._text, $3::pg_catalog._text, $4::pg_catalog._jsonb, $5::pg_catalog._date, $6::pg_catalog._inet, $8::pg_catalog._int4, $9::pg_catalog._int4, $11::pg_catalog._int4, $12::pg_catalog._int4) u(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10)) u(id, username, status, profile, signed_up, last_ip, tags, media_ids) ON u.id = o.id WHERE o.user_id = 2 ORDER BY 1, 2+SELECT o.id, u.id FROM suborders o+JOIN subusers u ON u.id = o.id+WHERE o.user_id = 2+ORDER BY 1, 2;++-- case+-- what: .. FROM subusers x LEFT JOIN subpackages y ON x.id = y.order_id (subpackages doesn't have any rows)+-- We send empty unnest(..) arrays in place of subpackages y+-- route select: 0,1+-- sql: SELECT * FROM subpackages y+-- route select: 0,1+-- sql: SELECT x.id, y.id FROM subusers x LEFT JOIN (SELECT u.c1, u.c2, u.c3, u.c4, u.c5 FROM unnest($1::pg_catalog._int8, $2::pg_catalog._int8, $3::pg_catalog._int8, $4::pg_catalog._timestamptz, $5::pg_catalog._timestamptz) u(c1, c2, c3, c4, c5)) y(id, user_id, order_id, shipped_at, estimated_arrival_time) ON x.id = y.order_id ORDER BY 1, 2+SELECT x.id, y.id FROM subusers x+LEFT JOIN subpackages y ON x.id = y.order_id+ORDER BY 1, 2;++-- case+-- what: JOIN on x.status = y.status with parameters in ON and WHERE+-- route select: 0,1+-- sql: SELECT * FROM subusers y+-- route select: 0+-- sql: SELECT x.id, y.id FROM subusers x JOIN (SELECT u.c1, u.c2, u.c3, u.c4, u.c5, u.c6, ($9::pg_catalog._varchar)[u.c7 + 1:u.c7 + u.c8], ($12::pg_catalog._int8)[u.c9 + 1:u.c9 + u.c10] FROM unnest($3::pg_catalog._int8, $4::pg_catalog._text, $5::pg_catalog._text, $6::pg_catalog._jsonb, $7::pg_catalog._date, $8::pg_catalog._inet, $10::pg_catalog._int4, $11::pg_catalog._int4, $13::pg_catalog._int4, $14::pg_catalog._int4) u(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10)) y(id, username, status, profile, signed_up, last_ip, tags, media_ids) ON x.status = y.status AND y.username <> $2 WHERE x.id = $1 ORDER BY 1, 2+-- $1 = 1+-- $2 = nobody+SELECT x.id, y.id FROM subusers x+JOIN subusers y ON x.status = y.status AND y.username <> $2+WHERE x.id = $1+ORDER BY 1, 2;++-- case+-- what: .. WHERE id <= $1 AND id IN (SELECT .. FROM suborders o JOIN subusers u ON .. WHERE o.id >= $2)+-- route select: 0,1+-- sql: SELECT * FROM subusers u+-- route select: 0,1+-- sql: SELECT u.id FROM suborders o JOIN (SELECT u.c1, u.c2, u.c3, u.c4, u.c5, u.c6, ($8::pg_catalog._varchar)[u.c7 + 1:u.c7 + u.c8], ($11::pg_catalog._int8)[u.c9 + 1:u.c9 + u.c10] FROM unnest($2::pg_catalog._int8, $3::pg_catalog._text, $4::pg_catalog._text, $5::pg_catalog._jsonb, $6::pg_catalog._date, $7::pg_catalog._inet, $9::pg_catalog._int4, $10::pg_catalog._int4, $12::pg_catalog._int4, $13::pg_catalog._int4) u(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10)) u(id, username, status, profile, signed_up, last_ip, tags, media_ids) ON o.id = u.id WHERE o.id >= $1+-- route select: 0,1+-- sql: SELECT id FROM subusers WHERE id <= $1 AND id IN (SELECT u.c1 FROM unnest($2::pg_catalog._int8) u(c1)) ORDER BY id+-- $1 = 3+-- $2 = 2+SELECT id FROM subusers+WHERE id <= $1 AND id IN (SELECT u.id FROM suborders o JOIN subusers u ON o.id = u.id WHERE o.id >= $2)+ORDER BY id;+diff --git a/integration/rust/tests/integration/subqueries/todo.sql b/integration/rust/tests/integration/subqueries/todo.sqlindex 9aac88539..e60dc24fd 100644--- a/integration/rust/tests/integration/subqueries/todo.sql+++ b/integration/rust/tests/integration/subqueries/todo.sql@@ -146,15 +146,15 @@
-- relevant to subqueries
--
-- Sharding key on one side only
--- [A1] [select] .. FROM <st1> JOIN <st2> ON <st1>.<col> = <st2>.<key>+-- [DONE] [A1] [select] .. FROM <st1> JOIN <st2> ON <st1>.<col> = <st2>.<key>
-- condition: <col> has sharding key values of rows on other shards
--- [A1 A2 A3 A4 Q5] [insert] INSERT INTO <st1> SELECT .. FROM <st2> JOIN .. ON ..+-- [DONE] [A1 A2 A3 A4 Q5] [insert] INSERT INTO <st1> SELECT .. FROM <st2> JOIN .. ON ..
-- relevant to subqueries
-- case: co-located on the key
-- case: key on one side only
-- Sharding key on neither side
--- [A1] [select] .. FROM <st1> <join> <st2> ON <st1>.<col> = <st2>.<col>+-- [DONE] [A1] [select] .. FROM <st1> <join> <st2> ON <st1>.<col> = <st2>.<col>
-- case: <join> = JOIN
-- case: <join> = LEFT JOIN
diff --git a/pgdog/src/frontend/client/query_engine/multi_step/fetch.rs b/pgdog/src/frontend/client/query_engine/multi_step/fetch.rsindex 744bf02f8..b7b766ac0 100644--- a/pgdog/src/frontend/client/query_engine/multi_step/fetch.rs+++ b/pgdog/src/frontend/client/query_engine/multi_step/fetch.rs@@ -21,6 +21,13 @@ pub(crate) async fn fetch_rows(
.await?;
let mut row_description = None;
+ // TODO(jkaczman): We should return an error if `data_rows` grows past a limit well below 1 GB (e.g., 100 MB) to ensure that we don't run out of memory+ // Currently, we keep all fetched rows in memory, then send the rows to the shards in Bind msg, which Postgres will reject if it's over 1 GB+ //+ // PERF(jkaczman): We could remove the intermediate Vec `data_rows`, and instead copy the rows directly into the unnest(..) arrays as we read them to avoid extra allocations+ // Currently, we allocate a DataRow in `data_rows` per row that we read+ // We then copy all of the rows into the arrays when we do the subquery rewrite in `new_select_with_unnest`+ // Based on some rudimentary benchmarking I did, this would remove roughly 35% of instructions corresponding to the JOIN overhead
let mut data_rows = Vec::new();
let mut error = None;
diff --git a/pgdog/src/frontend/client/query_engine/multi_step/subquery/clause/join_from.rs b/pgdog/src/frontend/client/query_engine/multi_step/subquery/clause/join_from.rsnew file mode 100644index 000000000..3948ab11d--- /dev/null+++ b/pgdog/src/frontend/client/query_engine/multi_step/subquery/clause/join_from.rs@@ -0,0 +1,91 @@+use pg_raw_parse::{+ Node, NodeMut,+ make::{MemoryToken, Unique},+ nodes::{A_Star, Alias, RangeSubselect, RangeVar, SelectStmt},+ transform,+};++use crate::{+ frontend::{+ client::query_engine::multi_step::SubqueryMulti,+ router::parser::rewrite::statement::insert::JoinFetch,+ },+ net::{Bind, DataRow, RowDescription},+};++impl<'a> SubqueryMulti<'a> {+ /// Puts the rows that we fetched from all shards (`data_rows`) in place of the table at `join_fetch.location`+ /// E.g., for SELECT .. FROM users x JOIN orders y ON x.status = y.status, we rewrite+ /// - .. JOIN orders y ON ..+ ///+ /// to+ /// - .. JOIN (SELECT u.c1, u.c2 FROM unnest($1::pg_catalog._int8, $2::pg_catalog._text) u(c1, c2)) AS y(id, status) ON ..+ ///+ /// The column names (id, status) are the names of the columns that the shards returned for SELECT * FROM orders y+ pub fn handle_join_from<'mem>(+ &self,+ join_fetch: &JoinFetch,+ mem: MemoryToken<'mem>,+ mut statement: Unique<'mem, Node<'mem>>,+ row_description: Option<&RowDescription>,+ data_rows: &[DataRow],+ new_bind: &mut Bind,+ ) -> Unique<'mem, Node<'mem>> {+ let Some(row_description) = row_description else {+ return statement;+ };++ let new_right_side = {+ let alias = {+ let mut alias = mem.make_node::<Alias>();+ alias+ .as_mut()+ .set_aliasname(Some(mem.copy_string(&join_fetch.name)));+ Self::make_alias(mem, &alias, row_description.clone())+ };++ let mut new_right_side = mem.make_node::<RangeSubselect>();+ new_right_side.as_mut().set_subquery(+ Self::new_select_with_unnest(new_bind, mem, Node::None, data_rows, row_description)+ .uncast(),+ );+ new_right_side.as_mut().set_alias(alias.as_option());+ new_right_side.uncast()+ };++ transform::transform(&mut statement, |node| match &*node {+ NodeMut::RangeVar(table) if table.location == join_fetch.location => {+ node.replace(mem.make_unique(new_right_side.as_ref()));+ None+ }+ _ => Some(node),+ });++ statement+ }++ /// Returns SELECT * FROM `table`, which we send to all shards to fetch the rows of `table`+ /// E.g., for orders y in .. JOIN orders y ON .., we return SELECT * FROM orders y+ ///+ /// TODO(jkaczman): We should only fetch the columns and rows of `table` that the statement reads+ /// E.g., for SELECT x.id FROM users x JOIN orders y ON x.status = y.status WHERE y.total > 100, we only need the status of the orders with a total over 100+ /// Currently, SELECT * fetches all columns and all rows of `table`, which is expensive for large tables+ pub(crate) fn new_select_from_table<'mem>(+ mem: MemoryToken<'mem>,+ table: &RangeVar,+ ) -> Unique<'mem, &'mem SelectStmt> {+ let target_list = {+ let star = mem+ .make_column_ref(mem.make_list(&[mem.make_node::<A_Star>().uncast()]))+ .uncast();+ mem.make_list(&[mem.make_res_target(None, mem.empty(), star)])+ };++ let from_clause = mem.make_list(&[mem.make_unique(table).uncast()]);++ let mut select = mem.make_node::<SelectStmt>();+ select.as_mut().set_target_list(target_list);+ select.as_mut().set_from_clause(from_clause);+ select+ }+}diff --git a/pgdog/src/frontend/client/query_engine/multi_step/subquery/clause/mod.rs b/pgdog/src/frontend/client/query_engine/multi_step/subquery/clause/mod.rsindex 48be26ce7..54ea7469e 100644--- a/pgdog/src/frontend/client/query_engine/multi_step/subquery/clause/mod.rs+++ b/pgdog/src/frontend/client/query_engine/multi_step/subquery/clause/mod.rs@@ -2,5 +2,6 @@
mod from_clause;
mod insert_select;
+mod join_from;
mod where_clause;
mod with_clause;
diff --git a/pgdog/src/frontend/client/query_engine/multi_step/subquery/evaluate.rs b/pgdog/src/frontend/client/query_engine/multi_step/subquery/evaluate.rsindex 8ea094619..a9a9e52ad 100644--- a/pgdog/src/frontend/client/query_engine/multi_step/subquery/evaluate.rs+++ b/pgdog/src/frontend/client/query_engine/multi_step/subquery/evaluate.rs@@ -17,7 +17,8 @@ use crate::{
insert::Subquery,
subquery::{
from_clause::parse_from_clause, insert_select::parse_insert_select,
- where_clause::parse_where_clause, with_clause::parse_with_clause,+ join_from::table_at_location, where_clause::parse_where_clause,+ with_clause::parse_with_clause,
},
},
},
@@ -32,6 +33,16 @@ impl<'ast> SubqueryMulti<'ast> {
subquery: &Subquery,
entire_ast: Node<'ast>,
) -> Result<(Owned<SelectStmt>, Bind), Error> {
+ if let Subquery::JoinFrom(join_fetch) = subquery {+ let table = table_at_location(entire_ast, join_fetch.location)+ .expect("The parser took `location` from this statement");++ return Ok((+ owned(|mem| Self::new_select_from_table(mem, table)),+ self.current_level_bind.clone(),+ ));+ }+
let subquery_ast: Node<'ast> = self.parse_out_relevant_query_to_send(subquery, entire_ast);
// We might have to reference earlier statements and perform a re-write. E.g., if we have CTE b referencing CTE a, then we need to include the re-written CTE (w/ unnest) here
@@ -62,6 +73,7 @@ impl<'ast> SubqueryMulti<'ast> {
Subquery::WhereClauseCte(alias) => {
parse_where_clause(entire_ast).and_then(|subselect| parse_with_clause(subselect, alias))
}
+ Subquery::JoinFrom(_) => unreachable!("`new_select_to_fetch_rows_of_subquery` handles JoinFrom"),
}.expect("We already ran these methods in the parser originally. No reason they shouldn't pass here.")
}
diff --git a/pgdog/src/frontend/client/query_engine/multi_step/subquery/mod.rs b/pgdog/src/frontend/client/query_engine/multi_step/subquery/mod.rsindex dfc13b5bb..275c3f1ad 100644--- a/pgdog/src/frontend/client/query_engine/multi_step/subquery/mod.rs+++ b/pgdog/src/frontend/client/query_engine/multi_step/subquery/mod.rs@@ -133,16 +133,13 @@ impl<'ast> SubqueryMulti<'ast> {
pub fn new_sub_engine<'b>(
parent_engine: &'b SubqueryMulti<'ast>,
- new_parent_ast: Node<'ast>,
subqueries: Vec<Subquery>,
+ client_request: &'ast ClientRequest,
) -> Self {
Self {
- subqueries,
top_level_bind: parent_engine.top_level_bind,
- current_level_bind: parent_engine.current_level_bind.clone(),- subquery_results: Vec::new(),
is_extended_protocol: parent_engine.is_extended_protocol,
- top_level_statement: new_parent_ast,+ ..Self::new(subqueries, client_request)
}
}
@@ -167,7 +164,6 @@ impl<'ast> SubqueryMulti<'ast> {
// Send the re-written statement
self.send_query_string(
engine,
- self.top_level_statement,
rewritten_outer_statement.to_string(),
context,
// `is_subquery` = false will send the response right back to the client
@@ -204,7 +200,6 @@ impl<'ast> SubqueryMulti<'ast> {
let results = self
.send_query_string(
engine,
- Node::SelectStmt(&rewritten_subquery_ast),
subquery_sql.to_string(),
context,
// 'is_subquery' will allow us to get the response back
diff --git a/pgdog/src/frontend/client/query_engine/multi_step/subquery/request.rs b/pgdog/src/frontend/client/query_engine/multi_step/subquery/request.rsindex 986fee4ef..d88164998 100644--- a/pgdog/src/frontend/client/query_engine/multi_step/subquery/request.rs+++ b/pgdog/src/frontend/client/query_engine/multi_step/subquery/request.rs@@ -1,6 +1,6 @@
//! Sending and receiving logic for subqueries
-use pg_raw_parse::{Node, deparse};+use pg_raw_parse::deparse;
use crate::{
frontend::{
@@ -23,7 +23,6 @@ impl<'a> SubqueryMulti<'a> {
pub(crate) async fn send_query_string(
&mut self,
engine: &mut QueryEngine,
- query_ast: Node<'_>,
query_string: String,
context: &mut QueryEngineContext<'_>,
is_subquery: bool,
@@ -65,7 +64,7 @@ impl<'a> SubqueryMulti<'a> {
let (new_ast, new_bind) = {
let mut subquery_multi =
- SubqueryMulti::new_sub_engine(self, query_ast, subqueries);+ SubqueryMulti::new_sub_engine(self, subqueries, &client_request);
Box::pin(
subquery_multi.evaluate_and_rewrite_outer_statement(engine, context),
@@ -77,14 +76,8 @@ impl<'a> SubqueryMulti<'a> {
let rewritten_subquery_sql = deparse(new_ast.stmt())?.as_str().to_string();
- Box::pin(self.send_query_string(- engine,- new_ast.stmt(),- rewritten_subquery_sql,- context,- true,- ))- .await+ Box::pin(self.send_query_string(engine, rewritten_subquery_sql, context, true))+ .await
}
// Seems unlikely we'll need to support INSERT split / Sharding Key Updates
@@ -115,7 +108,10 @@ impl<'a> SubqueryMulti<'a> {
// hand-rolling it into the SQL.
//
// So, this just drops all Parse/Binds that we come across, as we know we're handling subqueries.
- context.drop_extended_parse_and_bind = !self.is_extended_protocol;+ //+ // Why `|=` instead of `=`?+ // Because for JOINs next to subqueries in WHERE, we'll rewrite the statement twice+ context.drop_extended_parse_and_bind |= !self.is_extended_protocol;
// TODO(jkaczman): We rely on INSERT split for insert statements.
// If a user has that rewrite disabled, but subqueries
diff --git a/pgdog/src/frontend/client/query_engine/multi_step/subquery/rewrite.rs b/pgdog/src/frontend/client/query_engine/multi_step/subquery/rewrite.rsindex d00a72c52..e8275f322 100644--- a/pgdog/src/frontend/client/query_engine/multi_step/subquery/rewrite.rs+++ b/pgdog/src/frontend/client/query_engine/multi_step/subquery/rewrite.rs@@ -80,6 +80,9 @@ impl<'ast> SubqueryMulti<'ast> {
Subquery::Cte(alias) => {
self.handle_with_clause(alias, mem, stmt, row_description, data_rows, new_bind)
}
+ Subquery::JoinFrom(join_fetch) => {+ self.handle_join_from(join_fetch, mem, stmt, row_description, data_rows, new_bind)+ }
}
}
}
diff --git a/pgdog/src/frontend/client/query_engine/query.rs b/pgdog/src/frontend/client/query_engine/query.rsindex 57240c56e..0dc04740f 100644--- a/pgdog/src/frontend/client/query_engine/query.rs+++ b/pgdog/src/frontend/client/query_engine/query.rs@@ -7,8 +7,8 @@ use crate::{
router::parser::{explain_trace::ExplainTrace, rewrite::statement::plan::RewriteResult},
},
net::{
- DataRow, FromBytes, Message, Protocol, ProtocolMessage, Query, ReadyForQuery,- RowDescription, ToBytes, TransactionState,+ DataRow, FromBytes, Message, ParseComplete, Protocol, ProtocolMessage, Query,+ ReadyForQuery, RowDescription, ToBytes, TransactionState,
},
parameters::is_session_identity,
state::State,
@@ -156,6 +156,23 @@ impl QueryEngine {
)
.await?;
}
+ // If Postgres returns errors while we fetch rows (e.g., division by zero in the SELECT of a subquery), we return those errors to the client+ Err(multi_step::Error::Execution(error)) => {+ if let Some(transaction) = context.transaction.as_mut() {+ transaction.set_error();+ }++ if client_request+ .messages+ .iter()+ .any(|message| matches!(message, ProtocolMessage::Parse(_)))+ {+ let bytes_sent = context.stream.send(&ParseComplete).await?;+ self.stats.sent(bytes_sent);+ }++ self.error_response(context, client_request, *error).await?;+ }
Err(err) => return Err(err.into()),
}
}
diff --git a/pgdog/src/frontend/router/parser/rewrite/statement/insert.rs b/pgdog/src/frontend/router/parser/rewrite/statement/insert.rsindex d6b71eec9..1401b8154 100644--- a/pgdog/src/frontend/router/parser/rewrite/statement/insert.rs+++ b/pgdog/src/frontend/router/parser/rewrite/statement/insert.rs@@ -34,6 +34,22 @@ pub(crate) enum Subquery {
/// CTE present in WHERE clause
WhereClauseCte(String),
++ /// SELECT with JOIN(s) of two sharded tables where we fetch the rows of the table after JOIN from all shards first+ /// e.g., in SELECT .. FROM users x JOIN orders y ON x.status = y.status, we fetch orders y, then send the statement to all shards with the fetched rows in place of orders y+ JoinFrom(JoinFetch),+}++/// The table after JOIN that we fetch from all shards first+/// E.g., for SELECT * FROM users x JOIN orders y ON x.status = y.status, we fetch orders y with SELECT * FROM orders y+#[derive(Debug, Clone)]+pub(crate) struct JoinFetch {+ /// The position where the table starts in the SQL of the statement, e.g., 27 for orders in the example above+ /// We find orders y in the AST with this position to build SELECT * FROM orders y and to put the fetched rows in place of orders y+ pub(crate) location: i32,+ /// The alias of the table (y in the example above), or the name of the table if the table doesn't have an alias+ /// When we rewrite the statement, we use this name as the alias of the fetched rows+ pub(crate) name: String,
}
#[derive(Debug, Clone)]
diff --git a/pgdog/src/frontend/router/parser/rewrite/statement/subquery/join_from.rs b/pgdog/src/frontend/router/parser/rewrite/statement/subquery/join_from.rsnew file mode 100644index 000000000..d8398018c--- /dev/null+++ b/pgdog/src/frontend/router/parser/rewrite/statement/subquery/join_from.rs@@ -0,0 +1,232 @@+use std::ops::ControlFlow;++use itertools::Itertools;+use pg_raw_parse::{+ Node,+ nodes::{JoinExpr, JoinType, RangeVar},+ walk::{self, Recurse},+};++use crate::frontend::router::parser::{+ StatementParser, Table,+ rewrite::statement::{+ insert::{JoinFetch, Subquery},+ subquery::SubqueryRewrite,+ },+};++/// The table after JOIN, e.g., orders y in SELECT .. FROM users x JOIN orders y ON x.status = y.status+/// We call orders y the right side of the JOIN and users x the first table+struct JoinRightSide<'a> {+ table: &'a RangeVar,+ /// The alias of the table (y in the example above), or the name of the table if the table doesn't have an alias (orders in .. JOIN orders ON orders.status = ..)+ name: &'a str,+}++impl<'a, 'mem> SubqueryRewrite<'a, 'mem> {+ pub(crate) fn handle_subquery_in_join_from(&self) -> Option<Subquery> {+ let (first_table, join, right_side) = parse_join(self.outer_stmt)?;++ // If we have JOINs where one of the two tables isn't sharded, all rows of that table are on all shards, so we send those JOINs as-is+ //+ // TODO(jkaczman): LEFT JOINs from tables that aren't sharded to sharded tables return extra rows+ // E.g., for SELECT s.state, u.id FROM states s LEFT JOIN users u ON u.state = s.state, if the only user in CA is user 3 on Shard B:+ // - Shard A: the state CA is on Shard A, but user 3 isn't, so Shard A doesn't find a user for CA and returns (CA, NULL)+ // - Shard B: the state CA and user 3 are on Shard B, so Shard B returns (CA, 3)+ // The client receives both rows, but Postgres only returns (CA, 3)+ // We should fetch users from all shards first and then send the statement to one shard, since all shards would then return the same rows+ if !self.is_table_sharded(first_table) || !self.is_table_sharded(right_side.table) {+ return None;+ }++ let parser = StatementParser::new(self.outer_stmt, None, self.statement_rewrite.schema);+ if parser.is_joined_on_sharding_keys(join, right_side.name) {+ return None;+ }++ Some(Subquery::JoinFrom(JoinFetch {+ location: right_side.table.location,+ name: right_side.name.to_string(),+ }))+ }++ fn is_table_sharded(&self, table: &RangeVar) -> bool {+ self.statement_rewrite.schema.tables.is_table_sharded(+ Table::from(table),+ self.statement_rewrite.db_schema,+ self.statement_rewrite.user,+ self.statement_rewrite.search_path,+ )+ }+}++/// Returns the first table, the JOIN and the right side of the JOIN, if `outer_stmt` is SELECT .. FROM <first table> [LEFT | CROSS | NATURAL] JOIN <right side> .. (without WITH or FOR UPDATE)+/// E.g., for SELECT .. FROM users x JOIN orders y ON x.status = y.status, we return users x, the JOIN and orders y+/// Returns None for all other statements, e.g., SELECT .. FROM users x RIGHT JOIN orders y ON ..+fn parse_join<'a>(outer_stmt: Node<'a>) -> Option<(&'a RangeVar, &'a JoinExpr, JoinRightSide<'a>)> {+ let Node::SelectStmt(select) = outer_stmt else {+ return None;+ };++ if !select.locking_clause().is_empty() {+ return None;+ }++ if select.with_clause().is_some() {+ return None;+ }++ let Ok(Node::JoinExpr(join)) = select.from_clause().into_iter().exactly_one() else {+ return None;+ };++ if !matches!(join.jointype, JoinType::JOIN_INNER | JoinType::JOIN_LEFT) {+ return None;+ }++ let Node::RangeVar(first_table) = join.larg() else {+ return None;+ };++ Some((first_table, join, parse_right_side(join)?))+}++/// Returns the right side of `join` if the right side is a table, e.g., orders y in .. JOIN orders y ON ..+/// Returns None for all other right sides, e.g., .. JOIN (SELECT ..) y ON ..+/// We also return None for tables whose alias has column names (e.g., .. JOIN orders y(a, b) ON ..), since we don't put those column names in the alias of the fetched rows yet+fn parse_right_side<'a>(join: &'a JoinExpr) -> Option<JoinRightSide<'a>> {+ match join.rarg() {+ Node::RangeVar(table) => match table.alias() {+ Some(alias) if alias.colnames().is_empty() => Some(JoinRightSide {+ table,+ name: alias.aliasname()?,+ }),++ // If the table doesn't have an alias, column references use the name of the table (e.g., orders.id), so we use the name of the table as the alias of the fetched rows+ // We skip tables with a schema (e.g., public.orders), since public.orders.id couldn't refer to the fetched rows (aliases can't have a schema)+ None if table.schemaname().is_none() => Some(JoinRightSide {+ table,+ name: table.relname()?,+ }),++ _ => None,+ },++ _ => None,+ }+}++/// Returns the table that starts at `location` in the SQL of `stmt`, e.g., orders y for the location 27 in SELECT * FROM users x JOIN orders y ON ..+pub(crate) fn table_at_location(stmt: Node<'_>, location: i32) -> Option<&RangeVar> {+ walk::walk_manual(stmt, |node| match node {+ Node::RangeVar(table) if table.location == location => ControlFlow::Break(table),+ _ => Recurse::yes(),+ })+}++#[cfg(test)]+mod tests {+ use super::*;++ /// Returns true if `parse_join` accepts `sql`+ /// E.g., we return true for SELECT * FROM a x JOIN b y ON x.c = y.c and false for SELECT * FROM a x RIGHT JOIN b y ON x.c = y.c+ ///+ /// `parse_join` doesn't read the sharding config, so a and b don't have to be sharded tables in these tests+ fn is_rewritten(sql: &str) -> bool {+ let raw = pg_raw_parse::parse(sql).unwrap();+ parse_join(raw.stmts().next().unwrap()).is_some()+ }++ // This tests that `parse_join` accepts SELECT * FROM a x JOIN b y ON x.c = y.c+ // If a and b are sharded tables and c isn't the sharding key of both tables, we fetch y for this JOIN+ // Fetching y means that we read all rows of b from all shards first and then send the statement to all shards with those rows in place of b y+ // The tests below change parts of this statement (e.g., RIGHT JOIN instead of JOIN)+ #[test]+ fn test_join_is_rewritten() {+ assert!(is_rewritten("SELECT * FROM a x JOIN b y ON x.c = y.c"));+ }++ // This tests that `parse_join` rejects the JOINs that we can't rewrite by fetching y+ // We send these JOINs to the shards as-is+ #[test]+ fn test_joins_that_we_cant_rewrite() {+ // RIGHT JOIN also returns the rows of y that don't match any rows of x+ // If we fetched y, Shard A would join all rows of y with only the rows of x on Shard A+ // E.g., if the row of y with c = 5 only matches a row of x on Shard B, Shard A wouldn't find a row of x for c = 5 and would return (NULL, 5) for x.c and y.c+ // Postgres doesn't return (NULL, 5), since the row of y with c = 5 matches a row of x+ assert!(!is_rewritten(+ "SELECT * FROM a x RIGHT JOIN b y ON x.c = y.c"+ ));++ // FULL JOIN also returns the rows of y that don't match any rows of x+ // So if we fetched y, Shard A would return the same extra row (NULL, 5) as for RIGHT JOIN above+ assert!(!is_rewritten(+ "SELECT * FROM a x FULL JOIN b y ON x.c = y.c"+ ));++ // FOR UPDATE locks the rows of a and b that the statement reads+ // If we fetched y, the rewritten statement would read the rows of b from unnest(..) arrays instead of the table b, so Postgres wouldn't lock the rows of b+ assert!(!is_rewritten(+ "SELECT * FROM a x JOIN b y ON x.c = y.c FOR UPDATE"+ ));++ // LATERAL (SELECT c FROM b WHERE b.c = x.c) y runs the subquery once for each row of x and uses the x.c of that row+ // E.g., for the row of x with c = 5, y is SELECT c FROM b WHERE b.c = 5+ // For the row of x with c = 6, y is SELECT c FROM b WHERE b.c = 6+ // So y isn't one set of rows that we could fetch from all shards before we run the statement+ assert!(!is_rewritten(+ "SELECT * FROM a x JOIN LATERAL (SELECT c FROM b WHERE b.c = x.c) y ON true"+ ));+ }++ // This tests that `parse_join` rejects the JOINs that we could rewrite by fetching y, but don't rewrite yet+ //+ // Why aren't these JOINs in the subquery suite (tests/select.sql)?+ // Because the suite compares the rows that the client receives with the rows that Postgres returns+ // We send these JOINs to the shards as-is, so the client can receive different rows than Postgres returns+ #[test]+ fn test_joins_that_we_dont_rewrite_yet() {+ // Aliases can't have a schema, so we'd use b as the alias of the fetched rows+ // public.b.c in ON would then still refer to the table public.b, which isn't in the FROM of the rewritten statement+ assert!(!is_rewritten(+ "SELECT * FROM a x JOIN public.b ON x.c = public.b.c"+ ));++ // y(c, d) renames the first two columns of b to c and d+ // We don't put those column names in the alias of the fetched rows yet+ assert!(!is_rewritten(+ "SELECT * FROM a x JOIN b y(c, d) ON x.c = y.c"+ ));++ // We fetch y with SELECT * FROM b, so y has to be a table+ // For the derived table (SELECT c FROM b) y, we'd have to send the SELECT of the derived table instead+ assert!(!is_rewritten(+ "SELECT * FROM a x JOIN (SELECT c FROM b) y ON x.c = y.c"+ ));++ // We only fetch y if x is a sharded table+ // The sharding config only lists tables, so we can't tell whether the derived table (SELECT c FROM a) x is sharded+ assert!(!is_rewritten(+ "SELECT * FROM (SELECT c FROM a) x JOIN b y ON x.c = y.c"+ ));++ // For JOINs between three tables, we'd have to pick which tables stay on the shards and which tables we fetch+ assert!(!is_rewritten(+ "SELECT * FROM a x JOIN b y ON x.c = y.c JOIN d z ON z.c = y.c"+ ));++ // FROM a x, b y joins the tables with a comma and a condition in WHERE, which we don't rewrite yet (only JOIN .. ON ..)+ assert!(!is_rewritten("SELECT * FROM a x, b y WHERE x.c = y.c"));++ // If we have WITH, names in FROM can refer to CTEs (here, b refers to the CTE b)+ // We don't tell CTEs apart from tables here yet, so we'd fetch the table b instead of using the CTE b+ assert!(!is_rewritten(+ "WITH b AS (SELECT 1 AS c) SELECT * FROM a x JOIN b y ON x.c = y.c"+ ));++ // We don't rewrite UPDATE .. FROM yet (only SELECTs)+ assert!(!is_rewritten(+ "UPDATE a SET c = y.c FROM b y WHERE a.c = y.c"+ ));+ }+}diff --git a/pgdog/src/frontend/router/parser/rewrite/statement/subquery/mod.rs b/pgdog/src/frontend/router/parser/rewrite/statement/subquery/mod.rsindex b49e4865a..933f0bc39 100644--- a/pgdog/src/frontend/router/parser/rewrite/statement/subquery/mod.rs+++ b/pgdog/src/frontend/router/parser/rewrite/statement/subquery/mod.rs@@ -11,6 +11,7 @@ use crate::frontend::router::parser::{
pub(crate) mod from_clause;
pub(crate) mod insert_select;
+pub(crate) mod join_from;
pub(crate) mod where_clause;
pub(crate) mod with_clause;
@@ -81,6 +82,12 @@ impl<'a, 'mem> SubqueryRewrite<'a, 'mem> {
return Ok(vec![subquery]);
}
+ // Determine if there are JOINs in the FROM clause of a SELECT where we have to fetch the tables after JOIN from all shards first+ // E.g., .. FROM users x JOIN orders y ON x.status = y.status+ if let Some(subquery) = self.handle_subquery_in_join_from() {+ return Ok(vec![subquery]);+ }+
Ok(vec![])
}
diff --git a/pgdog/src/frontend/router/parser/statement.rs b/pgdog/src/frontend/router/parser/statement.rsindex 99db592d0..a018fd4ff 100644--- a/pgdog/src/frontend/router/parser/statement.rs+++ b/pgdog/src/frontend/router/parser/statement.rs@@ -48,7 +48,7 @@ use crate::{
round_robin,
sharding::{
ContextBuilder, LookupTable, PendingLookup, ResolvedLookups, SchemaSharder,
- ShardedTable, Tables, lookup,+ ShardedTable, ShardingFunction, Tables, lookup,
},
},
net::{messages::Format, parameter::ParameterValue},
@@ -658,6 +658,107 @@ impl<'a, 'b: 'a> StatementParser<'a, 'b> {
}
}
+ /// Returns true if the ON clause of `join` compares the sharding keys of both tables with `=` and both tables have the same `ShardingFunction`+ /// E.g., we return true for .. FROM users x JOIN orders y ON x.id = y.user_id (users sharded by id, orders sharded by user_id)+ /// The rows of x and y that the JOIN joins fundamentally align to the same shard, so we send the statement as-is+ ///+ /// If we return false, we fetch y from all shards first and rewrite the statement+ /// E.g., we return false for ON x.status = y.status, since users and orders with the same status can be on different shards+ pub(crate) fn is_joined_on_sharding_keys(+ &self,+ join: &'a nodes::JoinExpr,+ right_side_name: &str,+ ) -> bool {+ let Node::SelectStmt(select) = self.stmt else {+ return false;+ };++ // Aliases with column names rename the columns in order+ // E.g., if users has the columns (id, status), then in .. FROM users x(status, id) JOIN orders y ON x.id = y.user_id, x.id is the column status of users+ // `SearchContext::resolve_column` doesn't read those names, so we'd treat x.id as the sharding key id+ // Therefore, we return false+ if let Node::RangeVar(first_table) = join.larg()+ && first_table+ .alias()+ .is_some_and(|alias| !alias.colnames().is_empty())+ {+ return false;+ }++ // `parse_join` only accepts SELECTs without WITH, so we pass no CTE names+ let ctx = SearchContext::from_from_clause(select.from_clause(), &HashSet::new());++ for (a, b) in Self::columns_equal_in_on_clause(join.quals()) {+ // The column belonging to y (the table after JOIN) can be on either side of `=` (e.g., x.id = y.user_id or y.user_id = x.id)+ for (right_side_column, other_column) in [(a, b), (b, a)] {+ // We skip y.user_id = y.user_id (both columns belong to y) and y.user_id = id (we don't look up which table id belongs to)+ if right_side_column.table != Some(right_side_name)+ || other_column+ .table+ .is_none_or(|table| table == right_side_name)+ {+ continue;+ }++ let right_side_key = ctx+ .resolve_column(right_side_column)+ .and_then(|column| self.get_sharded_table(column));+ let other_key = ctx+ .resolve_column(other_column)+ .and_then(|column| self.get_sharded_table(column));++ if let (Some(right_side_key), Some(other_key)) = (right_side_key, other_key)+ && ShardingFunction::of(right_side_key)+ .is_some_and(|function| Some(function) == ShardingFunction::of(other_key))+ {+ return true;+ }+ }+ }++ false+ }++ /// Returns the pairs of columns that `on_clause` compares with `=`+ /// E.g., for ON x.id = y.user_id AND x.status = y.status, we return (x.id, y.user_id) and (x.status, y.status)+ ///+ /// `is_joined_on_sharding_keys` uses these pairs to decide whether the rows that the JOIN joins fundamentally align to the same shard+ /// If we have AND, all rows that the JOIN joins have x.id = y.user_id+ /// However, ON x.id = y.user_id OR x.status = y.status also joins a row of x with id 1 to a row of y with user_id 2 if both rows have the same status+ /// Those two rows can be on different shards, so we only return pairs from AND (not from OR)+ fn columns_equal_in_on_clause(on_clause: Node<'a>) -> Vec<(Column<'a>, Column<'a>)> {+ use nodes::{A_Expr_Kind, BoolExprType};++ match on_clause {+ Node::BoolExpr(expr) if expr.boolop == BoolExprType::AND_EXPR => expr+ .args()+ .into_iter()+ .flat_map(Self::columns_equal_in_on_clause)+ .collect(),++ Node::A_Expr(expr) if expr.kind == A_Expr_Kind::AEXPR_OP => {+ let operator = expr+ .name()+ .into_iter()+ .exactly_one()+ .ok()+ .and_then(Node::as_str);++ match (+ operator,+ Column::try_from(expr.lexpr()),+ Column::try_from(expr.rexpr()),+ ) {+ (Some("="), Ok(left), Ok(right)) => vec![(left, right)],+ // We return no pairs for other operators (e.g., x.id > y.user_id) and for comparisons with something other than columns (e.g., x.id = 5 or x.id = y.user_id + 1)+ _ => vec![],+ }+ }++ _ => vec![],+ }+ }+
/// Find sharded table config for a column.
/// Named configs (with explicit table names) match specific table+column.
/// Column-only configs match any table with that column name.
@@ -1476,6 +1577,80 @@ mod test {
}
}
+ /// Returns what `is_joined_on_sharding_keys` returns for the first JOIN in `stmt`, where y is the table after JOIN+ /// E.g., we return true for SELECT * FROM sharded x JOIN sharded y ON x.id = y.id, since x.id and y.id are both sharding keys+ fn joined_on_sharding_keys(stmt: &str) -> bool {+ let schema = test_schema();+ let raw = pg_raw_parse::parse(stmt).unwrap();+ let stmt = raw.stmts().next().unwrap();+ let Node::SelectStmt(select) = stmt else {+ panic!("not a SELECT: {stmt:?}");+ };+ let Some(Node::JoinExpr(join)) = select.from_clause().into_iter().next() else {+ panic!("no JOIN");+ };+ StatementParser::new(stmt, None, &schema).is_joined_on_sharding_keys(join, "y")+ }++ // This tests that we send JOINs on x.id = y.id to the shards as-is (without fetching y)+ // x and y are both the table `sharded` (sharded by id), so the rows that the JOIN joins on x.id = y.id fundamentally align to the same shard+ #[test]+ fn test_join_on_the_sharding_keys() {+ assert!(joined_on_sharding_keys(+ "SELECT * FROM sharded x JOIN sharded y ON x.id = y.id"+ ));++ // y.id = x.id has the column belonging to the table after JOIN first, as Rails writes ON clauses (e.g., .. JOIN users ON users.account_id = accounts.id)+ assert!(joined_on_sharding_keys(+ "SELECT * FROM sharded x JOIN sharded y ON y.id = x.id"+ ));++ // Other conditions in AND (x.value = y.value) only remove rows from the JOIN, so x.id = y.id is still true for all rows that the JOIN joins+ assert!(joined_on_sharding_keys(+ "SELECT * FROM sharded x JOIN sharded y ON x.id = y.id AND x.value = y.value"+ ));+ }++ // This tests that we fetch y if the JOIN can also join rows of x and y that are on different shards, or if we can't tell which columns the ON clause compares+ #[test]+ fn test_join_not_only_on_the_sharding_keys() {+ // If we have OR in the ON clause, the JOIN also joins rows with the same x.value and y.value but different ids (e.g., x.id = 1 and y.id = 2), which can be on different shards+ assert!(!joined_on_sharding_keys(+ "SELECT * FROM sharded x JOIN sharded y ON x.id = y.id OR x.value = y.value"+ ));++ // ON (x.id = y.id) IS NOT TRUE joins the rows where x.id and y.id differ (e.g., x.id = 1 and y.id = 2)+ assert!(!joined_on_sharding_keys(+ "SELECT * FROM sharded x JOIN sharded y ON (x.id = y.id) IS NOT TRUE"+ ));++ // x.id = y.id + 1 and x.id > y.id join rows with different ids (e.g., x.id = 2 and y.id = 1)+ assert!(!joined_on_sharding_keys(+ "SELECT * FROM sharded x JOIN sharded y ON x.id = y.id + 1"+ ));+ assert!(!joined_on_sharding_keys(+ "SELECT * FROM sharded x JOIN sharded y ON x.id > y.id"+ ));++ // y.id = y.id compares y with itself, so the JOIN joins all rows of x with all rows of y where y.id isn't NULL (e.g., a row of x on Shard A with a row of y on Shard B)+ assert!(!joined_on_sharding_keys(+ "SELECT * FROM sharded x JOIN sharded y ON y.id = y.id"+ ));++ // We don't look up whether id (without a table name) belongs to x or y+ // If id belongs to x, x.id = id joins all rows of x with all rows of y (as for y.id = y.id above)+ assert!(!joined_on_sharding_keys(+ "SELECT * FROM sharded x JOIN sharded y ON x.id = id"+ ));++ // x(value, id) renames the first two columns of the table `sharded` to value and id+ // So x.id is the second column of `sharded`, which doesn't have to be the sharding key id+ // If x.id isn't the sharding key, x.id = y.id can join rows of x and y on different shards+ assert!(!joined_on_sharding_keys(+ "SELECT * FROM sharded x(value, id) JOIN sharded y ON x.id = y.id"+ ));+ }+
fn run_test(stmt: &str, bind: Option<&Bind>) -> Result<Option<Shard>, Error> {
let schema = test_schema();
let raw = pg_raw_parse::parse(stmt).unwrap();
diff --git a/pgdog/src/frontend/router/sharding/tables.rs b/pgdog/src/frontend/router/sharding/tables.rsindex 175a1564f..a9bcd87ca 100644--- a/pgdog/src/frontend/router/sharding/tables.rs+++ b/pgdog/src/frontend/router/sharding/tables.rs@@ -48,6 +48,39 @@ impl ShardedTable {
}
}
+/// The settings in the sharding config that decide which shards the rows of sharded tables are on+/// - the data type of the sharding key+/// - the hash function (`hasher`)+/// - the mapping from values to shards (e.g., lists or ranges)+///+/// E.g., if users and orders have equal `ShardingFunction`s, the users with id 5 and the orders with user_id 5 are on the same shard+/// So for JOINs ON users.id = orders.user_id, the rows that the JOINs join fundamentally align to the same shard+#[derive(Debug, PartialEq)]+pub(crate) struct ShardingFunction<'a> {+ data_type: &'a DataType,+ hasher: &'a Hasher,+ mapping: Option<&'a Mapping>,+}++impl<'a> ShardingFunction<'a> {+ /// Returns the sharding function of `table`+ /// E.g., for orders sharded by the hash of the bigint column user_id, we return bigint and the hasher and mapping that the sharding config sets for orders+ ///+ /// Returns None for tables sharded by centroids (vectors) or by lookup queries (queries that we run to find the shards corresponding to values)+ /// For those tables, the data type, hasher and mapping don't decide the shards+ pub(crate) fn of(table: &'a ShardedTable) -> Option<Self> {+ if !table.centroids.is_empty() || table.lookup_query.is_some() {+ return None;+ }++ Some(Self {+ data_type: &table.data_type,+ hasher: &table.hasher,+ mapping: table.mapping.as_ref(),+ })+ }+}+
#[derive(Debug)]
pub(crate) struct Key<'a> {
pub(crate) table: &'a ShardedTable,