I am currently working on a project for the iPhone that requires accessing a large amount of hierarchical data stored in a local sqlite database. One of the more common operations is calculating a rollup status field. Right now, I'm doing that by recursing through all the descendants of that item (which can be anywhere from 1 to n levels deep). However, this ends up requiring a LOT of sql calls. Each sqlite call on an iPhone takes around 250ms to complete, and in the end this adds up to around 7.7 seconds of processing time. Does anyone have any suggestions of doing something like this in less than O(n) time? I think the root of the problem is the sheer number of sql calls being made, so that's what I'm looking to reduce.
+2
A:
You need a different table organization. Have a look at this article or at Joe Celko's book.
Charlie Martin
2009-05-06 22:32:14
I agree that is one solution, although some of the more complex sql examples they gave on the MySQL page unfortunately don't work in sqlite.One idea reading about the nested sets gave me was to try to find all the leaf nodes (which is a very simple query) under a specific subtree (which seems to be a more complex query). Any ideas on how to accomplish that? That would remove all recursion and let me do the rollup calculation in memory instead of with more queries.
Marc W
2009-05-06 23:04:38
Okay, I believe I found my answer. The query was pretty simple.SELECT node.name FROM nested_category AS parent, nested_category AS node WHERE parent.category_id = 6 AND node.lft BETWEEN parent.lft+1 AND parent.rgtThanks for the pointer! Now I just have to figure out how to convert 885 rows of hierarchical data into this new nested format. But that's a different issue entirely.
Marc W
2009-05-06 23:26:31
Cool. I'm not normally a database guy, I'm glad I got one.
Charlie Martin
2009-05-06 23:47:19