staltz
commented
3 years ago How much does 16 bits reduce the search space?
Note, the math I ran for this question was for the msg_key_bitmatrix.index where each message in the log has its own unique msg id. Under these same assumptions, with B=10, we would reduce the search space to ~900 msgs, which is probably fast enough to stream and run a pull.filter.
However, for other indexes like msg_value_content_vote_link_bitmatrix.index, B=10 would probably reduce the search space even more than the one above, so maybe we get a dozen of msgs, thus quite fast. Maybe the optimal number is not 16, but 10? That's even better. File size would be less than approx 1.5MB.
mixmix
arj03
some more crazy ideas to use bitvectors: I know it's not feasible to have jitdb indexes for votes, because there are two many vote roots (thus one index for each vote root), and so currenly in ssb-db2 we use leveldb for that. But what if we did something similar to radix sort?
Lets say we take the msgid at
msg.value.content.vote.link, convert it to buffer, and take the 1st bit, then all messages that have the 1st bit ofmsg.value.content.vote.linkequals 1 are indexed in a bitvector. You could do that for the 2nd and 3rd bits too, with the goal being to just limit the search space, and then once it's small enough, just scan the results in memory. This could be combined with #8.i.e. these bitvectors:
Then we can create a query such as
votesFor(msgid), pick the first 3 bits ofmsgidand then AND queries for the corresponding bitvectors mentioned in the list above. Maybe an optimal amount of these indexes could be about ~16?If we have 16 bitvectors for each shape of mentioned key, then we start to have a lot of indexes, e.g.:
In that case, maybe we could save all 16 vectors into one file, then we'd have bitmatrix files. Nx16 as opposed to Nx1:
Open questions
How much does 16 bits reduce the search space?
Lets assume the msg IDs have their 256 bits randomly distributed. If we have only one index for 1st bit, say
B=1, then the search space would be reduced in half. If we has two indexes, for the 1st and 2nd bit, sayB=2, then the search space would be reduced to one quarter of the originalNmessages in the log.In the general case, the search space is reduced to
N / (2**B).Assuming
Nis one million, you need approxB=19to get the search space reduced exactly to your target msg key. See wolfram alpha: https://www.wolframalpha.com/input/?i=%281+million%29+%2F+%282**b%29+%3D+1+solve+for+bNow, maybe we can do less than
19, maybe we don't need the search space to be exactly our desired result, there could be some false positives in there if we assume that scanning the search space is fast enough. Just have to experiment and see, but given that19is close to16, maybe we have to assume that16is a realistic value forB.Are there bad performance issues with this idea?
Hard to know exactly how this will perform, but there's these new costs involved:
Btimes larger than a bitvector, this could be approxBtimes slower to open and streamCould the GPU be used here?
Since we have a matrix of zeros and ones, this looks like a good use case for the GPU, and for parallelization, since we can just give a parts of the bitmatrix to different "GPU threads" and it should be mostly independent to each other. This is something we would do only if the linear scan of the bitmatrix is slow enough to justify the overhead in the GPU bus interface.