4 added 1920 characters in body
source | link

I have an entity with millions of instances. Each instance has to reference an ordered list of items. The lists have to be unique so no list will be stored more than once. But once created, both lists and entity instances are immutable. There will be far more entity instances than lists, and the database has to support fast insertions of entities.

So what's an insert-efficient, robust, way of storing immutable, unique, ordered lists?

 

Edit: The list items are simple integers, and the typical length is about 5 items. Long lists of, say 10 or 20 items are very unlikely but possible.


Edit: So far, I've considered these approaches:

1)

lists table has these columns: <list_id> <order> <item> so if list #5 contains the elements [10,20,30] the table will contain:

5   1   10
5   2   20
5   3   30

The entity table will have a item_list_id column that references the lists table (it's not a foreign key since list_id is not a unique column in the lists table - The this can be solved by adding another table with a single column that which contains all valid list_ids ).

  • This solution makes inserts a bit tricky
  • It also places the responsibility for enforcing the uniqueness of lists on the application, which isn't great.

2)

lists table has these columns: <list_id> <item1> <item2> <item3> ... <itemN> so if list #5 contains the elements [10,20,30] the table will contain:

5   10   20   30

The entity table will have a item_list_id column that references the lists table.

  • This solution is less robust since list lengths are limited (although this isn't a huge problem for me since my lists are VERY unlikely to contain more than 10 or 20 elements)
  • This approach is quite horrible to query ("find all lists in which a particular item appears" has to specify each and every column), and a nightmare to map using an ORM.
  • Insertions of new entities is not too bad since my lists are typically 4-5 items long, so I can probably index the first few columns.
  • Enforcement of uniqueness is still in the hands of the application.

3)

Use solution #1, but replace the meaningless list_id with a hash (say SHA-1) on the list in serialized form.

  • This way uniqueness is more strictly enforced since lists will have unique hashes
  • Insertions are simpler and quicker(?)
  • The data integrity enforcement is still in the hands of the application.

I have an entity with millions of instances. Each instance has to reference an ordered list of items. The lists have to be unique so no list will be stored more than once. But once created, both lists and entity instances are immutable. There will be far more entity instances than lists, and the database has to support fast insertions of entities.

So what's an insert-efficient, robust, way of storing immutable, unique, ordered lists?

Edit: The list items are simple integers, and the typical length is about 5 items. Long lists of, say 10 or 20 items are very unlikely but possible.

I have an entity with millions of instances. Each instance has to reference an ordered list of items. The lists have to be unique so no list will be stored more than once. But once created, both lists and entity instances are immutable. There will be far more entity instances than lists, and the database has to support fast insertions of entities.

So what's an insert-efficient, robust, way of storing immutable, unique, ordered lists?

 

Edit: The list items are simple integers, and the typical length is about 5 items. Long lists of, say 10 or 20 items are very unlikely but possible.


Edit: So far, I've considered these approaches:

1)

lists table has these columns: <list_id> <order> <item> so if list #5 contains the elements [10,20,30] the table will contain:

5   1   10
5   2   20
5   3   30

The entity table will have a item_list_id column that references the lists table (it's not a foreign key since list_id is not a unique column in the lists table - The this can be solved by adding another table with a single column that which contains all valid list_ids ).

  • This solution makes inserts a bit tricky
  • It also places the responsibility for enforcing the uniqueness of lists on the application, which isn't great.

2)

lists table has these columns: <list_id> <item1> <item2> <item3> ... <itemN> so if list #5 contains the elements [10,20,30] the table will contain:

5   10   20   30

The entity table will have a item_list_id column that references the lists table.

  • This solution is less robust since list lengths are limited (although this isn't a huge problem for me since my lists are VERY unlikely to contain more than 10 or 20 elements)
  • This approach is quite horrible to query ("find all lists in which a particular item appears" has to specify each and every column), and a nightmare to map using an ORM.
  • Insertions of new entities is not too bad since my lists are typically 4-5 items long, so I can probably index the first few columns.
  • Enforcement of uniqueness is still in the hands of the application.

3)

Use solution #1, but replace the meaningless list_id with a hash (say SHA-1) on the list in serialized form.

  • This way uniqueness is more strictly enforced since lists will have unique hashes
  • Insertions are simpler and quicker(?)
  • The data integrity enforcement is still in the hands of the application.
    Tweeted twitter.com/#!/StackDBAs/status/532181033416785920
3 added 154 characters in body
source | link

I have an entity with millions of instances. Each instance has to reference an ordered list of items. The lists have to be unique so no list will be stored more than once. But once created, both lists and entity instances are immutable. There will be far more entity instances than lists, and the database has to support fast insertions of entities.

So what's an insert-efficient, robust, way of storing immutable, unique, ordered lists?

Edit: The list items are simple integers, and the typical length is about 5 items. Long lists of, say 10 or 20 items are very unlikely but possible.

I have an entity with millions of instances. Each instance has to reference an ordered list of items. The lists have to be unique so no list will be stored more than once. But once created, both lists and entity instances are immutable. There will be far more entity instances than lists, and the database has to support fast insertions of entities.

So what's an insert-efficient, robust, way of storing immutable, unique, ordered lists?

I have an entity with millions of instances. Each instance has to reference an ordered list of items. The lists have to be unique so no list will be stored more than once. But once created, both lists and entity instances are immutable. There will be far more entity instances than lists, and the database has to support fast insertions of entities.

So what's an insert-efficient, robust, way of storing immutable, unique, ordered lists?

Edit: The list items are simple integers, and the typical length is about 5 items. Long lists of, say 10 or 20 items are very unlikely but possible.

2 deleted 16 characters in body
source | link

How to store immutable, unique, ordered, lists?

In my use case, I have an entity with millions of instances. Each instance has to reference an ordered list of items. The lists have to be unique so no list will be stored more than once. But once created, both lists and entity instances are immutable. There will be far more entity instances than lists, and the database has to support fast insertions of entities.

So what's an insert-efficient, robust, way of storing immutable, unique, ordered lists?

How to store immutable unique ordered lists?

In my use case, I have an entity with millions of instances. Each instance has to reference an ordered list of items. The lists have to be unique so no list will be stored more than once. But once created, both lists and entity instances are immutable. There will be far more entity instances than lists, and the database has to support fast insertions of entities.

So what's an insert-efficient, robust, way of storing immutable, unique, ordered lists?

How to store immutable, unique, ordered, lists?

I have an entity with millions of instances. Each instance has to reference an ordered list of items. The lists have to be unique so no list will be stored more than once. But once created, both lists and entity instances are immutable. There will be far more entity instances than lists, and the database has to support fast insertions of entities.

So what's an insert-efficient, robust, way of storing immutable, unique, ordered lists?

1
source | link