Perform large-scale point queries using a Bloomfilter index-MaxCompute(MaxCompute)-阿里云帮助中心

A Bloom filter (BF) is an efficient probabilistic data structure. MaxCompute supports Bloomfilter indexes for large-scale point query scenarios. This feature reduces unnecessary data scanning during queries, which improves query efficiency and performance. This topic describes how to use Bloomfilter indexes and provides examples.

Background information

Large-scale point queries are a common data warehouse scenario. You typically specify values in various columns to retrieve matching results from large datasets. In big data scenarios, the result data may be scattered across many files. Therefore, high-performance large-scale point queries require powerful retrieval capabilities.

MaxCompute reads data by table or partition. Predicate pushdown at the storage layer filters data based on the local metadata of files in tables or partitions. For more information, see ANALYZE. If data is scattered, filtering based on local metadata, such as the MIN or MAX value in a column, has a limited effect.

If the query columns are fixed, you can use a clustered table and set the Clustering Key as a filter condition. This method quickly excludes buckets that do not need to be read and filters data within the remaining buckets to accelerate queries. If you perform operations such as aggregation on conditional fields or joins with other tables, you can use the Shuffle Removal feature of clustering to further capitalize on the advantages of clustered tables. However, clustered tables still have the following drawbacks:

For hash-clustered tables, data is filtered only if the query condition contains all Clustering Keys. For range-clustered tables, the filtering effect is optimal only if the query condition includes the prefix of the Clustering Key and matches from left to right in the order of the Clustering Keys. If the query condition does not include the prefix, the filtering effect is poor.
If the query condition does not contain a Clustering Key, no filtering occurs. Therefore, clustered tables may be ineffective for queries on tables that have unfixed conditions.
When you write data, you must shuffle the data based on specified fields. This increases costs. If you encounter skewed keys, tasks may have long tails.

To address these issues, MaxCompute introduced the Bloomfilter index for large-scale point query scenarios.

Prerequisites

You have created a MaxCompute project. For more information, see Create a MaxCompute project.
Schema Evolution is enabled for your project. If Schema Evolution is not enabled for your project, you must run the setproject odps.schema.evolution.enable=true; command at the project level to ensure that subsequent operations can run successfully. Otherwise, an error similar to Failed to run ddltask - Schema evolution DDLs is not enabled in project:default is reported.

Function Introduction

A point query essentially checks whether an element exists in a set. A Bloomfilter can perform this check with high efficiency. Therefore, Bloomfilter indexes are used in both database and data lake technologies to support more granular data or file pruning.

Unlike database indexes such as B-tree or R-tree that locate a specific row, big data scenarios favor more lightweight indexes because of the cost of index building and maintenance. A Bloomfilter is highly efficient in both space and query speed, which makes it suitable for file pruning in point query scenarios. For this reason, MaxCompute uses this type of index.

Compared to clustered tables, a Bloomfilter index has the following advantages:

Efficient: Filters invalid data at a minimal cost.
Highly extensible: You can create a Bloomfilter index on one or more columns of a table. You can also use it with a clustered index by creating a Bloomfilter index on a non-Clustering Key.
Effective filtering: Provides a good filtering effect in scenarios with high cardinality and compact data distribution.

Advantages and disadvantages of a Bloomfilter index

Advantages
- High efficiency: The resource consumption for insert and query operations is lower than that of ordinary indexes.
- Space saving: It uses a bit array. For example, a bit array with 2³² (4,294,967,296) bits occupies only 512 MB of memory.
  Note
  The memory space that the bit array occupies is calculated as follows: 4294967296/8/1024/1024=512 MB.
Disadvantages
It has a certain false positive probability (FPP). An element that is not in a set might be incorrectly identified as being in the set. However, for most scenarios, consuming a few resources to read files that contain no data does not affect the overall efficiency. The final business accuracy is also not affected.

Bloom filter index scenarios

If you use one or more columns in a table as a condition for point query filtering, you can build a Bloomfilter index on the query columns that provide a significant filtering effect.
If you perform point query filtering on fields in a clustered table other than the Clustering Key, you can build a Bloomfilter index on the query columns.
After data in a clustered table is sorted by the Clustering Key, Sorted Key, or Z-order function, you can build a Bloomfilter index on the inserted data columns to achieve a better filtering effect.

Bloomfilter index limits

A Bloomfilter index is suitable only for equality checks, including = and in. It is not supported for range queries that use operators such as >, >=, <, or <=, or for IS NULL and IS NOT NULL queries.
The filtering effect depends on the data distribution. If the data is sparsely distributed, a Bloomfilter index may not filter data effectively.
You cannot build a Bloomfilter index on DECIMAL, INTERVAL_DAY_TIME, INTERVAL_YEAR_MONTH, or complex types such as STRUCT, MAP, ARRAY, and JSON.

Instructions

The following sections describe how to generate, use, view, and delete a Bloomfilter index, and how to change its properties.

Generate a Bloomfilter index

Create a Bloomfilter index

Use the following syntax:

CREATE BLOOMFILTER INDEX <index_name>
ON TABLE <table_name>
FOR COLUMNS(<column_name>)
IDXPROPERTIES('numitems'='xxx', 'fpp' = 'xx')
[COMMENT 'idxcomment'];

The following describes the parameters:

Parameter	Description
index_name	The name of the index.
table_name	The name of the table where the index resides.
column_name	The name of the column on which to create the index.
numitems	The estimated number of elements to be stored in the Bloomfilter. This value specifies the capacity of the Bloomfilter so that enough memory is allocated to store the expected number of elements. This setting affects the total number of bits used in the Bloomfilter and is important for filtering quality. If this value is too large, the bit array of the Bloomfilter is sparsely populated. This wastes disk space and degrades query performance. If this value is too small, the bit array of the Bloomfilter is too full. This increases the FPP of the Bloomfilter. The value must be greater than 0. You can estimate this value based on the number of distinct values in the index column. The maximum value cannot exceed 10,000,000.
fpp	The false positive probability. The value must be in the range `(0,1]`. A smaller value indicates higher accuracy for the BF but also larger storage usage. The recommended value is 0.1.

Note

Currently, you can create a Bloomfilter index on only one column of a table at a time. However, you can create separate Bloomfilter indexes for multiple columns of a table.

Merge a Bloomfilter index

No additional operations are required for incremental data. You can simply run the data insertion statement to merge the Bloomfilter index.

Use the following syntax:

INSERT OVERWRITE TABLE <table_name> [PARTITION <partition_spec>]
SELECT ......

The following table describes the parameters.

Parameter	Description
table_name	The name of the table where the index resides.
partition_spec	The information about the partitions into which you want to insert data. Expressions, such as functions, are not allowed. Only constants are supported. The format is `(partition_col1 = partition_col_value1, partition_col2 = partition_col_value2, ...)`.

When you insert new data into a table that has a Bloomfilter index, the system incrementally generates local Bloomfilter index data for the data file and supports predicate pushdown at the storage layer. Then, the system starts a BloomfilterAutoMergeTask to automatically merge the data into a new Bloomfilter index file. This process supports filtering during the planning stage and allows for more accurate resource allocation for the task. If the following keyword appears in the JSON Summary in Logview, the Bloomfilter index merge is successful:

You can then view the time that is taken to merge the Bloomfilter index on the SubStatusHistory tab in Logview:

Note

The data write task completes normally, regardless of whether the Bloomfilter index merge task is successful.
If the Bloomfilter index fails to merge because of a system issue, the new data cannot be filtered during the planning stage. However, the local Bloomfilter index data for the new data can still be used for filtering through predicate pushdown at the storage layer. You can check the execution plan to determine whether the Bloomfilter index was used. If not, you can run the REBUILD command on the index for the partition that was not effective during the query.
Dynamic partitions do not currently support automatic merging. After you write the data, you must manually run the REBUILD command on the index on the updated partitions.

If the automatic merge task fails as shown in the preceding figure, you must explicitly run the following merge command. This command supports rebuilding the Bloomfilter indexes for multiple partitions at the same time.

ALTER TABLE <table_name> [PARTITION <partition_spec>] REBUILD BLOOMFILTER INDEX;

Example 1:

ALTER TABLE table_name PARTITION (pt>='20210101') REBUILD BLOOMFILTER INDEX;

Example 2:

ALTER TABLE table_name PARTITION (pt>'20210101' AND pt<'20210303') REBUILD BLOOMFILTER INDEX;

Use a Bloomfilter index

Before you run a query, you can run the following command to enable the Bloomfilter index feature:

SET odps.sql.enable.bloom.filter.index=true;

Note

After the Bloomfilter index is enabled, an extra job is added to the query to perform file pruning. This reduces the number of files that the task needs to read.
If you do not set this parameter, file pruning cannot be performed in the planning stage. However, the system can still use predicate pushdown at the storage layer to filter data based on the local Bloomfilter index data. During the beta release, the default value of this parameter is `false`. The default value may be changed to `true` later based on online usage.
If the filtering effect of the Bloomfilter index is not significant, for example, if the result is scattered across multiple files and pruning does not significantly reduce the number of files, setting this parameter to `true` requires an extra index retrieval task. This may degrade task performance. In this case, you can set the parameter to `false`.

The following example shows a task in which a Bloomfilter index is in effect:

SET odps.sql.enable.bloom.filter.index=true;
SELECT * FROM bloomfilter_index_test WHERE key=392 AND value="val_392";

In Logview, job_1 in the following figure is the index job that uses the Bloomfilter index for file pruning.

In the Summary, the virtual table with the bf suffix corresponds to the Bloomfilter index file.

Note

For large amounts of data, the generated Bloomfilter file can be very large. Therefore, MaxCompute starts a distributed job for file pruning.

View the Bloomfilter index of a table

SHOW INDEXES ON <table_name>;

The following section describes the parameter.

`table_name`: The name of the table where the index resides.

Delete a Bloomfilter index

DROP INDEX [IF EXISTS] <idx_name> ON TABLE <table_name>;

The following section describes the parameters.

`idx_name`: The name of the index.
`table_name`: The name of the table where the index resides.

Change Bloomfilter index properties

ALTER INDEX <idx_name> ON <table_name> 
SET IDXPROPERTIES(['comment' = 'a'], ['fpp' = '0.01']);

The following section describes the parameters.

`idx_name`: The name of the index.
`table_name`: The name of the table where the index resides.

Examples

Example 1: Create a Bloomfilter index on a regular partitioned table

Prepare the data.

SET odps.namespace.schema=true;
SELECT * FROM bigdata_public_dataset.TPCDS_10G.call_center;

Create a partitioned test table named call_center_test.

CREATE TABLE IF NOT EXISTS call_center_test(
    cc_call_center_sk BIGINT NOT NULL, cc_call_center_id CHAR(16) NOT NULL, 
    cc_rec_start_date DATE, cc_rec_end_date DATE, 
    cc_closed_date_sk BIGINT, cc_open_date_sk BIGINT, 
    cc_name VARCHAR(50), cc_class VARCHAR(50), 
    cc_employees BIGINT, cc_sq_ft BIGINT, 
    cc_hours CHAR(20), cc_manager VARCHAR(40), 
    cc_mkt_id BIGINT, cc_mkt_class CHAR(50), 
    cc_mkt_desc VARCHAR(100), cc_market_manager VARCHAR(40), 
    cc_division BIGINT, cc_division_name VARCHAR(50), 
    cc_company BIGINT, cc_company_name CHAR(50), 
    cc_street_number CHAR(10), cc_street_name VARCHAR(60), 
    cc_street_type CHAR(15), cc_suite_number CHAR(10), 
    cc_city VARCHAR(60), cc_county VARCHAR(30), 
    cc_state CHAR(2), cc_zip CHAR(10), 
    cc_country VARCHAR(20), cc_gmt_offset DECIMAL(5,2), 
    cc_tax_percentage DECIMAL(5,2)
)
PARTITIONED BY (ds STRING );

Create an index.

CREATE BLOOMFILTER INDEX call_center_test_idx01 
ON table call_center_test 
FOR columns(cc_call_center_sk) 
IDXPROPERTIES('fpp' = '0.03', 'numitems'='1000000') 
COMMENT 'cc_call_center_sk index';

Import data.
Import data from the bigdata_public_dataset.TPCDS_10G.call_center public dataset table into the call_center_test table.
```
SET odps.namespace.schema=true;
INSERT OVERWRITE TABLE call_center_test PARTITION (ds='20241115') SELECT * FROM bigdata_public_dataset.TPCDS_10G.call_center LIMIT 10000;
```
If the following keyword appears in the JSON Summary in Logview, the Bloomfilter index merge is successful:

Query data.

SET odps.sql.enable.bloom.filter.index=true;
SELECT * FROM call_center_test WHERE cc_call_center_sk =10 AND ds='20241115';

The following result is returned:

+-------------------+-------------------+-------------------+-----------------+-------------------+-----------------+---------------+------------+--------------+------------+------------+----------------+------------+----------------------------+---------------------------------------------------------------------------------------+-------------------+-------------+------------------+------------+-----------------+------------------+----------------+----------------+-----------------+------------+---------------+------------+------------+---------------+---------------+-------------------+------------+
| cc_call_center_sk | cc_call_center_id | cc_rec_start_date | cc_rec_end_date | cc_closed_date_sk | cc_open_date_sk | cc_name       | cc_class   | cc_employees | cc_sq_ft   | cc_hours   | cc_manager     | cc_mkt_id  | cc_mkt_class               | cc_mkt_desc                                                                           | cc_market_manager | cc_division | cc_division_name | cc_company | cc_company_name | cc_street_number | cc_street_name | cc_street_type | cc_suite_number | cc_city    | cc_county     | cc_state   | cc_zip     | cc_country    | cc_gmt_offset | cc_tax_percentage | ds         |
+-------------------+-------------------+-------------------+-----------------+-------------------+-----------------+---------------+------------+--------------+------------+------------+----------------+------------+--------------+-------------+---------------------------------------------------------------------------------------+-------------------+-------------+------------------+------------+-----------------+------------------+----------------+----------------+-----------------+------------+---------------+------------+------------+---------------+---------------+-------------------+------------+
| 10                | AAAAAAAAKAAAAAAA  | 1998-01-01        | 2000-01-01      | NULL              | 2451050         | Hawaii/Alaska | large      | 187          | 95744      | 8AM-8AM    | Gregory Altman | 2          | Just back responses ought  | As existing eyebrows miss as the matters. Realistic stories may not face almost by a  | James Mcdonald    | 3           | pri              | 3          | pri             | 457              | 1st            | Boulevard      | Suite B         | Midway     | Walker County | AL         | 31904      | United States | -6            | 0.02              | 20241115   |
+-------------------+-------------------+-------------------+-----------------+-------------------+-----------------+---------------+------------+--------------+------------+------------+----------------+------------+----------------------------+---------------------------------------------------------------------------------------+-------------------+-------------+------------------+------------+-----------------+------------------+----------------+----------------+-----------------+------------+---------------+------------+------------+---------------+---------------+-------------------+------------+

The following information in Logview indicates that the Bloomfilter index is in effect. The virtual table with the bf suffix corresponds to the Bloomfilter index file.

View the Bloomfilter index of the table.

SHOW INDEXES ON call_center_test;

The following result is returned:

ID = 20241115093930589g9biyii****
{"Indexes": [{
            "id": "aabdaeb10a7b4e99a94716dabad8****",
            "indexColumns": [{"name": "cc_call_center_sk"}],
            "name": "call_center_test_idx01",
            "properties": {
                "comment": "cc_call_center_sk index",
                "fpp": "0.03",
                "numitems": "1000000"},
            "type": "BLOOMFILTER"}]}

OK

Change the Bloomfilter index properties.
The previous step shows that the original value of the numitems property is 1000000. You can run the following commands to change the property value to 10000.
```
-- Change the property.
ALTER INDEX call_center_test_idx01 ON call_center_test SET IDXPROPERTIES('fpp' = '0.03', 'numitems'='10000');

-- View the property.
SHOW INDEXES ON call_center_test;
```
The following result is returned:

Example 2: Create a Bloomfilter index on a hash-clustered partitioned table

Prepare the data.
1. Create the scope_tmp table.
```
CREATE TABLE if NOT EXISTS scope_tmp(
    phone STRING, 
    card STRING, 
    machine STRING, 
    geohash STRING);
```
2. On the MaxCompute client (odpscmd), you can use the Tunnel command to upload data to the scope_tmp table. For example, to upload the scope2.csv file from the bin directory of the MaxCompute client, you can run the following command:
```
Tunnel upload scope2.csv scope_tmp;
```

Create a partitioned test table named scope_hash_pt.

CREATE TABLE scope_hash_pt (
    phone STRING, 
    card STRING, 
    machine STRING,
    geohash STRING 
)
PARTITIONED BY (ds STRING)
clustered by (phone) 
sorted by (card) 
into 512 buckets;

Create an index for the scope_hash_pt partitioned table.

CREATE BLOOMFILTER INDEX scope_hash_pt_index01 
ON TABLE scope_hash_pt 
FOR columns(card) 
IDXPROPERTIES('fpp' = '0.03', 'numitems'='1000000') 
COMMENT 'card index';

You can import data.
```
INSERT OVERWRITE TABLE scope_hash_pt PARTITION (ds='20241115') SELECT * FROM scope_tmp;
```
If the following keyword appears in the JSON Summary in Logview, the Bloomfilter index merge succeeded:

You can query data from the scope_hash_pt table.

SET odps.sql.enable.bloom.filter.index=true;
SELECT * FROM scope_hash_pt WHERE card='073415764266290' and ds='20241115';

The following is the result:

+-------------+-----------------+----------------+------------+------------+
| phone       | card            | machine        | geohash    | ds         |
+-------------+-----------------+----------------+------------+------------+
| 1576426**** | 073415764266290 | 51133960245770 | fWbDDsf    | 20241115   |
+-------------+-----------------+----------------+------------+------------+

The following information in Logview indicates that the Bloom filter index is active. The virtual table with the bf suffix represents the Bloom filter index file.

Example 3: Create a Bloomfilter index on a partitioned table with Z-order data redistribution

Prepare the data. For more information, see Hash Bloomfilter data preparation.

Create a partitioned test table named scope_zorder_pt.

CREATE TABLE scope_zorder_pt(
    phone STRING, 
    card STRING, 
    machine STRING, 
    geohash STRING, 
    zvalue BIGINT
)
PARTITIONED BY (ds STRING)
;

Create an index.

CREATE BLOOMFILTER INDEX scope_zorder_pt_index01 
ON TABLE scope_zorder_pt 
FOR COLUMNS (card) 
IDXPROPERTIES('fpp' = '0.05', 'numitems'='1000000')
COMMENT 'idxcomment';

Import the data.

Download the following two JAR packages and save them locally, for example, to the D:\ drive.
- odps-zorder-1.0-SNAPSHOT.jar
- odps-zorder-1.0-SNAPSHOT-jar-with-dependencies.jar

Run the following commands to upload them as JAR resources.

-- Add resources.
ADD JAR D:\odps-zorder-1.0-SNAPSHOT.jar;
ADD JAR D:\odps-zorder-1.0-SNAPSHOT-jar-with-dependencies.jar;

Create a function by running the following command:

CREATE FUNCTION zorder AS 'com.aliyun.odps.zorder.evaluateZValue2WithSize' USING ' odps-zorder-1.0-SNAPSHOT-jar-with-dependencies.jar';

Use the function to write data to the partitioned test table scope_zorder_pt.

-- Remove the LIMIT restriction for ORDER BY.
SET odps.sql.validate.orderby.limit=false;

-- Write data.
INSERT OVERWRITE TABLE scope_zorder_pt PARTITION (ds='20241115') SELECT *,zorder(HASH(phone), 100000000, HASH(card), 100000000) AS zvalue FROM scope_tmp ORDER BY zvalue;

If the following keyword appears in the JSON Summary in Logview, it indicates that the Bloomfilter index merge was successful:

Query the data.

SET odps.sql.enable.bloom.filter.index=true;  
SELECT * FROM scope_zorder_pt WHERE card='073415764266290' AND ds='20241115';

The following result is returned:

+-------------+-----------------+----------------+------------+---------------------+------------+
| phone       | card            | machine        | geohash    | zvalue              | ds         |
+-------------+-----------------+----------------+------------+---------------------+------------+
| 1576426**** | 073415764266290 | 51133960245770 | fWbDDsf    | 3590549286038929408 | 20241115   |
+-------------+-----------------+----------------+------------+---------------------+------------+

The following information in Logview indicates that the Bloomfilter index is used. The virtual table with the bf suffix corresponds to the Bloomfilter index file.

Billing

Indexes occupy storage space and are metered based on usage in Pangu, the Apsara Distributed File System. This storage is billed as standard storage.
Creating and using indexes triggers additional computing tasks. For a query, the system first calculates the file information for the required data based on the index file. Then, based on the index calculation result, the system filters the input data during the execution plan stage to reduce the input data volume and compute the final result. Both index calculations and queries incur computing fees.
Indexes can speed up jobs for subscription customers. The resources used for index building and calculations are part of the user's subscription resources. Therefore, using indexes does not affect the cost of subscription jobs.

SQL operations trigger the following index-related tasks:

SQL operation	Triggered task	Input data volume for the index-related task	Billing
CREATE	Data Definition Language (DDL) operations do not trigger index building tasks.	None	No fees are incurred.
REBUILD	Index building. If an index exists, the REBUILD operation triggers an index rebuild. If no index exists, the REBUILD operation triggers a new index build.	When you rebuild an index, read and write operations are performed on the index columns and other columns simultaneously. Therefore, the input data volume is the full data volume after being filtered by the query condition for the index rebuild.	Index billing formula: `Unit price of a pay-as-you-go SQL job × Complexity 1 × Input data volume for the index-related task`. SQL query billing is based on the standard pay-as-you-go logic for SQL jobs.
INSERT	Builds an index for the newly inserted data. Executes the query in the SELECT part.	The data volume of the indexed columns in the table of the SELECT query.
SELECT	A query task uses the index calculation to output information for filtering data in the SELECT query. Executes the SELECT query based on the built index.	The data volume of the index file.