# US 2015/0149440 A1 · Systems and methods for finding optimal query plans

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

- Number: US 2015/0149440 A1
- Document ID: US20150149440A1
- Status: Published application
- Kind: A1
- Application number: 14/088,574
- Filed: 2013-11-25
- Published: 2015-05-28
- Earliest claimed: 2013-11-25
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Mihaela A. Bornea; Julian Dolby; Achille B. Fokoue-Nkoutche; Anastasios Kementsietsidis; Kavitha Srinivas
- Web page: https://patentgrep.com/patent/US20150149440A1

## CPC

- G06F 16/24545: {Selectivity estimation or determination}
- G06F 16/2453: Query optimisation
- G06F 16/24578: {using ranking}
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 16/2455: Query execution
- G06F 16/8365: {Query optimisation}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Systems and methods for optimizing a query, and more particularly, systems and methods for finding optimal plans for graph queries by casting the task of finding the optimal plan as an integer programming (ILP) problem. A method for optimizing a query, comprises building a data structure for a query, the data structure including a plurality of components, wherein each of the plurality of components corresponds to at least one graph pattern, determining a plurality of flows of query variables between the plurality of components, and determining a combination of the plurality of flows between the plurality of components that results in a minimum cost to execute the query.

## Claims

### Claim 1

A system for optimizing a query, comprising:
a construction module capable of building a data structure for a query, the data structure including a plurality of components, wherein each of the plurality of components corresponds to at least one graph pattern;
a flow module capable of determining a plurality of flows of query variables between the plurality of components; and
a cost determination and ranking module capable of determining a combination of the plurality of flows between the plurality of components that results in a minimum cost to execute the query.

### Claim 2 (depends on 1)

The system according to claim 1, further comprising a constraint module capable of ruling out one or more flows that would violate semantics of one or more control statements in the query.

### Claim 3 (depends on 1)

The system according to claim 1, further comprising a constraint module capable of generating one or more constraints for ruling out invalid flows of the plurality of flows.

### Claim 4 (depends on 3)

The system according to claim 3, wherein the one or more constraints are expressed as a function of decision variables.

### Claim 5 (depends on 3)

The system according to claim 3, wherein the one or more constraints comprise one of a component constraint enforcing semantics of an external view of one or more of the components, a graph constraint enforcing semantics of the plurality of flows of query variables, and a predecessor constraint enforcing semantics of one or more potential predecessors.

### Claim 6 (depends on 3)

The system according to claim 3, further comprising an integral linear programming (ILP) solver, wherein the cost determination and ranking module uses the ILP solver to solve a linear optimization problem of determining the combination of the plurality of flows between the plurality of components that results in the minimum cost under the one or more constraints generated by the constraint module.

### Claim 7 (depends on 1)

The system according to claim 1, wherein the graph pattern comprises at least one of a triple pattern and an operation on more than one triple pattern.

### Claim 8 (depends on 1)

The system according to claim 1, wherein a component of the plurality of components represents an access method for the graph pattern.

### Claim 9 (depends on 1)

The system according to claim 1, wherein a first component of the plurality of components comprises at least one proxy component representing a second component of the plurality of components that is connected to a query variable input of the first component.

### Claim 10 (depends on 1)

The system according to claim 1, wherein the minimum cost is a function of one or more access methods for evaluating each graph pattern.

### Claim 11

A method for optimizing a query, comprising:
building a data structure for a query, the data structure including a plurality of components, wherein each of the plurality of components corresponds to at least one graph pattern;
determining a plurality of flows of query variables between the plurality of components; and
determining a combination of the plurality of flows between the plurality of components that results in a minimum cost to execute the query.

### Claim 12 (depends on 11)

The method according to claim 11, wherein determining the plurality of flows of query variables comprises ruling out one or more flows that would violate semantics of one or more control statements in the query.

### Claim 13 (depends on 11)

The method according to claim 11, further comprising generating one or more constraints for ruling out invalid flows of the plurality of flows.

### Claim 14 (depends on 13)

The method according to claim 13, wherein the one or more constraints are expressed as a function of decision variables.

### Claim 15 (depends on 13)

The method according to claim 13, wherein the one or more constraints comprise one of a component constraint enforcing semantics of an external view of one or more of the components, a graph constraint enforcing semantics of the plurality of flows of query variables, and a predecessor constraint enforcing semantics of one or more potential predecessors.

### Claim 16 (depends on 13)

The method according to claim 13, further comprising using an integral linear programming (ILP) solver to solve a linear optimization problem of determining the combination of the plurality of flows between the plurality of components that results in the minimum cost under the one or more generated constraints.

### Claim 17 (depends on 11)

The method according to claim 11, wherein the graph pattern comprises at least one of a triple pattern and an operation on more than one triple pattern.

### Claim 18 (depends on 11)

The method according to claim 11, wherein a component of the plurality of components represents an access method for the graph pattern.

### Claim 19 (depends on 11)

The method according to claim 11, wherein a first component of the plurality of components comprises at least one proxy component representing a second component of the plurality of components that is connected to a query variable input of the first component.

### Claim 20 (depends on 11)

The method according to claim 11, wherein the minimum cost is a function of one or more access methods for evaluating each graph pattern.

### Claim 21 (depends on 11)

The method according to claim 11, wherein determining the combination of the plurality of flows that results in the minimum cost is performed within a predetermined time limit.

### Claim 22

An article of manufacture comprising a computer readable storage medium comprising program code tangibly embodied thereon, which when executed by a computer, performs method steps for optimizing a query, the method steps comprising:
building a data structure for a query, the data structure including a plurality of components, wherein each of the plurality of components corresponds to at least one graph pattern;
determining a plurality of flows of query variables between the plurality of components; and
determining a combination of the plurality of flows between the plurality of components that results in a minimum cost to execute the query.
