{"action":"created","issue":{"url":"https://api.github.com/repos/rethinkdb/rethinkdb/issues/4397","labels_url":"https://api.github.com/repos/rethinkdb/rethinkdb/issues/4397/labels{/name}","comments_url":"https://api.github.com/repos/rethinkdb/rethinkdb/issues/4397/comments","events_url":"https://api.github.com/repos/rethinkdb/rethinkdb/issues/4397/events","html_url":"https://github.com/rethinkdb/rethinkdb/issues/4397","id":88414833,"number":4397,"title":"Key compression","user":{"login":"indiedotkim","id":189316,"avatar_url":"https://avatars.githubusercontent.com/u/189316?v=3","gravatar_id":"","url":"https://api.github.com/users/indiedotkim","html_url":"https://github.com/indiedotkim","followers_url":"https://api.github.com/users/indiedotkim/followers","following_url":"https://api.github.com/users/indiedotkim/following{/other_user}","gists_url":"https://api.github.com/users/indiedotkim/gists{/gist_id}","starred_url":"https://api.github.com/users/indiedotkim/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/indiedotkim/subscriptions","organizations_url":"https://api.github.com/users/indiedotkim/orgs","repos_url":"https://api.github.com/users/indiedotkim/repos","events_url":"https://api.github.com/users/indiedotkim/events{/privacy}","received_events_url":"https://api.github.com/users/indiedotkim/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/rethinkdb/rethinkdb/labels/tp:enhancement","name":"tp:enhancement","color":"02e10c"}],"state":"open","locked":false,"assignee":null,"milestone":{"url":"https://api.github.com/repos/rethinkdb/rethinkdb/milestones/41","html_url":"https://github.com/rethinkdb/rethinkdb/milestones/subsequent","labels_url":"https://api.github.com/repos/rethinkdb/rethinkdb/milestones/41/labels","id":367201,"number":41,"title":"subsequent","description":"","creator":{"login":"coffeemug","id":48436,"avatar_url":"https://avatars.githubusercontent.com/u/48436?v=3","gravatar_id":"","url":"https://api.github.com/users/coffeemug","html_url":"https://github.com/coffeemug","followers_url":"https://api.github.com/users/coffeemug/followers","following_url":"https://api.github.com/users/coffeemug/following{/other_user}","gists_url":"https://api.github.com/users/coffeemug/gists{/gist_id}","starred_url":"https://api.github.com/users/coffeemug/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/coffeemug/subscriptions","organizations_url":"https://api.github.com/users/coffeemug/orgs","repos_url":"https://api.github.com/users/coffeemug/repos","events_url":"https://api.github.com/users/coffeemug/events{/privacy}","received_events_url":"https://api.github.com/users/coffeemug/received_events","type":"User","site_admin":false},"open_issues":338,"closed_issues":0,"state":"open","created_at":"2013-06-30T07:32:52Z","updated_at":"2015-06-16T23:34:14Z","due_on":null,"closed_at":null},"comments":6,"created_at":"2015-06-15T12:43:10Z","updated_at":"2015-06-16T23:35:07Z","closed_at":null,"body":"Hi!\r\n\r\nThis is a write-up of a mailing list discussion around key compression. It is (or maybe not) a simpler approach to full document compression as talked about in https://github.com/rethinkdb/rethinkdb/issues/1396.\r\n\r\nMy use-case involves data with a lot of acronyms as keys. For example, '\"AC\" : 6'. I would like to spell out these acronyms, but that would increase the data size considerably. In this specific use-case, key compression could come to rescue!\r\n\r\nStackOverflow has a related discussion about [key compression in MongoDB](http://stackoverflow.com/questions/11429804/why-are-key-names-stored-in-the-document-in-mongoddb). The gist of the discussion is: it can be done on an application level and full-document compression might be better. I think that application level compression is a burden, because it assumes that only one application is accessing the data, and, full-document compression does actually have an impact on performance since the compression/decompression of documents will take up processing time.\r\n\r\n@mlucy replied to my email with the following, which addresses the inherent schemaless structure of data in RethinkDB and the problem that keys can be created arbitrarily:\r\n\r\n> So, the general problem with key compression is that tables in RethinkDB don't have a fixed schema.  Theoretically the set of keys we need to compress might change over time, but even if that isn't the case we don't know what keys we need to compress when the table is first created, so we'd have to compute the key to compressed key mapping as people insert rows and store it somewhere so that things can be translated out again later.  We'd also need some logic to handle the case where people use an enormous number of keys (some people generate keys based on user input) and the case where people's schema changes as they rewrite their app, both of which might cause the number of keys in our map to grow too large to comfortably keep in memory, in which case we'd need a way to keep parts of it on disk or else we'd need to rewrite rows that have rarely-used keys to not use the compressed version of that key so that we can garbage-collect that key from the map.\r\n\r\n> We could theoretically allow users to provide a schema hint so we know what keys to compress when the table is first created,though; that might be the way to do it.\r\n\r\nI replied with a simple solution, which I thought would work, if the maximum number of keys is limited. This is not completely true -- see @mlucy's reply below -- but the core argument that I brought forward was:\r\n\r\n>  In order to avoid dealing with heuristics — since you do not want to recompute & rewrite your mappings when new documents are inserted — I would simply restrict the maximal number of keys in a table to a fixed number, if key compression is used. Otherwise, the number of keys is unrestricted.\r\n\r\n> Let’s say 65535 keys are allowed. I would then store 65535 string pointers in an array; the array index is the compressed version of the string that is being pointed to. Assuming 64-bit pointers and an average key-string-length of 32 (ASCII) characters, that requires only 1/2M byte in-memory for the array and another 2M byte in-memory for the original keys. The keys in the document are simply 16-bit unsigned ints now, which are an index of the previously created array. In this example, the 32 characters (on average) keys in the document would now only be 2 characters/bytes long.\r\n\r\nThe reason why this approach is problematic on a clusters is outlined by @mlucy here:\r\n\r\n> Capping the number of keys like that would probably be a reasonable approach.  A reverse map isn't a problem; tables in RethinkDB are already heavyweight objects so a little more memory usage per table is probably fine if it speeds up inserts.  It's a little more difficult than what you just described, though, because of the need to coordinate across the cluster.\r\n\r\n> Consider a cluster of three nodes A, B, and C where your table is sharded across all three of them.  If you insert a document that lives in the shard on A, it's important for scalability reasons that the write only goes to node A, so node B and C are entirely unaware of it.  If that insert produces a new key that needs to go into the key map, though, we can't only insert it into the key map on A, because then A, B, and C will all have different key maps, which is a problem during resharding (or even when reading the row).  If you're sending rows between machines and every machine has a different key map, you either need to make all the machines aware of each other's key maps, which is a painful synchronization problem, or you need to uncompress each row before sending it over the network, in which case your compression is saving on disk but not network traffic.  If you want to have a shared key map between A, B, and C, you have the same painful synchronization problem.  (What if A, B, and C are all trying to update the key map at the same time?  Are you going to hold writes on `A` until `B` and `C` acknowledge changes to the key map?  etc. etc.)\r\n\r\nWith that, the discussion was moved on here to preserve it for future reference."},"comment":{"url":"https://api.github.com/repos/rethinkdb/rethinkdb/issues/comments/112602702","html_url":"https://github.com/rethinkdb/rethinkdb/issues/4397#issuecomment-112602702","issue_url":"https://api.github.com/repos/rethinkdb/rethinkdb/issues/4397","id":112602702,"user":{"login":"indiedotkim","id":189316,"avatar_url":"https://avatars.githubusercontent.com/u/189316?v=3","gravatar_id":"","url":"https://api.github.com/users/indiedotkim","html_url":"https://github.com/indiedotkim","followers_url":"https://api.github.com/users/indiedotkim/followers","following_url":"https://api.github.com/users/indiedotkim/following{/other_user}","gists_url":"https://api.github.com/users/indiedotkim/gists{/gist_id}","starred_url":"https://api.github.com/users/indiedotkim/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/indiedotkim/subscriptions","organizations_url":"https://api.github.com/users/indiedotkim/orgs","repos_url":"https://api.github.com/users/indiedotkim/repos","events_url":"https://api.github.com/users/indiedotkim/events{/privacy}","received_events_url":"https://api.github.com/users/indiedotkim/received_events","type":"User","site_admin":false},"created_at":"2015-06-16T23:35:07Z","updated_at":"2015-06-16T23:35:07Z","body":"@danielmewes I actually do not quite understand why the whole table would have to be re-written when extending the key/value space. Don't you just use the newly created indexes in the table afterwards? The \"old\" part of the table can stay the same -- I would assume.\r\n\r\nFor example, with a table of three rows, I would map indexes 1 to the key \"movie-title\", 2 to \"genre\", 3 to \"description\". If I extend the table to six rows, rows 1-3 are untouched and I can add: 4 as \"popcorn-sold\", 5 as \"sodas-sold\", 6 as \"something-else\".\r\n"}}