TECHNIQUES FOR EXECUTING JOIN OPERATIONS USING BITMAP INDICES

Number: 20210240708
Published: 2021-08-05
Filed: 2020-02-04
Assignee: DISNEY ENTERPRISES, INC.
Inventors: MOLINARI; Guy
CPC: G06F16/24537; G06F16/2237; G06F16/24544; G06F16/2456; G06F16/24532
Verdict: Set aside database engineering, generic infra
Source: Google Patents · FreePatentsOnline

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.

Background

BACKGROUND Field of the Various Embodiments

The various embodiments relate generally to relational databases and structured query language execution and, more specifically, to techniques for executing join operations using bitmap indices. DESCRIPTION OF THE RELATED ART

A relational database typically includes a set of tables where different types of data records can be stored. The organizational structure of the set of tables is usually defined by a schema that describes, for each table, one or more fields where data values can be stored and the data types associated with those data values. For example, suppose that a given relational database were to store data records related to authors. A schema associated with the relational database could define an “author” table. The “author” table could store “author” data records that include a “name” field and a “birthdate” field. For a given “author” data record, the “name” field would store a character string corresponding to the name of an author, and the “birthplace” field would store a character string corresponding to the birthplace of that author. Each “author” data record also would include an automatically-assigned primary key value to serve as a unique identifier for that data record.

In addition to the set of tables discussed above, a relational database typically includes a query processor that executes queries written in structured query language (SQL). The query processor executes such queries to lo

Claims

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. || 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. || 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.