3

In a SQL database, the only way to represent an arbitrarily ordered set is to give every record an "Order" and every time you update or move an item around in this ordering you have to update or somehow maintain the entire list of ranks with a nightly job or something like that.

For example, I can represent the ordered set [C, B, D, A] in this way in a SQL database:

ID  Name   Order
1   A      4
2   B      2
3   C      1
4   D      3

If I want to move an item to a different position in the set, or prepend a new item, I may have to update a lot of items. In general there is a lot of maintenance overhead with this approach.

Querying the data once it is in the database is not an issue for SQL, the issue is the significant maintenance overhead of reordering the set. There is no simple operation in SQL to move an item to a new position in the set. The ordering is arbitrary and user-defined.

I realize that this can be accomplished using SQL, it's just very clunky to perform certain operations like prepending items, or moving an item to a new position. Even this example operation of reversing the order of the set requires a pretty lengthy, complex, query. The type of database I'm looking for might support such an operation natively, or at least more elegantly.

So, if I am designing an application (like Trello, for example) that very heavily involves ordered sets, it seems SQL is not the ideal database technology for me. Are there any databases whose syntax support ordered sets in a more natural way?

These are some CQL3 queries from the Cassandra documentation that seem close to what I'm looking for. This prepends an item to an ordered set.

UPDATE users SET top_places = [ 'the shire' ] + top_places WHERE user_id = 'frodo';

This one will set the value of the item at position 2 in the set. I suspect I could use this to easily perform arbitrary swaps/reorders.

UPDATE users SET top_places[2] = 'riddermark' WHERE user_id = 'frodo';

Unfortunately the documentation also states

And while we may (or may not) relax that rule a bit in the future, this still means that collections are not meant to be excessively large. They are not a replacement for a proper modelisation into tables.

which seems to suggest that ordered sets are not (yet) first class citizens in CQL3.

  • 2
    How large are these lists likely to be? You could quite easily simulate a linked list in SQL by storing the ids of next and previous records though you would need a recursive query to traverse the list. – Martin Smith Apr 20 '17 at 21:46
  • 2
    Leave gaps in your order number sequence. Instead of 1,2,3,4... use 1000, 2000, 3000, 4000... Then inserting a new item between two others is easy, split the difference, so for example 3500. Then 3750 between that, etc. Periodically (monthly, annually.) straighten it out to be 1000, 2000, ... – Jonathan Fite Apr 26 '17 at 16:30
  • 5
    The question seems to require that the APIs for what you want to do are already built-in to the querying language of the database platform. Does that really matter to you? As as long as someone can provide easy-to-use APIs that perform well enough does it really matter if there is "clunky" code under the hood? IMO asking for good ways to model this is a more actionable question then declaring that SQL databases aren't fit for the task and asking what else is out there. – Joe Obbish Apr 26 '17 at 19:45
  • 2
    Martin's suggestion about a linked list seems reasonable (and recursive queries are quite efficient nowadays, though I wouldn't want to do that on a multi-million row table). What about a graph database? That is essentially a linked list as well and should perform quite well. If you also need relational features, maybe a Hybrid like Agens Graph would be an alternative – a_horse_with_no_name Apr 27 '17 at 6:48
  • 3
    I don't see how it would be really different with an order column in SQL or a collection in Cassandra. Adding an element to position 3, for example, means that you either move all preceding elements backwards, or the rest forward. The clunkyness won't be any worse - what's more, to me it appears that SQL can do it more easily (UPDATE t SET order = order + 1 WHERE order > 3) than CQL (without rewriting the whole collection, leaving tombstones and thus affecting performance). All this, of course, if you don't opt for linked lists. – dezso May 7 '17 at 11:28
2

Most of the major relational DBMSs support structured types in the form of XML or JSON. These are order-preserving. Typically the corresponding programming language (T-SQL, PL/SQL) will have built-in features to manipulate these types much as SQL manipulates columns and rows.

Some relational stores also support ARRAY data types (one example). An item will retain its before and after relationship to those items adjacent to it irrespective of what happens in other parts of the array. Unlike, say, JSON the array itself cannot contain complex types so holding an array of surrogate IDs and pulling the remaining data on demand may be necessary.

If you choose to adopt structured types why not go the whole hog and use a DBMS designed around them. This is the realm of NoSQL. There are any number of products, each with advantages and drawbacks.

Finally I'd mention graph stores. Their schtick is to focus on the connectedness of items. This is appropriate for ordered lists as the defining characteristic is how one item follows another. So the items could be modelled as graph nodes with edges, specifically "follows" edges, linking nodes in the desired sequence.

Having worked with each of these to a greater or lesser extent it is my opinion that none of them is significantly less work in application programming terms, including the straight-up SQL approach which you dislike.

  • 1
    As a side note: an array in Postgres can contain complex types: create type typ1 as (col1 integer, col2 text); create table t1 (id integer, c1 typ1[]) – a_horse_with_no_name Sep 24 '17 at 11:56
2

I think you are missing one of the key principles of relational database design. I thought it was Dr E F Codd but I can't find a reference.

Data is stored without sorting, and is sorted when it is retrieved. This was intended to avoid the overhead of re-ordering the data with every update or insert.

Sorting is done with the order by clause when you select data.

The fact that some vendors store the data ordered by a clustered index is a bit misleading. If your data must be sorted you should always use order by rather than rely upon the the underlying storage.

As you must have some criteria for sorting, why not incorporate that in your query so that data is ordered as it is queried every time you select it.

1

It seems likely to me that these ordered sets are not arbitrarily ordered, but ordered on some characteristic, i.e., time, date, size, etc.

If you have a field for each of these characteristics, you just look at the set of data using the index of the characteristic field.

I hope I'm not missing something, but I didn't see anything in your question to indicate this 'standard approach' isn't what you need.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.