5 ms·

One reason for this is that if the list is lazy loaded (e.g. paginated) in any way, it can be more difficult to make sorting & filtering work on more dimensions

One reason for this is that if the list is lazy loaded (e.g. paginated) in any way, it can be more difficult to make sorting & filtering work on more dimensions - mainly it requires the list to be indexed in extra ways. Not impossible, but some applications weren't designed to support it from the beginning.

Retric 10y ago
If it's common to sort by X, you should add an index. 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. Remember, give me the next 100 of X less than Y is an O(N) operation.
- 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!
    - 10y ago

Retric 10y ago

If it's common to sort by X, you should add an index. 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. Remember, give me the next 100 of X less than Y is an O(N) operation.

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!
  - 10y ago