- Number
- 12086136
- Published
- 2024-09-10
- Filed
- 2020-02-04
- Assignee
- DISNEY ENTERPRISES, INC.
- Inventors
- Molinari; Guy
- CPC
- G06F16/24544; G06F16/2237; G06F16/24532; G06F16/24537; G06F16/2456
- Verdict
- Set aside database engineering, generic
- 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 (1) 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 (2) 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. (3) 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 locate and
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 of the first result bitmap corresponds to a respective first primary key value included in a set of first primary key values associated with the first table; 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 respective second primary key value included in a set of second primary key values associated with the second table; modifying the second result bitmap based on a bit-slice index associated with the second table to generate a third result bitmap, wherein each bit of the third result bitmap corresponds to one of the first primary key values included in the set of first primary key values, and wherein modifying the second result bitmap comprises transforming, within each data record of the second result bitmap for which a binary bit is set, one of the second primary key values associated with the data record to one of the first primary key values included in the set of first primary key 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 of the first result bitmap corresponds to a respective first primary key value included in a set of first primary key values associated with the first table; 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 respective second primary key value included in a set of second primary key values associated with the second table; modifying the second result bitmap based on a bit-slice index associated with the second table to generate a third result bitmap, wherein each bit of the third result bitmap corresponds to one of the first primary key values included in the set of first primary key values, and wherein modifying the second result bitmap comprises transforming, within each data record of the second result bitmap for which a binary bit is set, one of the second primary key values associated with the data record to one of the first primary key values included in the set of first primary key 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 of the first result bitmap corresponds to a respective first primary key value included in a set of first primary key 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 respective second primary key value included in a set of second primary key values, modifying the second result bitmap based on a bit-slice index associated with the second table to generate a third result bitmap, wherein each bit of the third result bitmap corresponds to one of the first primary key values included in the set of first primary key values, and wherein modifying the second result bitmap comprises transforming, within each data record of the second result bitmap for which a binary bit is set, one of the second primary key values associated with the data record to one of the first primary key values included in the set of first primary key values, and generating at least one query result based on the first result bitmap and the third result bitmap.