Global column indexing in a graph database

Patent metadata

Field	Value
Publication number	US-2018144004-A1
Application number	US-201615360872-A
Country	US
Kind code	A1
Filing date	Nov 23, 2016
Priority date	Nov 23, 2016
Publication date	May 24, 2018
Grant date	—

Abstract

Methods, systems, and computer-readable media for global column indexing in a graph database are disclosed. A plurality of data elements of a graph database are stored. The triples comprise identifiers, column names, and values. The column names are globally scoped in the graph database and are associated with data types. Indices corresponding to the column names are created. A particular one of the indices comprises one or more of the values associated with the corresponding column name. A query is performed on the graph database using one or more of the indices corresponding to one of more of the column names associated with the query.

First claim

What is claimed is:

1 . A system, comprising:
one or more computing devices that implement a graph database to:
store a plurality of data elements in the graph database, wherein the data elements comprise subject identifiers, column names, and values for the column names, wherein the column names are globally scoped in the graph database, and wherein the column names are associated with respective data types for the values;
create indices corresponding to the column names, wherein an individual one of the indices comprises one or more of the values associated with the corresponding column name; and
perform a query on the graph database, wherein the query returns one or more of the values, and wherein the query is performed using one or more of the indices corresponding to one of more of the column names associated with the query.

2 . The system as recited in claim 1 , wherein a first column name in the graph database is associated with a first data type, wherein a second column name in the graph database is associated with a second data type, wherein one or more of the values associated with the first column name are expressed using the first data type, and wherein one or more of the values associated with the second column name are expressed using the second data type.

3 . The system as recited in claim 1 , wherein creation of the indices is initiated in the graph database without user input directing the creation of the indices.

4 . The system as recited in claim 1 , wherein the one or more computing devices further implement the graph database to:
generate statistics associated with the indices, wherein the statistics comprise distributions of the values associated with the column names, and wherein the query is optimized based at least in part on the statistics.

5 . A method, comprising:
storing a plurality of data elements of a graph database, wherein the data elements comprise identifiers, column names, and values, wherein the column names are globally scoped in the graph database; creating indices corresponding to the column names, wherein an individual one of the indices comprises one or more of the values associated with the corresponding column name; and performing a query on the graph database, wherein the query is performed using one or more of the indices corresponding to one of more of the column names associated with the query.

6 . The method as recited in claim 5 , wherein a first column name in the graph database is associated with a first data type, wherein a second column name in the graph database is associated with a second data type, wherein one or more of the values associated with the first column name are expressed using the first data type, and wherein one or more of the values associated with the second column name are expressed using the second data type.

7 . The method as recited in claim 5 , wherein creation of the indices is initiated by a graph database service without user input directing the creation of the indices.

8 . The method as recited in claim 5 , further comprising:
generating statistics associated with the indices, wherein the statistics comprise distributions of the values associated with the column names.

9 . The method as recited in claim 8 , wherein generation of the statistics is initiated by a graph database service based at least in part on updates to one of more of the data elements in the graph database.

10 . The method as recited in claim 8 , further comprising:
optimizing the query based at least in part on the statistics.

11 . The method as recited in claim 10 , wherein optimizing the query comprises determining an order of the indices based at least in part on the statistics.

12 . The method as recited in claim 5 , wherein the indices are stored using separate data structures.

13 . A computer-readable storage medium to store program instructions that, if executed, cause one or more processors to perform:
storing a plurality of data elements associated with a graph database, wherein the data elements comprise subject identifiers, column names, and values, wherein the column names have a global scope in the graph database, and wherein the column names are associated with respective data types; creating indices corresponding to the column names, wherein an individual one of the indices comprises one or more of the values associated with the corresponding column name; and performing a query on the graph database, wherein the query returns one or more of the values, and wherein the query is performed using one or more of the indices corresponding to one of more of the column names associated with the query.

14 . The computer-readable storage medium as recited in claim 13 , wherein a first column name in the graph database is associated with a first data type, wherein a second column name in the graph database is associated with a second data type, wherein one or more of the values associated with the first column name are expressed using the first data type, and wherein one or more of the values associated with the second column name are expressed using the second data type.

15 . The computer-readable storage medium as recited in claim 13 , wherein creation of the indices is initiated by a graph database service without user input directing the creation of the indices.

16 . The computer-readable storage medium as recited in claim 13 , wherein the program instructions are further computer-executable to perform:
generating statistics associated with the indices, wherein the statistics comprise distributions of the values associated with the column names.

17 . The computer-readable storage medium as recited in claim 16 , wherein generation of the statistics is initiated by a graph database service based at least in part on updates to one of more of the data elements in the graph database.

18 . The computer-readable storage medium as recited in claim 16 , wherein the program instructions are further computer-executable to perform:
optimizing the query based at least in part on the statistics.

19 . The computer-readable storage medium as recited in claim 18 , wherein optimizing the query comprises determining an order of the indices based at least in part on the statistics.

20 . The computer-readable storage medium as recited in claim 13 , wherein the query comprises a semantic query.

Assignees

• Amazon Tech Inc

Inventors

• Bedi Kawarjit
• Gupta Piyush
• Wang Xingbo
• Mallidi Sainath Chowdary
• Gutmans Andi

Classifications

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/221 Primary

  Column-oriented storage; Management thereof · CPC title

• G06F16/2453

  Query optimisation · CPC title

• G06F17/30315 Primary

  Physics · mapped topic

• G06F17/30442

  Physics · mapped topic