2 ms·

I thought the point of nosql was O(1) GET and UPDATE operations

batmansmk 3y ago
By GET, do you mean “get all fields of the unique item with id=x”? Oltp (sql), mongo or cassandra are working similarly for this and have the same complexity. Even worse, the same operation on the same storage can have very different performance profile independently of the cluster size, making o(n) complexity a very secondary discussion. All technologies offer more or less the same data structures and algorithms at such a basic level. You have to dig into replication, disk layout, transactionality, constraints, … to start to see differences.
emmanueloga_ 3y ago
I think you are thinking "hashmaps", not nosql. There are some ways of persisting hash maps to disk [1], but the workhorse of most ACID DBs (including popular nosql DBs like mongo) are B-Trees, which have O(log n) complexity for all operations. In any case when working with JSON columns in SQL it is useful to index the documents internal fields, which the OP doesn't talk about. Found a nice example in this blog post [2]. -- 1: https://en.wikipedia.org/wiki/Linear_hashing https://en.wikipedia.org/wiki/Linear_hashing 2: https://antonz.org/json-virtual-columns/ https://antonz.org/json-virtual-columns/
- tonymet 3y ago
  why use b trees if the keys are out of order?
  - emmanueloga_ 3y ago
    DBs default to B-Trees even for synthetic primary keys because range queries are almost always necessary, for instance, if you want to paginate records. Some DBs also include a hash map index in addition to B-Trees, for instance Postgres [1], but still use B-Trees for primary keys. Sqlite3 doesn't support Hash indexes. There's a very short chapter in "Modern B-Trees Techniques" [2] that compare B-Trees with Hash indexes: * Durability schemes are simple and robust for b-trees, not so for hash maps. * Ordering has advantages for concurrency control by means of key range locking. * "Very few database implementation teams find hash indexes among the opportunities or features with a high ratio of benefit and effort, in particular if B-tree indexes are required in any case in order to support range queries and ordered scans." -- 1: https://www.postgresql.org/docs/current/indexes-types.html#INDEXES-TYPES-HASH https://www.postgresql.org/docs/current/indexes-types.html#I... 2: https://w6113.github.io/files/papers/btreesurvey-graefe.pdf https://w6113.github.io/files/papers/btreesurvey-graefe.pdf
    - tonymet 3y ago
      very nice thanks
deleted 3y ago
[deleted]
chipdart 3y ago
> I thought the point of nosql was O(1) GET and UPDATE operations Tha was never the case. It would be silly to assume that given ultimately your GET and UPDATE operations are inter-process requests which involve serialization/deserializarion, and most of the time even require at least a network call.
- tonymet 3y ago
  network, encode/decode are still constant in terms of the dataset size. Still O(1). O(1) doesn't mean "instant" it means "does not grow with the dataset"

By GET, do you mean “get all fields of the unique item with id=x”? Oltp (sql), mongo or cassandra are working similarly for this and have the same complexity. Even worse, the same operation on the same storage can have very different performance profile independently of the cluster size, making o(n) complexity a very secondary discussion. All technologies offer more or less the same data structures and algorithms at such a basic level. You have to dig into replication, disk layout, transactionality, constraints, … to start to see differences.

emmanueloga_ 3y ago

I think you are thinking "hashmaps", not nosql. There are some ways of persisting hash maps to disk [1], but the workhorse of most ACID DBs (including popular nosql DBs like mongo) are B-Trees, which have O(log n) complexity for all operations. In any case when working with JSON columns in SQL it is useful to index the documents internal fields, which the OP doesn't talk about. Found a nice example in this blog post [2]. -- 1: https://en.wikipedia.org/wiki/Linear_hashing https://en.wikipedia.org/wiki/Linear_hashing 2: https://antonz.org/json-virtual-columns/ https://antonz.org/json-virtual-columns/

tonymet 3y ago
why use b trees if the keys are out of order?
- emmanueloga_ 3y ago
  DBs default to B-Trees even for synthetic primary keys because range queries are almost always necessary, for instance, if you want to paginate records. Some DBs also include a hash map index in addition to B-Trees, for instance Postgres [1], but still use B-Trees for primary keys. Sqlite3 doesn't support Hash indexes. There's a very short chapter in "Modern B-Trees Techniques" [2] that compare B-Trees with Hash indexes: * Durability schemes are simple and robust for b-trees, not so for hash maps. * Ordering has advantages for concurrency control by means of key range locking. * "Very few database implementation teams find hash indexes among the opportunities or features with a high ratio of benefit and effort, in particular if B-tree indexes are required in any case in order to support range queries and ordered scans." -- 1: https://www.postgresql.org/docs/current/indexes-types.html#INDEXES-TYPES-HASH https://www.postgresql.org/docs/current/indexes-types.html#I... 2: https://w6113.github.io/files/papers/btreesurvey-graefe.pdf https://w6113.github.io/files/papers/btreesurvey-graefe.pdf
  - tonymet 3y ago
    very nice thanks

deleted 3y ago

[deleted]

chipdart 3y ago

> I thought the point of nosql was O(1) GET and UPDATE operations Tha was never the case. It would be silly to assume that given ultimately your GET and UPDATE operations are inter-process requests which involve serialization/deserializarion, and most of the time even require at least a network call.

tonymet 3y ago
network, encode/decode are still constant in terms of the dataset size. Still O(1). O(1) doesn't mean "instant" it means "does not grow with the dataset"