SYSTEM AND METHOD FOR ANALYSIS OF A DATABASE PROXY

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.

BACKGROUND OF THE INVENTION

Databases are used for storing digital data or information. In addition to storing data, modern database systems enable users and applications to search for, and retrieve stored data. Various systems and methods are used in order to improve and provide services. For example, database management systems (DBMSs) are designed to interact with users or applications and provide data storage and retrieval operations.

Horizontal partitioning is a database design or principal whereby rows of a table in a database are stored separately. As known in the art, a database shard is a partition in a database. Specifically, a shard is a horizontal partition in a database. Accordingly, an individual partition in a database may be referred to as a shard or a database shard. As known in the art, shards may be used to partition a large database across a number of servers or partitions. Generally, sharding is used in order to distribute or split data over multiple machines.

However, if a table is split across a number of shards, when retrieving data from the table, data from multiple shards needs to be joined, aggregated or merged.

SUMMARY OF EMBODIMENTS OF THE INVENTION

A system and method for analyzing database queries may include determining a set of tables referenced in a query; representing the set of tables as, or 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. A system and method may include storing a set of tables on at least one shard based on a common key. A system and method may include 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. A system and method may include distributing a first and second tables over at least two shards based on a common key. A common key used for distributing a first and second tables over at least two shards may be a table column.

A system and method may storing a first and second portions of a table on a respective first and second shards based on a respective first and second ranges of values of the common key. A system and method may determine that data from at least two shards is required in order to complete a record in a response for a query if at least one vertex in the graph is not connected to at least one other vertex in the graph. A method for determining a shard conflict may include distributing a plurality of tables across two or more shards according to a common key; receiving a query and determining a set of tables related to the query; representing the set of tables by vertices of a graph; and, if at least on 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.

A controller may be configured to determine a set of tables referenced in a query; a controller may be configured to determine which tables in the query are included in a set of relevant tables. A controller may represent the set of tables by vertices of a graph; and if the graph is incomplete then determine the query is associated with a shard conflict. A controller may be adapted to determine a query is not associated with a shard conflict if and only if the graph is complete.

It will be appreciated that for simplicity and clarity of illustration, elements shown in the figures have not necessarily been drawn accurately or to scale. For example, the dimensions of some of the elements may be exaggerated relative to other elements for clarity, or several physical components may be included in one functional block or element. Further, where considered appropriate, reference numerals may be repeated among the figures to indicate corresponding or analogous elements.

DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION

Reference is now made toFIG. 1, which shows a high-level block diagram of a system100according to embodiments of the present invention. As shown, system100may include a network110that may be, may comprise or may be part of, a private or public internet protocol (IP) network, or the internet, or a combination thereof. Additionally or alternatively, network110may be, comprise or be part of, a global system for mobile communications (GSM) network. For example, network110may include or comprise an IP network such as the internet, a GSM related network and any equipment for bridging or otherwise connecting such networks as known in the art.

As shown by blocks140and150, system100may include a plurality of storage systems. Storage systems140and150may include or may be any suitable storage systems. For example, storage systems140and150include one or more hard disk drives, removable or fixed storage units. In some embodiments, storage systems140and150may be, or include, network storage devices and may be geographically distant from one another or from other components of system100. Storage systems140and150may each include a server and/or a management system (e.g., a DBMS). As shown, storage system140may include shard145and storage system150may include shard155. Shards145and155may be shards as known in the art, e.g., associated with a partition or server in storage systems140and150respectively.

For the sake of clarity and simplicity, only one shard is shown in each of storage systems140and150, however, it will be understood that any number of shards may be included in storage systems140and150. Likewise, for the sake of clarity, only two storage systems (140and150) are shown, however, it will be understood that system100may include any number of storage systems that may be similar to storage systems140and150.

As shown by block120, system100may include a database front end unit120, referred to herein as DFEU120. As known in the art, a front end or proxy may provide an interface between a database and its clients. For example, a proxy may receive (or intercept) requests sent from a user or application to a database, examine the requests, possibly process the requests and either transfer the requests to the database or generate requests to the database based on received or intercepted requests. A proxy may receive responses from a database, process the responses and send the (possibly processed) responses to clients of the database. DFEU120may be a proxy or front end or it may be included in a proxy or front end. DFEU120may be any module, unit or component designed and configured to perform functionalities and methods as described herein. For example, in an embodiment, DFEU120is a computing device similar to computing device600including a memory and controller wherein the memory stores instructions that, when executed by the controller, cause the controller to determine whether or not a shard conflict exists. For example, a computing device similar to computing device600determines whether or not a shard conflict will be encountered when generating a response for a query.

A computing device similar to computing device600may perform analysis of join, merge or aggregation operations related to a database as described herein. DFEU120may receive requests or queries from users or applications, determine whether or not a shard conflict exists with relation to a request or query, process the requests or queries and interact with storage systems140and150in order to respond to queries or perform related tasks. For example, a request for data stored in storage systems140and150may be sent (e.g., from a user or application) to DFEU120over network110. DFEU120may process a request and, based on processing a request, DFEU120may interact with storage systems140and150in order to retrieve requested data or perform other operations. DEFU120may send or otherwise provide retrieved or requested data to the requesting entity.

As shown, system100may include, or be connected to, a client computing device130. Client computing device130may include or may be, for example, a server, a personal computer or a desktop computer, a mobile or laptop computer. In some embodiments, client computing device130may be a network device, a smartphone or a mobile phone or any other suitable computing device capable of at least communicating with DEFU120over network110. Client computing device130may be any suitable computing device configured or adapted to enable a user or an application to interact with DEFU120.

As discussed, if a table is split into portions, and portions of the table are stored on more than one shard, then, in order to retrieve data from the table, a plurality of shards may need to be accessed. Accordingly, a system may need to join, aggregate or merge data portions retrieved from a plurality of shards in order to provide the requested data. In other cases, if data from two tables is needed in order to complete a request for data and each of the two tables is stored on a different shard then two shards need to be accessed and data retrieved from the two shards needs to be merged, aggregated or joined. Clearly, the more shards involved in the process, the greater the challenge.

Reference is made toFIG. 2, showing a distribution of tables across shards. As shown, in an exemplary case, tables215,216,225and226which are tables related to departments and employees in an organization, are stored on shards210and220.

As shown, table215stored on shard210is a department table that includes a column with a department identification number (labeled “Dep. ID”), where an identification number of a department is stored. As shown, table215further includes a department name column (labeled “Dep. NAME”) and an additional column (labeled “No. of employees”) for the number of employees in each department. It will be understood that other or additional columns may be included in table215. Table225stored on shard220is similar to table215. Other types of tables and other data may be stored.

As shown, table216stored on shard210is an employee table. As shown, table216includes a column for employee identification (labeled “Employee ID”), a column with employee name (labeled “Employee NAME”) and a column that indicates the department to which the employee belongs (labeled “Dep. ID”). For example, as shown, employee Jack belongs to the operations department (Dep. ID “2”). Table226stored on shard220is similar to table216.

Queries or requests from a database typically involve some logical relations between entities. For example, a user may request the list (e.g., names of employees) of all employees in the management department. Using the tables and shards shown byFIG. 2, a system may have to retrieve data from both shards210and220in order to generate a response. For example, having found the employee named David in table226on shard220, a system now needs to access table215on shard210in order to find the name of the department with department ID1(the marketing department in the current example).

As referred to herein, a shard conflict exists if, for at least one record or other object in a response to a query, data from at least two shards must be retrieved. For example and as described, a response or a result record may need to include an employee with the “Name” of the employee's department name. If the result record can be composed using data in a single shard then, as referred to herein, no shard conflict exists. However, if, for example, a cartesian product (and possibly filtering of the cartesian product result) of data from two or more shards are required then a system may determine a shard conflict exists. For example, when distributing tables over shards as shown inFIG. 2, to generate a record that includes both an employee and the name of the relevant department, a system may need to retrieve both table215and table225, generate a cartesian product as known in the art to produce a set of products and then filter out all products that do not match a criteria.

For example, since it may not be known in advance which employee in tables215and226belongs to which department in table215, a cartesian product would include a set that includes all possible combinations of all employees and all departments. The resulting (typically very large) set may subsequently need to be processed in order to filter out irrelevant products or identify relevant ones.

As discussed, there typically exists some logic or rational with respect to queries that require joining, aggregating or joining data items from two or more shards. According to an embodiment of the invention, a plurality of tables (or other constructs in a database or shards) are distributed across two or more shards according to a common key. When distributing a plurality of tables based on the same key, the key is referred to herein as a common key to indicate the key is common to the plurality of tables. For example, instead of storing tables215,216,225and226on shards210and220as shown inFIG. 2, a different arrangement may be used.

Reference is made toFIG. 3, showing a distribution of tables across shards according to embodiments of the invention. As shown by tables315,320,335and340, tables215,216,225and226may be distributed on shards310and330based on a common (or same) key. For example, shards310and330may be stored on storage systems140and150respectively as shown by shards145and155.

In an exemplary case or embodiment, the department identification (Dep. ID), key or value may be used in order to split a department table and store the resulting tables on shards310and330. As shown, shard310may store a department table315that may include departments with a department identification in a specific range, e.g., one to two (1-->2). As shown, an employees table320in shard310may include employees belonging to departments in departments table315. For example, only employees belonging to departments with an identification key value in the specific range (1-->2) are included in employees table320stored on shard310. Similarly, shard330includes a departments table335that includes departments having a department key value or identification number that is in the range of three to four (3-->4) and shard330also includes an employees table340that includes employees associated with the respective range of departments. For example and as shown, employees table340includes employees that belong to departments having a department identification value in the range of three to four (3-->4).

Otherwise described, in this example, employees and departments are shard tables, sharded by department identification. Any other key (or column in a table) may be used for splitting tables as exemplified byFIG. 3. Any number of tables may be split and distributed or re-distributed across a plurality of a respective number of shards based on a common key or column as described herein. For example, an organization may maintain an expenses table that lists expenses per departments and per employees. In an embodiment, an employees table, departments table and expenses table may be distributed across a number of shards based on a common key (e.g., a department identification). Accordingly, details related to the employees and expenses of a specific department may be stored (and found) in the same shard that stores details of the specific department.

As shown by table350, an embodiment may include a distribution table or list. For example, DFEU120may store and maintain a table or list similar to table350on storage140. As shown by table350, a distribution table or list may include, for each table, a key used for distributing the table and an identification of the table. Other entries in a distribution list may be a key value or range of values, an identification of shards used for storing the table and the like. For the sake of simplicity, names of tables are shown under table identification in table350, however, it will be understood that any identification may be used, e.g., an internal identification used by DFEU120. Similarly, as shown, entries in the key column in table350are “Dep. ID”, in accordance with examples described herein, however, it will be understood that any identification of a key may be used, e.g., an identification of keys as generated by DFEU120.

For example, a distribution list or table maintained by DFEU120indicates that a common key to be used is the department identification in the departments table. Although not shown by table350, a distribution table may further indicate that the range of 1 to 2 is stored on shard310in tables315and320(depending on whether it is a department or employee), the range of 3 to 4 is stored on tables335and340shard330and so on. For example, two entries in table350may be related to departments of an organization and may include a respective first and second key ranges and a respective first and second shards. Accordingly, when new data is to be added to a table, DFEU120may consult a distribution table and determine which table on which shard is to be updated with the new data.

For example, in the exemplary scenario described herein with reference toFIG. 3, if a new employee is to be added to the management department, DFEU120may consult the distribution table in order to find the shard and table for the given key value (4 in this case) and determine that the new employee is to be added to table340on shard330since these are the table and shard for storing entries using the common key of department identification as described.

Embodiments of the invention may examine a query, request or any interaction with a database and determine whether or not a shard conflict is associated with the request, query or interaction. For the sake of simplicity, the term query is used herein to refer to any message or request received, from a client (that may be a user or an application) by a database.

In an embodiment, DFEU120examines a query and determines whether or not the query causes or generates a shard conflict. If a shard conflict is determined, DFEU120may perform a number of actions. For example, if a shard conflict is determined, the relevant query may be rejected or it may be passed on to an entity for further prosecution. In an embodiment, if a shard conflict is identified then the query may be sent to all relevant shards, responses from all relevant shards may be collected and a response to the query may be generated by joining, merging or aggregating records from the responses received from the relevant shards.

For example, upon detecting a shard conflict, DFEU120(or another unit to which DFEU120may send a request that causes a shard conflict) may split a query into a number of queries which are then executed on a number of shards. By executing a query on a shard, it is meant performing an operation based on the query with respect to data in the shard. For example, if the query includes searching for a data element then executing the query on a shard includes searching for the element in data stored in the shard.

Results from a number of shards may then be aggregated or joined as known in the art. Any system or method for splitting a query (after DFEU120determines that a shard conflict exists with respect to the query) may be used without departing from the scope of the invention.

For example, if a shard conflict is determined or identified, a query or request may be executed separately on each relevant shard and results from a plurality of prosecutions on a plurality of shards may be unified to produce a response.

If DFEU120determines no shard conflict is related to a query (or, as described herein, If DFEU120determines no shard conflict exists), DFEU120may identify the relevant shard or shards and send the query to the relevant shards for further processing. For example, using entries in a table similar to table350described herein, DFEU120determines which shard stores the relevant table and sends the query to the shard for prosecution.

It will be noted that a request may not cause a shard conflict while still requiring accessing multiple shards. For example, if data is distributed as shown inFIG. 3, a query for the list of ALL departments may require accessing more than one shard but no aggregation (or joining) of data from multiple shards is required in order to complete (or produce or generate) records in the response. On the other hand, a statement may request data for a specific department and still cause a shard conflict. For example, a query for ALL employees of “Marketing” when distribution is as shown inFIG. 2will cause a shard conflict since, in order to determine the name of departments for employees found in table226on shard220, data from table215on shard210needs to be used.

As described, DFEU120may examine a query and determine whether or not all tables or other data constructs referenced in the query or relevant to the query are stored on the same shard. In an embodiment, DFEU120examines a query and determines which tables in the query are the set of relevant tables by identifying the set of tables which are referenced by the query or which are relevant to the query. For example, DFEU120identifies a “FROM” clause in a query. As known in the art, a “FROM” clause in a structured query language (SQL) indicates the tables from which data is requested. Accordingly, DFEU120may examine a query and may determine the tables that need to be accessed in order to generate a response for the query. It will be understood that DFEU120may be configured to parse any applicable query or request and that any method of identifying the relevant tables in a database may be used by embodiments of the invention.

In the discussion below, a query is related to, includes or references, a set of shard tables denoted here by {S0, . . . , Sn-1}, and, for each 0<=i<=N−1, SKiis the key based on which table Siis distributed across shards. For example, shard table Simay be table215and SKimay be the department identification number or column as described herein. For example, in an embodiment, a key is a column number.

DFEU120may represent the query as a graph where the tables are represented as vertices on the graph and for each binary predicate Si.SKi=Sj.SKjthere's an edge between Siand Sj. The binary predicate Si.SKi=Sj.SKjas used herein is generally the statement the key SKiof table Siis the same as the key SKjof table Sj.

From transitivity, DFEU120may determine that if, Si.SKi=Sj.SKjand, in addition, Sj.SKj=Sm.SKm, then there are edges between Sjand Smand between Sito Sm. To determine a shard conflict, DFEU120may check or determine whether or not the graph is complete. As described herein, in an embodiment, if DFEU120determines the graph is complete then DFEU120further determines no shard conflict exists with respect to the relevant query. In an embodiment, DFEU120determines a query is not associated with a shard conflict if, and only if, the graph is complete.

As referred to herein, a graph is complete if each vertex on the graph is connected to all other vertices on the graph. As referred to herein, two vertices on a graph are connected if and only if there is an edge between them.

In an embodiment, DFEU120determines whether or not a graph is complete. For example, DFEU120determines a graph is complete if there exists a path (comprising one or more edges) from any vertex on the graph to any other vertex on the graph. In an embodiment, DFEU120determines the graph is incomplete if, for at least one vertex on the graph, there exists no path of edges to another vertex on the graph.

In an embodiment, if all vertices representing tables on a graph are connected then DFEU120may determine no shard conflict exists with relation to the query. If the graph is incomplete, that is, at least one vertex on the graph is not connected by a line or edge (or a plurality of edges as described) to at least one other vertex on the graph, then DFEU120determines that the graph is incomplete and a shard conflict exists.

For example, in the case shown byFIG. 2, tables215,216,225and226are not distributed by a common or same key and, accordingly, if tables215,216,225and226are relevant to a query, then DFEU120determines a shard conflict exists (e.g., both shards220and210need to be accessed). In another case, e.g., as shown byFIG. 3, if the relevant tables are the employees and department tables, DFEU120identifies that these two tables are distributed across shards using the same or common key (the department ID as described) and therefore determines no shard conflict exists with respect to the query.

Reference is made toFIGS. 4A,4B,4C and4D that graphically depict example graphs, vertices and edges according to embodiments of the invention. As shown byFIG. 4A, the relevant tables in a query are S1and S2and if the keys used to distribute tables S1and S2are the same (as indicated by S1.SK1=S2.SK2) then DFEU120may determine an edge exists between, or connects, the two vertices as shown and no shard conflict exists. Otherwise described, in this example and as shown byFIG. 4A, selecting * from S1 and S2 where S1.SK1=S2.SK2 does not result a shard conflict as indicated by the line connecting S1 and S2 (where “*” may be any element in S1 and S2).

As shown byFIG. 4B, since the key used for S1 is not the same as the one used for S2 (e.g., when the parameter or key used for distributing S1 over shards is not the same parameter or key used for distributing S2 over shards) no edge (or connection) exists between the vertices and therefore, in this example, DFEU120determines a shard conflict exists. Otherwise described, in this example and as shown byFIG. 4Bselecting * from S1 and S2 where S1.SK1=S2.col will generate a shard conflict as indicated by an absence of a line connecting S1 and S2

As exemplified byFIG. 4C, since the keys used for tables S1, S2and S3are the same (as indicated by (S1.SK1=S2.SK2) and (S2.SK2=S3.SK3), the graph is complete, edges connect all vertices and therefore, in this case, DFEU120may determine no shard conflict arises. Note that if the key of tables S1 and S2 are the same and the keys of tables S2 and S3 then DFEU120may determine that the keys of S1 and S3 are the same as well. Otherwise described, in this example and as shown byFIG. 4C, selecting * from S1 join S2 on (S1.SK1=S2.SK2) join S3 on (S2.SK2=S3.SK3) does not generate or cause a shard conflict as indicated by the lines connecting S1, S2 and S3.

As shown byFIG. 4D, if only some of the vertices are connected DFEU120may determine a shard conflict exists. For example, as shown byFIG. 4D, vertex S4 is not connected to vertex S2, therefore, the graph shown inFIG. 4Dis incomplete. For example, although the keys used for tables S1and S2are the same, and the keys used for tables S3and S4are the same, not all vertices are connected because the key used for tables S1 and S2 is not the same as the key used for tables S3 and S4. Accordingly, in the case shown byFIG. 4CDFEU120may determine a shard conflict exists. Otherwise described, in this example and as shown byFIG. 4Dselecting * from S1 join S2 on (S1.SK1=S2.SK2) join S3 join S4 on (S3.SK3=S4.SK4) will cause or generate a shard conflict, for example, as indicated by absence of lines connecting S3 and S2 with S1 and S2.

Reference is made toFIG. 5showing pseudo code according to embodiments of the invention. Code similar to the pseudo code shown inFIG. 5may be used by DFEU120in order to determine whether or not a shard conflict as described herein is expected when responding to, or otherwise processing, a query. As common in the art, the patterns “//”, “/*” and “*/” are used inFIG. 5to indicate or denote comments in the code. Other languages and other specific code may be used.

Generally, for “N” distributed tables, each table may be assigned a unique identification or index, accordingly, the pseudo code shown inFIG. 5is for tables numbered 0 to N−1. For example, when determining which tables are referenced in a query, DFEU120also may determine the number of tables and sets “N” to the correct number. In an embodiment, DFEU120associates each of the tables identified as related to the query with a unique value or number selected from values of 0 to (N−1).

Blocks are used in the pseudo code shown inFIG. 5to represent vertices in a graph, where vertices represent tables as described herein. Any suitable object may be used to implement blocks, e.g., a memory that stores a value.

In an embodiment, each block represents one or more vertices. In an embodiment, initially or at a first step, each block is a singleton. As known in the art, a singleton is a mathematical expression that describes a group consisting one element, in the present example, initially, a singleton describes a group consisting a single vertex. Accordingly, initially, a graph includes N vertices and no edges since no vertices are yet connected by edges.

For example, initially, the block consisting or representing table 1 is the singleton {1} and the block consisting or representing table n−3 is the singleton {n−3}. Accordingly, initially, for any vertexi, where: 0<=i<=N−1, the vertex is contained in (or represented by) the block {i}.

In an embodiment, at any given point of the process, blocks are orthogonal (e.g., a logical intersection of any two blocks is an empty group) and a unification of all blocks contains or represents all vertices.

As shown, if it is determined that a first and second tables (e.g., table “i” and table “j” as shown) are distributed using the same key then the blocks containing or representing the tables are joined by unifying them into one block. In one embodiment, unifying, joining or merging a first and second blocks into a third block connects two vertices groups respectively represented by the first and second blocks. As a result of merging or unifying a first and second blocks into a third block, the third block now represents the two vertices groups previously represented by the first and second blocks.

In an embodiment, blocks represent unconnected vertices or parts of the graph. For example, following the creation of the third block as described, no edges are determined between any blocks on the graph, e.g., between the third block and any other blocks representing vertices on the graph. Accordingly, in an embodiment, blocks represent unconnected parts of graph.

Accordingly and as further shown, if, at the end of the process, only one block remains then it is determined that no shard conflict exists. For example and as shown, the pseudo code inFIG. 5will return one (“1”) that may be interpreted as “TRUE” if only one block remains, indicating that no shard conflict exists with respect to a query related to the N tables identified. As shown, the pseudo code inFIG. 5will return zero (“0”) that may be interpreted as “FALSE” if more than one block remains, indicating that a shard conflict exists, or is to be expected, with respect to the query.

Blocks as described may be realized or implemented using any suitable method or means. For example, in an embodiment, each block is a set of N bits, each bit identified by its index and, in order for a block to contain or represent table “i”, bit “i” in the block is set. Accordingly, in such specific implementation or embodiment, in order to unify, join or merge two blocks representing tables “i” and “j”, a new block that has bits “i” and “j” set is created and the new block replaces the two blocks previously used for representing tables “i” and “j”. Accordingly, when identifying two tables distributed using the same key, the number of blocks is reduced by one since a single block is now used to represent both tables.

It will be understood that any applicable method or system may be used in order to represent vertices of a graph, determine edges connecting vertices, and determining whether or not a shard conflict is expected for a query by without departing from the scope of the invention. For example, other methods for representing vertices may use objects other than sets of bits as described herein, may use other methods for joining objects when an edge is identified etc.

Special cases may need to be addressed. For example, if, based on analyzing a query, DFEU120determines that an “OR” condition (as further described below) exists then DFEU120may analyze a number of relations between tables and determine whether or not a shard conflict exists or is to be expected based on an analysis of a number of relations or branches. For example, an “OR” condition may be in the form of: select an employee from tables S1, S2and S3where the same key is used for distributing tables S1and S2as described herein and, in addition, the same key is used for distributing tables S1and S3or the key used for distributing table S2is some column or key of S3. For example, using the terminology used herein, such condition or criteria may be expressed by:

Select employee from S1, S2, S3 where S1.SK1=S2.SK2 AND ((S2.SK2=S3.SK3) OR (S2.SK2=S3.Col)). In this case, two branches or conditions that DFEU120may check are:

2) S1.SK1=S2.SK2 AND S2.SK2=S3.Col. where S3.Col may be any column of S3 as specified in a query.

Accordingly, DFEU120may check the two conditions above as described herein and, only if both or all conditions are satisfied then DFEU120may determine that no shard conflict exists, otherwise, DFEU120may determine a shard conflict exists or is to be expected. Any other logical terms that may appear in a query (e.g., “if”, “else” and the like) may be parsed and analyzed by DFEU120and all logical branches or conditions may be examined as described herein. In an embodiment, DFEU120checks all possible or logical branches in a query, generates a set of logical statements and only if all logical statements indicate that no shard conflict exists then DFEU120determines no shard conflict is associated with responding to the query or request. Generally, DFEU120may ignore non-sharded tables except for special cases. For DFEU120may be configured to server queries or requests from a master or global table using a predefined logic or protocol.

Reference is made toFIG. 6, showing high level block diagram of an exemplary computing device according to embodiments of the present invention. Computing device600may include a controller605that may be, for example, a central processing unit processor (CPU), a chip or any suitable computing or computational device, an operating system615, a memory620, a storage630, an input devices635and an output devices640. In an embodiment, DFEU120includes components included in computing device600.

Operating system615may be a commercial operating system. Memory620may be or may include, for example, a Random Access Memory (RAM), a Dynamic RAM (DRAM), a Flash memory, or other suitable memory units or storage units. Memory620may be or may include a plurality of, possibly different memory units.

Executable code625may be any executable code, e.g., an application, a program, a process, task or script. Executable code625may be executed by controller605. For example, executable code625may be an application that performs operations described herein with respect to DFEU120. Executable code625may be an application that performs the methods described herein. Controller605may be configured to perform methods described herein for example by executing code or software, for example stored in memory620.

Where applicable, executable code625may carry out operations described herein in real-time. Computing device600and executable code625may be configured to perform methods described herein in real-time. For example, computing device600and executable code625may update, process and/or act upon information at the same rate the information, or a relevant events, are received. For example, in an embodiment, computing device600process queries and determines whether or not a shard conflict exists at the rate the queries are received from a plurality of client computing devices130.

In some embodiments, more than one computing device600may be used. For example, a plurality of computing devices that include components similar to those included in computing device600may be connected to a network and used as a system. For example, a plurality of computing devices600may be used in order to deploy a plurality of DFEU120units, e.g., when scaling up a database by adding storage systems similar to storage systems140and150.

Storage630may be or may include, for example, a hard disk drive or other suitable removable and/or fixed storage units. Content may be stored in storage630and may be loaded from storage630into memory620where it may be processed by controller605. Input devices635may be or may include a mouse, a keyboard, a touch screen or pad or any suitable input device. Output devices640may include one or more displays, speakers and/or any other suitable output devices.

Any applicable input/output (I/O) devices may be connected to computing device600as shown by blocks635and640. For example, a wired or wireless network interface card (NIC).

Embodiments of the invention may include an article such as a computer or processor non-transitory readable medium, or a computer or processor non-transitory storage medium, such as for example a memory, a disk drive, or a USB flash memory, encoding, including or storing instructions, e.g., computer-executable instructions, which, when executed by a processor or controller, carry out methods disclosed herein. For example, a storage medium such as memory620, computer-executable instructions such as executable code625and a controller such as controller605.

A system according to embodiments of the invention may include components such as, but not limited to, a plurality of central processing units (CPU) or any other suitable multi-purpose or specific processors or controllers, a plurality of input units, a plurality of output units, a plurality of memory units, and a plurality of storage units. In some embodiments, a system may include or may be, a personal computer, a desktop computer, a mobile computer, a laptop computer, a notebook computer or any other suitable computing device. Unless explicitly stated, the method embodiments described herein are not constrained to a particular order or sequence. Additionally, some of the described method embodiments or elements thereof can occur or be performed at the same point in time.