How to sort 56k complex objects quickly.

This is not something I will go indepth for, because the actual implementation
will probably change for your project AND I just want to get this out there
quickly.

So my issue was that I was trying to sort 56 000 objects quickly, for the sake
of pagination, using LINQs .Take and .Skip methods. Say I wanted the 30th page
of items and I wanted to have 15 items per page, I’d Skip the first 29 pages
worth of items ( 29 * 15) and then .Take the next 15 items. It’d look like

db.Table.Skip(435).Take(15).ToList();

but was running into issues when I tried to do that because you need to use
OrderBy first on the set of objects, in order to be able to skip the first ones,
since they’re not in any reliable order to .Skip in the first place.

db.Table.OrderBy(item => item.ID).Skip(435).Take(15).ToList();

I’m sure with more simple objects, just adding the OrderBy call would be enough
to do the trick, but my objects were a wrapper around 4 or 5 other objects.
Definitely not a good idea, but it’s what I’ve got! So anyway, the issue was
that it was taking over 3 seconds for just 56k objects. I tried not only
Orderby, but Take’ing the 30 pages and GetRange’ing the last page worth. That
was actually a small improvement initially, since I only ever tested it on the
first page, which meant that there was only 30 or so objects being pulled and
dealt with.

But as you might imagine, as I got to page 1000, there was a Timeout exception
naturally, as it was trying to deal with 15000 items in memory. So this very
last thing I tried, I didn’t really expect it to work for me, since I was
already sorting by ID:

I .Select’ed only the IDs for the objects I wanted to pull, rather that the
entire object. Simple right? What that means is that once I was ready to list
only the 15 items I wanted to show, I didn’t have to OrderBy all the objects and
then Skip and Take from that, I only had to deal with simple integers instead,
and then find the associated ids later with a line that looks something like the
following, with a healthy mix of .Where and .Any:

db.Table.Where( item =>
                sorted_item_ids.Any(
                    item_id =>
                       item_id ==
                     item.deeper_object.item_id)) .ToList();
                

In the likely case that that’s not as clear as it seems, it’s looking to match
any objects from db.Table with any of the item_ids from the sorted_item_ids
list, which is an array of ints, and then finally turns the resulting IQueryable
into a List<table_object>.

And there you have it! I’m not sure this post makes any sense as I wrote it
pretty quickly, so maybe I’ll come back to it later and clean it up. (Fat
chance, right?)

Latest Project: A new website!

What’s up dudes! It’s been a while, but I’ve been busy. If you’ve been following me on Twitter, you’ll see that I’ve been working on this new website. It’s basically just like 5000best.com/movies or easyqueue or whatever it’s called. I’ve never used them, since I only use it on the xbox, and the interface is pretty bad!

But anyways, the project has been underway for a few weeks now, and while it’s my first website that I’m building from as scratch as you can get with C#’s ASP.NET MVC4, it’s coming along nicely. So far, I’ve managed to pull down the Netflix API’s Index, so that’s about 55k titles that I’ve got to play around with. The dataset is pretty complete, which means that it’s pretty comprehensive.

Once I got MVC4 set up and working, which was not easy, even with sec_goat’s help by the way, was getting a database local server working. I don’t want to get into that too much, because I’m still sick of the idea, but basically MVC4 uses 2012 SQL databases, and I had SQL SERVER 2008, so I needed to update to 2012 to match the server I had created. That meant I needed to update to ’08, ’08 SP1, ’08 R2, ’08 R2 SP1, ’08 R2 SP3, then finally ’12. I think I even needed SP1 on the ’12. But it really isn’t clear the order to me, since at that point I was just installing everything I could and trying to get it to work. It was frustrating.

Another issue I am currently dealing with is the idea of Database Normalization. What that is is essentially splitting up a database in order to get to be the least redundant as it could possibly be. Reducing columns that work out to the same thing. Like say you had an ingredient list, and you added ketchup and mustard and pickles. But EVERY single time you didn’t use ketchup, you took away mustard too, so that means that you might as well have one column called toppings yes or no, rather than a ketchup and a mustard column. Well, that’s actually a really poor example. As usual, Stack Overflow has a better example, as well as About.com actually.

So back to the issue. I used to have ALL the relevant data from the Netflix API in one massive, ugly table, but I wasn’t happy with how long that it was taking to get data from it (and apparently DB Normalization doesn’t really help with that, but maybe it does, I really don’t know at this point) so I endeavored to break it up. So it’s most of the movie data, like year released, duration, rating etc in one table, then a list of all the genres into another, then a cross table, linking one genre to one movie ID. And with Box Art, I’ve got a table of movie id’s linked with the box art of relevant sizes. That way whenever I need to box art for a movie ID, I can just select it from the BoxArt table, rather than look through the whole movies database. Dunno if it helps my speed case at all, but I hope so.

Right this minute, I’m building the list of Movie to Genre table to make. It’s been about 20 minutes since I’ve started writing this, and it’s at movie 909 out of 55k. It’ll take about 10 hours I think to create the table in full, but I’m told that isn’t a terrible amount of time. But again, I don’t know for sure.

So there you have it, good news and bad new. A lot of frustration but a lot of new information, so you take what you can get. I definitely don’t like knowing absolutely nothing about DBM and SQL, and asking really basic questions, but I guess that’s just part of the job. Er, hobby.