Instructions caching on columnar database
The presently disclosed subject matter includes a system and method of managing computer memory of a column-oriented database, which enables to reduce the tradeoff between eviction and recycling of intermediate query results and thus retain much of the recycling capability at a considerably lower computer memory cost. The computer memory comprises one or more intermediates, each intermediate being generated by execution of a respective instruction, the instruction being part of a given query. An hierarchical data-structure is generated and stored in the computer memory, wherein different nodes in the hierarchical data-structure represent different respective intermediates stored in the computer memory. Responsive to a delete command, the at least one intermediate is deleted from the computer memory, while a respective node representing the at least one intermediate is maintained in the hierarchical data-structure.
1 . A computerized method of managing a cache of a column-oriented database; the cache being adapted to store at least one or more intermediates, each intermediate being an intermediate query result generated by execution of a respective instruction, the instruction being part of a given Structured Query Language (SQL) query for information from the column-oriented database; the method comprising, using a computer processor for:
generating a hierarchical data-structure and storing the hierarchical data-structure in a computer memory; wherein different nodes in the hierarchical data-structure represent different respective intermediates at least some of which are stored in the cache and wherein each of the different respective intermediates is at least initially stored in the cache;
responsive to a delete command, the delete command instructing to delete at least one of the intermediates that were at least initially stored in the cache from the cache, deleting the at least one intermediate from the cache;
responsive to the delete command, maintaining in the hierarchical data-structure a respective node representing the at least one intermediate whereby there is no intermediate that corresponds to the respective node available in the cache;
flagging the respective node representing the at least one intermediate, the flagging being indicative that there is no intermediate that corresponds to the flagged respective node available in the cache; and
executing an SQL database query, wherein executing the SQL database query comprises:
dividing the SQL database query into one or more instructions to generate a respective instruction set;
updating the hierarchical data-structure giving rise to an updated data-structure, wherein each instruction from among a group of instructions is represented by a respective node in the updated data-structure;
for each instruction in the instruction set, determining a respective intermediate, comprising:
when a respective intermediate is available in the cache, retrieving the intermediate from the cache;
otherwise, when a respective intermediate is not available in the cache, executing the instruction to determine a respective intermediate; and
providing the query result using the determined intermediates;
wherein each instruction in the instruction set is represented by a query-specific leaf node in the hierarchical data-structure, and wherein executing the instruction comprises:
for each query-specific leaf node, when a respective intermediate represented by the leaf node is not available in the cache, retrieving from the cache one or more earlier intermediates, the one or more earlier intermediates being represented by one or more respective parent nodes of the query-specific leaf node; and
using the one or more earlier intermediates for calculating the respective intermediate represented by the query specific leaf node;
flagging one or more nodes in the updated data structure, the flagging being indicative whether or not an intermediate represented by a given node is available in the cache;
wherein the hierarchical data-structure is a directed acyclic graph data-structure;
wherein the deletion command is executed according to a predefined eviction policy, the eviction policy comprising one or more rules for evicting intermediates from the cache in order to clear cache space, wherein the one or more rules comprise a rule instructing to maintain in the cache only intermediates represented in the hierarchical data-structure by leaf nodes, wherein the one or more rules comprise a rule instructing to determine whether to delete an intermediate from the cache based on a combination of parameters characterizing the intermediate, comprising: a processing intensiveness parameter and a cache consumption parameter, and wherein the one or more rules further include a weight factor for each one of the parameters.
2 . The method according to claim 1 wherein the column-oriented database is a MonetDB database.
3 . A processing unit of a column-oriented database management system configured to manage a cache, the cache being adapted to store at least one or more intermediates, each intermediate being an intermediate query result generated by execution of a respective instruction, the instruction being part of a given Structured Query Language (SQL) query for information from the column-oriented database; the processing unit being operatively connected to at least one computer processor and configured to:
generate a hierarchical data-structure and storing the hierarchical data-structure in a computer memory; wherein different nodes in the hierarchical data-structure represent different respective intermediates at least some of which are stored in the cache and wherein each of the different respective intermediates is at least initially stored in the cache;
responsive to a delete command, the delete command instructing to delete at least one of the intermediates that were at least initially stored in the cache from the cache, delete the at least one intermediate from the cache;
responsive to the delete command, maintain in the hierarchical data-structure a respective node representing the at least one intermediate whereby there is no intermediate that corresponds to the respective node available in the cache;
flag the respective node representing the at least one intermediate, the flagging being indicative that there is no intermediate that corresponds to the flagged respective node available in the cache; and
execute an SQL database query, wherein to execute the SQL database query the processor is further configured to:
divide the SQL database query into one or more instructions to generate a respective instruction set;
update the hierarchical data-structure giving rise to an updated data-structure, wherein each instruction from among a group of instructions is represented by a respective node in the updated data-structure;
for each instruction in the instruction set, determine a respective intermediate, comprising:
when a respective intermediate is available in the cache, retrieve the intermediate from the cache;
otherwise, when a respective intermediate is not available in the cache, execute the instruction to determine a respective intermediate; and
provide the query result using the determined intermediates;
wherein each instruction in the instruction set is represented by a query-specific leaf node in the hierarchical data-structure, and wherein to execute the instruction the processor if further configured to:
for each query-specific leaf node, when a respective intermediate represented by the leaf node is not available in the cache, retrieve from the cache one or more earlier intermediates, the one or more earlier intermediates being represented by one or more respective parent nodes of the query-specific leaf node; and
use the one or more earlier intermediates for calculating the respective intermediate represented by the query specific leaf node;
flag one or more nodes in the updated data structure, the flagging being indicative whether or not an intermediate represented by a given node is available in the cache;
wherein the hierarchical data-structure is a directed acyclic graph data-structure;
wherein the deletion command is executed according to a predefined eviction policy, the eviction policy comprising one or more rules for evicting intermediates from the cache in order to clear cache space, wherein the one or more rules comprise a rule instructing to maintain in the cache only intermediates represented in the hierarchical data-structure by leaf nodes, wherein the one or more rules comprise a rule instructing to determine whether to delete an intermediate from the cache based on a combination of parameters characterizing the intermediate, comprising: a processing intensiveness parameter and a cache consumption parameter, and wherein the one or more rules further include a weight factor for each one of the parameters.
4 . A database management system comprising a query kernel of a column-oriented database management system configured to manage a cache, the cache being adapted to store at least one or more intermediates, each intermediate being an intermediate query result generated by execution of a respective instruction, the instruction being part of a given Structured Query Language (SQL) query for information from the column-oriented database; the query kernel being operatively connected to at least one computer processor and configured to:
generate a hierarchical data-structure and storing the hierarchical data-structure in a computer memory; wherein different nodes in the hierarchical data-structure represent different respective intermediates at least some of which are stored in the cache and wherein each of the different respective intermediates is at least initially stored in the cache;
responsive to a delete command, the delete command instructing to delete at least one of the intermediates that were at least initially stored in the cache from the cache, delete the at least one intermediate from the cache;
responsive to the delete command, maintain in the hierarchical data-structure a respective node representing the at least one intermediate whereby there is no intermediate that corresponds to the respective node available in the cache;
flag the respective node representing the at least one intermediate, the flagging being indicative that there is no intermediate that corresponds to the flagged respective node available in the cache; and
execute an SQL database query, wherein to execute the SQL database query the processor is further configured to:
divide the SQL database query into one or more instructions to generate a respective instruction set;
update the hierarchical data-structure giving rise to an updated data-structure, wherein each instruction from among a group of instructions is represented by a respective node in the updated data-structure;
for each instruction in the instruction set, determine a respective intermediate, comprising:
when a respective intermediate is available in the cache, retrieve the intermediate from the cache;
otherwise, when a respective intermediate is not available in the cache, execute the instruction to determine a respective intermediate; and
provide the query result using the determined intermediates;
wherein each instruction in the instruction set is represented by a query-specific leaf node in the hierarchical data-structure, and wherein to execute the instruction the processor if further configured to:
for each query-specific leaf node, when a respective intermediate represented by the leaf node is not available in the cache, retrieve from the cache one or more earlier intermediates, the one or more earlier intermediates being represented by one or more respective parent nodes of the query-specific leaf node; and
use the one or more earlier intermediates for calculating the respective intermediate represented by the query specific leaf node;
flag one or more nodes in the updated data structure, the flagging being indicative whether or not an intermediate represented by a given node is available in the cache;
wherein the hierarchical data-structure is a directed acyclic graph data-structure;
wherein the deletion command is executed according to a predefined eviction policy, the eviction policy comprising one or more rules for evicting intermediates from the cache in order to clear cache space, wherein the one or more rules comprise a rule instructing to maintain in the cache only intermediates represented in the hierarchical data-structure by leaf nodes, wherein the one or more rules comprise a rule instructing to determine whether to delete an intermediate from the cache based on a combination of parameters characterizing the intermediate, comprising: a processing intensiveness parameter and a cache consumption parameter, and wherein the one or more rules further include a weight factor for each one of the parameters.
5 . A non-transitory program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps of managing cache of a column-oriented database the cache being adapted to store at least one or more intermediates, each intermediate being an intermediate query result generated by execution of a respective instruction, the instruction being part of a given Structured Query Language (SQL) query for information from the column-oriented database; the method comprising:
generating a hierarchical data-structure and storing the hierarchical data-structure in a computer memory; wherein different nodes in the hierarchical data-structure represent different respective intermediates at least some of which are stored in the cache and wherein each of the different respective intermediates is at least initially stored in the cache;
responsive to a delete command, the delete command instructing to delete at least one of the intermediates that were at least initially stored in the cache from the cache, deleting the at least one intermediate from the cache;
responsive to the delete command, maintaining in the hierarchical data-structure a respective node representing the at least one intermediate whereby there is no intermediate that corresponds to the respective node available in the cache;
flagging the respective node representing the least one intermediate, the flagging being indicative that there is no intermediate that corresponds to the flagged respective node available in the cache; and
executing an SQL database query, wherein executing the SQL database query comprises:
dividing the SQL database query into one or more instructions to generate a respective instruction set;
updating the hierarchical data-structure giving rise to an updated data-structure, wherein each instruction from among a group of instructions is represented by a respective node in the updated data-structure;
for each instruction in the instruction set, determining a respective intermediate, comprising:
when a respective intermediate is available in the cache, retrieving the intermediate from the cache;
otherwise, when a respective intermediate is not available in the cache, executing the instruction to determine a respective intermediate; and
providing the query result using the determined intermediates;
wherein each instruction in the instruction set is represented by a query-specific leaf node in the hierarchical data-structure, and wherein executing the instruction comprises:
for each query-specific leaf node, when a respective intermediate represented by the leaf node is not available in the cache, retrieving from the cache one or more earlier intermediates, the one or more earlier intermediates being represented by one or more respective parent nodes of the query-specific leaf node; and
using the one or more earlier intermediates for calculating the respective intermediate represented by the query specific leaf node;
flagging one or more nodes in the updated data structure, the flagging being indicative whether or not an intermediate represented by a given node is available in the cache;
wherein the hierarchical data-structure is a directed acyclic graph data-structure;
wherein the deletion command is executed according to a predefined eviction policy, the eviction policy comprising one or more rules for evicting intermediates from the cache in order to clear cache space, wherein the one or more rules comprise a rule instructing to maintain in the cache only intermediates represented in the hierarchical data-structure by leaf nodes, wherein the one or more rules comprise a rule instructing to determine whether to delete an intermediate from the cache based on a combination of parameters characterizing the intermediate, comprising: a processing intensiveness parameter and a cache consumption parameter, and wherein the one or more rules further include a weight factor for each one of the parameters.
6 . The method according to claim 1 , wherein each and every one of the different respective intermediates is at least initially stored in the cache.
7 . The method according to claim 1 , wherein each and every one of the different respective intermediates is at least initially stored in the cache even after the cache initially became full.
8 . The processing unit according to claim 3 , wherein each and every one of the different respective intermediates is at least initially stored in the cache.
9 . The processing unit according to claim 3 , wherein each and every one of the different respective intermediates is at least initially stored in the cache even after the cache initially became full.
10 . The database management system according to claim 4 , wherein each and every one of the different respective intermediates is at least initially stored in the cache.
11 . The database management system according to claim 4 , wherein each and every one of the different respective intermediates is at least initially stored in the cache even after the cache initially became full.
12 . The non-transitory program storage device according to claim 5 , wherein each and every one of the different respective intermediates is at least initially stored in the cache.
13 . The non-transitory program storage device according to claim 5 , wherein each and every one of the different respective intermediates is at least initially stored in the cache even after the cache initially became full.