lgtm 👍

I’m convinced Toby just likes implementing stuff from papers he finds on the internet ;)

Curious why this is useful for split key determination. Doesn't this imply that, if all of the key-values are the same length, then a split becomes uniformly random? It seems to me that, in that case, you'd want the split to be preferentially near the middle of the data (if not exactly near the middle).

LGTM

@toddlipcon: the idea is to end up with a weighted sampling of all the keys in a range by the total size in bytes of the key + value. Let's say you kept a sample of 100 key/values. When finished, you'd pull all 100 keys out of the sample, sort them, and take the 50th as the split key.

that still depends on a linear scan over all of the keys in order to construct the reservoir sample. If you're going to scan the whole range, couldn't you do this exactly with the simple algorithm (pseudocode):

total_size = sum the byte size of all files in the range
scanner = new InternalScanner();
scanned_size = 0
while scanner.stats.bytes_scanned() < total_size / 2:
scanner.next()

or something of that sort?

Or, assuming you have a tree structure key index in your SSTables, you could probably do this with a logarithmic number of seeks instead of a linear scan.

Yep, that would work and certainly has the benefit of simplicity and would
take half the time on scan. We don't have a particularly accurate signal
for total bytes in the range and don't have access (or at least don't want
to try to ghetto-rig access) to the low level rocksdb MST files. Still, the
split key does not have to be anywhere near an exact choice, so we could
use RocksDB's estimate for size of range.

Tobias, up to you how you want to do it.

On Wed, Sep 10, 2014 at 11:48 AM, Todd Lipcon notifications@github.com
wrote:

that still depends on a linear scan over all of the keys in order to
construct the reservoir sample. If you're going to scan the whole range,
couldn't you do this exactly with the simple algorithm (pseudocode):

total_size = sum the byte size of all files in the range
scanner = new InternalScanner();
scanned_size = 0
while scanner.stats.bytes_scanned() < total_size / 2:
scanner.next()

or something of that sort?

Or, assuming you have a tree structure key index in your SSTables, you
could probably do this with a logarithmic number of seeks instead of a
linear scan.

—
Reply to this email directly or view it on GitHub
#44 (comment).

Leaving it as is for now, to be reconsidered as stats evolve.