COLUMN ORDERING FOR INPUT/OUTPUT OPTIMIZATION IN TABULAR DATA

• US 20180107696A1
• Filed: 06/03/2016
• Published: 04/19/2018
• Est. Priority Date: 06/04/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: MOSCIBRODA, Thomas, CHEN, Liang Jeff, HUANG, Xiao, YAN, Ying, CHEN, Yueguo, ZHENG, Xudong, BIAN, Haoqiong
• Granted Patent: US 11,514,011 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24553 of query operations
• CPC Class Codes: G06F 16/24557 Efficient disk access during query execution
• CPC Class Codes: G06F 16/2457 with adaptation to user needs
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04

Abstract

Systems, methods, and computer-readable media for determining column ordering of a data storage table for search optimization are described herein. In some examples, a computing system is configured to receive input containing statistics of a plurality of queries. The computing system can then determine a new column order (i.e., layout) based at least in part on the statistics. In some example techniques described herein, the computing system can determine the new column order based at least in part on the hardware components storing the data storage table, storage system parameters, and/or user preference information. Example techniques described herein can apply the new column order to data subsequently added to the data storage table. Example techniques described herein can apply the new column order to existing data in the data storage table.

Claims

1. A system comprising:

a processor;

a memory storing a column ordering framework, for actuation by the processor, the column ordering framework comprising;

a workload manager module configured process data regarding a first column layout of a tabular storage to determine a query workload associated with the first column layout; and

an order generating module configured to calculate a second column layout for the tabular storage based at least in part on the query workload.

2. A system as claim 1 recites, wherein the data comprises at least one of:

a frequency of a query;

a list of the columns accessed for the query;

a time stamp for the query;

or

a seek cost for the query.

3. A system as claim 1 recites, the column ordering framework further comprising at least one of:

a user preference module configured to receive and process user preference inputs regarding the tabular storage;

a hardware simulator module configured to receive data associated with the hardware storing the tabular storage;

or

a system setting module configured to receive system settings related to the tabular storage.

4. A computer-implemented method, comprising:

ascertaining a first order for columns of a table, the table comprising a plurality of columns;

receiving statistics associated with one or more queries;

determining a first cost for the one or more queries based at least in part on the statistics;

determining a second order for columns of the table, the second order having a lower cost than the first cost; and

applying the second order to create an ordered table.

5. A method as claim 4 recites, further comprising:

receiving one or more inputs related to at least one of;

a user preference associated with the table;

a hardware component;

or

a system parameter,

wherein the determining the second order for columns of the table is based at least in part on the one or more inputs.

6. A method as claim 4 recites, wherein the ordered table comprises:

the table configured in the first column order; and

data added subsequent to a determination of the second order for columns of the table configured in the second column order.

7. A method as any claim 4 recites, wherein the ordered table comprises:

the table and data added subsequent to a determination of the second order for columns of the table configured in the second column order.

8. A computer-readable medium having thereon computer-executable instructions, the computer-executable instructions responsive to execution configuring a device to perform operations comprising:

accessing a table comprising a first plurality of columns;

identifying at least two related columns of the first plurality of columns;

determining whether the at least two related columns of the first plurality of columns are close to one another;

responsive to determining the at least two related columns of the first plurality of columns are not close to one another, determining a new order for the first plurality of columns based at least in part on locating the at least two related columns close to one another; and

applying the new order to a second plurality of columns to create an ordered table, the second plurality of columns being added to the table subsequent to the determining the new order for the first plurality of columns.

9. A computer-readable medium as claim 8 recites, wherein the identification of the at least two related columns comprises a determination that the at least two related columns will likely be accessed together.

10. A computer-readable medium as claim 8 recites, wherein the determining whether the at least two related columns of the plurality of columns are close to one another is based at least in part on a cost.