10 ms·

> Why do you need the time component anyway? To sort or filter the records by time. Sure, you can just add an extra column if you need this, but there are case

> Why do you need the time component anyway? To sort or filter the records by time. Sure, you can just add an extra column if you need this, but there are cases when this is not convenient to do. E.g. when you want to be able to export the records info files, naming the files with the IDs and still be able to sort them.

danbruc 3y ago
More importantly if you have an index on purely random IDs, then each insert will go to some random position into the tree whereas having IDs that increase with time will make all new IDs end up at the end of the tree which reduces index fragmentation.
- EGreg 3y ago
  Or, you could use a graph database and stop having frustrating relational impedance mismatch, nonlocality etc. You can have O(1) lookups instead of O(log N) for almost everything
  - victor106 3y ago
    That sounds too good to be true. Is that really true of all grapdb’s? Also, if that’s really true why can’t everyone just use graphdb’s?
    - EGreg 3y ago
      Because of vendor lock-in with the LAMP stack over the years. Every host used MySQL, how many had Neo4j as available?
  - e12e 3y ago
    How big is the 1 though?
    - EGreg 3y ago
      Look, if you have N items related to X, at insert time, you store them in an array and have X point to that array, instead of foreign keys. For example, when a user has 7 articles. Do you want to just point to where the articles are stored? Or do you want to do O(log n) lookup for each article? And if you have many-to-many, do you want to join an Intermediate Table for even more processing, or just follow a pointer to a range of an intermediate node directly and traverse?
      - ndriscoll 3y ago
        How is that different from a clustered index?
        EGreg 3y ago
        A clustered index requires O(log N) lookups, since it's still an index. I'm talking about pointing directly to the location of an array where things are stored. That array isn't a clustered index. Each array is different.
        ndriscoll 3y ago
        What about when you delete rows? Do you just leave the space unused now? Or if you update a row to be larger? Rewrite the whole array (so possibly O(n) updates)? How do you deal with data that gets accessed in different orders based on relationships from multiple other entities? Duplicate the data? If so, updates now get amplified and you can fit less data in RAM so you're more likely to require disk IO. If not, you need a layer of indirection (so you have an array of pointers instead of an array of data). Even with a layer of indirection, updates that grow a row and require a reallocation will cause you to have to go update all pointers (also, those pointers need to be indexed to find who you need to update). To avoid write amplification, you can use an array of ids instead of an array of pointers. Now you want an id <-> pointer lookup, which could be done with a hash map in O(1), or with a tree in O(logN) if you want to also allow efficient range queries. I'm not exactly sure on the implementation details, but for ballpark numbers, for an 8 kB page size with 80% fill factor and 16 B entries (8 B key + 8 B pointer), with 10E9 rows, log(N) ought to be ~4 (page IOs). Not ideal, but the point is for a lot of real-world engineering, O(logN) is effectively O(1) (with a small enough constant factor that it's fine for general use). So if your data is not write-once, trees are a well-rounded default data structure.
  - danbruc 3y ago
    That will depend on which graph database you use as a graph database might just store the graph in an underlying relational database. And it will also depend on what kind of data you have and what kind of queries you want to perform. For a graph database it might be faster to navigate along links in the graph but I would guess you will have to pay a big performance penalty if you have to operate orthogonally to your links, like aggregate across all instances of some entity.
  - coding123 3y ago
    Graph databases don't solve that. All databases, document, graph, rel ALL implement indexes to find specific things in the exactly the same way. Very well known tree, hash and other techniques. The representation (outside of indexing) has properties that make your USE CASE better or worse. EGreg would not be someone to hire to architect a solution. He'll just put your 1Trillion row per month use-case in a graph DB like Neo4J and you'll just watch it fall over when you run billing.
- sgarland 3y ago
  Page splits… page splits everywhere.
- lazide 3y ago
  depending on scale and architecture, either behavior can be better. it’s easier to shard when writes occur randomly over the overall space. it’s easier to coalesce when writes all happen in a given place (head or tail)
  - remram 3y ago
    If that is the case then why shouldn't the storage system hash the IDs itself, to spread them as it requires?
    - lazide 3y ago
      Because sometimes you want some data to be collocated, while the rest sharded. For instance, you might use a random object ID as a prefix value in the index, followed by attribute ID which isn’t. Or a modified time, so you can have a history of values which can be read out linearly. If using it directly, that means Objects and their data are sharded randomly across, but when looking for an objects attributes (or attribute by time), their index entries are always co-located and you can read them out linearly with good performance. If blindly hashing keys to distribute them, you can’t do that. Also, you can’t really do a linear read at all, since no data will be ‘associatable’ with others, as the index value is randomized, and what is stored in the index has no related to the key provided by the user. You can only do a straight get, not a read. That is very limiting, and expensive with large data sets as most algorithms benefit greatly from having ordered data. (Well, you could do a read, but you’d get back entries in completely random order) Needless to say, this is ‘advanced’ usage and requires pretty deep understanding of your data and indexing/write/read patterns, which is why random hashing is the most common hash map behavior.
      - remram 3y ago
        Sounds like it should be an attribute of the index and not require a change in the data. To me, anyway. CREATE INDEX ... USING HASH;
        lazide 3y ago
- deleted 3y ago
  [deleted]
willis936 3y ago
One benefit of keeping it separate is that you can choose the precision of the timestamp necessary. "Millisecond precision" is arbitrary and commonly insufficient.
- preseinger 3y ago
  it's commonly totally sufficient for IDs to represent a rough sort order millisecond precision is great for a lot of use cases
  - willis936 3y ago
    I didn't say that it wasn't. Hell even ms is too precise for many use cases (usually where date is used instead). What I said was that it's useful to be able to select timestamp precision independently of UUID implementation. One size that fits all fits none best.
    - dtech 3y ago
      Lucky for you, they also define UUIDv8 as a free-for-all where you can do whatever you want, and nanosecond precision is one of the examples given in the RFC.
eru 3y ago
> E.g. when you want to be able to export the records info files, naming the files with the IDs and still be able to sort them. You could name them by (time, id)?

danbruc 3y ago

More importantly if you have an index on purely random IDs, then each insert will go to some random position into the tree whereas having IDs that increase with time will make all new IDs end up at the end of the tree which reduces index fragmentation.

EGreg 3y ago
Or, you could use a graph database and stop having frustrating relational impedance mismatch, nonlocality etc. You can have O(1) lookups instead of O(log N) for almost everything
- victor106 3y ago
  That sounds too good to be true. Is that really true of all grapdb’s? Also, if that’s really true why can’t everyone just use graphdb’s?
  - EGreg 3y ago
    Because of vendor lock-in with the LAMP stack over the years. Every host used MySQL, how many had Neo4j as available?
- e12e 3y ago
  How big is the 1 though?
  - EGreg 3y ago
    Look, if you have N items related to X, at insert time, you store them in an array and have X point to that array, instead of foreign keys. For example, when a user has 7 articles. Do you want to just point to where the articles are stored? Or do you want to do O(log n) lookup for each article? And if you have many-to-many, do you want to join an Intermediate Table for even more processing, or just follow a pointer to a range of an intermediate node directly and traverse?
    - ndriscoll 3y ago
      How is that different from a clustered index?
      - EGreg 3y ago
        A clustered index requires O(log N) lookups, since it's still an index. I'm talking about pointing directly to the location of an array where things are stored. That array isn't a clustered index. Each array is different.
        ndriscoll 3y ago
        What about when you delete rows? Do you just leave the space unused now? Or if you update a row to be larger? Rewrite the whole array (so possibly O(n) updates)? How do you deal with data that gets accessed in different orders based on relationships from multiple other entities? Duplicate the data? If so, updates now get amplified and you can fit less data in RAM so you're more likely to require disk IO. If not, you need a layer of indirection (so you have an array of pointers instead of an array of data). Even with a layer of indirection, updates that grow a row and require a reallocation will cause you to have to go update all pointers (also, those pointers need to be indexed to find who you need to update). To avoid write amplification, you can use an array of ids instead of an array of pointers. Now you want an id <-> pointer lookup, which could be done with a hash map in O(1), or with a tree in O(logN) if you want to also allow efficient range queries. I'm not exactly sure on the implementation details, but for ballpark numbers, for an 8 kB page size with 80% fill factor and 16 B entries (8 B key + 8 B pointer), with 10E9 rows, log(N) ought to be ~4 (page IOs). Not ideal, but the point is for a lot of real-world engineering, O(logN) is effectively O(1) (with a small enough constant factor that it's fine for general use). So if your data is not write-once, trees are a well-rounded default data structure.
- danbruc 3y ago
  That will depend on which graph database you use as a graph database might just store the graph in an underlying relational database. And it will also depend on what kind of data you have and what kind of queries you want to perform. For a graph database it might be faster to navigate along links in the graph but I would guess you will have to pay a big performance penalty if you have to operate orthogonally to your links, like aggregate across all instances of some entity.
- coding123 3y ago
  Graph databases don't solve that. All databases, document, graph, rel ALL implement indexes to find specific things in the exactly the same way. Very well known tree, hash and other techniques. The representation (outside of indexing) has properties that make your USE CASE better or worse. EGreg would not be someone to hire to architect a solution. He'll just put your 1Trillion row per month use-case in a graph DB like Neo4J and you'll just watch it fall over when you run billing.
sgarland 3y ago
Page splits… page splits everywhere.
lazide 3y ago
depending on scale and architecture, either behavior can be better. it’s easier to shard when writes occur randomly over the overall space. it’s easier to coalesce when writes all happen in a given place (head or tail)
- remram 3y ago
  If that is the case then why shouldn't the storage system hash the IDs itself, to spread them as it requires?
  - lazide 3y ago
    Because sometimes you want some data to be collocated, while the rest sharded. For instance, you might use a random object ID as a prefix value in the index, followed by attribute ID which isn’t. Or a modified time, so you can have a history of values which can be read out linearly. If using it directly, that means Objects and their data are sharded randomly across, but when looking for an objects attributes (or attribute by time), their index entries are always co-located and you can read them out linearly with good performance. If blindly hashing keys to distribute them, you can’t do that. Also, you can’t really do a linear read at all, since no data will be ‘associatable’ with others, as the index value is randomized, and what is stored in the index has no related to the key provided by the user. You can only do a straight get, not a read. That is very limiting, and expensive with large data sets as most algorithms benefit greatly from having ordered data. (Well, you could do a read, but you’d get back entries in completely random order) Needless to say, this is ‘advanced’ usage and requires pretty deep understanding of your data and indexing/write/read patterns, which is why random hashing is the most common hash map behavior.
    - remram 3y ago
      Sounds like it should be an attribute of the index and not require a change in the data. To me, anyway. CREATE INDEX ... USING HASH;
      - lazide 3y ago
deleted 3y ago
[deleted]

willis936 3y ago

One benefit of keeping it separate is that you can choose the precision of the timestamp necessary. "Millisecond precision" is arbitrary and commonly insufficient.

preseinger 3y ago
it's commonly totally sufficient for IDs to represent a rough sort order millisecond precision is great for a lot of use cases
- willis936 3y ago
  I didn't say that it wasn't. Hell even ms is too precise for many use cases (usually where date is used instead). What I said was that it's useful to be able to select timestamp precision independently of UUID implementation. One size that fits all fits none best.
  - dtech 3y ago
    Lucky for you, they also define UUIDv8 as a free-for-all where you can do whatever you want, and nanosecond precision is one of the examples given in the RFC.

eru 3y ago

> E.g. when you want to be able to export the records info files, naming the files with the IDs and still be able to sort them. You could name them by (time, id)?