System and method for analysis of a database proxy

• US 10,496,645 B1
• Filed: 12/30/2015
• Issued: 12/03/2019
• Est. Priority Date: 10/28/2013
• Status: Active Grant

• Current Assignee: Ignite ScaleArc Solutions, Inc.
• Original Assignee: Ignite ScaleArc Solutions, Inc.
• Inventors: Asner, Noam, Levari, Doron
• Primary Examiner(s): Conyers, Dawaune A
• Application Number:
  US14/985,277
• Time in Patent Office: 1,434 Days
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/2456 Join operations

Abstract

A system and method for processing a database query may include determining a set of tables referenced in a query; representing the set of tables by vertices of a graph; and, if the graph is incomplete, then determining the query is associated with a shard conflict. A system and method may determine a query is not associated with a shard conflict if, and only if, the graph is complete.

Claims

1. A method for analyzing join operations in a database proxy, the method comprising:

identifying a set of N relevant shard tables referenced in a query, the query received by the proxy, wherein N>

1;

representing the referenced shard tables as vertices of a graph having N vertices {S₀, . . . S_N-1}, each of the vertices representing a corresponding one of the referenced shard tables, SK_i being a key based upon which the shard table represented by S_i is distributed across shards, and SK_j being a key based upon which the shard table represented by S_j is distributed across shards;

for each pair of vertices S_i and S_j for (0<

=i<

=N−

1) and (0<

=j<

=N−

1) and i≠

j, inserting into the graph an edge connecting vertices S_i and S_j if and only if (a) SK_i is the same key as SK_j and (b) SK_i and SK_j are defined to have matching values or value ranges;

if and only if the graph contains a path comprising one or more edges from each vertex on the graph to all other vertices on the graph, determining the query will not cause a shard conflict, and

upon determining the query will not cause a shard conflict, consulting a distribution table to identify a shard storing the referenced shard tables; and

executing the query on the shard.

2. The method of claim 1 further comprising, for each pair of vertices S_i and S_j for (0<

=i<

=N−

1) and (0<

=j<

=N−

1) and i≠

j, consulting a distribution table to determine the key SK_i and its value or value range for table S_i and to determine the key SK_j and its value or value range for table S_j.

3. The method of claim 1 further comprising, if and only if the graph contains at least one pair of vertices for which no path of edges exist from one vertex of the pair to the other vertex of the pair, determining the query will cause a shard conflict.

4. The method of claim 3, further comprising:

splitting the query into a plurality of queries, and

executing the plurality of queries on a plurality of shards.

5. The method of claim 3, further comprising:

consulting a distribution table to identify relevant shards storing the referenced shard tables;

executing the query separately on each relevant shard;

receiving responses from the relevant shards; and

joining, merging or aggregating responses received from the relevant shards.

6. A system comprising:

a memory; and

a controller, the controller configured to;

identify N referenced shard tables referenced in a query received by the proxy, where N>

1;

representing the referenced shard tables as vertices of a graph having N vertices {S₀, . . . S_N-1}, each of the vertices representing a corresponding one of the referenced shard tables, SK_i being a key based upon which the shard table represented by S_i is distributed across shards, and SK_j being a key based upon which the shard table represented by S_j is distributed across shards;

for each pair of vertices S_i and S_j for (0<

=i<

=N−

1) and (0<

=j<

=N−

1) and i≠

j, inserting into the graph an edge connecting vertices S_i and S_j if and only if (a) SK_i is the same key as SK_j and (b) SK_i and SK_j are defined to have matching values or value ranges;

if and only if the graph contains a path comprising one or more edges from each vertex on the graph to all other vertices on the graph, determined the query will not cause a shard conflict;

consult a distribution table to identify a shard storing the reference shard tables upon determination that the query will not cause a shard conflict; and

executing the query on the shard.

7. The system of claim 6 wherein, for each pair of vertices S_i and S_j for (0<

=i<

=N−

1) and (0<

=j<

=N−

1) and i≠

j, the controller is further configured to;

Consult a distribution table to determined the key SK_i and its value or value range for table S_i, and to

determine the key SK_j and its value or value range for table S_j.

8. The system of claim 6 wherein, if and only if the graph contains at least one pair of vertices for which no path of edges exist from one vertex of the pair to the other vertex of the pair, determine the query will cause a shard conflict.

9. The method of claim 8, the controller further configured to:

split the query into a plurality of queries; and

execute the plurality of queries on a plurality of shards.

10. The system of claim 8, the controller further configured to:

consult a distribution table to identify relevant shards storing the referenced shard tables, execute the request separately on each relevant shard, receive responses from the relevant shards, and

join, merge or aggregate responses received from the relevant shards.