Efficient in-memory DB query processing over any semi-structured data formats
Techniques are described herein for maintaining two copies of the same semi-structured data, where each copy is organized in a different format. One copy is in a first-format that may be convenient for storage, but inefficient for query processing. For example, the first-format may be a textual format that needs to be parsed every time a query needs to access individual data items within a semi-structured object. The database system intelligently loads semi-structured first-format data into volatile memory and, while doing so, converts the semi-structured first-format data to a second-format. Because the data in volatile memory is in the second-format, processing queries against the second-format data both allows disk I/O to be avoided, and increases the efficiency of the queries themselves. For example, the parsing that may be necessary to run a query against a cached copy of the first-format data is avoided.
1. A method comprising:
maintaining, by a database server, a set of first-format data;
wherein the database server maintains the set of first-format data on persistent storage;
wherein the set of first-format data:
is accessible to the database server,
represents a set of semi-structured documents, and
is stored in a first-format;
converting, by the database server, the set of first-format data to a second-format to produce a set of second-format data;
wherein the second-format is one of:
a row-based mirror format;
a set-based mirror format; or
a master-detail mirror format;
wherein the database server maintains the set of second-format data in volatile memory;
wherein the second-format is different from and independent of the first-format;
wherein the set of second-format data is accessible to the database server;
the database server executing database operations that make changes to the set of first-format data;
the database server maintaining the set of second-format data transactionally consistent with the set of first-format data as the database server executes database operations that make changes to the set of first-format data;
wherein maintaining the set of second-format data transactionally consistent with the set of first-format data as the database server executes database operations that make changes to the set of first-format data includes ensuring that any data items provided to a transaction from the set of second-format data are the same version that would have been provided if the data items were provided from the set of first-format data;
receiving, by the database server, a request to execute a database command that requires particular information from the set of semi-structured documents; and
in response to receiving the request, the database server executing the database command;
wherein, during execution of the database command, the database server obtains at least some of the particular information from the set of second-format data.
2. The method of claim 1 further comprising the database server rewriting the database command to cause execution of the database command to obtain at least some of the particular information from the set of second-format data.
3. The method of claim 1 wherein:
the set of first-format data is stored in an on-disk table; and
the second-format is the master-detail mirror format in which information about the set of semi-structured documents is stored in a hidden column of the on-disk table.
4. The method of claim 1 further comprising, during execution of the database command, the database server obtaining a first portion of the particular information from the set of second-format data, and a second portion of the particular information from the set of first-format data.
5. The method of claim 1 wherein:
the second-format is the row-based mirror format; and
converting the set of first-format data to the second-format comprises generating an in-memory table in which each row has a field-name-dictionary component, a tree-node-navigation component, and a leaf-scalar-value component for a document that corresponds to the row.
6. The method of claim 5 wherein a separate column unit stores each of the field-name-dictionary component, the tree-node-navigation component, and the leaf-scalar-value component.
7. The method of claim 5 wherein a single column unit stores the field-name-dictionary component, the tree-node-navigation component, and the leaf-scalar-value component.
8. The method of claim 1 wherein the second-format is the set-based mirror format, and converting the set of first-format data to the second-format comprises:
generating an in-memory table in which:
each row of the in-memory table corresponds to a corresponding document from the set of semi-structured documents; and
each row has a tree-node-navigation component for the corresponding document that corresponds to the row; and
generating a shared dictionary for at least one of:
a field-name-dictionary component of all documents in the set of semi-structured documents; or
a leaf-scalar-value component of all documents in the set of semi-structured documents.
9. The method of claim 8 further comprising generating an in-memory bitmap index for the shared dictionary.
10. The method of claim 1 wherein the second-format is the master-detail mirror format, and converting the set of first-format data to the second-format comprises:
generating a data guide for the set of semi-structured documents;
based on the data guide, generating one or more view definitions; and
generating an in-memory view for each view definition of the one or more view definitions.
11. The method of claim 10 wherein:
the step of generating the data guide is performed before the database server receives the request; and
the step of generating the in-memory view is performed after the database server receives the request.
12. The method of claim 10 wherein both generating the data guide and generating the in-memory view are performed after the database server receives the request.
13. The method of claim 1 wherein maintaining the set of second-format data transactionally consistent with the set of first-format data comprises, in response to an operation that performed an update to a particular semi-structured document in the set of semi-structured documents, invalidating a portion of the set of second-format data that corresponds to the particular semi-structured document.
14. The method of claim 13 further comprising, in response to the operation that updates the particular semi-structured document, storing an entry that reflects the update in an in-memory journal associated with the set of second-format data.
15. The method of claim 1 wherein the second-format is the set-based mirror format and the step of converting the set of first-format data to the second-format comprises merging a hierarchical tree of nodes of each document in the set of semi-structured documents to generate a super hierarchical tree of nodes.
16. The method of claim 15 further comprising generating a compressed bitmap for each node in the super hierarchical tree of nodes, wherein the compressed bitmap for each node indicates which semi-structured documents in the set of semi-structured documents share the node.
17. The method of claim 1 further comprising storing, in volatile memory in conjunction with the set of second-format data, a textual version of documents from the set of semi-structured documents.
18. The method of claim 17 further comprising:
the database server using the set of second-format data to determine which documents satisfy a predicate of a query; and
the database server generating a result set of the query by extracting values from the textual version of documents that is stored in volatile memory in conjunction with the set of second-format data.
19. One or more non-transitory computer-readable media having stored thereon instructions that, when executed by one or more computing devices, cause a database server to perform:
maintaining, by a database server, a set of first-format data;
wherein the database server maintains the set of first-format data on persistent storage;
wherein the set of first-format data:
is accessible to the database server,
represents a set of semi-structured documents, and
is stored in a first-format;
converting, by the database server, the set of first-format data to a second-format to produce a set of second-format data;
wherein the second-format is one of:
a row-based mirror format;
a set-based mirror format; or
a master-detail mirror format;
wherein the database server maintains the set of second-format data in volatile memory;
wherein the second-format is different from and independent of the first-format;
wherein the set of second-format data is accessible to the database server;
the database server executing database operations that make changes to the set of first-format data;
the database server maintaining the set of second-format data transactionally consistent with the set of first-format data as the database server executes database operations that make changes to the set of first-format data;
wherein maintaining the set of second-format data transactionally consistent with the set of first-format data as the database server executes database operations that make changes to the set of first-format data includes ensuring that any data items provided to a transaction from the set of second-format data are the same version that would have been provided if the data items were provided from the set of first-format data;
receiving, by the database server, a request to execute a database command that requires particular information from the set of semi-structured documents; and
in response to receiving the request, the database server executing the database command;
wherein, during execution of the database command, the database server obtains at least some of the particular information from the set of second-format data.
20. The one or more non-transitory computer-readable media of claim 19 , wherein the instructions further comprise instructions that, when executed by one or more computing device, cause: the database server rewriting the database command to cause execution of the database command to obtain at least some of the particular information from the set of second-format data.
21. The one or more non-transitory computer-readable media of claim 19 wherein:
the set of first-format data is stored in an on-disk table; and
the second-format is the master-detail mirror format in which information about the set of semi-structured documents is stored in a hidden column of the on-disk table.
22. The one or more non-transitory computer-readable media of claim 19 wherein the instructions further comprise instructions that, when executed by one or more computing device, cause: during execution of the database command, the database server obtaining a first portion of the particular information from the set of second-format data, and a second portion of the particular information from the set of first-format data.
23. The one or more non-transitory computer-readable media of claim 19 wherein:
the second-format is the row-based mirror format; and
converting the set of first-format data to the second-format comprises generating an in-memory table in which each row has a field-name-dictionary component, a tree-node-navigation component, and a leaf-scalar-value component for a document that corresponds to the row.
24. The one or more non-transitory computer-readable media of claim 23 wherein a separate column unit stores each of the field-name-dictionary component, the tree-node-navigation component, and the leaf-scalar-value component.
25. The one or more non-transitory computer-readable media of claim 23 wherein a single column unit stores the field-name-dictionary component, the tree-node-navigation component, and the leaf-scalar-value component.
26. The one or more non-transitory computer-readable media of claim 19 wherein the second-format is the set-based mirror format, and converting the set of first-format data to the second-format comprises:
generating an in-memory table in which:
each row of the in-memory table corresponds to a corresponding document from the set of semi-structured documents; and
each row has a tree-node-navigation component for the corresponding document that corresponds to the row; and
generating a shared dictionary for at least one of:
a field-name-dictionary component of all documents in the set of semi-structured documents; or
a leaf-scalar-value component of all documents in the set of semi-structured documents.
27. The one or more non-transitory computer-readable media of claim 26 wherein the instructions further comprise instructions that, when executed by one or more computing device, cause: generating an in-memory bitmap index for the shared dictionary.
28. The one or more non-transitory computer-readable media of claim 19 wherein the second-format is the master-detail mirror format, and converting the set of first-format data to the second-format comprises:
generating a data guide for the set of semi-structured documents;
based on the data guide, generating one or more view definitions; and
generating an in-memory view for each view definition of the one or more view definitions.
29. The one or more non-transitory computer-readable media of claim 28 wherein:
the step of generating the data guide is performed before the database server receives the request; and
the step of generating the in-memory view is performed after the database server receives the request.
30. The one or more non-transitory computer-readable media of claim 28 wherein both generating the data guide and generating the in-memory view are performed after the database server receives the request.
31. The one or more non-transitory computer-readable media of claim 19 wherein maintaining the set of second-format data transactionally consistent with the set of first-format data comprises, in response to an operation that performed an update to a particular semi-structured document in the set of semi-structured documents, invalidating a portion of the set of second-format data that corresponds to the particular semi-structured document.
32. The one or more non-transitory computer-readable media of claim 31 wherein the instructions further comprise instructions that, when executed by one or more computing device, cause: in response to the operation that updates the particular semi-structured document, storing an entry that reflects the update in an in-memory journal associated with the set of second-format data.
33. The one or more non-transitory computer-readable media of claim 19 wherein the second-format is the set-based mirror format and the step of converting the set of first-format data to the second-format comprises merging a hierarchical tree of nodes of each document in the set of semi-structured documents to generate a super hierarchical tree of nodes.
34. The one or more non-transitory computer-readable media of claim 33 wherein the instructions further comprise instructions that, when executed by one or more computing device, cause: generating a compressed bitmap for each node in the super hierarchical tree of nodes, wherein the compressed bitmap for each node indicates which semi-structured documents in the set of semi-structured documents share the node.
35. The one or more non-transitory computer-readable media of claim 19 wherein the instructions further comprise instructions that, when executed by one or more computing device, cause: storing, in volatile memory in conjunction with the set of second-format data, a textual version of documents from the set of semi-structured documents.
36. The one or more non-transitory computer-readable media of claim 35 wherein the instructions further comprise instructions that, when executed by one or more computing device, cause:
the database server using the set of second-format data to determine which documents satisfy a predicate of a query; and
the database server generating a result set of the query by extracting values from the textual version of documents that is stored in volatile memory in conjunction with the set of second-format data.