Partitioned distributed database systems, devices, and methods

• US 10,268,704 B1
• Filed: 10/11/2018
• Issued: 04/23/2019
• Est. Priority Date: 10/12/2017
• Status: Active Grant

• Current Assignee: Vast.com, Inc. (Vroom, Inc.)
• Original Assignee: Vast.com, Inc. (Vroom, Inc.)
• Inventors: Sanderson, Graham Carlos, Smith, Benedict John Elliot
• Primary Examiner(s): Bullock, Joshua
• Application Number:
  US16/158,189
• Time in Patent Office: 194 Days
• Field of Search: 707736
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2428 Query predicate definition using graphical user interfaces, including menus and forms G06F16/2423 takes precedence
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/252 between a Database Management System and a front-end application
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning

Abstract

A client system can improve processing speeds by executing queries locally. A remote database can have a partitioned, columnar database. Queries from the client can be executed on the remote database, and blocks of a partition of the partitioned, columnar database can be sent to the client. Once the client has enough blocks to form the partition, the client can execute queries that reference the partition. The queries can be executed using templates for specialized expression evaluators.

Claims

1. A computer-implemented query system for website query transmission and partial dataset receiving over a computer network connection, the computer-implemented query system comprising:

a user input device;

an output device; and

one or more processors configured to;

receive, through the user input device, a first user command;

construct a first query based at least in part on the first user command;

send the first query through a network to query a server database on a remote server, wherein the server database comprises records corresponding to a plurality of inventory items, wherein the first query operates on a server partition of the server database that includes a cluster of related records of the server database;

receive, from the remote server, a first response to the first query;

transmit data to the output device to present a website including a result generated based at least in part on the first response, the result comprising data related to one or more of the plurality of inventory items;

receive a plurality of blocks sufficient to form a local partition that comprises at least a portion of the server partition of the server database;

receive, through the user input device, a second user command;

construct a second query based at least in part on the second user command;

after receiving the plurality of blocks;

use the plurality of blocks to construct and locally store a local database comprising the local partition;

determine that the second query references the local database stored in the computer-implemented query system;

execute the second query; and

transmit data to the output device to present, in the website, a second result generated based at least in part on a result of the second query, the second result comprising data related to one or more of the plurality of inventory items.

2. The computer-implemented query system of claim 1, wherein the local partition includes a local plurality of records that correspond to at least a subset of the cluster of related records of the server database, and each of the local plurality of records include a subset of fields of the cluster of related records of the server database.

3. The computer-implemented query system of claim 1, wherein the one or more processors are further configured to, before receiving the plurality of blocks:

send a plurality of queries to the remote server; and

receive, from the remote server, a plurality of query responses in response to the plurality of queries.

4. The computer-implemented query system of claim 1, wherein the blocks include data that is compressed, compacted, or encoded.

5. The computer-implemented query system of claim 1, wherein the server database comprises data encoded using at least one of:

dictionary variants of primitives;

or

normalized row references.

6. The computer-implemented query system of claim 1, wherein the server database includes a Huffman tree encoded field.

7. The computer-implemented query system of claim 1, wherein the first query operates on the data, and the second query operates on a narrower subset of the data.

8. The computer-implemented query system of claim 1, wherein the one or more processors are further configured to:

construct a third query based at least in part on the second user command;

send the third query through the network to query the database;

receive, from the remote server in response to sending the third query, picture data for displaying a graphical image; and

transmit the picture data to the output device to supplement the second result.

9. The computer-implemented query system of claim 1, wherein the second query is executed without backbone latency, network latency, or connection latency to the remote server.

10. The computer-implemented query system of claim 1, wherein, when presenting the second result requires missing data that is not available in the local partition, the one or more processors are further configured to:

send a request through the network to the remote server to retrieve the missing data;

prior to receiving a response to the request for the missing data, transmit data to the output device to present a partial result based on data available in the local partition; and

after receiving the missing data from the remote server, transmit data to the output device to supplement the partial result.

11. The computer-implemented query system of claim 10, wherein the missing data comprises data that is at least 10 times larger than the data stored in any field of the local partition.

12. The computer-implemented query system of claim 10,

wherein the user input device is configured to present a graphical user interface feature that enables a user to dynamically adjust a parameter of the second query;

and

wherein the one or more processors are further configured to, in response to an adjustment to the parameter of the second query caused by the graphical user interface feature;

determine that additional missing data is required to fully update the results presented by the output device;

send a request through the network to the remote server to retrieve the additional missing data;

prior to receiving a response to the request for the additional missing data, transmit data to the output device to present a partial updated result based on data available in the local partition; and

after receiving the additional missing data from the remote server, transmit data to the output device to supplement the updated result.

13. The computer-implemented query system of claim 12,

wherein the graphical user interface feature comprises an activated state and a deactivated state, with the activated state allowing dynamic adjustment of the graphical user interface feature to cause dynamic adjustment of the parameter of the second query;

and

wherein the one or more processors are further configured to;

when the graphical user interface feature is in the activated state, refrain from requesting the additional missing data until the graphical user interface feature transitions to the deactivated state.

14. A computer-implemented method for partial database receiving over a network connection for progressively faster query execution and faster website display, the method comprising:

receiving one or more first user commands;

constructing one or more first queries based at least in part on the first user commands;

determining that at least one of the first queries references a server partition of the database located on a remote server that does not yet have available a corresponding local partition in a client computer system, wherein the database located on the remote server comprises records corresponding to a plurality of inventory items;

sending the first queries to the remote server;

receiving, from the remote server, one or more first responses to the first queries;

receiving blocks to form the local partition of the database;

receiving one or more second user commands;

constructing one or more second queries based at least in part on the second user commands;

after receiving sufficient blocks to form the local partition of the database;

determining that the second queries reference the local partition of the database; and

executing the second queries.

15. The method of claim 14, wherein the local partition of the database is formed from the blocks, and the local partition corresponds to and is a subset of the server partition.

16. The method of claim 14, wherein the database is a columnar database, and a partition scheme is based on a column of the database.

17. The method of claim 14, wherein the database includes over ten million bitsets, and the second query is executed in under 300 ms.

18. The method of claim 14, further comprising:

executing the second queries in 20 ms or faster, wherein the database includes at least 1 million records.

19. A server configured to provide faster responses for websites presenting inventory items, the server comprising:

one or more storage devices comprising a partitioned, columnar database, wherein the partitioned, columnar database comprises records corresponding to a plurality of inventory items; and

one or more processors configured to;

receive, from a client system, a first query on the columnar database;

determine a server partition of the columnar database referenced by the first query;

execute the first query on the server partition of partitioned, columnar database;

send a first response to the first query to the client system, the first response comprising data related to one or more of the plurality of inventory items;

send one or more first blocks comprising data from the server partition to the client system;

receive a second query on the server partition of the partitioned, columnar database;

execute the second query on the server partition of the partitioned, columnar database;

send a second response to the second query to the client system, the second response comprising data related to one or more of the plurality of inventory items; and

send a sufficient number of blocks comprising data from the server partition to the client system for the client system to construct a local partition corresponding to the server partition of the partitioned, columnar database, the sufficient number of blocks including the one or more first blocks.

20. The server of claim 19, wherein sending the sufficient number of blocks is configured to enable the client system to construct the local partition to comprise a plurality of records of the server partition, with each of the plurality of records comprising a subset of fields of the server partition.