5 ms·

I'm not sure I understand how a JOIN would have fixed this problem. That is, if each chunk is fetching 1k rows, and you're doing 50 simultaneous chunks, then y

I'm not sure I understand how a JOIN would have fixed this problem. That is, if each chunk is fetching 1k rows, and you're doing 50 simultaneous chunks, then you're doing a 50,000 row query, and that's ALSO going to be extremely slow, in terms of exclusive database contention (less of an issue with bigquery) and result set memory usage (definitely still a huge issue for python). In fact, one of my most frequent pieces of feedback to junior engineers who are just working on a larger backend for the first time is "this query tries to fetch too much data at once, it will take too long and use way more memory then it needs to, please use find_each to automatically batch the query so that we balance memory usage and database contention". Indeed, Rails by default will use the exact same batching strategy the junior engineer chose in this case: fetch 1k items, process those items, and move on to the next 1k items. I understand that the author rankles about things not being done the "right way" with JOIN, but I question whether their focus on "best practices" is preventing them from seeing the optimization forest (split things up into parallel background tasks, don't try to keep the entire dataset in memory at once) for the "doing things right" trees (use JOIN)

civilized 4y ago
Two clear inefficiencies in the junior's code: 1. It is pushing the entire id table back and forth through the network connection, bit by bit. Replacing with a join completely eliminates this. 2. A query with an IN clause is (probably) doing a hash join under the hood to calculate the result of the IN clause. So the junior's code is effectively submitting a join query over and over, each time with a slightly different tiny chunk of data, rather than asking for the joined data once and processing the result in batches. It is also worth considering if the entire data processing pipeline can be in SQL, but I can't tell if that's the case from the blog post.
HelloNurse 4y ago
Do you know what's slower than fetching 50000 rows with a big join? Fetching them with the overhead of thousands of tiny queries instead of one, and repeating disk reads thousands of times because you cannot consolidate the thousands of query executions.
- jerf 4y ago
  Definitely don't underestimate a good database's ability to stream large queries. One of the many ways an ORM-centric view of the world can mess you up, since ORMs have a constitutional bias towards instantiating the entire result of the query in memory. (They don't have to, it isn't completely impossible for them to stream, but even if your ORM can stream it probably doesn't take much to convince it not to, even perhaps accidentally.) It is generally better all the way around to send a single query that is everything you want, if at all possible, let the database do its thing, and then spew a stream of all the results you want at you as fast as the network can carry it, than to be sitting there constantly harassing the poor thing with tiny query after tiny query, adding latency every step of the way. Match it with code that can consume the result as a stream and you can do a lot of work without using a lot of simultaneous resources. This does break down eventually but I feel this is another one of the several places where developers still sometimes subconsciously have an early-2000s view of the world, as if all relational databases start panting and sweating if you ask them to return more than a couple hundred rows of any kind. No, set them up with the right indexes and foreign keys and they'll happily stream gigabytes at you, without the CPU even hardly doing anything. It's just as likely to be the consuming code that is the bottleneck! You get up to "big data" and this approach stops working but what constitutes "big data" has also gotten a lot bigger since the early 2000s. Even in the engineering-centric company I work for, a lot of engineers & management assume that things are "big data" way before they should.
  - btilly 4y ago
    The applicability of this advice definitely depends on the database, drivers, and query. For example with PostgreSQL you need to create a cursor, then FETCH NEXT 1000 over and over again in a loop. This is a bit of a pain, but is the difference between processing as data arrives, with only small buffers everywhere, versus waiting for all data to arrive before doing anything. What exactly you need to do and how to make it work is very much database specific.
    - jerf 4y ago
      Yeah, I wish this was more standard. SQL is not so much a standard as a skeleton of a standard. Better than nothing, maybe, but still every database I walk up I pretty quickly hit issues like this. I'm not trying to promise that every database will stream a petabyte without a problem; I'm more trying to help people get out of an early 2000s mindset and if nothing else, check what their DB will do. A lot of old programmer's tales about how to baby old databases along are actively pessimal and unnecessary in 2022/almost 2023. Don't spend days writing code to correctly slice and dice a query into tiny pieces when you could just send it in one shot and get better performance in every way.
mijoharas 4y ago
> I'm not sure I understand how a JOIN would have fixed this problem If the set of things in A that have ids in B is very small, then very little data is returned from the JOIN query, while a lot may be returned from the B query by itself. (if that set of things is large, then you'll still want to batch the joined query as well, i.e. using find_each in rails. They're orthogonal requirements)
- nightpool 4y ago
  Sure, I mentioned this in my comment as well, but I think it's clear from the use-case of the article that the cardinalities of the two tables are approximately the same.
Normal_gaussian 4y ago
> then you're doing a 50,000 row query, and that's ALSO going to be extremely slow, in terms of exclusive database contention In the example the author gives the query cost is very likely dominated by finding matching rows in A. Where there is no index, then we can expect a full scan of A (or the index of A.id) for every batch of B. This is the case no matter how many rows of B you are searching with; by running the query 50x you make this cost 50x greater. Using a join you pay it once. In addition, and probably more to the point, the round trip database costs (serialisation, parsing, planning, scheduling, network comms) are going to dominate the actual query costs for something like this (unless A is exceptionally large). Furthermore, the memory cost to the DB of the serialisation and parsing is likely to be much larger than just storing all those ids in their native format - and there would be no client memory footprint in a join. For the final result set the client can reduce their memory footprint by using a streaming result which every BigData DB supports, and most others too. If you are particularly concerned about client side memory it is best to either: do everything on the database, or manifest a temporary result table and batch out of that. There are circumstances where the JOIN will be too expensive to do all at once. I've worked with what is claimed to be "BigData" for about 4 years and have had only a few situations like that; but none of them would be ameanable to a batching like this, and instead need much more complex architectural steps to make cheaper.
- nightpool 4y ago
  > In the example the author gives the query cost is very likely dominated by finding matching rows in A. Where there is no index, then we can expect a full scan of A (or the index of A.id) for every batch of B. Why would you expect that there's no index? I have never seen a single database system where the most basic primary key A.id wasn't indexed. Instead, I would expect that you're correct below that cost of the query is dominated by fetching the rows from disk and serializing them—this is a linear cost that increases with the number of rows returned, so fetching 50,000 rows should be about 50x as slow as fetching 1,000 rows (especially as long as you're fetching them in some sort of block-cache-amenable order, such as in increasing ID order, so that you're seeking to sequential places on the disk most of the time instead of fetching just random blocks) > In addition, and probably more to the point, the round trip database costs (serialisation, parsing, planning, scheduling, network comms) are going to dominate the actual query costs for something like this (unless A is exceptionally large). Aside from a small overhead, serialization, parsing and network comms will all increasing linearly with the amount of data returned. 50,000 rows of data will be about 50x the serialization and network cost of 1,000 rows. > Furthermore, the memory cost to the DB of the serialisation and parsing is likely to be much larger than just storing all those ids in their native format - and there would be no client memory footprint in a join. For the final result set the client can reduce their memory footprint by using a streaming result which every BigData DB supports, and most others too Sure, I can absolutely agree that using a streaming result set would be the best of all possible worlds here. However, it does require you to keep a client connection open for 50x longer than batching would, which on many databases (e.g. Postgres), would lead to more memory usage and CPU contention then batching the result in a background job queueing system. This comes down to what % of your total pipeline is spent in the database in question compared to data processing or other databases—if only 20% of your job's runtime is fetching the rows from this database, then it's a bad idea to monopolize that DB memory for the much larger amount of time it takes you to process the entire result set, when instead you could be yielding that memory back to the system for other transactions to use. But if 80%+ of your time is spent in the database, then the small amount of time that other transactions would be able to reclaim wouldn't be worth the amount of fixed overhead from re-planning, re-executing, re-fetching the index from cache, etc. And obviously these—as you may have been able to guess, my experience here is rooted in OLTP workloads using Postgres, and I'm sure there are plenty of differences with BigQuery's architecture.
btilly 4y ago
A join would have fixed the problem by pushing the logic inside of the database where it would have been optimized more easily. It would have traversed the indexes in parallel. Once. But they didn't. Instead they made the database parse every single record, compile it, and then try to optimize it. Which will come up with a plan where you had to do index lookup after index lookup. That parsing and optimization overhead is probably most of your time. But even ignoring that, a single scan for `n` things in an index with `m` things winds up taking an average time `O(n log(m/n))`. Which is generally faster than the `O(n log(m))` of separate lookups. This change saves a tremendous amount of work on the database, and therefore reduces contention for resources. That's database 101, and any competent DBA should be able to give you the lecture. As a programmer you might not understand how much of a difference it makes. But trust me, it does. Now about data quantity. You're giving cargo cult advice on queries that is only sometimes going to be right. What is the actual tradeoff for find_each? The one win is that you return limited data on each trip. 50,000 records really isn't that much these days, so I discount the win. But it can matter, particularly for memory constrained containers. But what is happening inside the database if you fetch 50,000 records from a join, in batches of a thousand? As I understand, it uses limit and offset statements to figure out the result. But how doe that work? First, it calculates the join to find 1000 records and returns them. Second, it calculates the join to find 2000 records, throws 1000 away, and returns the rest. Third, it calculates the join to find 3000 records, throws 2000 away, and returns the rest. And so on until it has found a full 1,275,000 records, of which it has thrown away 1,225,000 and returned 50,000. Guess what this means for total database work required? And the behavior is fundamentally quadratic. If you have 10x the data to process, your database has to do 100x the work. There are definitely a lot of use cases where you need to batch records. But your batch size should be as large as you can comfortably use. And you need to realize that you're trading off trading up front memory for time and more work inside of the database. The next time that you find yourself having to go down the "optimization tree", I strongly recommend considering whether you're in fact trying to put a patch on a self-inflicted wound. Try proper joins, indexes, and a larger batch size first. See how much of a difference that makes. Alternately take advantage of the fact that you know your tables in a way that Rails doesn't. Order the results by primary key. Every time you fetch a batch, record the largest primary key you returned. Then instead of offset/limit on the next query, use a limit and a condition on the key. This will eliminate almost all of the duplicate work in most situations, at the cost of having somewhat more fragile logic.
zxcvbnm 4y ago
Fetching 50k rows is a nobrainer, neither speed nor memory wise. Relational db-s are super fast when used properly
scott_s 4y ago
Without a join, you are sending the entirety of Table B over the wire and processing it in Python. Then you send that back to the database, inline in a query, to do an ad-hoc join on Table A. The results are then sent back over the wire to the Python side. Notably, the result set may be small, and it may always be small. Table B may grow very large, and all of it will always be sent over the wire and processed in Python. With a join, the database is able to do the join on Table A and Table B in place, using whatever indexes it already has built up. The only thing sent over and processed by the Python is the result set. Even if Table B becomes very large, only the result set is sent over the wire and processed in Python. Without a join in the query, you're essentially having to replicate the kind of logic that already exists in the database engine, in Python. That is, the database engine is already doing chunking and parallelization for you.
- nightpool 4y ago
  Sure, I mean, I want to be clear—there's certainly a lot of inefficiency here. But my point is that the OP is talking about their data processing pipeline taking HOURS to handle queries for 50,000 IDs (50 parallel queries—1,000 IDs per query). When it comes down to it, I just don't believe that the inefficiency in serializing 1,000 numbers in python and then deserializing them in BigQuery has anything to do with the problems OP was experiencing. Remember—OP is probably going to be getting back 50,000 rows from the database anyway, the additional work here is linear with respect to the amount of rows retrieved. Sending 50,000 numbers over the wire to get back 50,000 rows worth of data is not an "hours long" processing cost, in the scheme of things.

civilized 4y ago

Two clear inefficiencies in the junior's code: 1. It is pushing the entire id table back and forth through the network connection, bit by bit. Replacing with a join completely eliminates this. 2. A query with an IN clause is (probably) doing a hash join under the hood to calculate the result of the IN clause. So the junior's code is effectively submitting a join query over and over, each time with a slightly different tiny chunk of data, rather than asking for the joined data once and processing the result in batches. It is also worth considering if the entire data processing pipeline can be in SQL, but I can't tell if that's the case from the blog post.

HelloNurse 4y ago

Do you know what's slower than fetching 50000 rows with a big join? Fetching them with the overhead of thousands of tiny queries instead of one, and repeating disk reads thousands of times because you cannot consolidate the thousands of query executions.

jerf 4y ago
Definitely don't underestimate a good database's ability to stream large queries. One of the many ways an ORM-centric view of the world can mess you up, since ORMs have a constitutional bias towards instantiating the entire result of the query in memory. (They don't have to, it isn't completely impossible for them to stream, but even if your ORM can stream it probably doesn't take much to convince it not to, even perhaps accidentally.) It is generally better all the way around to send a single query that is everything you want, if at all possible, let the database do its thing, and then spew a stream of all the results you want at you as fast as the network can carry it, than to be sitting there constantly harassing the poor thing with tiny query after tiny query, adding latency every step of the way. Match it with code that can consume the result as a stream and you can do a lot of work without using a lot of simultaneous resources. This does break down eventually but I feel this is another one of the several places where developers still sometimes subconsciously have an early-2000s view of the world, as if all relational databases start panting and sweating if you ask them to return more than a couple hundred rows of any kind. No, set them up with the right indexes and foreign keys and they'll happily stream gigabytes at you, without the CPU even hardly doing anything. It's just as likely to be the consuming code that is the bottleneck! You get up to "big data" and this approach stops working but what constitutes "big data" has also gotten a lot bigger since the early 2000s. Even in the engineering-centric company I work for, a lot of engineers & management assume that things are "big data" way before they should.
- btilly 4y ago
  The applicability of this advice definitely depends on the database, drivers, and query. For example with PostgreSQL you need to create a cursor, then FETCH NEXT 1000 over and over again in a loop. This is a bit of a pain, but is the difference between processing as data arrives, with only small buffers everywhere, versus waiting for all data to arrive before doing anything. What exactly you need to do and how to make it work is very much database specific.
  - jerf 4y ago
    Yeah, I wish this was more standard. SQL is not so much a standard as a skeleton of a standard. Better than nothing, maybe, but still every database I walk up I pretty quickly hit issues like this. I'm not trying to promise that every database will stream a petabyte without a problem; I'm more trying to help people get out of an early 2000s mindset and if nothing else, check what their DB will do. A lot of old programmer's tales about how to baby old databases along are actively pessimal and unnecessary in 2022/almost 2023. Don't spend days writing code to correctly slice and dice a query into tiny pieces when you could just send it in one shot and get better performance in every way.

mijoharas 4y ago

> I'm not sure I understand how a JOIN would have fixed this problem If the set of things in A that have ids in B is very small, then very little data is returned from the JOIN query, while a lot may be returned from the B query by itself. (if that set of things is large, then you'll still want to batch the joined query as well, i.e. using find_each in rails. They're orthogonal requirements)

nightpool 4y ago
Sure, I mentioned this in my comment as well, but I think it's clear from the use-case of the article that the cardinalities of the two tables are approximately the same.

Normal_gaussian 4y ago

> then you're doing a 50,000 row query, and that's ALSO going to be extremely slow, in terms of exclusive database contention In the example the author gives the query cost is very likely dominated by finding matching rows in A. Where there is no index, then we can expect a full scan of A (or the index of A.id) for every batch of B. This is the case no matter how many rows of B you are searching with; by running the query 50x you make this cost 50x greater. Using a join you pay it once. In addition, and probably more to the point, the round trip database costs (serialisation, parsing, planning, scheduling, network comms) are going to dominate the actual query costs for something like this (unless A is exceptionally large). Furthermore, the memory cost to the DB of the serialisation and parsing is likely to be much larger than just storing all those ids in their native format - and there would be no client memory footprint in a join. For the final result set the client can reduce their memory footprint by using a streaming result which every BigData DB supports, and most others too. If you are particularly concerned about client side memory it is best to either: do everything on the database, or manifest a temporary result table and batch out of that. There are circumstances where the JOIN will be too expensive to do all at once. I've worked with what is claimed to be "BigData" for about 4 years and have had only a few situations like that; but none of them would be ameanable to a batching like this, and instead need much more complex architectural steps to make cheaper.

nightpool 4y ago
> In the example the author gives the query cost is very likely dominated by finding matching rows in A. Where there is no index, then we can expect a full scan of A (or the index of A.id) for every batch of B. Why would you expect that there's no index? I have never seen a single database system where the most basic primary key A.id wasn't indexed. Instead, I would expect that you're correct below that cost of the query is dominated by fetching the rows from disk and serializing them—this is a linear cost that increases with the number of rows returned, so fetching 50,000 rows should be about 50x as slow as fetching 1,000 rows (especially as long as you're fetching them in some sort of block-cache-amenable order, such as in increasing ID order, so that you're seeking to sequential places on the disk most of the time instead of fetching just random blocks) > In addition, and probably more to the point, the round trip database costs (serialisation, parsing, planning, scheduling, network comms) are going to dominate the actual query costs for something like this (unless A is exceptionally large). Aside from a small overhead, serialization, parsing and network comms will all increasing linearly with the amount of data returned. 50,000 rows of data will be about 50x the serialization and network cost of 1,000 rows. > Furthermore, the memory cost to the DB of the serialisation and parsing is likely to be much larger than just storing all those ids in their native format - and there would be no client memory footprint in a join. For the final result set the client can reduce their memory footprint by using a streaming result which every BigData DB supports, and most others too Sure, I can absolutely agree that using a streaming result set would be the best of all possible worlds here. However, it does require you to keep a client connection open for 50x longer than batching would, which on many databases (e.g. Postgres), would lead to more memory usage and CPU contention then batching the result in a background job queueing system. This comes down to what % of your total pipeline is spent in the database in question compared to data processing or other databases—if only 20% of your job's runtime is fetching the rows from this database, then it's a bad idea to monopolize that DB memory for the much larger amount of time it takes you to process the entire result set, when instead you could be yielding that memory back to the system for other transactions to use. But if 80%+ of your time is spent in the database, then the small amount of time that other transactions would be able to reclaim wouldn't be worth the amount of fixed overhead from re-planning, re-executing, re-fetching the index from cache, etc. And obviously these—as you may have been able to guess, my experience here is rooted in OLTP workloads using Postgres, and I'm sure there are plenty of differences with BigQuery's architecture.

btilly 4y ago

A join would have fixed the problem by pushing the logic inside of the database where it would have been optimized more easily. It would have traversed the indexes in parallel. Once. But they didn't. Instead they made the database parse every single record, compile it, and then try to optimize it. Which will come up with a plan where you had to do index lookup after index lookup. That parsing and optimization overhead is probably most of your time. But even ignoring that, a single scan for `n` things in an index with `m` things winds up taking an average time `O(n log(m/n))`. Which is generally faster than the `O(n log(m))` of separate lookups. This change saves a tremendous amount of work on the database, and therefore reduces contention for resources. That's database 101, and any competent DBA should be able to give you the lecture. As a programmer you might not understand how much of a difference it makes. But trust me, it does. Now about data quantity. You're giving cargo cult advice on queries that is only sometimes going to be right. What is the actual tradeoff for find_each? The one win is that you return limited data on each trip. 50,000 records really isn't that much these days, so I discount the win. But it can matter, particularly for memory constrained containers. But what is happening inside the database if you fetch 50,000 records from a join, in batches of a thousand? As I understand, it uses limit and offset statements to figure out the result. But how doe that work? First, it calculates the join to find 1000 records and returns them. Second, it calculates the join to find 2000 records, throws 1000 away, and returns the rest. Third, it calculates the join to find 3000 records, throws 2000 away, and returns the rest. And so on until it has found a full 1,275,000 records, of which it has thrown away 1,225,000 and returned 50,000. Guess what this means for total database work required? And the behavior is fundamentally quadratic. If you have 10x the data to process, your database has to do 100x the work. There are definitely a lot of use cases where you need to batch records. But your batch size should be as large as you can comfortably use. And you need to realize that you're trading off trading up front memory for time and more work inside of the database. The next time that you find yourself having to go down the "optimization tree", I strongly recommend considering whether you're in fact trying to put a patch on a self-inflicted wound. Try proper joins, indexes, and a larger batch size first. See how much of a difference that makes. Alternately take advantage of the fact that you know your tables in a way that Rails doesn't. Order the results by primary key. Every time you fetch a batch, record the largest primary key you returned. Then instead of offset/limit on the next query, use a limit and a condition on the key. This will eliminate almost all of the duplicate work in most situations, at the cost of having somewhat more fragile logic.

zxcvbnm 4y ago

Fetching 50k rows is a nobrainer, neither speed nor memory wise. Relational db-s are super fast when used properly

scott_s 4y ago

Without a join, you are sending the entirety of Table B over the wire and processing it in Python. Then you send that back to the database, inline in a query, to do an ad-hoc join on Table A. The results are then sent back over the wire to the Python side. Notably, the result set may be small, and it may always be small. Table B may grow very large, and all of it will always be sent over the wire and processed in Python. With a join, the database is able to do the join on Table A and Table B in place, using whatever indexes it already has built up. The only thing sent over and processed by the Python is the result set. Even if Table B becomes very large, only the result set is sent over the wire and processed in Python. Without a join in the query, you're essentially having to replicate the kind of logic that already exists in the database engine, in Python. That is, the database engine is already doing chunking and parallelization for you.

nightpool 4y ago
Sure, I mean, I want to be clear—there's certainly a lot of inefficiency here. But my point is that the OP is talking about their data processing pipeline taking HOURS to handle queries for 50,000 IDs (50 parallel queries—1,000 IDs per query). When it comes down to it, I just don't believe that the inefficiency in serializing 1,000 numbers in python and then deserializing them in BigQuery has anything to do with the problems OP was experiencing. Remember—OP is probably going to be getting back 50,000 rows from the database anyway, the additional work here is linear with respect to the amount of rows retrieved. Sending 50,000 numbers over the wire to get back 50,000 rows worth of data is not an "hours long" processing cost, in the scheme of things.