3 ms·

How is multi-indexing implemented? What kind of query performance can it attain? This seems somewhat similar to hyperdex's search function. It is implemented t

How is multi-indexing implemented? What kind of query performance can it attain? This seems somewhat similar to hyperdex's search function. It is implemented through what is called hyperspace hashing. How would you compare yourself to hyperdex?

coffeemug 13y ago
An index in RethinkDB is an additional BTree that stores a record keyed by the value of the index, not by the value of a primary key. When you query by an index, RethinkDB looks the records up by looking at the index BTree instead of the main BTree. This is similar to how most RDBMSes implement indexes. Multi-indexing is implemented by inserting multiple rows into the index B-Tree. So if your index for a document returns [1, 2], Rethink stores two records into the index BTree -- one keyed by 1, the other keyed by 2. This is different from hyperdex -- we don't do any algorithmic tricks with spaces to make this more efficient. The model we used fit extremely well into our architecture, so @jdoliner just went ahead and implemented it. Hope this makes sense -- great questions! (Also, love your username)
- continuations 13y ago
  How do you handle distribution of documents among nodes? Say document X has 3 tags "A", "B", "C". Do you place all documents with tag "A" in the same node, all docs with tag "B" in the same (but potentially different) node, and all docs with tag "C"...? In that case you'd need to put document X in potentially 3 different nodes. Or do you not do that kind of "pre-sorting" and just send queries to every node asking for match for tag "A"? (I like my username too. I was surprised it was still available)
  - coffeemug 13y ago
    Documents are distributed across nodes based on a primary key. Currently we use range-based sharding, but will be moving towards hash-based sharding soon. So, for any given document, we look at the primary key and determine where a document should be. We store a secondary index for a shard on the same node where the master for the shard resides. So if you're storing users whose last names are between A-M on node A, all secondary indexes for users with last names between A and M will also be on node A. That means that for any secondary index query we have to contact all nodes that have shards for a table, but we do a number of systems tricks to make this really efficient.
    - continuations 13y ago
      > but we do a number of systems tricks to make this really efficient. Can you talk about these tricks? I'd love to learn more about it.

coffeemug 13y ago

An index in RethinkDB is an additional BTree that stores a record keyed by the value of the index, not by the value of a primary key. When you query by an index, RethinkDB looks the records up by looking at the index BTree instead of the main BTree. This is similar to how most RDBMSes implement indexes. Multi-indexing is implemented by inserting multiple rows into the index B-Tree. So if your index for a document returns [1, 2], Rethink stores two records into the index BTree -- one keyed by 1, the other keyed by 2. This is different from hyperdex -- we don't do any algorithmic tricks with spaces to make this more efficient. The model we used fit extremely well into our architecture, so @jdoliner just went ahead and implemented it. Hope this makes sense -- great questions! (Also, love your username)

continuations 13y ago
How do you handle distribution of documents among nodes? Say document X has 3 tags "A", "B", "C". Do you place all documents with tag "A" in the same node, all docs with tag "B" in the same (but potentially different) node, and all docs with tag "C"...? In that case you'd need to put document X in potentially 3 different nodes. Or do you not do that kind of "pre-sorting" and just send queries to every node asking for match for tag "A"? (I like my username too. I was surprised it was still available)
- coffeemug 13y ago
  Documents are distributed across nodes based on a primary key. Currently we use range-based sharding, but will be moving towards hash-based sharding soon. So, for any given document, we look at the primary key and determine where a document should be. We store a secondary index for a shard on the same node where the master for the shard resides. So if you're storing users whose last names are between A-M on node A, all secondary indexes for users with last names between A and M will also be on node A. That means that for any secondary index query we have to contact all nodes that have shards for a table, but we do a number of systems tricks to make this really efficient.
  - continuations 13y ago
    > but we do a number of systems tricks to make this really efficient. Can you talk about these tricks? I'd love to learn more about it.