Query optimizations for asynchronous distributed queries on graphs with schema

1 . A method comprising:

performing query augmentation for a graph pattern matching query to be executed against a graph, wherein:

the graph has a graph schema defining: vertex types, vertex properties, edge types, and edge properties,

the graph pattern matching query includes a graph pattern including at least one source vertex, at least one destination vertex, and at least one edge connecting a source vertex to a destination vertex,

performing the query augmentation comprises:

inferring, from the graph pattern matching query, schema information based on the graph schema;

identifying one or more vertex or edge types, from the schema information, missing from the graph pattern; and

adding one or more vertex or edge type labels corresponding to the one or more vertex or edge types to the graph pattern in the graph pattern matching query to form an augmented query; and

performing query execution planning based on the augmented query,

wherein the method is performed by one or more computing devices.

2 . The method of claim 1 , wherein identifying the one or more vertex or edge types missing from the graph pattern comprises:

determining that at least one of a particular source vertex or a particular destination vertex in the graph pattern has a particular vertex type label;

determining that a connecting edge connecting the particular source vertex to the particular destination vertex does not have an edge type label;

inferring at least one edge type label based on the graph schema and the particular vertex type label; and

adding the at least one edge type label to the connecting edge in the graph pattern.

3 . The method of claim 1 , wherein identifying the one or more vertex or edge types missing from the graph pattern comprises:

determining that a particular edge in the graph pattern has a particular edge type label, wherein the particular edge connects a particular source vertex to a particular destination vertex;

determining that at least one of the particular source vertex or the particular destination vertex does not have a vertex type label;

inferring at least one vertex type label based on the edge type label and the graph schema; and

adding the at least one vertex type label to the particular source vertex or the particular destination vertex in the graph pattern.

4 . The method of claim 1 , wherein identifying the one or more vertex or edge types missing from the graph pattern comprises:

determining that the graph pattern specifies a vertex or edge property for a particular vertex or a particular edge, wherein the vertex or edge property exists for a subset of vertex types or edge types in the graph schema;

inferring at least one vertex or edge type corresponding to the specified vertex or edge property based on the graph schema; and

adding at least one vertex or edge type label corresponding to the at least one vertex or edge type to the particular vertex or the particular edge in the graph pattern.

5 . The method of claim 1 , wherein performing the query augmentation comprises:

determining that the graph pattern matching query includes a property access for a vertex or edge type that does not include the property based on the graph schema; and

replacing the property access with a NULL value in the graph pattern matching query.

6 . The method of claim 1 , wherein performing the query augmentation comprises repeating query augmentation until no further missing schema information is identified.

7 . The method of claim 1 , further comprising:

performing schema information removal to remove redundant schema information or schema information that is not relevant during runtime.

8 . The method of claim 7 , wherein performing the schema information removal comprises:

determining that the graph pattern specifies a connecting edge with an edge type that uniquely connects to a particular destination vertex type based on the graph schema;

determining that a particular destination vertex of the connecting edge has a particular vertex type label of the particular destination vertex type; and

removing the particular vertex type label from the particular destination vertex in the graph pattern.

9 . The method of claim 7 , wherein performing the schema information removal comprises:

determining that the graph pattern specifies a connecting edge for which only a particular edge type is possible based on the graph schema;

determining that the connecting edge has a particular edge type label of the particular edge type; and

removing the particular edge type label from the connecting edge in the graph pattern.

10 . The method of claim 7 , wherein performing the schema information removal comprises removing inconsistent labels with property accesses.

11 . One or more non-transitory storage media storing instructions which, when executed by one or more computing devices, cause:

performing query augmentation for a graph pattern matching query to be executed against a graph, wherein:

the graph has a graph schema defining: vertex types, vertex properties, edge types, and edge properties,

the graph pattern matching query includes a graph pattern including at least one source vertex, at least one destination vertex, and at least one edge connecting a source vertex to a destination vertex,

performing the query augmentation comprises:

inferring, from the graph pattern matching query, schema information based on the graph schema;

identifying one or more vertex or edge types, from the schema information, missing from the graph pattern; and

adding one or more vertex or edge type labels corresponding to the one or more vertex or edge types to the graph pattern in the graph pattern matching query to form an augmented query; and

performing query execution planning based on the augmented query.

12 . The one or more non-transitory storage media of claim 11 , wherein identifying the one or more vertex or edge types missing from the graph pattern comprises:

determining that at least one of a particular source vertex or a particular destination vertex in the graph pattern has a particular vertex type label;

determining that a connecting edge connecting the particular source vertex to the particular destination vertex does not have an edge type label;

inferring at least one edge type label based on the graph schema and the particular vertex type label; and

adding the at least one edge type label to the connecting edge in the graph pattern.

13 . The one or more non-transitory storage media of claim 11 , wherein identifying the one or more vertex or edge types missing from the graph pattern comprises:

determining that a particular edge in the graph pattern has a particular edge type label, wherein the particular edge connects a particular source vertex to a particular destination vertex;

determining that at least one of the particular source vertex or the particular destination vertex does not have a vertex type label;

inferring at least one vertex type label based on the edge type label and the graph schema; and

adding the at least one vertex type label to the particular source vertex or the particular destination vertex in the graph pattern.

14 . The one or more non-transitory storage media of claim 11 , wherein identifying the one or more vertex or edge types missing from the graph pattern comprises:

determining that the graph pattern specifies a vertex or edge property for a particular vertex or a particular edge, wherein the vertex or edge property exists for a subset of vertex types or edge types in the graph schema;

inferring at least one vertex or edge type corresponding to the specified vertex or edge property based on the graph schema; and

adding at least one vertex or edge type label corresponding to the at least one vertex or edge type to the particular vertex or the particular edge in the graph pattern.

15 . The one or more non-transitory storage media of claim 11 , wherein performing the query augmentation comprises:

determining that the graph pattern matching query includes a property access for a vertex or edge type that does not include the property based on the graph schema; and

replacing the property access with a NULL value in the graph pattern matching query.

16 . The one or more non-transitory storage media of claim 11 , wherein performing the query augmentation comprises repeating query augmentation until no further missing schema information is identified.

17 . The one or more non-transitory storage media of claim 11 , further comprising:

performing schema information removal to remove redundant schema information or schema information that is not relevant during runtime.

18 . The one or more non-transitory storage media of claim 17 , wherein performing the schema information removal comprises:

determining that the graph pattern specifies a connecting edge with an edge type that uniquely connects to a particular destination vertex type based on the graph schema;

determining that a particular destination vertex of the connecting edge has a particular vertex type label of the particular destination vertex type; and

removing the particular destination vertex type label from the particular destination vertex in the graph pattern.

19 . The one or more non-transitory storage media of claim 17 , wherein performing the schema information removal comprises:

determining that the graph pattern specifies a connecting edge for which only a particular edge type is possible based on the graph schema;

determining that the connecting edge has a particular edge type label of the particular edge type; and

removing the particular edge type label from the connecting edge in the graph pattern.

20 . The one or more non-transitory storage media of claim 17 , wherein performing the schema information removal comprises removing inconsistent labels with property accesses.