asterixdb-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Chen Li <che...@gmail.com>
Subject Re: Question on LSMified secondary indexes
Date Mon, 07 Mar 2016 16:58:21 GMT
The second feature (using metadata to describe the content of each LSM
component) is described in Sattam's PhD thesis.

Chen

On Mon, Mar 7, 2016 at 6:28 AM, abdullah alamoudi <bamousaa@gmail.com>
wrote:

> Hi Veeral,
> Two points:
> 1. Keys in our LSM index are not mutually exclusive between different
> components.
> 2. We have the concept of filtered LSM index in which we store (min-max) of
> a field(not necessarily the key) and we can use them then when answering
> queries to know which components to look at.
>
> Hope this helps,
> Abdullah.
>
> On Mon, Mar 7, 2016 at 4:48 PM, Veeral Shah <veerals@gmail.com> wrote:
>
> >    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
> >
>

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