apache / apache/paimon

[Feature] Using bitmap index to accelerate the query

Offen
#4,530 2 Kommentare 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen
enhancement
Vorherrschende Sprache
Java
Sterne
3.4k
Forks
1.4k
Ø Merge
1 T. 9 Std.
Gemergte PRs (30 T.)
423

Beschreibung

### Search before asking

- [X] I searched in the [issues](https://github.com/apache/paimon/issues) and found nothing similar.

### Motivation

Currently we have introduced bitmap indexes. There are some optimisations that we can do when the user queries only against the bitmap indexed columns.

Suppose we have a table `usershop_behavior` with a bitmap index on the `gender` column and a bsi index on the `gmv` column.
```sql
CREATE TABLE usershop_behavior (
uid BIGINT
gender STRING,
gmv BIGINT
) WITH (
'file-index.bitmap.columns' = 'gender',
'file-index.bsi.columns' = 'gmv'
);
```

The bitmap index and bsi index can be used not only for filtering, but also for some simple aggregation like:
```sql
SELECT
gender,
COUNT(*) AS total,
SUM(gmv) AS total_gmv,
AVG(gmv) AS avg_gmv
FROM usershop_behavior
GROUP BY gender

SELECT
gender,
COUNT(*) AS total,
SUM(gmv) AS total_gmv,
AVG(gmv) AS avg_gmv
FROM usershop_behavior
WHERE gender='M'
GROUP BY gender
```

BSI index can be useful in topk scenarios
```sql
SELECT *
FROM usershop_behavior
ORDER BY gmv DESC
LIMIT 10;

SELECT *
FROM usershop_behavior
WHERE gender='M'
ORDER BY gmv DESC
LIMIT 10;
```

### Solution

Apache Flink and Apache Spark are already provides some interfaces. e.g.

Apache Flink:
`org.apache.flink.table.connector.source.abilities.SupportsAggregatePushDown`

Apache Spark:
`org.apache.spark.sql.connector.read.SupportsPushDownTopN`
`org.apache.spark.sql.connector.read.SupportsPushDownAggregates`

When queries hit the bitmap index rules, we can rewrite TableScan to BitmapIndexScan.

### Anything else?

Currently our index is designed to be used only for Data Skipping and it is not as reliable as filtering using partitioned keys. (We can't tell the flink&spark engine that filtering with indexes is reliable.)

This is because creating the index is split into several steps.
1. stop the ingesting task
2. using alter table to add index options
3. call rewrite index procedure
4. restart the ingesting task

We need to find a way to make indexes reliable, like partition keys. (e.g. throw exception when index is empty?)
Otherwise it's hard for our index to do its job.

### Are you willing to submit a PR?

- [ ] I'm willing to submit a PR!

Beitragsleitfaden

Für dieses Repository ist kein Beitragsleitfaden indexiert

Rechercherichtung

Beginne damit, die genannten Schnittstellen SupportsAggregatePushDown und SupportsPushDownTopN zu überprüfen, und verfolge anschließend, wie ein TableScan in einen BitmapIndexScan umgeschrieben werden könnte. Lege fest, wie Bitmap- und BSI-Indizes die aufgeführten Aggregationen und Top-k-Abfragen unterstützen würden, einschließlich des zuverlässigen Umgangs mit fehlenden oder unvollständigen Indizes.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Bewertung

Tech-Stack
java, spark
Bereich
data-engineering, databases, performance
Issue-Typ
Feature
Schwierigkeit
5/5
Geschätzter Aufwand
Über eine Woche
Aktivitätsstatus
Veraltet
Klarheit
Muss geklärt werden
Anfängerfreundlichkeit
25/100

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.