# US 2021/0240708 A1 · Techniques for executing join operations using bitmap indices

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

- Number: US 2021/0240708 A1
- Document ID: US20210240708A1
- Status: Published application
- Kind: A1
- Application number: 16/782,025
- Filed: 2020-02-04
- Published: 2021-08-05
- Earliest claimed: 2020-02-04
- Assignees: Disney Enterprises, Inc.
- Applicants: Disney Enterprises, Inc.
- Inventors: Guy MOLINARI
- Web page: https://patentgrep.com/patent/US20210240708A1

## CPC

- G06F 16/24537: {of operators}
- G06F 16/2237: {Vectors, bitmaps or matrices}
- G06F 16/24532: {of parallel queries}
- G06F 16/24544: {Join order optimisation}
- G06F 16/2456: {Join operations}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A database engine uses bitmap slice indices (BSIs) to combine result bitmaps derived from parent and child tables related via one or more foreign key relationships. To execute a query that involves a parent table and a child table, the database engine parses the query into a parent predicate corresponding to the parent table and a child predicate corresponding to the child table. The database engine executes the parent predicate using a parent bitmap index to generate a parent result bitmap and executes the child predicate using a child bitmap index to generate a child result bitmap. The database engine transforms the child result bitmap, based on the BSI, to generate a transformed child result bitmap having columns that correspond to the primary key of the parent table. The database engine can then combine the parent result bitmap directly with the transformed child result bitmap to generate query results.

## Claims

### Claim 1

A computer-implemented method for executing a query across different tables included in a database, the method comprising:
executing a first portion of the query against a first table included in the database to generate a first result bitmap, wherein each bit in the first result bitmap corresponds to a different value included in a first set of values;
executing a second portion of the query against a second table included in the database to generate a second result bitmap, wherein each bit of the second result bitmap corresponds to a different value included in a second set of values;
generating a third result bitmap based on the second result bitmap and a bit-slice index associated with the second table, wherein each bit of the third result bitmap corresponds to a different value included in the first set of values; and
generating at least one query result based on the first result bitmap and the third result bitmap.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein the first portion of the query corresponds to a first condition, and the first result bitmap indicates one or more data records included in the first table that meet the first condition.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1, wherein the second portion of the query corresponds to a second condition, and the second result bitmap indicates one or more data records included in the second table that meet the second condition.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1, wherein the first portion of the query is executed at least partially in parallel with the second portion of the query.

### Claim 5 (depends on 1)

The computer-implemented method of claim 1, wherein a third portion of the query indicates that a JOIN operation should be performed between one or more data records extracted from the first table and one or more data records extracted from the second table.

### Claim 6 (depends on 1)

The computer-implemented method of claim 1, wherein the first table and the second table are associated with one another via a foreign key relationship.

### Claim 7 (depends on 1)

The computer-implemented method of claim 1, wherein the bit-slice index comprises a mapping from the second set of values to the first set of values.

### Claim 8 (depends on 1)

The computer-implemented method of claim 1, wherein the bit-slice index comprises a mapping from each value included in the second set of values to a binary representation of a particular value included in the first set of values.

### Claim 9 (depends on 1)

The computer-implemented method of claim 1, wherein generating the third result bitmap comprises assigning each bit of the second result bitmap a particular value included in the first set of values.

### Claim 10 (depends on 1)

The computer-implemented method of claim 1, further comprising executing an AND operation between the first result bitmap and the second result bitmap to generate the at least one query result.

### Claim 11

A non-transitory computer-readable medium storing program instructions that, when executed by a processor, cause the processor to execute a query across different tables included in a database by performing the steps of:
executing a first portion of the query against a first table included in the database to generate a first result bitmap, wherein each bit in the first result bitmap corresponds to a different value included in a first set of values;
executing a second portion of the query against a second table included in the database to generate a second result bitmap, wherein each bit of the second result bitmap corresponds to a different value included in a second set of values;
generating a third result bitmap based on the second result bitmap and a bit-slice index associated with the second table, wherein each bit of the third result bitmap corresponds to a different value included in the first set of values; and
generating at least one query result based on the first result bitmap and the third result bitmap.

### Claim 12 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein the first portion of the query corresponds to a first condition, and the first result bitmap indicates one or more data records included in the first table that meet the first condition.

### Claim 13 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein the second portion of the query corresponds to a second condition, and the second result bitmap indicates one or more data records included in the second table that meet the second condition.

### Claim 14 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein a third portion of the query indicates that a JOIN operation should be performed between one or more data records extracted from the first table and one or more data records extracted from the second table.

### Claim 15 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein the bit-slice index comprises a mapping from the second set of values to the first set of values.

### Claim 16 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein the step of generating the third result bitmap comprises assigning each bit of the second result bitmap a particular value included in the first set of values.

### Claim 17 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein the step of generating the at least one query result comprises performing an aggregation operation across a combination of the first result bitmap and the second result bitmap.

### Claim 18 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein the step of executing the first portion of the query against the first table comprises scanning the first table to identify one or more data records that meet a condition associated with the first portion of the query.

### Claim 19 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein the step of executing the second portion of the query against the second table comprises scanning the second table to identify one or more data records that meet a condition associated with the second portion of the query.

### Claim 20

A system, comprising:
a memory storing a software application; and
a processor that, when executing the software application, is configured to perform the steps of:
executing a first portion of the query against a first table included in the database to generate a first result bitmap, wherein each bit in the first result bitmap corresponds to a different value included in a first set of values,
executing a second portion of the query against a second table included in the database to generate a second result bitmap, wherein each bit of the second result bitmap corresponds to a different value included in a second set of values,
generating a third result bitmap based on the second result bitmap and a bit-slice index associated with the second table, wherein each bit of the third result bitmap corresponds to a different value included in the first set of values, and
generating at least one query result based on the first result bitmap and the third result bitmap.
