Database layered filtering

A non-transitory computer readable medium having program instructions stored thereon that are capable of causing a computer system to perform operations comprising:

• storing records in a log-structured merge tree (LSM tree) that comprises a hierarchy of levels;
• receiving a request to perform a key range search to locate records of the LSM tree that fall within a specified key range and satisfy selection criteria;
• and
• performing the key range search, wherein the performing includes a plurality of level scans, wherein a given level scan involves searching a respective level of the hierarchy of levels for records that fall within the specified key range, and wherein the plurality of level scans includes:
• a first set of level scans that each involve a filter operation in which particular records involved in that level scan are filtered out based on the selection criteria;
• and
• a second set of level scans that do not involve the filter operation.

A system, comprising:

• at least one processor;
• and
• a memory having program instructions stored thereon that are executable by the at least one processor to perform operations comprising:
• storing records in a log-structured merge tree (LSM tree) that comprises a hierarchy of levels;
• receiving a request to perform a key range search to locate records of the LSM tree that fall within a specified key range and satisfy selection criteria;
• and
• performing the key range search, wherein the performing includes a plurality of level scans, wherein a given level scan involves searching a respective level of the hierarchy of levels for records that fall within the specified key range, and wherein the plurality of level scans includes:
• a first set of level scans that each involve a filter operation in which particular records involved in that level scan are filtered out based on the selection criteria;
• and
• a second set of level scans that do not involve the filter operation.