US 9,805,079 B2Granted

Executing constant time relational queries against structured and semi-structured data

AssigneeXcalar, Inc.

InventorsVikram Joshi, Jerene Yang, Brent Lim Tze Hao, Michael Brown

Life of this patent

Estimating the term…

Loading patent…

Abstract

Techniques are described herein for performing database operations against location and access transparent metadata units called fat pointers organized into globally distributed data structures. The fat pointers are created by extracting values corresponding to a particular key and paring each value with a reference to the local location and server that has the native format record containing the value. The fat pointers may be transferred to any server in the cluster, even if the server is different from the server that has the native format record. In general, most operations are performed against fat pointers rather than the native format records. This allows the cluster to perform work against arbitrary types of data efficiently and in a constant amount of time despite the variable sizes and structures of records.

Claims32

Dependent claims

A method comprising:

assigning each record of a plurality of records to a corresponding segment of a plurality of segments;
based on a pseudorandom algorithm, selecting a subset of the plurality of segments as a sample population;
distributing the sample population across one or more target computing devices of a plurality of computing devices;
prior to receiving a request to perform a particular database operation, creating a globally distributed data structure as an index for a particular key;
wherein the globally distributed data structure comprises a plurality of locally distributed data structures for the particular key;
wherein creating the globally distributed data structure includes:
identifying a set of records, each of which has at least one value that corresponds to the particular key;
for each record of the set of records, performing the steps of:
creating a fat pointer to the record based, at least in part, on:
a given value in the record that corresponds to the particular key;
and
a location of the record on a target computing device of the plurality of computing devices;
based on the given value, sending the fat pointer to a host computing device in the plurality of computing devices;
in response to receiving the fat pointer at the host computing device, performing the steps of:
identifying a locally distributed data structure for the particular key;
storing the fat pointer, within the locally distributed data structure, based on the given value;
in response to receiving the request to perform the particular database operation, determining that the request makes reference to the particular key;
and
generating a response to the request based, at least in part, on information obtained from the globally distributed data structure for the particular key.

16 more elements

One or more non-transitory storage media storing instructions which, when executed by one or more computing devices, cause performance of a method comprising the steps of:

assigning each record of a plurality of records to a corresponding segment of a plurality of segments;
based on a pseudorandom algorithm, selecting a subset of the plurality of segments as a sample population;
distributing the sample population across one or more target computing devices of a plurality of computing devices;
prior to receiving a request to perform a particular database operation, creating a globally distributed data structure as an index for a particular key;
wherein the globally distributed data structure comprises a plurality of locally distributed data structures for the particular key;
wherein creating the globally distributed data structure includes:
identifying a set of records, each of which has at least one value that corresponds to the particular key;
for each record of the set of records, performing the steps of:
creating a fat pointer to the record based, at least in part, on:
a given value in the record that corresponds to the particular key;
and
a location of the record on a target computing device of the plurality of computing devices;
based on the given value, sending the fat pointer to a host computing device in the plurality of computing devices;
in response to receiving the fat pointer at the host computing device, performing the steps of:
identifying a locally distributed data structure for the particular key;
storing the fat pointer, within the locally distributed data structure, based on the given value;
in response to receiving the request to perform the particular database operation, determining that the request makes reference to the particular key;
and
generating a response to the request based, at least in part, on information obtained from the globally distributed data structure for the particular key.

16 more elements

Dependencies are inferred from the claim text.

Facts

Application: 14/720,481Filed 22 May 2015 · us provisional application
Priority: 22 Aug 2014
Published: US 2016/0055191 A125 Feb 2016
Granted: 31 Oct 2017
Term ends: Not estimatedThe source records don’t support an estimate.

Classification14 codes

G06F 16/2272
Indexing structures: management thereof
G06F 3/04842
For the control of specific functions or operations, e.g. selecting or manipulating an object, an image or a displayed text element, setting a…:…
G06F 16/2228
Indexing; Data structures therefor; Storage structures: indexing structures
G06F 16/2428
Query formulation: query predicate definition using graphical user interfaces, including menus and forms