dolthub / dolthub/dolt

Optimize DISTINCT and GROUP BY for key prefixes

Open
#9,596 0 comments 0 reactions 0 assignees View on GitHub
analyzer enhancement performance
Dominant language
Go
Stars
24.4k
Forks
873
Avg merge
1d 5h
Merged PRs (30d)
108

Description

If a table `test` has an index on a column `c0`, then the following queries can all be optimized by an engine that is aware of the tree structure of tables:

- `SELECT DISTINCT c0 FROM test;`
- `SELECT c0, COUNT(*) FROM test GROUP BY c0;`

These are both queries that a user might reasonably want to know about an indexed column: what different values does it have, and how many rows have each of these values? These are also both things that can be efficiently computed with a tree walk: the algorithm can detect when the key column doesn't change inside a block and read that block's count instead of recursing into it.

However, we don't currently optimize either of these queries.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.