I just recently wrapped up using a similar "store serialized data" set-up myself. In my example, I'm allowing the user insert/remove/reorder items on a list. This type of operation is pain to do with SQL operations. If you have a list, A,B,C,D,E,F and you want to insert G before C, then you either have to:
delete all, then insert A,B,G,C,D,E,F.
set "sortnumber" on G to "3", and increment sortnumber on all >= 3.
set "sortnumber" of G to be the average of B and C.
The latter is the cleverest, but eventually you run out of space in floating-point land, unless you have a Cron come in and clean everything up periodically. And of course, reordering (the example was an insert), and removing need to be considered as well. So it's a choice between lots of deletes and inserts (but really easy). Semi-annoying logic of reordering/removing and a few updates. Or clever hack that requires a cron to cover your ass.
What I did instead was stored the list as JSON, convert it to an array, and use array splicing functions to reorder things. Then, I convert it back to JSON and store it. It's worked extraordinarily well... It takes a fraction of the amount of time to do native data structure stuff than it does to touch the DB several times.
> It takes a fraction of the amount of time to do native data structure stuff than it does to touch the DB several times.
And app processes are much easier to scale than a database. Even in "slow" languages (Ruby in my case) array operations are extremely fast, definitely "fast enough".
While your approach to do this in JSON is cool, I think you have overlooked the 'direct' solution to do this in a RDBMS - with a linked list. Here is a quick suggestion (works in Postgres):
create table l (
id char primary key references l(prev) deferrable initially deferred,
prev char unique not null references l(id) deferrable initially deferred,
mydata text not null
);
then I populate the table with your example items:
test=# select * from l;
select * from l;
id | prev | mydata
----+------+--------
A | F | dA
B | A | dB
C | B | dC
D | C | dD
E | D | dE
F | E | dF
(6 rows)
to insert a new item into the list, you would do:
begin;
update l set prev='G' where prev='C';
insert into l (id, prev, mydata) values ('G', 'C', 'data for G');
commit;
so that's one update, one insert for an insertion into the list. Note that the two commands have to be in one transaction, because inside the transaction the foreign key constraint is violated (as allowed by the deferrable initially deferred modifier).
Let's inspect our list again:
test=# select * from l;
select * from l;
id | prev | mydata
----+------+------------
A | F | dA
B | A | dB
C | B | dC
E | D | dE
F | E | dF
D | G | dD
G | C | data for G
so the predecessor of G is C, and the predecessor of D is G, like specified.
Of course, you loose the ability to sort with 'order by', but that's no big deal: you know the predecessor and successor of each item, so it's easy to traverse the list in either order. This could be done on the client side [probably the best solution in your case], in the application code, or inside the database with a stored procedure or with a recursive query (coming in PostgreSQL 8.4), in Oracle it could probably be done with 'connect by'.
In reality, you would of course choose other datatypes for id and prev (probably integer), but I wanted to translate your example as literally as possible. Another problem that's easily solved: how do I get all elements of one list? Solution: Either give me one 'starting element' and the list is traversed and returned. Or introduce a listId attribute and select by that, which is probably faster but without sort order.
Aha! I did forget the linked list approach. So essentially, each item on the list stores what is before (or) after it. I'm assuming it's an arbitrary choice that you're using "prev" instead of "next," correct?
The use of deferred, I've never heard of, but it makes perfect sense in this case. Unless, of course, you want to insert the record first and then modify the update to exclude the item you just inserted.
Right now, I'm using MySQL.. I only have 4 tables, and product is not launched. Would you advise switching to Postgres?
> I'm assuming it's an arbitrary choice that you're using "prev" instead of "next," correct?
yes, in effect it's a doubly linked list (circularly doubly linked), so you could remember the id of the first element of the list and then traverse in any order as long as this id does not reappear.
> Unless, of course, you want to insert the record first and then modify the update to exclude the item you just inserted.
yes - in this case you would get a violation of the unique constraint:
begin;
insert into l (id, prev, mydata) values ('G', 'C', 'data for G');
update l set prev='G' where prev='C';
commit;
this would violate the unique constraint for prev, because after the insert (but before the update!), both the new element and the element not yet updated have prev set to 'C' - the transaction will then be rolled back.
In standard SQL this would be possible because it allows to declare unique constraints (and I think other constraints, such as check clauses) as deferrable, too - PostgreSQL doesn't implement this, it allows deferrable only for foreign key constraints. But usually it's no problem to order the commands in a way that only foreign key constraints get violated during a transaction.
> Right now, I'm using MySQL.. I only have 4 tables,
and product is not launched. Would you advise
switching to Postgres?
as an entrepreneur, you should probably do what's best for your customers - and they will likely not care which RDBMS you use:-)
Perhaps you could play around a little bit with PostgreSQL on the side and (perhaps) make the switch once you are comfortable with it. And keep your JSON-based lists - if the system works, why bother with a rewrite / schema change (for now?).
Considering momentum, I think PostgreSQL is gaining steam while MySQL is losing momentum (some key developers left after the aquisition by Sun) - of course, that's my subjective impression.
The data I'm having the user order is not only order-specific, but is recursive. That is, one of the items on the list, rather than be a letter like "B" can be a list in and of itself. It's basically like "files and folders"
A major problem isn't only the UI, which took me days to make (drag and drop for files/folders ... anybody seen anything like this done before in HTML+JS?), but mostly is in the updating/validation. I receive information, like "moved item: /path/to/item to before /some/other/path" and I now need to make sure this is a valid action (eg: can't put a folder into one of its own subfolders, can't put a file in a file, etc), and also update the database to reflect this.
I chose to use JSON to encode objects in the DB, then decode them into an array, and do some easy/fast array stuff to perform the action they requested. Just judging on the array code, which does several "isset()" calls and splices, I'd imagine doing this with a DB would be a major heartache... but I have no doubt you'd be able to come up with some brilliant way to do it.
yeah, of course! And if it works, then, by definition, it's good for your customers and thus for you! Also, your approach is probably more flexible (no fixed schema for the recursive list structure), which makes it easier and faster for you to iterate and react to customer feedback.
If at some time you want to have a more fixed structure or let the database do some of the server-side validation work of your tree-like structure, here is a good writeup by Phil Greenspun showing how to model and query tree-like datastructures with an RDBMS:
http://philip.greenspun.com/sql/trees.html
(the rest of the document 'SQL for Web Nerds' is also quite good stuff:
http://philip.greenspun.com/sql
)
he uses 'connect by', which is a non-standard Oracle extension, the same thing can be achieved with 'with recursive'-queries, which is standard SQL (1999) and part of PostgreSQL 8.4
Also, Joe Celko's Book 'SQL for Smarties' has a good chapter covering hierarchical data structures in SQL (he also has a separate book about 'trees and hierarchies' in SQL).
Oh, and good luck and much success with your startup!
Comments
I just recently wrapped up using a similar "store serialized data" set-up myself. In my example, I'm allowing the user insert/remove/reorder items on a list. This type of operation is pain to do with SQL operations. If you have a list, A,B,C,D,E,F and you want to insert G before C, then you either have to:
The latter is the cleverest, but eventually you run out of space in floating-point land, unless you have a Cron come in and clean everything up periodically. And of course, reordering (the example was an insert), and removing need to be considered as well. So it's a choice between lots of deletes and inserts (but really easy). Semi-annoying logic of reordering/removing and a few updates. Or clever hack that requires a cron to cover your ass.What I did instead was stored the list as JSON, convert it to an array, and use array splicing functions to reorder things. Then, I convert it back to JSON and store it. It's worked extraordinarily well... It takes a fraction of the amount of time to do native data structure stuff than it does to touch the DB several times.
> It takes a fraction of the amount of time to do native data structure stuff than it does to touch the DB several times.
And app processes are much easier to scale than a database. Even in "slow" languages (Ruby in my case) array operations are extremely fast, definitely "fast enough".
While your approach to do this in JSON is cool, I think you have overlooked the 'direct' solution to do this in a RDBMS - with a linked list. Here is a quick suggestion (works in Postgres):
then I populate the table with your example items: let's see how that looks like: to insert a new item into the list, you would do: so that's one update, one insert for an insertion into the list. Note that the two commands have to be in one transaction, because inside the transaction the foreign key constraint is violated (as allowed by the deferrable initially deferred modifier).Let's inspect our list again:
so the predecessor of G is C, and the predecessor of D is G, like specified.Of course, you loose the ability to sort with 'order by', but that's no big deal: you know the predecessor and successor of each item, so it's easy to traverse the list in either order. This could be done on the client side [probably the best solution in your case], in the application code, or inside the database with a stored procedure or with a recursive query (coming in PostgreSQL 8.4), in Oracle it could probably be done with 'connect by'.
In reality, you would of course choose other datatypes for id and prev (probably integer), but I wanted to translate your example as literally as possible. Another problem that's easily solved: how do I get all elements of one list? Solution: Either give me one 'starting element' and the list is traversed and returned. Or introduce a listId attribute and select by that, which is probably faster but without sort order.
Aha! I did forget the linked list approach. So essentially, each item on the list stores what is before (or) after it. I'm assuming it's an arbitrary choice that you're using "prev" instead of "next," correct?
The use of deferred, I've never heard of, but it makes perfect sense in this case. Unless, of course, you want to insert the record first and then modify the update to exclude the item you just inserted.
Right now, I'm using MySQL.. I only have 4 tables, and product is not launched. Would you advise switching to Postgres?
> I'm assuming it's an arbitrary choice that you're using "prev" instead of "next," correct?
yes, in effect it's a doubly linked list (circularly doubly linked), so you could remember the id of the first element of the list and then traverse in any order as long as this id does not reappear.
> Unless, of course, you want to insert the record first and then modify the update to exclude the item you just inserted.
yes - in this case you would get a violation of the unique constraint:
this would violate the unique constraint for prev, because after the insert (but before the update!), both the new element and the element not yet updated have prev set to 'C' - the transaction will then be rolled back.In standard SQL this would be possible because it allows to declare unique constraints (and I think other constraints, such as check clauses) as deferrable, too - PostgreSQL doesn't implement this, it allows deferrable only for foreign key constraints. But usually it's no problem to order the commands in a way that only foreign key constraints get violated during a transaction.
> Right now, I'm using MySQL.. I only have 4 tables, and product is not launched. Would you advise switching to Postgres?
as an entrepreneur, you should probably do what's best for your customers - and they will likely not care which RDBMS you use:-) Perhaps you could play around a little bit with PostgreSQL on the side and (perhaps) make the switch once you are comfortable with it. And keep your JSON-based lists - if the system works, why bother with a rewrite / schema change (for now?).
Considering momentum, I think PostgreSQL is gaining steam while MySQL is losing momentum (some key developers left after the aquisition by Sun) - of course, that's my subjective impression.
Technically, of course I think that PostgreSQL is better - here is a good comparison: http://www.wikivs.com/wiki/MySQL_vs_PostgreSQL for amusement, read the discussion here: http://www.reddit.com/r/programming/comments/764fp/mysql_vs_...
There's one more thing I forgot to mention...
The data I'm having the user order is not only order-specific, but is recursive. That is, one of the items on the list, rather than be a letter like "B" can be a list in and of itself. It's basically like "files and folders"
A major problem isn't only the UI, which took me days to make (drag and drop for files/folders ... anybody seen anything like this done before in HTML+JS?), but mostly is in the updating/validation. I receive information, like "moved item: /path/to/item to before /some/other/path" and I now need to make sure this is a valid action (eg: can't put a folder into one of its own subfolders, can't put a file in a file, etc), and also update the database to reflect this.
I chose to use JSON to encode objects in the DB, then decode them into an array, and do some easy/fast array stuff to perform the action they requested. Just judging on the array code, which does several "isset()" calls and splices, I'd imagine doing this with a DB would be a major heartache... but I have no doubt you'd be able to come up with some brilliant way to do it.
To each their own :)
> To each their own :)
yeah, of course! And if it works, then, by definition, it's good for your customers and thus for you! Also, your approach is probably more flexible (no fixed schema for the recursive list structure), which makes it easier and faster for you to iterate and react to customer feedback.
If at some time you want to have a more fixed structure or let the database do some of the server-side validation work of your tree-like structure, here is a good writeup by Phil Greenspun showing how to model and query tree-like datastructures with an RDBMS: http://philip.greenspun.com/sql/trees.html (the rest of the document 'SQL for Web Nerds' is also quite good stuff: http://philip.greenspun.com/sql )
he uses 'connect by', which is a non-standard Oracle extension, the same thing can be achieved with 'with recursive'-queries, which is standard SQL (1999) and part of PostgreSQL 8.4 Also, Joe Celko's Book 'SQL for Smarties' has a good chapter covering hierarchical data structures in SQL (he also has a separate book about 'trees and hierarchies' in SQL).
Oh, and good luck and much success with your startup!
A tree widget with DD? http://extjs.com/deploy/dev/examples/tree/reorder.html
I bet there are lots of others too. This doesn't sound like something you'd ever want to write yourself (unless the widget IS your project).