# US 2012/0254887 A1 · Parallelizing scheduler for database commands

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

- Number: US 2012/0254887 A1
- Document ID: US20120254887A1
- Status: Published application
- Kind: A1
- Application number: 13/077,962
- Filed: 2011-03-31
- Published: 2012-10-04
- Earliest claimed: 2011-03-31
- Assignees: VeriSign, Inc.
- Inventors: John Rodriguez
- Web page: https://patentgrep.com/patent/US20120254887A1

## CPC

- G06F 16/24524: {Access plan code generation and invalidation; Reuse of access plans}
- G06F 16/2308: {Concurrency control (transaction processing G06F9/466)}
- G06F 16/2343: {Locking methods, e.g. distributed locking or locking implementation details}
- G06F 16/2379: {Updates performed during online database operations; commit processing}
- G06F 16/24526: {Internal representations for queries}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system, method, and computer-readable medium, is described that enables a parallelizing scheduler to analyze database instructions, determine data dependencies among instructions, and provide a multi-threaded approach to running instructions in parallel while preserving data dependencies.

## Claims

### Claim 1

A computer-implemented method of parallelizing database commands comprising:
receiving, by a computer, a sequence of database commands;
processing the commands into data dependent chains;
grouping the database commands based on data dependencies into an execution schedule with operation levels, wherein at least one graph level has at least two database operations designated to be performed in parallel; and
providing the execution schedule.

### Claim 2 (depends on 1)

The method of claim 1, wherein the providing comprises:
executing the commands on a database, wherein the commands are executed in parallel based on the execution schedule.

### Claim 3 (depends on 1)

The method of claim 1, wherein the processing comprises:
determining the successor dependencies for each command; and
performing a topological sort based on the successor dependencies.

### Claim 4 (depends on 1)

The method of claim 1, wherein the processing comprises:
determining the predecessor dependencies for each command; and
performing a reverse topological sort based on the predecessor dependencies.

### Claim 5 (depends on 1)

The method of claim 1, wherein the grouping comprises:
organizing commands within the graph levels by moving data dependencies vertically based on a limit to the number of parallel operations in each level.

### Claim 6 (depends on 1)

The method of claim 1, wherein the processing comprises:
representing each command in bit vector notation; and
logically ANDing two commands together to determine whether a data dependency exists.

### Claim 7 (depends on 1)

The method of claim 1, wherein the providing comprises:
providing a file describing the execution schedule.

### Claim 8

A system of parallelizing database commands comprising:
a non-transitory memory storing instructions; and
a processor executing the instructions to cause the system to perform a method comprising:
receiving, by a computer, a sequence of database commands;
processing the commands into data dependent chains;
grouping the database commands based on data dependencies into an execution schedule with operation levels, wherein at least one graph level has at least two database operations designated to be performed in parallel; and
providing the execution schedule.

### Claim 9 (depends on 8)

The system of claim 8, wherein the providing comprises:
executing the commands on a database, wherein the commands are executed in parallel based on the execution schedule

### Claim 10 (depends on 8)

The system of claim 8, wherein the processing comprises:
determining the successor dependencies for each command; and
performing a topological sort based on the successor dependencies.

### Claim 11 (depends on 8)

The system of claim 8, wherein the processing comprises:
determining the predecessor dependencies for each command; and
performing a reverse topological sort based on the predecessor dependencies.

### Claim 12 (depends on 8)

The system of claim 8, wherein the grouping comprises:
organizing commands within the graph levels by moving data dependencies vertically based on a limit to the number of parallel operations in each level.

### Claim 13 (depends on 8)

The system of claim 8, wherein the processing comprises:
representing each command in bit vector notation; and
logically ANDing two commands together to determine whether a data dependency exists.

### Claim 14 (depends on 8)

The system of claim 8, wherein the providing comprises:
providing a file describing the execution schedule.

### Claim 15

A non-transitory computer-readable storage medium containing instructions which, when executed on a processor, perform a method comprising:
receiving, by a computer, a sequence of database commands;
processing the commands into data dependent chains;
grouping the database commands based on data dependencies into an execution schedule with graph levels, wherein at least one graph level has at least two database operations designated to be performed in parallel; and
providing the execution schedule.

### Claim 16 (depends on 15)

The computer-readable medium of claim 15, wherein the providing comprises:
executing the commands on a database, wherein the commands are executed in parallel based on the execution schedule.

### Claim 17 (depends on 15)

The computer-readable medium of claim 15, wherein the processing comprises:
determining the successor dependencies for each command; and
performing a topological sort based on the successor dependencies.

### Claim 18 (depends on 15)

The computer-readable medium of claim 15, wherein the processing comprises:
determining the predecessor dependencies for each command; and
performing a reverse topological sort based on the predecessor dependencies.

### Claim 19 (depends on 15)

The computer-readable medium of claim 15, wherein the grouping comprises:
organizing commands within the graphlevels by moving data dependencies vertically based on a limit to the number of parallel operations in each level.

### Claim 20 (depends on 15)

The computer-readable medium of claim 15, wherein the processing comprises:
representing each command in bit vector notation; and
logically ANDing two commands together to determine whether a data dependency exists.

### Claim 21 (depends on 15)

The computer-readable medium of claim 15, wherein the providing comprises:
providing a file describing the execution schedule.
