公开(公告)号：US20220129433A1

公开(公告)日：2022-04-28

申请号：US17079149

申请日：2020-10-23

Applicant: salesforce.com, inc.

Inventor： Rohit Agrawal ,  Aditya Shetty ,  Kaushal Mittal ,  Terry Chong ,  Thomas Fanghaenel ,  Vaibhav Arora

IPC: G06F16/22

Abstract: Techniques are disclosed relating to building an in-memory multi-level data structure useable to determine presence or absence of key ranges in files consisting of database records. In various embodiments, a computer system operates a database, including maintaining a set of records having a set of corresponding keys that are accessible in key-sorted order and generates a multi-level data structure that facilitates key range lookups against the set of records. The generating may include accessing ones of the set of keys in key-sorted order and determining, for a particular accessed key that includes a set of characters, an intermediate level within the multi-level data structure and a subset of the characters of the particular accessed key for insertion. The computer system may insert, starting at the intermediate level, information that identifies the subset of characters, with the inserting being performed without traversing any levels before the intermediate level.

公开(公告)号：US11886401B2

公开(公告)日：2024-01-30

申请号：US17647570

申请日：2022-01-10

Applicant: salesforce.com, inc.

Inventor： Rohit Agrawal ,  Aditya Dharmanand Shetty ,  Thomas Fanghaenel

IPC: G06F16/00 ,  G06F16/215 ,  H03M7/30 ,  G06F16/22

CPC classification number: G06F16/215 ,  G06F16/2246 ,  G06F16/2272 ,  H03M7/30

Abstract: Techniques are disclosed relating to compressing database keys. A computer system may receive a request to write a database record to a storage medium. The database record may include a database key and a corresponding data value. The computer system may compress the database key by replacing a portion of the database key with particular data that identifies a location of a reference database key and an amount of similarity determined between the database key and the reference database key. The computer system may write the database record to the storage medium. The database record may include the compressed database key and the corresponding data value.

公开(公告)号：US11829398B2

公开(公告)日：2023-11-28

申请号：US16845921

申请日：2020-04-10

Applicant: salesforce.com, inc.

Inventor： Jacob Jonghan Park ,  Rohit Agrawal ,  Thomas Fanghaenel

IPC: G06F15/16 ,  G06F16/33 ,  G06F16/182 ,  G06F16/338 ,  G06F16/17 ,  G06F21/62

CPC classification number: G06F16/3346 ,  G06F16/1734 ,  G06F16/182 ,  G06F16/338 ,  G06F21/6218 ,  G06F2221/0751

Abstract: Techniques are disclosed relating to probabilistic data structures. A database node may maintaining a probabilistic data structure capable of encoding database keys. The probabilistic data structure may include a plurality of levels that are each capable of storing an indication of a transition between successive characters in a database key. The database node may insert a particular database key into the probabilistic data structure and the particular database key may comprise a series of characters. The inserting may include setting, for each transition between successive characters of the series of characters, an indication in a corresponding level of the plurality of levels that is indicative of that transition. The database node may further maintain lineage information specifying one or more lineages that correspond to the transition.

公开(公告)号：US11537569B2

公开(公告)日：2022-12-27

申请号：US17009605

申请日：2020-09-01

Applicant: salesforce.com, inc.

Inventor： Rohit Agrawal ,  Aditya Shetty ,  Kaushal Mittal ,  Terry Chong ,  Thomas Fanghaenel ,  Vaibhav Arora

IPC: G06F16/22 ,  G06F16/21 ,  G06F21/62

Abstract: Techniques are disclosed relating to merge operations for multi-level data structures, such as log-structured merge-trees (LSM trees). A computer system may store, in a database, a plurality of files as part of an LSM tree and a plurality of database key structures. A given one of the plurality of database key structures may indicate, for a corresponding one of the plurality of files, a set of key ranges derived from database records that are included in the corresponding file. The computer system may determine, using ones of the plurality of database key structures, a key range overlap that is indicative of an extent of overlap of key ranges from a set of the plurality of files with respect to a particular key range. Based on the determined key range overlap, the computer system may assign a priority level to a merge operation that involves the set of files.

公开(公告)号：US11221999B2

公开(公告)日：2022-01-11

申请号：US16457842

申请日：2019-06-28

Applicant: salesforce.com, inc.

Inventor： Rohit Agrawal ,  Aditya Dharmanand Shetty ,  Thomas Fanghaenel

IPC: G06F17/00 ,  G06F16/215 ,  H03M7/30 ,  G06F16/22

Abstract: Techniques are disclosed relating to compressing database keys. A computer system may receive a request to write a database record to a storage medium. The database record may include a database key and a corresponding data value. The computer system may compress the database key by replacing a portion of the database key with particular data that identifies a location of a reference database key and an amount of similarity determined between the database key and the reference database key. The computer system may write the database record to the storage medium. The database record may include the compressed database key and the corresponding data value.