Salesforce, Inc.

Salesforce Com, Inc.

Rohit Agrawal

Thomas Fanghaenel

Aditya Dharmanand Shetty

Terry Chong

Kaushal Mittal

Vaibhav Arora

Jacob Jonghan Park

Techniques are disclosed relating to index metadata that is usable for accessing multi-level data structures. A computer system may operate a database, including maintaining a set of records having a set of corresponding keys. The computer system may create multi-level data structures that facilitate key range lookups against those records. A given multi-level data structure may store key information indicative of a subset of the corresponding keys. The computer system may create separate index metadata that is usable for accessing the multi-level data structures. The index metadata may specify indications of key information that is stored in the multi-level data structures and locations of the multi-level data structures. The computer system may perform a key range lookup that includes using the index metadata to determine a particular set of the multi-level data structures whose key information corresponds to a key range of the key range lookup.

Index for multi-level data structures

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.

Merges using key range data structures

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.

Database key compression

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.

Three-dimensional probabilistic data structure

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.

Building of tries over sorted keys

A computing system may repair a database index for a database table by placing a first structural lock on the database table to prevent modifications to the structure of the table. The computing system may scan the database table to determine a plurality of database records. The system may probe the database index for the database records to identify records with missing entries in the index. Based on the probing, the system may place a first data lock on a record of the database table corresponding to a missing index entry to prevent modification of data in the record. In response to placing the first record lock, the system adds an index entry for the locked database record to the database index. During repair of the index, one or more processes may use the database index to locate one of the plurality of database records included in the database table.

Growing community of inventors

San Francisco, CA, United States of America

Rohit Agrawal