Patent Publication Number: US-10311054-B2

Title: Query data splitting

Description:
TECHNICAL FIELD 
     The present disclosure relates to databases, and more specifically to determining a specific query to send to a database. 
     BACKGROUND 
     Databases are widely used in various types of business and applications. In recent years, the number of data objects that can be and are stored in a database has increased exponentially, which causes a problem when performing federated data searches on the data objects in the database because it consumes too much time and resources to perform the search. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Aspects and implementations of the present disclosure will be understood more fully from the detailed description given below and from the accompanying drawings of various aspects and implementations of the disclosure, which, however, should not be taken to limit the disclosure to the specific aspects or implementations, but are for explanation and understanding only. 
         FIG. 1  depicts a block diagram of a network architecture in which implementations of the present disclosure can operate. 
         FIG. 2  illustrates an example of a query tree in accordance with some implementations of the present disclosure. 
         FIG. 3  shows a flow diagram illustrating an example of query data splitting in accordance with some implementations of the present disclosure. 
         FIG. 4  shows a diagrammatic representation of a machine in the form of a computer system, in accordance with one example. 
     
    
    
     DETAILED DESCRIPTION 
     Methods and systems for providing query data splitting are described. 
     In a federated data environment in which data from disparate sources is aggregated into a virtual database, processing a large number of small queries results in inefficient use of resources and slow performance. The present disclosure includes a method and system for optimization for data federation. In one example, the method detects queries that will return similar data (i.e., the method detects whether one query is a generalized version of another). The method also analyzes statistics from query executions. Based on the analysis, the results of general queries can be exploited to the benefit of the less general queries. 
       FIG. 1  depicts a block diagram of a network architecture  100  in which implementations of the present disclosure can operate. The network architecture  100  includes a query data splitting system  120  communicably coupled to a client device  110  and a database  130  via network  102 . Network  102  may be a private network (e.g., a local area network (LAN), a wide area network (WAN), intranet, or other similar private networks) or a public network (e.g., the Internet). Query data splitting system  120  may include one or more machines such as server computers, desktop computers, or any other computing device. 
     The client device  110  may be personal computers (PC), laptops, mobile phones, tablet computers, or any other computing devices. The client device  110  may run an operating system (OS) that manages hardware and software of the client device  110 . An application or a daemon (not shown) may run on the client device  110  (e.g., on the OS of each client device) to enable a user to submit a query and receive the results of the query. 
     Database  130  may be implemented on one or more machines, such as server computers, desktop computers, or any other computing device. An example of the database  130  is a persistent storage that is capable of storing data that is collected from various data sources including local and remote computing devices such as desktop computers, laptop computers, handheld computers, server computers, gateway computers, mobile communications devices, cell phones, smart phones, or similar computing device. In some embodiments, database  130  might be a network-attached file server, while in other embodiments administration database  130  might be some other type of persistent storage such as an object-oriented database, a relational database, and so forth. The database  130  may be part of the query data splitting system  120  or coupled to the query data splitting system  120  directly or via a network. In an example, the database  130  can be a relational database management system (RDBMS) used for the storage of information used for financial records, manufacturing and logistical information, personnel data, and the like. In an example, the database  130  can include data federation processing logic to enable a search for and retrieval of the query results. 
     The query data splitting system  120 , of examples of the disclosure, can receive queries from the client device  110 , analyze the queries, and determine how the queries relate to each other. For example, the query data splitting system  120  may oversee and manage the analysis of the queries and determine a specific query to send to the database  130  to obtain a result for the query. The query data splitting system  120  may be implemented on one or more machines, such as server computers, desktop computers, or any other computing device. 
     The query data splitting system  120  may include a cache  128 , a query tree engine  122 , a replicator  124 , and a router  126 . The query data splitting system  120  can receive queries from one or more client devices  110 . The queries can be analyzed by the query tree engine  122  to determine the relationship between the queries and to determine which specific query to send to the database  130  to obtain query results via the router  126 . 
     In another example, the query data splitting system  120  can determine whether to send a specific query to either the database  130  or to the cache  128  via the router  126 . The cache  128  is random access memory that is located closely to the processing device in the computing system that implements the query data splitting system  120 . In an example, the cache  128  is on the same chip as the processing device. The cache  128  enables the query data splitting system  120  to access the data stored in cache more quickly than it would to access the data stored in the database  130 . 
     The replicator  124  is a component of the query data splitting system  120 . The replicator  124  can receive a query result from the database  130  and replicate the result. The router  126  can route the replicated result to be stored in the cache  128  for quick access. 
     The query tree engine  122  can create a distinctive node for each unique query and determine whether the query is either the same as another query, a parent or superset of the other query, a child or a subset of the other query, or independent of the other query. Table 1 shows an example of 4 different queries and the relationships between the queries. 
     
       
         
           
               
             
               
                 TABLE 1 
               
             
            
               
                   
               
               
                 sample queries 
               
            
           
           
               
               
               
            
               
                 ID 
                 Query 
                 Note 
               
               
                   
               
               
                 1 
                 select * from BOOKS 
                 The most general query 
               
               
                 2 
                 select * from BOOKS where 
                 Only newer books 
               
               
                   
                 published &gt; 1999 
               
               
                 3 
                 select * from BOOKS where 
                 Subset of newer books 
               
               
                   
                 published &gt; 1999 
                 (subset of data returned by 
               
               
                   
                 AND and genre=‘sci-fi’ 
                 query 2) 
               
               
                 4 
                 select * from BOOKS where 
                 Only a subset of query 1 
               
               
                   
                 published &lt;= 1999 
               
               
                   
               
            
           
         
       
     
     As shown in Table 1, the first query (ID #1) is the most general query of the four queries. This query selects from all books. The second query (ID #2) selects newer books, in this example, the second query selects only books that are published later than 1999. As such, the second query is a subset of the first query, and the first query is a superset of the second query. This can also be referred to as the second query is a child of the first query or the first query is a parent of the second query. 
     The third query (ID #3) as illustrated in Table 1 selects only books that are published later than 1999 having a genre of science fiction or “sci-fi”. Thus, the third query is a subset or a child of the second query. 
     The fourth query (ID #4) selects books that were published during or before 1999. Accordingly, the fourth query is a subset or child of the first query but is independent of the second and third queries. After the query tree engine  122  determines how the queries relate to each other, the query tree engine  122  can construct a query tree. 
       FIG. 2  illustrates an example of a query tree  200  in accordance with some implementations of the present disclosure. The relations between the queries can be described using a graph called a “query tree.” 
     In the example query tree  200  as shown in  FIG. 2 , node  1   210  relates to the first query (ID #1) of Table 1, node  2   220  relates to the second query (ID #2), node  3   230  relates to the third query (ID #3), and node  4   240  relates to the fourth query (ID #4). The example query tree  200  illustrates that node  1   210  is a parent of node  2   220  and of node  4   240 , while node  2   220  is a parent of node  3   230 . The example query tree  200  also illustrates a time window  250 , which is used to measure how many times each query is run or submitted within a certain window of time. The window can be any finite duration of time. In the example of query tree  200 , the time window is 10 minutes. The time window can be configurable and variable and can be tuned based on admins experience and can also depend on the available size of the query result warehouse. 
     In this example, the query tree engine  122  can measure a frequency of a certain query within the time window  250 . The frequency of a query is the number of times the query was received by the query tree engine  122  from one or more clients during the time window. In the example query tree  200 , the frequency of node  1   210  (which relates to the first query or ID #1 of Table 1) within the 10 minute window of time window  250  is “1” as denoted by “F1”. Stated differently, the first query was received one time within the 10 minute time window. Likewise, the frequency of node  2   220  is 2 as denoted by “F2”, the frequency of node  3   230  is 1 as denoted by “F1”, and the frequency of node  4   240  is 1 as denoted by “F1”. 
     The fact that sample queries are being submitted repeatedly to the query data splitting system  120  is quite a natural process. For example, a query can be embedded in an enterprise information system and thus can be run repetitively. 
     The query tree  200  also includes an average size of the result set by the query represented by the node. For example, the result set from node  1   210  or the first query or ID #1 of Table 1 is 10 kilobytes in size, the result set from node  2   220  or the second query is an average of 7 kilobytes in size, the result set from node  3   230  or the third query is 2 kilobytes in size, and the result set from node  4   240  or the fourth query is 3 kilobytes in size. 
     In the example query tree  200 , suppose the fourth query is received again by the query data splitting system  120  from a client device  110 . The query data splitting system  120  can look into the cache  128  to see, whether the parent node of node  4  (node  1 ) has the query results stored. If the answer is yes, the query data splitting system  120  can run the query  4  on the stored results of query  1  from the cache  128 . 
     In furtherance to this example, assume that the query results data for node  1  are not in the cache  128 . In this case the query data splitting system  120  has multiple options. One option is that the query data splitting system  120  can run query  4  directly on the database  130 . Another option is that the query data splitting system  120  can run query  1  on the database  130 . The query data splitting system  120  can decide what is better. For example, if the query data splitting system  120  runs the query  1  on the database  130  and the result are stored into the cache  128 , then the query data splitting system  120  can run successive query  4 &#39;s on result stored from query  1  from the cache  128 . The benefit of this approach is that the stored results of query  1  will also be available to query  2  and in turn to query  3 . 
     The query data splitting system  120  can add a node that represents a new query to the query tree  200  and recompute the statistics in view of the newly added node. After the new node is added to the query tree  200 , the query tree engine  122  can find the ancestors and children of the new query node. 
       FIG. 3  shows a flow diagram illustrating a method  300  for implementing query data splitting in accordance with some implementations of the present disclosure. Method  300  may be performed by processing logic that may comprise hardware (e.g., circuitry, dedicated logic, programmable logic, microcode, etc.), software (such as instructions run on a processing device), firmware, or a combination thereof. In one implementation, method  300  is performed by the query data splitting system  120  described with respect to  FIG. 1 . 
     Method  300  begins at block  310 , where the query data splitting system  120  receives a first and second query from, for example, a client device  110 . Then, at block  320 , the query data splitting system  120  can determine that the second query is a subset of the first query. In one example, the query data splitting system  120  can determine that the second query is a subset of the first query by finding matching nodes in a graph discussed above. If the graph does not include a matching node for at least one of the two queries, the query data splitting system  120  can evaluate both queries to determine whether the second query is a subset of the first query, and then add a node to the graph for each query that does not have a match in the graph. For example, the query data splitting system  120  can determine a first set of tables, a first set of columns, and a first set of conditions associated with the first query and a second set of tables, a second set of columns, and a second set of conditions associated with the second query. An example of the tables, columns and conditions is illustrated in Table 1 as discussed above. 
     From the tables, columns and conditions (e.g., see Table 1, above), the query data splitting system  120  can determine that the second query is a subset of the first query when the second set of tables is equal to or is a subset of the first set of tables, and when the second set of columns is equal to or is a subset of the first set of columns, and when each condition in the second set of conditions is included in the first set of conditions or when each condition in the second set of conditions is covered by the first set of conditions (e.g., if the first query requests to select all of the books and the second query requests to select some of the books that satisfy certain criteria). 
     Subsequently, at block  330 , the query data splitting system  120  can determine a first set of attributes associated with the first query and a second set of attributes associated with the second query. In an example, the set of attributes includes a frequency of a number of instances of receiving a query within a predefined time window  250 . In another example, the set of attributes includes a size of the query result. 
     Lastly, at block  340 , the query data splitting system  120  can determine whether to submit the second query or the first query to the database  130  in view of the first set of attributes and the second set of attributes. For example, the query data splitting system  120  can determine to submit the second query to the database when a product of the second frequency and the size of the second query is less than a product of the first frequency and the size of the first query. In another example, the query data splitting system  120  can determine to submit the first query to the database when a product of the second frequency and the size of the second query is greater than or equal a product of the first frequency and the size of the first query. 
     In another example, after receiving the first and second queries and their respective sets of attributes, the query data splitting system  120  can receive a third query from a client device  110 , can determine that the second query is a subset of the third query, can determine that a third set of attributes of the third query includes a third frequency of a number of instances of receiving the third query within a predefined time period and a size of the results of the third query, and can then determine whether to submit the first query, the second query, or the third query to the database  130  in view of the first, second, and third sets of attributes. 
     In the above example, the query data splitting system  120  can determine to submit the first query to the database  130  when a product of the second frequency and the second size is greater than or equal a product of the first frequency and the first size and when the product of the second frequency and the second size is less than a product of the third frequency and the third size. 
     To further illustrate the examples as discussed above, suppose the first query has a frequency of “1” within the time window  250  and the size or average size of the query results for query  1  is 10 kilobytes, and further suppose that the second query has a frequency of “2” within the time window  250  and the size or average size of the query results for query  2  is 7 kilobytes. In this case, the product of the attributes for node  1  is less than the product of the attributes for node  2  (10K vs. 14K), therefore, the query data splitting system  120  can determine to submit the first query to the database  130 . 
       FIG. 4  depicts a diagrammatic representation of a machine in the form of a computer system  400  within which a set of memory instructions, for causing the machine to perform any one or more of the methodologies discussed herein, may be executed. In alternative examples, the machine may be connected (e.g., networked) to other machines in a Local Area Network (LAN), an intranet, an extranet, or the Internet. The machine may operate in the capacity of a server or a client machine in a client-server network environment, or as a peer machine in a peer-to-peer (or distributed) network environment. The machine may be a personal computer (PC), a tablet PC, a set-top box (STB), a Personal Digital Assistant (PDA), a cellular telephone, a web appliance, a server, a network router, switch or bridge, or any machine capable of executing a set of instructions (sequential or otherwise) that specify actions to be taken by that machine. Further, while only a single machine is illustrated, the term “machine” shall also be taken to include any collection of machines (e.g., computers) that individually or jointly execute a set (or multiple sets) of instructions to perform any one or more of the methodologies discussed herein. 
     The computer system  400  includes a processing device  402  (e.g., a processor), a main memory  404  (e.g., read-only memory (ROM), flash memory, dynamic random access memory (DRAM) such as synchronous DRAM (SDRAM), etc.), a static memory  406  (e.g., flash memory, static random access memory (SRAM), etc.), and a secondary memory  416  (e.g., a data storage device), which communicate with each other via a bus  408 . 
     The processing device  402  represents one or more general-purpose processing devices such as a microprocessor, central processing unit, or the like. More particularly, the processing device  402  may be a complex instruction set computing (CISC) microprocessor, reduced instruction set computing (RISC) microprocessor, very long instruction word (VLIW) microprocessor, processor implementing other instruction sets, or processors implementing a combination of instruction sets. The processing device  402  may also be one or more special-purpose processing devices such as an application specific integrated circuit (ASIC), a field programmable gate array (FPGA), a digital signal processor (DSP), network processor, or the like. The processing device  402  is configured to execute the operations for the query data splitting system  120  for performing steps discussed herein. 
     The computer system  400  may further include a network interface device  422 . The network interface device may be in communication with a network  102 . The computer system  400  also may include a video display unit  410  (e.g., a liquid crystal display (LCD), a touch screen, or a cathode ray tube (CRT)), an alphanumeric input device  412  (e.g., a keyboard), a cursor control device  414  (e.g., a mouse), and a signal generation device  420  (e.g., a speaker). 
     The secondary memory  416  may include a computer-readable storage medium (or more specifically a non-transitory computer-readable storage medium)  424  on which is stored one or more sets of instructions  426  (e.g., instructions executed by the query data splitting system  120 ) for the computer system  400  representing any one or more of the methodologies or functions described herein. The instructions  426  for the computer system  400  may also reside, completely or at least partially, within the main memory  404  and/or within the processing device  402  during execution thereof by the computer system  400 , the main memory  404  and the processing device  402  also constituting computer-readable storage media. The instructions  426  for the computer system  400  may further be transmitted or received over a network via the network interface device  422 . 
     While the computer-readable storage medium  424  is shown in an example to be a single medium, the term “computer-readable storage medium” should be taken to include a single medium or multiple media (e.g., a centralized or distributed database, and/or associated caches and servers) that store the one or more sets of instructions  426 . The term “computer-readable storage medium” shall also be taken to include any medium that is capable of storing or encoding a set of instructions for execution by the machine that cause the machine to perform any one or more of the methodologies of the disclosure. The term “computer-readable storage medium” shall accordingly be taken to include, but not be limited to, solid-state memories, and optical and magnetic media. 
     Some portions of the detailed descriptions above are presented in terms of symbolic representations of operations on data bits within a computer memory. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like. 
     It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise, as apparent from the following discussion, it is appreciated that throughout the description, discussions utilizing terms such as “configuring,” “associating,” “executing,” “adjusting,” “sending,” “receiving,” “determining,” “transmitting,” “identifying,” “specifying,” “granting,” “accessing,” “assigning,” “detecting,” and “requesting,” or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system&#39;s registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices. 
     The disclosure also relates to an apparatus for performing the operations herein. This apparatus may be specially constructed for the required purposes, or it may be a general purpose computer system selectively programmed by a computer program stored in the computer system. Such a computer program may be stored in a computer readable storage medium, such as, but not limited to, any type of disk including optical disks, CD-ROMs, and magnetic-optical disks, read-only memories (ROMs), random access memories (RAMs), EPROMs, EEPROMs, magnetic disk storage media, optical storage media, flash memory devices, other type of machine-accessible storage media, or any type of media suitable for storing electronic instructions, each coupled to a computer system bus. 
     The descriptions and displays presented herein are not inherently related to any particular computer or other apparatus. Various general purpose systems may be used with programs in accordance with the teachings herein, or it may prove convenient to construct a more specialized apparatus to perform the required method steps. The required structure for a variety of these systems will appear as set forth in the description below. In addition, the disclosure is not described with reference to any particular programming language. It will be appreciated that a variety of programming languages may be used to implement the teachings of the disclosure as described herein. 
     It is to be understood that the above description is intended to be illustrative, and not restrictive. Many other examples will be apparent to those of skill in the art upon reading and understanding the above description. Although the disclosure has been described with reference to specific examples, it will be recognized that the disclosure is not limited to the examples described, but can be practiced with modification and alteration within the spirit and scope of the appended claims. Accordingly, the specification and drawings are to be regarded in an illustrative sense rather than a restrictive sense. The scope of the disclosure should, therefore, be determined with reference to the appended claims, along with the full scope of equivalents to which such claims are entitled.