In-memory database search optimization using graph community structure

Abstract

Database searching is optimized utilizing a graph community structure. A graph is created from transaction data based upon adjacent value occurrences. This may be done by scanning transaction data from top to bottom, and creating an edge between a current index value and a previous index value. Next, algorithms identify communities in the graph to create a graph community structure. These communities comprise blocks of patterns of similar value-ids distributed in the transaction data. Scanning and transition indices may be created with an eye toward reducing memory usage and enhancing performance. Query searching is then executed in an efficient manner on a per-community basis. For example, exact queries, range queries, and/or “AND” queries may be executed more efficiently upon communities of records, skipping those not belonging to the same community. Embodiments are suited to search an in-memory database having large volumes of column-oriented data stored in RAM.

What is claimed is: 
     
       1. A computer-implemented method comprising:
 providing transaction data comprising a plurality of records including columns, and an index in a column-oriented in-memory database; 
 generating a graph from the transaction data; 
 applying an algorithm to the graph to create a graph community structure; 
 defining a plurality of communities in the transaction data using the graph community structure executed in parallel upon at least two of the columns; 
 executing a database query on records in a community, skipping records outside of the community; 
 evaluating the community based upon performance gains versus searching value identifiers across multiple communities, wherein the performance gains are in AND queries using intersecting attribute vector blocks of multiple columns; 
 based upon the evaluating, re-applying the algorithm independently to each column to create an alternative graph community structure for each column; and 
 displaying a search result resulting from re-executing the database query on records in an alternative community defined in the transaction data using the alternative graph community structure. 
 
     
     
       2. A method as in  claim 1  wherein the graph is generated by identifying adjacent value occurrences in the transaction data, and creating an edge between a current index value and a previous index value. 
     
     
       3. A method as in  claim 1  wherein the algorithm considers a modularity measure. 
     
     
       4. A method as in  claim 1  wherein the transaction data is column-oriented data. 
     
     
       5. A method as in  claim 1  wherein the algorithm is applied by an engine of the column-oriented in-memory database. 
     
     
       6. A non-transitory computer readable storage medium embodying a computer program for performing a method, said method comprising:
 providing transaction data comprising a plurality of records including columns, in a column-oriented in-memory database; 
 generating a graph from the transaction data; 
 applying an algorithm to the graph to create a graph community structure; 
 defining a plurality of communities in the transaction data using the graph community structure executed in parallel upon at least two of the columns; 
 evaluating a community based upon performance gains versus searching value identifiers across multiple communities; 
 executing a database query on records in the community, skipping records outside of the community, wherein the performance gains are in AND queries using intersecting attribute vector blocks of multiple columns; 
 based upon the evaluating, re-applying the algorithm independently to each column to create an alternative graph community structure for each column; and 
 displaying a search result resulting from re-executing the database query on records in an alternative community defined in the transaction data using the alternative graph community structure. 
 
     
     
       7. A non-transitory computer readable storage medium as in  claim 6  wherein the graph is generated by identifying adjacent value occurrences in the transaction data, and creating an edge between a current index value and a previous index value. 
     
     
       8. A non-transitory computer readable storage medium as in  claim 6  wherein the algorithm considers a modularity measure. 
     
     
       9. A non-transitory computer readable storage medium as in  claim 6  wherein the transaction data is column-oriented data. 
     
     
       10. A non-transitory computer readable storage medium as in  claim 6  wherein the algorithm is applied by an engine of the column-oriented in-memory database. 
     
     
       11. A computer system comprising:
 one or more hardware processors; 
 a software program, executable on said computer system, the software program configured to cause the at least one or more hardware processors to: 
 provide column-oriented transaction data comprising a plurality of records including columns, in a column-oriented in-memory database; 
 generate a graph from the transaction data; 
 apply an algorithm to the graph to create a graph community structure; 
 define a plurality of communities in the transaction data using the graph community structure executed in parallel upon at least two of the columns; 
 evaluate a community based upon performance gains versus searching value identifiers across multiple communities; 
 execute a database query on records in the community, skipping records outside of the community, wherein the performance gains are in AND queries using intersecting attribute vector blocks of multiple columns; 
 based upon the evaluating, re-apply the algorithm independently to each column to create an alternative graph community structure for each column; and 
 display a search result resulting from re-executing the database query on records in an alternative community defined in the transaction data using the alternative graph community structure. 
 
     
     
       12. A computer system as in  claim 11  wherein the graph is generated by identifying adjacent value occurrences in the transaction data, and creating an edge between a current index value and a previous index value. 
     
     
       13. A computer system as in  claim 11  wherein the algorithm considers a modularity measure.