asterixdb-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Veeral Shah <>
Subject Question on LSMified secondary indexes
Date Mon, 07 Mar 2016 13:48:09 GMT
   Had a small question around asterixdb LSMified secondry index structure
(Disclaimer : I dont have complete familiarity with the LSM file formats in
asterixdb - hence below also sort of validates my understanding),

In a classic LSM implementation, files (aka SST files in leveldb) at level
L1 onwards (L1, L2, L3,...), are sorted based on keys (assuming key types
where linear order can be imposed) and the key ranges of any two SST files,
in a level, are mutually exclusive. Since the LSM files are immutable, a
file's key range at a level remains fixed (unless compaction happens). So
taking a case of a asterixdb LSMified secondary index, assuming the keys
are byte strings, all keys should be alphabetically sorted.

 If above is true, there may be a merit in creating an additional in-memory
"coarse-index" (for each level) which keeps info about key.max and key.min
for each file region (say an SST file is broken into multiple smaller
regions of fixed size). This would help in quickly figuring out where a key
could fall, in  a given LSM level. (The coarse-index is to be
created/recreated during startup and compaction)

 Thanks and regards
Veeral Shah

  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message