# US 2019/0318025 A1 · Computation Reuse in Analytics Job Service

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0318025 A1
- Document ID: US20190318025A1
- Status: Published application
- Kind: A1
- Application number: 15/952,347
- Filed: 2018-04-13
- Published: 2019-10-17
- Earliest claimed: 2018-04-13
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Alekh JINDAL; Hiren PATEL; Shi QIAO; Jieming DI; Malay Kumar BAG; Zhicheng YIN
- Web page: https://patentgrep.com/patent/US20190318025A1

## CPC

- G06F 16/2393: {Updating materialised views}
- G06F 16/24539: {using cached or materialised query results}
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 16/24542: {Plan optimisation}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Described herein is a system and method for detecting and reusing overlapping computations. Overlapping subgraphs of the query are determined using a normalized signature for a particular subgraph that identifies a particular subgraph across recurring instances of data. A normalized signature for each overlapping subgraph for the determined overlapping subgraphs of the query is provided. For each overlapping subgraph determined to be materialized: whether or not the particular subgraph has been materialized is determined using a precise signature corresponding to a normalized signature of the particular overlapping subgraph. The precise signature identifies a particular subgraph corresponding to the normalized signature within a particular recurring instance of data. When the particular subgraph has not been materialized, the subgraph is materialized and used to respond to the query. When the particular subgraph has been materialized, the materialized subgraph is used to respond to the query.

## Claims

### Claim 1

A system for reusing overlapping computations in an analytics job service, comprising:
a computer comprising a processor and a memory having computer-executable instructions stored thereupon which, when executed by the processor, cause the computer to:
receive a query;
determine overlapping subgraphs of the query using stored information regarding analyzed workload data, the stored information including a normalized signature for a particular subgraph, the normalized signature identifies a particular subgraph across recurring instances of data;
provide information regarding the determined overlapping subgraphs of the query, the information regarding overlapping subgraphs comprising a normalized signature for each overlapping subgraph;
using the provided information, determine which of the overlapping subgraphs is to be materialized;
for each overlapping subgraph determined to be materialized:
determine whether or not the particular subgraph has been materialized using a precise signature corresponding to a normalized signature of the particular overlapping subgraph, the precise signature identifies a particular subgraph corresponding to the normalized signature within a particular recurring instance of data;
when the particular subgraph has not been materialized, materialize the subgraph and use the materialized subgraph to respond to the query; and
when the particular subgraph has been materialized, use the materialized subgraph to respond to the query.

### Claim 2 (depends on 1)

The system of claim 1, wherein analysis of workload data is performed prior to receiving the query.

### Claim 3 (depends on 1)

The system of claim 1, wherein the normalized signature is independent of a particular instance of data.

### Claim 4 (depends on 1)

The system of claim 1, wherein the stored information regarding analyzed workload data further comprises at least one of compiled query subgraphs, optimized plans and estimated statistics, execution graphs and resources, or actual runtime statistics of executed queries.

### Claim 5 (depends on 1)

The system of claim 1, wherein the stored information regarding analyzed workload data further comprises information regarding a physical design for at least one subgraph to be materialized.

### Claim 6 (depends on 1)

The system of claim 1, wherein the stored information regarding analyzed workload data further comprises information regarding expiry of a materialized subgraph.

### Claim 7 (depends on 1)

The system of claim 1, wherein the stored information regarding analyzed workload data is based, at least in part, upon a user selectable setting regarding at least one of storage costs, latency, CPU hours, or frequency.

### Claim 8 (depends on 1)

The system of claim 1, wherein the stored information regarding analyzed workload data is based upon analysis of runtime statistics of subgraphs of a plurality of jobs including at least one of latency, cardinality, data size, or resource consumption of subgraphs.

### Claim 9

A method of automatically reusing overlapping computations in an analytics job service, comprising:
receiving a query;
determining overlapping subgraphs of the query using stored information regarding analyzed workload data, the stored information including a normalized signature for a particular subgraph, the normalized signature identifies a particular subgraph across recurring instances of data;
providing information regarding the determined overlapping subgraphs of the query, the information regarding overlapping subgraphs comprising a normalized signature for each overlapping subgraph;
using the provided information, determining which of the overlapping subgraphs is to be materialized;
for each overlapping subgraph determined to be materialized:
determining whether or not the particular subgraph has been materialized using a precise signature corresponding to a normalized signature of the particular overlapping subgraph, the precise signature identifies a particular subgraph corresponding to the normalized signature within a particular recurring instance of data;
when the particular subgraph has not been materialized, materializing the subgraph and use the materialized subgraph to respond to the query; and
when the particular subgraph has been materialized, using the materialized subgraph to respond to the query.

### Claim 10 (depends on 9)

The method of claim 9, wherein analysis of workload data is performed prior to receiving the query.

### Claim 11 (depends on 9)

The method of claim 9, wherein the normalized signature is independent of a particular instance of data.

### Claim 12 (depends on 9)

The method of claim 9, wherein the stored information regarding analyzed workload data further comprises at least one of compiled query subgraphs, optimized plans and estimated statistics, execution graphs and resources, or actual runtime statistics of executed queries.

### Claim 13 (depends on 9)

The method of claim 9, wherein the stored information regarding analyzed workload data further comprises information regarding a physical design for at least one subgraph to be materialized.

### Claim 14 (depends on 9)

The method of claim 9, wherein the stored information regarding analyzed workload data further comprises information regarding expiry of a materialized subgraph.

### Claim 15 (depends on 9)

The method of claim 9, wherein the stored information regarding analyzed workload data is based, at least in part, upon a user selectable setting regarding at least one of storage costs, latency, CPU hours, or frequency.

### Claim 16 (depends on 9)

The method of claim 9, wherein the stored information regarding analyzed workload data is based upon analysis of runtime statistics of subgraphs of a plurality of jobs including at least one of latency, cardinality, data size, or resource consumption of subgraphs.

### Claim 17

A computer storage media storing computer-readable instructions that when executed cause a computing device to:
determine overlapping subgraphs of the query using stored information regarding analyzed workload data, the stored information including a normalized signature for a particular subgraph, the normalized signature identifies a particular subgraph across recurring instances of data;
provide information regarding the determined overlapping subgraphs of the query, the information regarding overlapping subgraphs comprising a normalized signature for each overlapping subgraph;
using the provided information, determine which of the overlapping subgraphs is to be materialized;
for each overlapping subgraph determined to be materialized:
determine whether or not the particular subgraph has been materialized using a precise signature corresponding to a normalized signature of the particular overlapping subgraph, the precise signature identifies a particular subgraph corresponding to the normalized signature within a particular recurring instance of data;
when the particular subgraph has not been materialized, materialize the subgraph and use the materialized subgraph to respond to the query; and
when the particular subgraph has been materialized, use the materialized subgraph to respond to the query.

### Claim 18 (depends on 17)

The computer storage media of claim 17, wherein the stored information regarding analyzed workload data further comprises at least one of compiled query subgraphs, optimized plans and estimated statistics, execution graphs and resources, or actual runtime statistics of executed queries.

### Claim 19 (depends on 17)

The computer storage media of claim 17, wherein the stored information regarding analyzed workload data further comprises information regarding a physical design for at least one subgraph to be materialized.

### Claim 20 (depends on 17)

The computer storage media of claim 17, wherein the stored information regarding analyzed workload data further comprises information regarding expiry of a materialized subgraph.
