6 ms·

A lot of that is due to absolutely lousy code. We had a system management backend at my last company. Loading the users list was unbearably slow; 10+ seconds o

A lot of that is due to absolutely lousy code. We had a system management backend at my last company. Loading the users list was unbearably slow; 10+ seconds on a warm cache. Not too terrible, except that most user management tasks required a page reload, so it was just wildly infuriating. Eventually I took a look at the code for the page, which queried LDAP for user data and the database for permissions data. It did: get list of users foreach user: get list of all permissions filter down to the ones assigned directly to the user foreach user: get list of all groups foreach group: get list of all permissions filter down to the ones assigned to the group filter down to the ones the user has I'm no algorithm genius, but I'm pretty sure O(n^2+n^3) is not an efficient one. I replaced it with get list of all users get list of all groups get list of all permissions <filter accordingly> Suffice to say, it was a lot more responsive. Also worth noting was that fetching the user list required shelling out to a command (a python script) which shelled out to a command (ldapsearch), and the whole system was a nightmare. There were also dozens of pages where almost no processing was done in the view, but a bunch of objects with lazy-loaded properties were passed into the template and always used, so when benchmarking you'd get 0.01 seconds for the entire function and then 233 seconds for "return render(...)' because for every single row in the database (dozens or hundreds) the template would access a property that would trigger another SQL call to the backend, rather than just doing one giant "SELECT ALL THE THINGS" and hammering it out that way. Note that we also weren't using Django's foreign keys support, so we couldn't even tell Django to "fetch everything non-lazily" because it had no idea. If that app were written right it could have run on a Raspberry Pi 2, but instead there was no amount of cores that could have sped it up.

JJMcJ 5y ago
Your pattern is quite powerful: get data from several sources and do the rearranging on the client (which might be a web server), instead of multiple interactions for each data item. For SQL you can also do a stored procedure. Sometimes that works well if you are good at your DBMS's procedure language and the schema is good.
- spfzero 5y ago
  Though stored procs will always execute on the server that is probably already the system bottleneck.
  - funnybeam 5y ago
    Sending multiple queries from your web server will likely put more load on the database server than using a stored procedure. With either technique you are still pulling all the data you need from the DB but with multiple queries instead of a stored procedure you are usually pulling more data than you need with each query and then dropping any rows or fields you’re not interested in. Together with multiple calls over the network to the DB server and (often) multiple SQL connection setups this is much worse for performance on both the web and database servers
    - bigbizisverywyz 5y ago
      >Sending multiple queries from your web server will likely put more load on the database server than using a stored procedure. Lots of people seem to not realize that db roundtrips are expensive, and should be avoided whenever possible. One of the best illustrations of this I've found is in Transaction Processing book by Jim Gray and Andreas Reuters where they illustrate the relative cost of getting data from CPU vs CPU cache vs RAM vs cross host query.
      - JJMcJ 5y ago
        Except for open and writing to files, it's about the heaviest action on a backend server.
IfOnlyYouKnew 5y ago
I believe the parent's point was that code tends to be faster than what people expect, not slower.
- namenotrequired 5y ago
  I think the child's point is that people expect code to be slower than it is because they have seen code be slow far more than necessary.
tra3 5y ago
This is an example of N+1 problem [0]. It should be a FizzBuzz for anyone doing any CRUD apps. [0]: https://stackoverflow.com/questions/97197/what-is-the-n1-selects-problem-in-orm-object-relational-mapping https://stackoverflow.com/questions/97197/what-is-the-n1-sel...
onlyrealcuzzo 5y ago
Yeah - you likely want to do this a single simple query - which you can optimize if necessary. an O(N+1) query is bad. An O(N^2) query is something I have rarely seen. Congrats!
benhoyt 5y ago
Yeah, I see this a lot. I think it's especially easy to introduce this kind of "accidentally quadratic" behaviour using magical ORMs like Django's, where an innocent-looking attribute access like user.groups can trigger a database query ... access user.groups inside a loop and things get bad quickly. In the case of groups and permissions there's probably only a few of each, so fetching all of them is probably fine. But depending on your data -- say you're fetching comments written by a subset of users, you can tweak the above to use IN filtering, something like this Python-ish code: users = select('SELECT id, name FROM users WHERE id IN $1', user_ids) comments = select('SELECT user_id, text FROM comments WHERE user_id IN $1', user_ids) comments_by_user_id = defaultdict(list) for c in comments: comments_by_user_id[c.user_id].append(c) for u in users: u.comments = comments_by_user_id[u.id] Only two queries, and O(users + comments). For development, we had a ?queries=1 query parameter you could add to the URL to show the number of SQL queries and their total time at the bottom of the page. Very helpful when trying to optimize this stuff. "Why is this page doing 350 queries totalling 5 seconds? Oops, I must have an N+1 query issue!"
- simonw 5y ago
  Django's prefetch_related mechanism essentially implements the pattern you describe here for you: https://docs.djangoproject.com/en/3.2/ref/models/querysets/#prefetch-related https://docs.djangoproject.com/en/3.2/ref/models/querysets/#...
  - benhoyt 5y ago
    Thanks. Yeah, I think I used that years ago when I first ran into this problem, and it worked well. Whether one uses an ORM or not, one needs to know how to use one's tools. My problem (not just with Django, but with ORMs in general) is how they make bad code look good. Like the following (I don't know Django well anymore, but something like this): users = User.objects.all() for u in user: print(u.name, len(u.comments)) To someone who doesn't know the ORM (or Python) well, u.comments looks cheap ("good"), but it's actually doing a db query under the hood each time around the loop ("bad"). Not to mention it's fetching all the comments when we're only using their count. Whereas if you did that in a more direct-SQL way: users = select('SELECT id, name FROM users WHERE id IN $1', user_ids) for u in user: num_comments = get('SELECT COUNT(*) FROM comments WHERE user_id = $1', u.id) print(u.name, num_comments) This makes the bad pattern look bad. "Oops, I'm doing an SQL query every loop!" The other thing I don't like about (most) ORMs is they fetch all the columns by default, even if the code only uses one or two of them. I know most ORMs provide a way to explicitly specify the columns you want, but the easy/simple default is to fetch them all. I get the value ORMs provide: save a lot of boilerplate and give you nice classes with methods for your tables. I wonder if there's a middle ground where you couldn't do obviously bad things with the ORM without explicitly opting into them. Or even just a heuristic mode for development where it yelled loudly if it detected what looked like an N+1 issue or other query inside a loop.
VintageCool 5y ago
I did some work to improve performance on a dashboard several years ago. The way the statistics were queried was generally terrible, so I spent some time setting up aggregations and cleaning that up, but then... the performance was still terrible. It turned out that the dashboard had been built on top of Wordpress. The way that it checked if the user had permission to access the dashboard was to query all users, join the meta table which held the permission as a serialized object, run a full text search to check which users had permission to access this page, and return the list of all users with permission to access the page. Then, it checked if the current user was in that list. I switched it to only check permissions for the current user, and the page loaded instantaneously.
- dimitrios1 5y ago
  If I look at traces of all the service calls at my company within our microservices environment, the "meat" of each service is a fraction of the latency -- the part that's actually fetching the data from a database, or running an intense calculation. Often times its between 20-40ms Everything else are network hops and what I call "distributed clutter", including authorizing via a third party like Auth0 multiple times for machine-to-machine token (because "zero trust"!), multiple parameter store calls, hitting a dcache, if interacting with a serverless function, cold starts, API gateway latency, etc... So for the meat of a 20-40 ms call, we get about a 400ms-2s backend response time. Then if you are loading a front end SPA with javascript...fugetaboutit it But DevOps will say "but my managed services and infinite scalability!"
  - scns 5y ago
    Like this? https://www.youtube.com/watch?v=y8OnoxKotPQ https://www.youtube.com/watch?v=y8OnoxKotPQ
    - dimitrios1 5y ago
      Exactly like that.
Thaxll 5y ago
Filter in app is rarely the right solution, your data should be organized in a way that you can get what you need in a single query. Reasons: - it's memory efficient - it's atomic - it's faster Also doesn't LDAP support filtering in query?
- zetsurin 5y ago
  Given the context, it probably took the poster very little time to implement that fix, without digging into ldapsearch. With massive speedup, for their likely smallish ldap install. Seems like not a bad call at all.
unclebucknasty 5y ago
Not sure what the exact use case was (i.e. the output of the filtering) but—from reading the first algo—seems to be something to do with determining group membership and permissions for a user. In that case, was there a reason joins couldn't be used? As it still seems pretty wasteful (and less performant) to load all of this data in memory and post-process; whereas a well-indexed database could possibly do it faster and with less-memory usage.
afrodc_ 5y ago
Is there a reason you shelled out with a subprocess versus using a library like ldap3? Just curious
chenxiaolong 5y ago
I had to fix a similar thing in our internal password reset email sender last year. The code was doing something like: for each user in (get_freeipa_users | grep_attribute uid): email = (get_freeipa_users | client_side_find user | grep_attribute email) last_change = (get_freeipa_users | client_side_find user | grep_attribute krblastpwdchange) expiration = (get_freeipa_users | client_side_find user | grep_attribute krbpasswordexpiration) # Some slightly incorrect date math... send_email I changed it to a single LDAP query for every user that requests only the needed attributes. It cut that Jenkins job's runtime from 45 minutes to 0.2 seconds.
codebolt 5y ago
I'd also add that groups and permissions are probably constant and can be cached with a long timeout.
hnbad 5y ago
In defense of whoever wrote the original code: it probably would have been reasonably fast if it had been a database query with proper indexes. The filters would have whittled the selection down to only the relevant data, whereas returning basically three entire tables of data to then throw away most of it would have been extremely inefficient. The mistake of course was not thinking about why this approach is faster in a database query and that it doesn't work that way when you already need to get all the data out of LDAP to do anything with it.

JJMcJ 5y ago

Your pattern is quite powerful: get data from several sources and do the rearranging on the client (which might be a web server), instead of multiple interactions for each data item. For SQL you can also do a stored procedure. Sometimes that works well if you are good at your DBMS's procedure language and the schema is good.

spfzero 5y ago
Though stored procs will always execute on the server that is probably already the system bottleneck.
- funnybeam 5y ago
  Sending multiple queries from your web server will likely put more load on the database server than using a stored procedure. With either technique you are still pulling all the data you need from the DB but with multiple queries instead of a stored procedure you are usually pulling more data than you need with each query and then dropping any rows or fields you’re not interested in. Together with multiple calls over the network to the DB server and (often) multiple SQL connection setups this is much worse for performance on both the web and database servers
  - bigbizisverywyz 5y ago
    >Sending multiple queries from your web server will likely put more load on the database server than using a stored procedure. Lots of people seem to not realize that db roundtrips are expensive, and should be avoided whenever possible. One of the best illustrations of this I've found is in Transaction Processing book by Jim Gray and Andreas Reuters where they illustrate the relative cost of getting data from CPU vs CPU cache vs RAM vs cross host query.
    - JJMcJ 5y ago
      Except for open and writing to files, it's about the heaviest action on a backend server.

IfOnlyYouKnew 5y ago

I believe the parent's point was that code tends to be faster than what people expect, not slower.

namenotrequired 5y ago
I think the child's point is that people expect code to be slower than it is because they have seen code be slow far more than necessary.

tra3 5y ago

This is an example of N+1 problem [0]. It should be a FizzBuzz for anyone doing any CRUD apps. [0]: https://stackoverflow.com/questions/97197/what-is-the-n1-selects-problem-in-orm-object-relational-mapping https://stackoverflow.com/questions/97197/what-is-the-n1-sel...

onlyrealcuzzo 5y ago

Yeah - you likely want to do this a single simple query - which you can optimize if necessary. an O(N+1) query is bad. An O(N^2) query is something I have rarely seen. Congrats!

benhoyt 5y ago

Yeah, I see this a lot. I think it's especially easy to introduce this kind of "accidentally quadratic" behaviour using magical ORMs like Django's, where an innocent-looking attribute access like user.groups can trigger a database query ... access user.groups inside a loop and things get bad quickly. In the case of groups and permissions there's probably only a few of each, so fetching all of them is probably fine. But depending on your data -- say you're fetching comments written by a subset of users, you can tweak the above to use IN filtering, something like this Python-ish code: users = select('SELECT id, name FROM users WHERE id IN $1', user_ids) comments = select('SELECT user_id, text FROM comments WHERE user_id IN $1', user_ids) comments_by_user_id = defaultdict(list) for c in comments: comments_by_user_id[c.user_id].append(c) for u in users: u.comments = comments_by_user_id[u.id] Only two queries, and O(users + comments). For development, we had a ?queries=1 query parameter you could add to the URL to show the number of SQL queries and their total time at the bottom of the page. Very helpful when trying to optimize this stuff. "Why is this page doing 350 queries totalling 5 seconds? Oops, I must have an N+1 query issue!"

simonw 5y ago
Django's prefetch_related mechanism essentially implements the pattern you describe here for you: https://docs.djangoproject.com/en/3.2/ref/models/querysets/#prefetch-related https://docs.djangoproject.com/en/3.2/ref/models/querysets/#...
- benhoyt 5y ago
  Thanks. Yeah, I think I used that years ago when I first ran into this problem, and it worked well. Whether one uses an ORM or not, one needs to know how to use one's tools. My problem (not just with Django, but with ORMs in general) is how they make bad code look good. Like the following (I don't know Django well anymore, but something like this): users = User.objects.all() for u in user: print(u.name, len(u.comments)) To someone who doesn't know the ORM (or Python) well, u.comments looks cheap ("good"), but it's actually doing a db query under the hood each time around the loop ("bad"). Not to mention it's fetching all the comments when we're only using their count. Whereas if you did that in a more direct-SQL way: users = select('SELECT id, name FROM users WHERE id IN $1', user_ids) for u in user: num_comments = get('SELECT COUNT(*) FROM comments WHERE user_id = $1', u.id) print(u.name, num_comments) This makes the bad pattern look bad. "Oops, I'm doing an SQL query every loop!" The other thing I don't like about (most) ORMs is they fetch all the columns by default, even if the code only uses one or two of them. I know most ORMs provide a way to explicitly specify the columns you want, but the easy/simple default is to fetch them all. I get the value ORMs provide: save a lot of boilerplate and give you nice classes with methods for your tables. I wonder if there's a middle ground where you couldn't do obviously bad things with the ORM without explicitly opting into them. Or even just a heuristic mode for development where it yelled loudly if it detected what looked like an N+1 issue or other query inside a loop.

VintageCool 5y ago

I did some work to improve performance on a dashboard several years ago. The way the statistics were queried was generally terrible, so I spent some time setting up aggregations and cleaning that up, but then... the performance was still terrible. It turned out that the dashboard had been built on top of Wordpress. The way that it checked if the user had permission to access the dashboard was to query all users, join the meta table which held the permission as a serialized object, run a full text search to check which users had permission to access this page, and return the list of all users with permission to access the page. Then, it checked if the current user was in that list. I switched it to only check permissions for the current user, and the page loaded instantaneously.

dimitrios1 5y ago
If I look at traces of all the service calls at my company within our microservices environment, the "meat" of each service is a fraction of the latency -- the part that's actually fetching the data from a database, or running an intense calculation. Often times its between 20-40ms Everything else are network hops and what I call "distributed clutter", including authorizing via a third party like Auth0 multiple times for machine-to-machine token (because "zero trust"!), multiple parameter store calls, hitting a dcache, if interacting with a serverless function, cold starts, API gateway latency, etc... So for the meat of a 20-40 ms call, we get about a 400ms-2s backend response time. Then if you are loading a front end SPA with javascript...fugetaboutit it But DevOps will say "but my managed services and infinite scalability!"
- scns 5y ago
  Like this? https://www.youtube.com/watch?v=y8OnoxKotPQ https://www.youtube.com/watch?v=y8OnoxKotPQ
  - dimitrios1 5y ago
    Exactly like that.

Thaxll 5y ago

Filter in app is rarely the right solution, your data should be organized in a way that you can get what you need in a single query. Reasons: - it's memory efficient - it's atomic - it's faster Also doesn't LDAP support filtering in query?

zetsurin 5y ago
Given the context, it probably took the poster very little time to implement that fix, without digging into ldapsearch. With massive speedup, for their likely smallish ldap install. Seems like not a bad call at all.

unclebucknasty 5y ago

Not sure what the exact use case was (i.e. the output of the filtering) but—from reading the first algo—seems to be something to do with determining group membership and permissions for a user. In that case, was there a reason joins couldn't be used? As it still seems pretty wasteful (and less performant) to load all of this data in memory and post-process; whereas a well-indexed database could possibly do it faster and with less-memory usage.

afrodc_ 5y ago

Is there a reason you shelled out with a subprocess versus using a library like ldap3? Just curious

chenxiaolong 5y ago

I had to fix a similar thing in our internal password reset email sender last year. The code was doing something like: for each user in (get_freeipa_users | grep_attribute uid): email = (get_freeipa_users | client_side_find user | grep_attribute email) last_change = (get_freeipa_users | client_side_find user | grep_attribute krblastpwdchange) expiration = (get_freeipa_users | client_side_find user | grep_attribute krbpasswordexpiration) # Some slightly incorrect date math... send_email I changed it to a single LDAP query for every user that requests only the needed attributes. It cut that Jenkins job's runtime from 45 minutes to 0.2 seconds.

codebolt 5y ago

I'd also add that groups and permissions are probably constant and can be cached with a long timeout.

hnbad 5y ago

In defense of whoever wrote the original code: it probably would have been reasonably fast if it had been a database query with proper indexes. The filters would have whittled the selection down to only the relevant data, whereas returning basically three entire tables of data to then throw away most of it would have been extremely inefficient. The mistake of course was not thinking about why this approach is faster in a database query and that it doesn't work that way when you already need to get all the data out of LDAP to do anything with it.