System and method for analysis of a database proxy

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 0 , . . . 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 0 , . . . 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.