5 ms·

> But, if it's rare to sort by X then doing it the hard way is at worst (O) x log x which is a generally a non issue out to a few billion records. Not really t

by gregmac 10y ago

> But, if it's rare to sort by X then doing it the hard way is at worst (O) x log x which is a generally a non issue out to a few billion records. Not really true. Users aren't understanding if "sometimes the list page takes over 10 seconds to load". They don't understand (or care) that they are doing a non-indexed query or that the alternative is they don't get to do it at all. Removing a feature is often not acceptable, and so often the only resolution to a problem like this is to add an index. Of course, indexes increase the write times to your database. Indexes on every field increase the write times by a lot. Except sometimes you can't simply add an index, because you're displaying a calculated value and only calculate it for the page you're displaying. In order to sort by that value, you have to calculate for the entire system, so now you're into O(n^2) or worse complexity. You can also denormalize or pre-cache calculated values in some way (even going as far as adding something like ElasticSearch on top), but that introduces another dimension of problems (expensive updates, more potential for bugs and/or stale data). Do this for several fields, and you're now talking about quite a significant development effort, both up-front and for on-going maintenance, to support sorting that wasn't ever an actual requested feature and that only a small minority of users actually use. I know this because I have inherited exactly this problem before. Even as thousands turn to millions (let alone billions), anything worse than O(n log n) becomes painfully obvious rather quickly, and it tends to happen to the entire system at once. Suddenly you have to fix a whole bunch of "this feature is unusable slow, you broke my business" problems at the same time, while getting further and further behind your actual planned schedule. > Remember, give me the next 100 of X less than Y is an O(N) operation. ..IIF you spent the time to implement caching (and deal with the additional cache invalidation complexity problems). Many apps do paging on the database, or only do expensive joins after paging. Heck, many apps are even stupider and query the entire dataset from the DB, do paging in code, then throw it all away afterwards (so every time the client asks for the next page, it transfers the entire result set from the DBMS).

Retric 10y ago
Ed: The specifics on how things get broken are complex and fixing them can be non-trivial. But, punting these issues often means they keep showing up when you want to do some other completely reasonable thing. People talk about unit tests as a huge thing, but when your software can't handle basic functionality things are already horribly broken. As to removing features to avoid slow pages when using the feature, that's a horrible tradeoff.
rhizome 10y ago
Heck, many apps are even stupider and query the entire dataset from the DB, do paging in code I would only expect to see something like this at a company with glacial bureaucracy because that's a technique that was already garbage in 2007 when I had to babysit an app whose devs decided to retrieve a user's entire object graph whenever doing a User#show. 10sec load times are similiarly the domain of the DMV and trivial hobby apps on a free Heroku. At the risk of exposing myself as an FB user and thus older than 25, I think a better example for discussion is FB's wall sort: "Top Stories" vs. "Most Recent." If you're like me, you like "Most Recent," but Zuck has his own ideas about how I should live my life and will switch me back to "Top Stories" anywhere from 6 to 24 hours after my last visit. You cannot hard-set your wall to "Most Recent." Educated me would think that sorting by date descending is the O(nlogn)-iest of sorts, yet here we are, with Big Data Massage turning out to be a forced default. Point being, I hope: it's not just a choice between 10s loads and the elimination of features. The difference is rarely that stark, and with simple attribute sorts (even multiple) should be nigh-on unnoticeable. Except sometimes you can't simply add an index, because you're displaying a calculated value and only calculate it for the page you're displaying. In order to sort by that value, you have to calculate for the entire system, so now you're into O(n^2) or worse complexity. You can also denormalize or pre-cache calculated values in some way (even going as far as adding something like ElasticSearch on top), but that introduces another dimension of problems (expensive updates, more potential for bugs and/or stale data). I have a heuristic that if you're doing temp tables and derived values and whatnot, you're edging into reporting, so denormalizing and aggregating makes a lot of sense for that. Apologies if I've ranted entirely past your point!
- gregmac 10y ago
  > I have a heuristic that if you're doing temp tables and derived values and whatnot, you're edging into reporting, so denormalizing and aggregating makes a lot of sense for that. Totally agree. > 10sec load times are similiarly the domain of the DMV and trivial hobby apps on a free Heroku. Unfortunately, the app I was talking about: 1) Allows customization of several views, including adding several columns that are expensive (and users can add all of them, if they want). This was not a big deal with hundreds of items, but is with hundreds of thousands. 2) Has a hierarchy above these objects, but doesn't enforce any context. So literally you can load this view for the entire system (which can be hundreds of thousands of objects, with some columns that summarize data from tens of millions of rows) 3) Some of the expensive calculated values are time-dependent, eg "past hour", "past day" etc, which also makes pre-calculating a very expensive operation (not impacting user time directly, but adding overall load to the system). 4) Was built on top of MS SQL server, deployed both as a "cloud" model and as a product on-premise at customer sites. This meant several customers were heavily invested in SQL licenses, and beefy hardware to run it all. Even if we overlooked the challenge of updating our own product (half a million lines? give or take) and data migration (dozens of ten to hundred-GB databases, and hundreds of smaller ones), changing to another DBMS and telling our customers that their tens-of-thousands of dollars investments in hardware/licenses were useless was unacceptable. So yes, in this case it was possible to get multiple-minute load times in the worst cases. Why would anyone want to see many of these columns for hundreds of thousands of rows at once? I have no idea, but they could, and it was slow, and they complained. To your point: this absolutely should have been considered 'reporting', but the app didn't make that distinction. This was the main view of data, essentially, and it was possible for users to make it really slow. We ended up redoing part of the UI at one point, and during that time, removed sorting from some of the columns. Users complained about this at the time, but got over it. We also put a hard limit on of 20,000 objects: more than that and it just says "please pick a group" first. Again, users complained about this, but got over it. Going through that was crappy, but the constant complains about being slow stopped. I should note, there is a separate reporting UI that does allow sorting by everything. I wanted to go much further than that, and completely re-think the UI and some of the design concepts (such as not allowing a single list to be viewed for the entire system at once, and instead either summarizing multiple groups, or displaying detail for one) but at the time the business side (including up to the CEO) was unwilling to do a change like that, and we also had no formal product management to really push the issue.

by gregmac 10y ago

Retric 10y ago

Ed: The specifics on how things get broken are complex and fixing them can be non-trivial. But, punting these issues often means they keep showing up when you want to do some other completely reasonable thing. People talk about unit tests as a huge thing, but when your software can't handle basic functionality things are already horribly broken. As to removing features to avoid slow pages when using the feature, that's a horrible tradeoff.

rhizome 10y ago

Heck, many apps are even stupider and query the entire dataset from the DB, do paging in code I would only expect to see something like this at a company with glacial bureaucracy because that's a technique that was already garbage in 2007 when I had to babysit an app whose devs decided to retrieve a user's entire object graph whenever doing a User#show. 10sec load times are similiarly the domain of the DMV and trivial hobby apps on a free Heroku. At the risk of exposing myself as an FB user and thus older than 25, I think a better example for discussion is FB's wall sort: "Top Stories" vs. "Most Recent." If you're like me, you like "Most Recent," but Zuck has his own ideas about how I should live my life and will switch me back to "Top Stories" anywhere from 6 to 24 hours after my last visit. You cannot hard-set your wall to "Most Recent." Educated me would think that sorting by date descending is the O(nlogn)-iest of sorts, yet here we are, with Big Data Massage turning out to be a forced default. Point being, I hope: it's not just a choice between 10s loads and the elimination of features. The difference is rarely that stark, and with simple attribute sorts (even multiple) should be nigh-on unnoticeable. Except sometimes you can't simply add an index, because you're displaying a calculated value and only calculate it for the page you're displaying. In order to sort by that value, you have to calculate for the entire system, so now you're into O(n^2) or worse complexity. You can also denormalize or pre-cache calculated values in some way (even going as far as adding something like ElasticSearch on top), but that introduces another dimension of problems (expensive updates, more potential for bugs and/or stale data). I have a heuristic that if you're doing temp tables and derived values and whatnot, you're edging into reporting, so denormalizing and aggregating makes a lot of sense for that. Apologies if I've ranted entirely past your point!

gregmac 10y ago
> I have a heuristic that if you're doing temp tables and derived values and whatnot, you're edging into reporting, so denormalizing and aggregating makes a lot of sense for that. Totally agree. > 10sec load times are similiarly the domain of the DMV and trivial hobby apps on a free Heroku. Unfortunately, the app I was talking about: 1) Allows customization of several views, including adding several columns that are expensive (and users can add all of them, if they want). This was not a big deal with hundreds of items, but is with hundreds of thousands. 2) Has a hierarchy above these objects, but doesn't enforce any context. So literally you can load this view for the entire system (which can be hundreds of thousands of objects, with some columns that summarize data from tens of millions of rows) 3) Some of the expensive calculated values are time-dependent, eg "past hour", "past day" etc, which also makes pre-calculating a very expensive operation (not impacting user time directly, but adding overall load to the system). 4) Was built on top of MS SQL server, deployed both as a "cloud" model and as a product on-premise at customer sites. This meant several customers were heavily invested in SQL licenses, and beefy hardware to run it all. Even if we overlooked the challenge of updating our own product (half a million lines? give or take) and data migration (dozens of ten to hundred-GB databases, and hundreds of smaller ones), changing to another DBMS and telling our customers that their tens-of-thousands of dollars investments in hardware/licenses were useless was unacceptable. So yes, in this case it was possible to get multiple-minute load times in the worst cases. Why would anyone want to see many of these columns for hundreds of thousands of rows at once? I have no idea, but they could, and it was slow, and they complained. To your point: this absolutely should have been considered 'reporting', but the app didn't make that distinction. This was the main view of data, essentially, and it was possible for users to make it really slow. We ended up redoing part of the UI at one point, and during that time, removed sorting from some of the columns. Users complained about this at the time, but got over it. We also put a hard limit on of 20,000 objects: more than that and it just says "please pick a group" first. Again, users complained about this, but got over it. Going through that was crappy, but the constant complains about being slow stopped. I should note, there is a separate reporting UI that does allow sorting by everything. I wanted to go much further than that, and completely re-think the UI and some of the design concepts (such as not allowing a single list to be viewed for the entire system at once, and instead either summarizing multiple groups, or displaying detail for one) but at the time the business side (including up to the CEO) was unwilling to do a change like that, and we also had no formal product management to really push the issue.