Adaptive row-batch processing of database data

• US 8,548,986 B2
• Filed: 03/19/2010
• Issued: 10/01/2013
• Est. Priority Date: 03/19/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Surna, Aleksandras, Larson, Per-Ake, Rangarajan, Srikumar
• Primary Examiner(s): Woo, Isaac M
• Assistant Examiner(s): Khong, Alexander
• Application Number:
  US12/727,235
• Publication Number:
  US 20110231389A1
• Time in Patent Office: 1,292 Days
• Field of Search: 707/718
• US Class Current: 707/718
• CPC Class Codes: G06F 16/24557 Efficient disk access during query execution

Abstract

Architecture that provides for greater interoperability between column stores and row stores by leveraging the advantages both have to offer. The architecture operates automatically (e.g., dynamically) to move between row oriented processing mode and batch processing mode, and the combination thereof, when it is more beneficial to run in one mode relative to the other mode, or both modes. The auto-switching of data processing between batch and row oriented mode occurs during the execution of a single query. The architecture can automatically modify an operator in the query tree and/or remove an operator if desired at runtime for more efficient processing. This approach also accounts for memory constraints for either of row or column processing.

Claims

1. A computer-implemented query system having a physical storage media, comprising:

a query plan for execution against data stores that include row data stores and column data stores; and

a query execution component that controls execution of the query plan to switch between row-wise processing and column-wise processing based on the data stores accessed as part of query plan execution, row-wise processing including processing a plurality of rows one at a time and column-wise processing including processing another plurality of rows as one batch, the query execution component being configured to switch from row-wise processing to column-wise processing and the query execution component being configured to switch from column-wise processing to row-wise processing.

2. The system of claim 1, wherein the query execution component switches between row-wise processing and column-wise processing during plan execution to output query results in a column format.

3. The system of claim 1, wherein the query execution component switches between row-wise processing and column-wise processing during plan execution to output query results in a row format.

4. The system of claim 1, wherein the query execution component dynamically modifies the query plan or removes an operator in the query plan at runtime based on an amount of data associated with query plan execution at stages of execution.

5. The system of claim 1, wherein the query execution component defaults to row-wise processing of the query plan and switches to column-wise processing based on data storage format of the data stores accessed as part of processing the query plan.

6. The system of claim 1, wherein the query execution component modifies an operator of the query plan to optimize query execution performance for a given data store.

7. The system of claim 1, wherein the query execution component analyzes the query execution plan after compilation to identify one or more query operators for removal.

8. The system of claim 1, wherein the query execution component determines memory capabilities to execute the query plan in memory and switches between query plans based on available memory.

9. The system of claim 1, wherein the query plan is modified to remove one or more repartitioning operators based on data tables and associated hash tables fitting into memory.

10. A computer-implemented query system having a physical storage media, comprising:

a query plan for execution against data stores that include row data stores and column data stores; and

a query execution component that controls execution of the query plan to switch between row-wise processing and column-wise processing at runtime based on a determination of available memory made at runtime as part of query plan execution, the query execution component defaults to row-wise processing of the query plan and switches to column-wise processing based on memory available to accommodate column-wise processing of the query plan, row-wise processing including processing a plurality of rows one at a time and column-wise processing including processing another plurality of rows as one batch, the query execution component being configured to switch from row-wise processing to column-wise processing and the query execution component being configured to switch from column-wise processing to row-wise processing.

11. The system of claim 10, wherein the query execution component switches between row-wise processing and column-wise processing during plan execution to output query results in a column format or a row format.

12. The system of claim 10, wherein the query execution component dynamically modifies the query plan or removes an operator in the query plan at runtime based on an amount of data associated with query plan execution at stages of execution.

13. The system of claim 10, wherein the query execution component analyzes the query execution plan after compilation to identify one or more query operators for removal, and removes one or more repartitioning operators based on data tables and associated hash tables fitting into memory.

14. A computer-implemented query method executable via a processor and memory, comprising:

receiving a query plan for execution against row data stores and column data stores;

determining available resources for query plan processing;

monitoring query results at steps of plan execution relative to the available resources;

dynamically switching between row-wise processing and column-wise processing at runtime based on the available resources, dynamically switching between row-wise processing and column-wise processing at runtime including switching between row-wise processing and column-wise processing at a start of execution; and

processing a modified query plan using a first thread, processing the modified query plan including fetching one or more data items from a memory space used by a second thread.

15. The method of claim 14, further comprising switching to row-wise processing based on lack of in-memory processing due to query results that cannot fit into memory.

16. The method of claim 14, further comprising switching to column-wise processing based on available memory for in-memory processing of query results.

17. The method of claim 14, further comprising:

analyzing the query plan at compile time; and

tagging a candidate operator for removal.

18. The method of claim 17, further comprising removing repartitioning operators tagged for removal at runtime based on capability to fit data tables into memory with associated hash tables.

19. The method of claim 14, further comprising outputting row format data or column format data based on a data store receiving query results.

20. The method of claim 14, further comprising:

partitioning tables to allow the partitioned tables to fit into available memory; and

processing the query plan against hash tables of the partitioned tables while in memory.