IP Library Granted Patent US 11,487,719
Granted Patent B2
US 11,487,719 · App. 17/126,744 · Granted Nov 1, 2022

Single table multi-schema data store in a key value store

Inventor: John Anthony Kline (Mountain View, CA)
Assignee: Google LLC
G06F16/211G06F16/2291G06F16/2455G06F16/24575G06F16/284
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 11,487,719
App. No.
17/126,744
Granted
Nov 1, 2022
Kind
B2
Abstract

A system of creating a multi-schema data store of a key-value store may include a computing device. The system may receive a query to search for data from the multi-schema data store, wherein a first portion of the data corresponds to a first schema and a second portion of the data corresponds to one or more other schemas, the first and second portions of the data being stored in the multi-schema data store in interleaved format, wherein the query comprises a unique identifier associated with the data. The system may parse one or more entries of the multi-schema data store in a sequential order until a first entry is found that corresponds to the unique identifier, without assuming a hierarchy between schemas in the multi-schema data store. The system may compare the query to one or more proximate entries of the multi-schema data store.

Claims (43)

1. A system of accessing a multi-schema data store, the system comprising:

a computing device; and

a first computer-readable storage medium portion comprising the multi-schema data store, wherein the multi-schema data store is part of a key value store; and

a second computer-readable storage medium portion in communication with the first computer-readable storage medium portion, wherein the second computer-readable storage medium portion comprises programming instructions that are configured to cause the computing device to:

receive a query to search for data from the multi-schema data store, wherein a first portion of the data corresponds to a first schema and a second portion of the data corresponds to one or more other schemas, the first and second portions of the data being stored in the multi-schema data store in interleaved format, wherein the query comprises a unique identifier associated with the data,

parse one or more entries of the multi-schema data store in a sequential order until a first entry is found that corresponds to the unique identifier,

compare the query to one or more entries of the multi-schema data store, and

return one or more search results that includes data from at least one of: the first entry, or one or more of the entries that satisfies the query.

2. The system of claim 1 , wherein the programming instructions for parsing one or more entries of the multi-schema data store in a sequential order until a first entry is found that corresponds to the unique identifier comprise programming instructions to determine a schema associated with the first entry.

3. The system of claim 2 , wherein the programming instructions for determining a schema associated with the first entry comprise programming instructions to identify an attribute configuration associated with the first entry.

4. The system of claim 3 , further comprising programming instructions that are configured to cause the computing device to:

identify a second schema associated with one or more of the entries of the multi-schema data store; and

determine that the schema associated with the first entry is above the second schema in a hierarchy.

5. The system of claim 1 , wherein the programming instructions are further configured to cause the computing device to join information across different schemas in the multi-schema data store to satisfy the query.

6. The system of claim 5 , wherein the join is an automatic join implemented in response to an explicit join being omitted from the received query.

7. The system of claim 5 , wherein the join is performed assuming a hierarchy between the first schema and the one or more other schemas.

8. The system of claim 1 , wherein:

the query includes an alias, and

the one or more search results are returned according to a schema of the multi-schema data store registered with the alias.

9. The system of claim 1 , wherein the programming instructions for parsing the one or more entries comprise programming instructions for parsing the one or more entries without assuming a hierarchy between schemas in the multi-schema data store.

10. The system of claim 1 , wherein the one or more entries are located in proximity to the first entry.

11. The system of claim 1 , wherein the one or more search results includes data from the first entry and the one or more entries that satisfies the query.

12. A method of accessing a multi-schema data store, the method comprising:

receiving, by a computing device, a query to search for data from the multi-schema data store contained in a computer-readable storage medium, the multi-schema data store being a part of a key-value store, wherein a first portion of the data corresponds to a first schema and a second portion of the data corresponds to one or more other schemas, the first and second portions of the data being stored in the multi-schema data store in interleaved format, wherein the query comprises a unique identifier associated with the data;

parsing, by the computing device, one or more entries of the multi-schema data store in a sequential order until a first entry is found that corresponds to the unique identifier;

comparing, by the computing device, the query to one or more entries of the multi-schema data store; and

returning, by the computing device, one or more search results that includes data from at least one of: the first entry, or one or more of the entries that satisfies the query.

13. The method of claim 12 , wherein parsing one or more entries of the multi-schema data store in a sequential order until a first entry is found that corresponds to the unique identifier comprises determining a schema associated with the first entry.

14. The method of claim 13 , wherein determining a schema associated with the first entry comprises identifying an attribute configuration associated with the first entry.

15. The method of claim 14 , further comprising:

identifying a second schema associated with one or more of the entries of the multi-schema data store; and

determining that the schema associated with the first entry is above the second schema in a hierarchy.

16. The method of claim 12 , wherein parsing the one or more entries further comprises parsing the one or more entries, without assuming a hierarchy between schemas in the multi-schema data store.

17. The method of claim 12 , wherein the one or more entries are located in proximity to the first entry.

18. The method of claim 12 , wherein the one or more search results includes data from the first entry and the one or more entries that satisfies the query.

19. One or more non-transitory computer-readable storage media encoded with computer program instructions that when executed by one or more processors cause the one or more processors to perform operations comprising:

receiving a query to search for data from a multi-schema data store, wherein a first portion of the data corresponds to a first schema and a second portion of the data corresponds to one or more other schemas, the first and second portions of the data being stored in the multi-schema data store in interleaved format, wherein the query comprises a unique identifier associated with the data,

parsing one or more entries of the multi-schema data store in a sequential order until a first entry is found that corresponds to the unique identifier,

comparing the query to one or more entries of the multi-schema data store, and

returning one or more search results that includes data from at least one of: the first entry, or one or more of the entries that satisfies the query.

20. The computer-readable storage media of claim 19 ,

wherein parsing the one or more entries without assuming a hierarchy between schemas in the multi-schema data store; and

wherein the one or more entries are located in proximity to the first entry.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Dec 21, 2020
From: KLINE, JOHN ANTHONY
To: GOOGLE INC.
Reel/Frame 054818/0010 →
Continuity (4)
Division 16416956 · May 20, 2019
Continuation 14927591 · Oct 30, 2015
Provisional Application 62236435 · Oct 2, 2015
Related Publication 20210103565A1 · Apr 8, 2021