# US 10,120,902 B2 · Apparatus and method for processing distributed relational algebra operators in a distributed database

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

- Number: US 10,120,902 B2
- Document ID: US10120902B2
- Status: Granted
- Kind: B2
- Application number: 14/185,802
- Filed: 2014-02-20
- Published: 2015-08-20
- Granted: 2018-11-06
- Earliest claimed: 2014-02-20
- Assignees: Citus Data Bilgi Islemleri Ticaret A.S.
- Applicants: Citus Data Bilgi Islemleri Ticaret A.S.
- Inventors: Ozgun Erdogan; Sumedh Pathak; Hadi Moshayedi; Metin Doslu
- Web page: https://patentgrep.com/patent/US10120902B2

## CPC

- G06F 16/24544: {Join order optimisation}
- G06F 16/24542: {Plan optimisation}
- G06F 16/2471: {Distributed queries}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A database system includes a query planner with instructions executed by a processor to generate a logical plan tree. Each node of the logical plan tree is a distributed relational algebra operator. Each child node of the logical plan tree produces results processed by a parent node. The logical plan tree includes a distributed relational operator that reparations tuples of results that are at least 1 GB on a dimension and regroups the tuples on the dimension to avoid broadcasting the tuples between machines and thereby avoid consumption of network bandwidth associated with broadcasting the tuples. The logical plan tree is modified according to algebraic transformation rules. The logical plan tree is mapped to distributed query execution primitives. The distributed query execution primitives are processed on machines storing partitions of a distributed database table.

## Claims

### Claim 1

A database system, comprising:
a query planner with instructions executed by a processor to generate a logical plan tree, wherein each node of the logical plan tree is a distributed relational algebra operator, wherein at least one distributed relational algebra operator is a distributed extended relational algebra operator that represents at least one of an aggregation operator, a sorting operator and an extended projection and wherein each child node of the logical plan tree produces results processed by a parent node, wherein the logical plan tree includes a distributed relational operator that repartitions tuples of results that are at least 1 GB on a dimension and regroups the tuples on the dimension to avoid broadcasting the tuples between machines and thereby avoid consumption of network bandwidth associated with broadcasting the tuples,
wherein the logical plan tree is mapped to distributed query execution primitives, and wherein the distributed query execution primitives are processed on a plurality of machines storing partitions of a distributed database table,
wherein the aggregation operator is used by a grouping operator and applies one of sum, count, min, max and average functions, the sorting operator turns a relation into a list of tuples sorted according to one or more attributes and the extended projection performs computations involving columns of an argument relation to produce new columns; and
wherein the query planner has instructions executed by the processor to generate logical plan tree instances, including a first logical plan tree instance with the aggregation operator, a second logical plan tree instance with the sorting operator and a third logical plan tree instance with the extended projection.

### Claim 2 (depends on 1)

The database system of claim 1 wherein the partitions of the distributed database table are modeled as modular blocks, wherein each machine holds a plurality of modular blocks.

### Claim 3 (depends on 1)

The database system of claim 1 wherein the logical plan tree includes a collect node operative as a parent to collect tuples of results produced by a child node.

### Claim 4 (depends on 3)

The database system of claim 3 wherein the collect node is moved up the logical plan tree when a parent operator of the collect node is unary and the collect node is commutative with the parent operator.

### Claim 5 (depends on 3)

The database system of claim 3 wherein e collect node is moved up the logical plan tree when a parent operator of the collect node is binary and the collect node is factorizable with the parent operator.

### Claim 6 (depends on 1)

The database system of claim 1 wherein the distributed relational algebra operator is selected from a filter node, a project node, a union node, a difference node, a join node, and a Cartesian product node.

### Claim 7 (depends on 6)

The database system of claim 6 wherein the distributed relational algebra operator is moved down the logical plan tree when a child operator of the distributed relational algebra operator is unary and the distributed relational algebra operator is commutative with the child operator.

### Claim 8 (depends on 6)

The database system claim 6 wherein the distributed relational algebra operator is moved down the logical plan tree when a children operator of the distributed relational algebra operator is binary and the distributed relational algebra operator is distributive with the children operator.

### Claim 9 (depends on 1)

The database system of claim 1 wherein the distributed relational algebra operator is an extended node, wherein the extended node represents at least one of duplicate elimination, aggregate function, grouping of tuples, a sorting operator, and extended projection.

### Claim 10 (depends on 9)

The database system of claim 9 wherein the extended node is split into a second node and a third node, wherein one of the second node or the third node is moved down the logical plan tree when a child operator is a collect node.

### Claim 11 (depends on 1)

The database system of claim 1 wherein the query planner applies logical algebraic transformations to move nodes in the logical plan tree, wherein the logical algebraic transformations observe the commutativity, distributivity, idempower, or associativity properties of the distributed relational algebra operators.

### Claim 12 (depends on 1)

The database system of claim 1 wherein the query planner includes a join strategy optimizer with instructions executed by a machine to estimate the network bandwidth for a plurality of alternate join strategies to produce network bandwidth estimates and to select a join strategy associated with the lowest network bandwidth estimate.

### Claim 13 (depends on 12)

The database system of claim 12 wherein selecting a join strategy includes selecting a join method and a join order.

### Claim 14 (depends on 13)

The database system of claim 13 wherein a join method is selected from a broadcast join, a colocated join, a single repartition join, a dual repartition join, and a Cartesian product join.

### Claim 15 (depends on 12)

The database system of claim 12 wherein the join strategy optimizer uses statistics about underlying data of the distributed database table to estimate the network bandwidth for the plurality of alternate join strategies.

### Claim 16 (depends on 15)

The database system of claim 15 wherein the statistics include at least one of sizes for the partitions of the distributed database table, minimum and maximum values of attributes in the partitions of the distributed database table, histograms on attributes in the partitions of the distributed database table, and random samples of the tuples in the partitions of the distributed database table.

### Claim 17 (depends on 12)

The database system of claim 12 wherein the join strategy optimizer uses heuristic based techniques.

### Claim 18 (depends on 12)

The database system of claim 12 wherein the join strategy optimizer uses cost based techniques.

### Claim 19 (depends on 12)

The database system of claim 12 wherein the join strategy optimizer estimates the network bandwidth for the plurality of alternate join strategies using at least one of dynamic programming, Selinger-style dynamic programming, greedy search, and branch-and-bound search.

### Claim 20 (depends on 1)

The database system of claim 1 wherein mapping the logical plan tree to distributed query execution primitives includes at least one of partition pruning and join pruning.

### Claim 21 (depends on 1)

The database system of claim 1 wherein the distributed query execution primitives are modeled within a physical plan tree.

### Claim 22 (depends on 21)

The database system of claim 21 wherein each subtree of the logical plan tree enclosed by a collect node or repartition node is represented as a job in the physical plan tree.

### Claim 23 (depends on 21)

The database system of claim 21 wherein the job in the physical plan tree has a plurality of tasks, wherein each task is assigned to one or more machines.

### Claim 24 (depends on 1)

The database of claim 1 wherein each distributed query execution primitive is selected from a SQL query, a data transmit function, a map function, and a merge function.

### Claim 25 (depends on 1)

The database of claim 1 wherein results produced by a child node are fragmented across the plurality of machines to form result fragments, wherein each result fragment is assigned to one or more machines.