Subscribe to
Posts
Comments
NSLog(); Header Image

Order in the Database!

Andy and I are working hard on PulpFiction today. Our next challenge was in presenting a list of folders in an outline view. The folders are stored in a database, and so when Cocoa calls this method, we need to have an answer ready:

- (id)outlineView:(NSOutlineView *)outlineView child:(int)index ofItem:(id)item

There's no guarantee that it'll query our database in any order, and databases just don't keep order anyway. Each item in the database could maintain an "orderID" but in a list of 100, if someone moves item 92 to the second position, you've got to instantly UPDATE another 91 items or so. Additions to the list, subtractions - every action would result in tons of UPDATEs.

Our solution was (is currently) to store an array in the prefs. The array keeps the order, can match the "index" of the method call, and can simply map to an NSString (we'd use an NSNumber, but the database returns only strings of course). This NSString is the unique folderID. Easy enough. Subfolders will point to an NSDictionary containing the name of the folder and an array. And so on.

This is something I call "arbitrary order" of a database. Yes, there are "ORDER BY" statements, but they typically sort on things like "product_name" or "date_added" or whatever. Suppose you're building a DB-driven site for a customer who wants to list his products in whatever order he wants. Suppose he's got 100 products. Talk about a headache. I've never found a solution I like, that's for sure.

6 Responses to "Order in the Database!"

  1. Each item in the database could maintain an "orderID" but in a list of 100, if someone moves item 92 to the second position, you've got to instantly UPDATE another 91 items or so.

    Why can't you just swap the orderId's? Assuming you have a unique identifier for both items, it should only require 2 update statements:

    UPDATE Table SET orderId = aOrderId WHERE uniqueID = bId

    UPDATE Table SET orderId = bOrderId WHERE uniqueID = aId

    Additions to the list, subtractions - every action would result in tons of UPDATEs.

    Insertion and deletion should need no more than one UPDATE and a INSERT and DELETE, respectively. For example, if you want to insert an item with orderId 5:

    UPDATE Table SET orderId = orderId + 1 WHERE orderId >= 5

    INSERT...

    or delete:

    DELETE FROM Table WHERE orderId = 5

    UPDATE Table SET orderId = orderId - 1 WHERE orderId >= 5

    Obviously, there'd need to be some other bits on the where clause, since you're doing some sort of fancy-pants hierarchical stuff.

  2. Why can't you just swap the orderId's? Assuming you have a unique identifier for both items, it should only require 2 update statements:

    Whoops. I wasn't paying attention. To move an item from position 92 to position 2, you'd need to do something like

    UPDATE Table SET orderId = orderId + 1 WHERE orderId >= 2

    UPDATE Table SET orderId = 2 WHERE orderId = 93

    UPDATE Table SET orderId = orderId - 1 WHERE orderId >= 94

    You could also just delete the item at position 93 and re-insert it at position 2.

  3. It's one update statement, but it's still a bunch of updates. Our abstraction doesn't hit the database at all - it's a user-level preference. The database shouldn't care about the order of these things, and with our abstraction, it doesn't need to.

  4. Why not use an ordering system similar to the Dewey Decimal System, where you can insert an entry into a non-integer index location? Then you can re-sort and normalize back up to integers when your app has spare cycles?

    I don't work with Databases much, and I'm sure this violates some well held concepts, but it seems like trying to renumber things when the user is waiting would be like standing at the fast food restaurant, waiting for the entire food inventory to be re-counted while you're trying to get your fries.

  5. Ross: yes, using some rating would work if I'd just want to get a list of ordered items from the database, but the real problem is, how can I get item #n from the database? I haven't found a solution in SQL yet (other than querying for the whole list each time and only reading item #n).

  6. There is a non-standard way supported by (at least AFAIK) MS SQL Server and Frontbase, where you can do

    SELECT TOP(n, m) * FROM * WHERE * ORDER BY *

    where n is the offset and m is the length of the slice. For example, to get the seventh smallest value, you'd do SELECT TOP (6, 1). To get the seventh largest value, you'd do the same thing but instead of doing just an ORDER BY you'd do an ORDER BY (col) DESC.


Trackback URI | Comments RSS

Leave a Reply to Erik J. Barzeski

Please abide by the comment policy. Valid HTML includes: <blockquote><p>, <em>, <strong>, <ul>, <ol>, and <a href>. Please use the "Quote Me" functionality to quote comments.