System and method for analysis of a database proxy

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.

1 . A method for analyzing join operations in a database proxy comprising plurality of tables, the method comprising:
 identifying a set of N relevant shard tables referenced in a query, the query received by the proxy;   respectively assigning a set of indices {S 0 , . . . , S N-1 } to the set of relevant shard tables, wherein the values of the indices are between 0 and N−1;   representing the set of relevant tables as vertices of a graph;   for (0<=i<=N−1) and (0<=j<=N−1):   denoting SK i  and SK j  as the keys based on which each respective table S i  and S j  is distributed across shards;   defining an edge between vertices S i  and S j  for each binary predicate S i .SK i =S j .SK j , wherein key SK i  of table S i  equals key SK j  of table S j ;   defining the graph is complete if there exists one or more edges from any of said vertices on the graph to any other vertex on the graph; and   if the graph is incomplete then determining the query is associated with a shard conflict.   
     
     
         2 . The method of  claim 1 , comprising determining the query is not associated with a shard conflict if and only if the graph is complete. 
     
     
         3 . The method of  claim 1 , comprising storing the set of tables on at least one shard based on a common key. 
     
     
         4 . The method of  claim 1 , comprising determining a first and a third vertices are connected if the first and a second vertices on the graph are connected and the second and the third vertices on the graph are connected. 
     
     
         5 . The method of  claim 1 , comprising distributing a first and second tables over at least two shards based on a common key. 
     
     
         6 . The method of  claim 3 , wherein the common key is a column. 
     
     
         7 . The method of  claim 3 , comprising storing a first and a second portion of a table on a respective first and a second shard based on a respective first and second ranges of values of the common key. 
     
     
         8 . The method of  claim 1 , wherein if at least one vertex in the graph is not connected to at least one other vertex in the graph then determining that data from at least two shards is required in order to complete a record in a response for the query. 
     
     
         9 . A method for determining a shard conflict, the method comprising:
 distributing a plurality of tables across two or more shards according to a common key;   receiving a query and determining a set of N tables related to the query;   respectively assigning a set of indices {S 0 , . . . , S N-1 } to the set of N tables, wherein the values of the indices are between 0 and N−1;   representing the set of tables by vertices of a graph;   for (0<=i<=N−1) and (0<=j<=N−1):   denoting SK i  and SK j  as the keys based on which each respective table S i  and S j  is distributed across shards;   defining an edge between vertices S i  and S j  for each binary predicate S i .SK i =S j .SK j , wherein key SK i  of table S i  equals key SK j  of table S j ;   defining the graph is complete if there exists one or more edges from any of said vertices on the graph to any other vertex on the graph; and   if at least one vertex in the graph is not connected to at least one other vertex in the graph then determining the query is associated with a shard conflict.   
     
     
         10 . A system comprising:
 a memory; and   a controller, the controller configured to:   determine a set of N, which are referenced in a query, are a set of relevant tables;   respectively assign a set of indices {S 0 , . . . , S N-1 } to the set of N tables, wherein the values of the indices are between 0 and N−1;   represent the set of N tables by vertices of a graph;   for (0<=i<=N−1) and (0<=j<=N−1):   denote SK i  and SK i  as the keys based on which each respective table S i  and S j  is distributed across shards;   define an edge between vertices S i  and S j  for each binary predicate S i .SK i =S j .SK j , wherein key SK i  of table S i  equals key SK j  of table S j ;   define the graph is complete if there exists one or more edges from any of said vertices on the graph to any other vertex on the graph; and   if the graph is incomplete then determine the query is associated with a shard conflict.   
     
     
         11 . The system of  claim 10 , wherein the controller is adapted to determine the query is not associated with a shard conflict if and only if the graph is complete. 
     
     
         12 . The system of  claim 10 , wherein at least some tables included in the set of tables are stored on at least one shard based on a common key. 
     
     
         13 . The system of  claim 10 , wherein the controller is adapted to determine a first and a third vertices are connected if the first and a second vertices on the graph are connected and the second and the third vertices on the graph are connected. 
     
     
         14 . The system of  claim 10 , wherein at least a first and a second tables related to the query are distributed over at least two shards based on a common key. 
     
     
         15 . The system of  claim 12 , wherein the common key is a column. 
     
     
         16 . The system of  claim 12 , wherein a first and second portions of a table are stored on a respective first and second shards based on a respective first and second ranges of values of the common key. 
     
     
         17 . The system of  claim 10 , wherein the controller is adapted to determine that data from at least two shards is required in order to complete a record in a response for the query if at least one vertex in the graph is not connected to at least one other vertex in the graph. 
     
     
         18 . The system of  claim 10 , wherein the controller is adapted to distribute at least some of the tables across two or more shards according to a common key.