9 ms·

Joins are not inherently expensive, but they can lead to expensive queries. For example, say I want to find the 10 most recent users with a phone number as thei

by yashap 3y ago

Joins are not inherently expensive, but they can lead to expensive queries. For example, say I want to find the 10 most recent users with a phone number as their primary contact method: SELECT … FROM User JOIN ContactMethod on ContactMethod.userId = User.id WHERE ContactMethod.priority = ‘primary’ AND ContactMethod.type = ‘phoneNumber’ ORDER BY User.createdAt DESC LIMIT 10 If there are a very large number of users, and a very large number of phone number primary contacts, you cannot make this query fast/efficient (on most RDBMSes). You CAN make this query fast/efficient by denormalizing, ensuring the user creation date and primary contact method are on the same table, and then creating a compound index. But if they’re in separate tables, and you have to join, you can’t make it efficient, because you can’t create cross-table compound indeces. This pattern of join, filter by something in table A, sort by something in table B, and query out one page of data, is something that comes up a lot. It’s why ppl thing joins are generally expensive, but it’s more like they’re expensive in specific cases.

franckpachot 3y ago
With an index on User (createdAt, id) and one on ContactMethod ( primary,ContactMethod,userId), it should be fast (check that the the execution plan starts with User). Except if lot of recent users have no phones, but that will not be better in a single table (except if columnar storage)
- aidos 3y ago
  I imagine so too. You’ll be able to interate over the users in order and hit an instant index on contact method. select * from user where exists ( select true from contact_method cm where cm.contact_id = contact.id and cm.method = 'phone' and cm.primary ) order by created_at desc limit 10 —- partial index is even faster create index primary_phone on contact_method (contact_id) where method = 'phone' and primary;
- yashap 3y ago
  See my reply here: https://news.ycombinator.com/item?id=37116015 https://news.ycombinator.com/item?id=37116015
deleted 3y ago
[deleted]
Turskarama 3y ago
In my experience with SQL, a query like that should return in under a second even if you have 100k or more users. There are some other tricks you can use if you're clever/lucky as well. If you're just using integer IDs (which is reasonable if your system isn't distributed) then you could order by userid on you ContactMethod table and still get the same speed as you would with no join.
- yashap 3y ago
  See my reply here: https://news.ycombinator.com/item?id=37116015 https://news.ycombinator.com/item?id=37116015
Zanfa 3y ago
> If there are a very large number of users, and a very large number of phone number primary contacts, you cannot make this query fast/efficient I think specific numbers would help make this point better. With a few hundred thousand to low millions of users this should be plenty fast in Postgres for example. That’s magnitudes more than most startups ever reach anyway.
- yashap 3y ago
  See my reply here: https://news.ycombinator.com/item?id=37116015 https://news.ycombinator.com/item?id=37116015
unnouinceput 3y ago
If the tables involved in the join are of 100M+ records what I do when the joins use varchar columns to improve the performance is to use an additional integer column of the varchar one that is a CRC of it (or hash if you prefer that) and use the integer one instead in the join.
- aidos 3y ago
  That seems weirdly convoluted. So you store two columns to represent the foreign key?
  - unnouinceput 3y ago
    If you use a varchar as FK then you're definitely doing something wrong from beginning. OP was talking about getting the phone number under certain conditions, and a phone number column is a varchar.
    - aidos 3y ago
      I don’t think they ever did a lookup on phone number and even if you needed to, you would just index it and it’d be fast. You can even use things like tri-gram indexes to give you super fast partial phone number matching.
tlarkworthy 3y ago
Yes this is the exact situation where sql falls short. You can't make cross-table indexes to serve OLAP-esq queries, and the most recent X is the common one for pagination in applications. I prefer to denormalize manually at write time in a transaction, rather than use triggers or materialized views.
- ako 3y ago
  Why do you prefer manually doing this rather than using materialized views? Materialized views seem easier to create and maintain?
  - tlarkworthy 3y ago
    Because they are o(n) complexity to refresh so either you settle for eventual complexity or have expensive writes. By forwarding just the index data to the right table you maintain an consistent idiomatic index at 0(1) write cost
    - aidos 3y ago
      Agreed. Matarialized views will be limited in use until we get nice incremental updating versions.
    - gen220 3y ago
      Have you considered implementing this with database triggers instead of in your application logic? Requires a bit of brainpower to set up a system around it, but it makes your application logic dramatically simpler. (You don't have to remember to update `foo.bar` every time you write a function that touches `moo.bar`, and if you run migrations in SQL, the updates will also cascade naturally). It's really high up on my personal wish list for Postgres to support incrementally-materialized views. It doesn't seem like it would be impossible to implement (since, as I suggested, you can implement it on your own with triggers), but IDK, I assume there are higher-priority issues on their docket.
      - tlarkworthy 3y ago
zepolen 3y ago
For 10 million users + telephones, this takes 1ms. create table users ( id serial primary key not null, created_at timestamp not null default now() ); create table users_telephones ( user_id int references users(id) not null, is_primary boolean not null default true, telephone varchar not null ); insert into users select i, NOW() + (random() * (interval '90 days')) + '30 days' from generate_series(1, 10000000) i; insert into users_telephones select id, true, random() :: text from users limit 10000000; -- all users have a primary telephone insert into users_telephones select id, false, random() :: text from users limit 200000; -- some users have a non primary telephone create index on users(created_at); create index on users_telephones(user_id); create index on users_telephones(user_id, is_primary) where is_primary; select count(*) from users; count ---------- 10000000 (1 row) Time: 160.911 ms select count(*) from users_telephones; count ---------- 10200000 (1 row) Time: 176.361 ms select * from users u join users_telephones ut on u.id = ut.user_id where ut.is_primary order by created_at limit 10; id | created_at | user_id | is_primary | telephone ---------+----------------------------+---------+------------+-------------------- 9017755 | 2023-09-11 11:45:37.65744 | 9017755 | t | 0.7182410419408853 6061687 | 2023-09-11 11:45:39.271054 | 6061687 | t | 0.3608686654204689 9823470 | 2023-09-11 11:45:39.284201 | 9823470 | t | 0.3026398665522869 2622527 | 2023-09-11 11:45:39.919549 | 2622527 | t | 0.1929579716250771 7585920 | 2023-09-11 11:45:40.256742 | 7585920 | t | 0.3830236472843005 5077138 | 2023-09-11 11:45:41.076164 | 5077138 | t | 0.9058939392225689 1496883 | 2023-09-11 11:45:42.459194 | 1496883 | t | 0.1519510558344308 9234364 | 2023-09-11 11:45:42.965896 | 9234364 | t | 0.8254433522266105 6988331 | 2023-09-11 11:45:43.130548 | 6988331 | t | 0.9577098184736457 7916398 | 2023-09-11 11:45:43.559425 | 7916398 | t | 0.9681218675498862 (10 rows) Time: 0.973 ms
- aidos 3y ago
  Thanks for bothering to work it through, I was too lazy. But, yeah, exactly. Everyone thinks they need to optimise the life out of this stuff at the beginning but the db can do a lot with normalised data and the appropriate indexes. Side note - is_primary isn’t required in the partial index itself since they’ll all be “true” due to the where clause.
yashap 3y ago
Lots of replies to this one! I created a little benchmark that you can easily run yourself, as long as you have Docker installed. It shows how, for cases like the one I described above, the only way to have consistently fast queries (i.e. even with a cold cache) is to denormalize, so you can create the ideal compound index. The normalize/join version takes 15x longer, which can be the difference between 1s and 15s queries, 2s and 30s, etc. The benchmark: https://gist.github.com/yashap/6d7a34ef37c6b7d3e4fc11b0bece70b0 https://gist.github.com/yashap/6d7a34ef37c6b7d3e4fc11b0bece7... Note: I think in almost all cases you should start with a denormalized schema and use joins. But when you hit cases like the above, it's fine to denormalize just for these specific cases - often you'll just have one or a few such cases in your entire app, where the combination of data size/shape/queries means you cannot have efficient queries without denormalizing. And when people say "joins are slow", it's often cases like this that they're talking about - it's not the join itself that's slow, but rather that cross-table compound indexes are impossible in most RDBMSes, and without that you just can't create good enough indexes for fast queries with lots of data and cold caches.
- throwdbaaway 3y ago
  Nice benchmark script. With EXPLAIN (ANALYZE, BUFFERS), I see that * normalized/join version needs to read 5600 pages * normalized/join version with an additional UNIQUE INDEX .. INCLUDE (type) needs to read 4500 pages * denormalized version only needs to read 66 pages, almost 100x fewer Related to this pagination use case, when using mysql, even the denormalized version may take minutes: https://dom.as/2015/07/30/on-order-by-optimization/ https://dom.as/2015/07/30/on-order-by-optimization/
  - yashap 3y ago
    Ooh ty, will give that article a read! And yeah, that's really the trick to queries that are consistently fast, even with cold caches - read few pages :)

by yashap 3y ago

franckpachot 3y ago

With an index on User (createdAt, id) and one on ContactMethod ( primary,ContactMethod,userId), it should be fast (check that the the execution plan starts with User). Except if lot of recent users have no phones, but that will not be better in a single table (except if columnar storage)

aidos 3y ago
I imagine so too. You’ll be able to interate over the users in order and hit an instant index on contact method. select * from user where exists ( select true from contact_method cm where cm.contact_id = contact.id and cm.method = 'phone' and cm.primary ) order by created_at desc limit 10 —- partial index is even faster create index primary_phone on contact_method (contact_id) where method = 'phone' and primary;
yashap 3y ago
See my reply here: https://news.ycombinator.com/item?id=37116015 https://news.ycombinator.com/item?id=37116015

deleted 3y ago

[deleted]

Turskarama 3y ago

In my experience with SQL, a query like that should return in under a second even if you have 100k or more users. There are some other tricks you can use if you're clever/lucky as well. If you're just using integer IDs (which is reasonable if your system isn't distributed) then you could order by userid on you ContactMethod table and still get the same speed as you would with no join.

yashap 3y ago
See my reply here: https://news.ycombinator.com/item?id=37116015 https://news.ycombinator.com/item?id=37116015

Zanfa 3y ago

> If there are a very large number of users, and a very large number of phone number primary contacts, you cannot make this query fast/efficient I think specific numbers would help make this point better. With a few hundred thousand to low millions of users this should be plenty fast in Postgres for example. That’s magnitudes more than most startups ever reach anyway.

yashap 3y ago
See my reply here: https://news.ycombinator.com/item?id=37116015 https://news.ycombinator.com/item?id=37116015

unnouinceput 3y ago

If the tables involved in the join are of 100M+ records what I do when the joins use varchar columns to improve the performance is to use an additional integer column of the varchar one that is a CRC of it (or hash if you prefer that) and use the integer one instead in the join.

aidos 3y ago
That seems weirdly convoluted. So you store two columns to represent the foreign key?
- unnouinceput 3y ago
  If you use a varchar as FK then you're definitely doing something wrong from beginning. OP was talking about getting the phone number under certain conditions, and a phone number column is a varchar.
  - aidos 3y ago
    I don’t think they ever did a lookup on phone number and even if you needed to, you would just index it and it’d be fast. You can even use things like tri-gram indexes to give you super fast partial phone number matching.

tlarkworthy 3y ago

Yes this is the exact situation where sql falls short. You can't make cross-table indexes to serve OLAP-esq queries, and the most recent X is the common one for pagination in applications. I prefer to denormalize manually at write time in a transaction, rather than use triggers or materialized views.

ako 3y ago
Why do you prefer manually doing this rather than using materialized views? Materialized views seem easier to create and maintain?
- tlarkworthy 3y ago
  Because they are o(n) complexity to refresh so either you settle for eventual complexity or have expensive writes. By forwarding just the index data to the right table you maintain an consistent idiomatic index at 0(1) write cost
  - aidos 3y ago
    Agreed. Matarialized views will be limited in use until we get nice incremental updating versions.
  - gen220 3y ago
    Have you considered implementing this with database triggers instead of in your application logic? Requires a bit of brainpower to set up a system around it, but it makes your application logic dramatically simpler. (You don't have to remember to update `foo.bar` every time you write a function that touches `moo.bar`, and if you run migrations in SQL, the updates will also cascade naturally). It's really high up on my personal wish list for Postgres to support incrementally-materialized views. It doesn't seem like it would be impossible to implement (since, as I suggested, you can implement it on your own with triggers), but IDK, I assume there are higher-priority issues on their docket.
    - tlarkworthy 3y ago

zepolen 3y ago

For 10 million users + telephones, this takes 1ms. create table users ( id serial primary key not null, created_at timestamp not null default now() ); create table users_telephones ( user_id int references users(id) not null, is_primary boolean not null default true, telephone varchar not null ); insert into users select i, NOW() + (random() * (interval '90 days')) + '30 days' from generate_series(1, 10000000) i; insert into users_telephones select id, true, random() :: text from users limit 10000000; -- all users have a primary telephone insert into users_telephones select id, false, random() :: text from users limit 200000; -- some users have a non primary telephone create index on users(created_at); create index on users_telephones(user_id); create index on users_telephones(user_id, is_primary) where is_primary; select count(*) from users; count ---------- 10000000 (1 row) Time: 160.911 ms select count(*) from users_telephones; count ---------- 10200000 (1 row) Time: 176.361 ms select * from users u join users_telephones ut on u.id = ut.user_id where ut.is_primary order by created_at limit 10; id | created_at | user_id | is_primary | telephone ---------+----------------------------+---------+------------+-------------------- 9017755 | 2023-09-11 11:45:37.65744 | 9017755 | t | 0.7182410419408853 6061687 | 2023-09-11 11:45:39.271054 | 6061687 | t | 0.3608686654204689 9823470 | 2023-09-11 11:45:39.284201 | 9823470 | t | 0.3026398665522869 2622527 | 2023-09-11 11:45:39.919549 | 2622527 | t | 0.1929579716250771 7585920 | 2023-09-11 11:45:40.256742 | 7585920 | t | 0.3830236472843005 5077138 | 2023-09-11 11:45:41.076164 | 5077138 | t | 0.9058939392225689 1496883 | 2023-09-11 11:45:42.459194 | 1496883 | t | 0.1519510558344308 9234364 | 2023-09-11 11:45:42.965896 | 9234364 | t | 0.8254433522266105 6988331 | 2023-09-11 11:45:43.130548 | 6988331 | t | 0.9577098184736457 7916398 | 2023-09-11 11:45:43.559425 | 7916398 | t | 0.9681218675498862 (10 rows) Time: 0.973 ms

aidos 3y ago
Thanks for bothering to work it through, I was too lazy. But, yeah, exactly. Everyone thinks they need to optimise the life out of this stuff at the beginning but the db can do a lot with normalised data and the appropriate indexes. Side note - is_primary isn’t required in the partial index itself since they’ll all be “true” due to the where clause.

yashap 3y ago

Lots of replies to this one! I created a little benchmark that you can easily run yourself, as long as you have Docker installed. It shows how, for cases like the one I described above, the only way to have consistently fast queries (i.e. even with a cold cache) is to denormalize, so you can create the ideal compound index. The normalize/join version takes 15x longer, which can be the difference between 1s and 15s queries, 2s and 30s, etc. The benchmark: https://gist.github.com/yashap/6d7a34ef37c6b7d3e4fc11b0bece70b0 https://gist.github.com/yashap/6d7a34ef37c6b7d3e4fc11b0bece7... Note: I think in almost all cases you should start with a denormalized schema and use joins. But when you hit cases like the above, it's fine to denormalize just for these specific cases - often you'll just have one or a few such cases in your entire app, where the combination of data size/shape/queries means you cannot have efficient queries without denormalizing. And when people say "joins are slow", it's often cases like this that they're talking about - it's not the join itself that's slow, but rather that cross-table compound indexes are impossible in most RDBMSes, and without that you just can't create good enough indexes for fast queries with lots of data and cold caches.

throwdbaaway 3y ago
Nice benchmark script. With EXPLAIN (ANALYZE, BUFFERS), I see that * normalized/join version needs to read 5600 pages * normalized/join version with an additional UNIQUE INDEX .. INCLUDE (type) needs to read 4500 pages * denormalized version only needs to read 66 pages, almost 100x fewer Related to this pagination use case, when using mysql, even the denormalized version may take minutes: https://dom.as/2015/07/30/on-order-by-optimization/ https://dom.as/2015/07/30/on-order-by-optimization/
- yashap 3y ago
  Ooh ty, will give that article a read! And yeah, that's really the trick to queries that are consistently fast, even with cold caches - read few pages :)