dolthub / dolthub/dolt

Optimize OFFSET on indexed table.

Open
#8,878 0 comments 0 reactions 0 assignees View on GitHub
analyzer sql
Dominant language
Go
Stars
24.4k
Forks
873
Avg merge
1d 8h
Merged PRs (30d)
120

Description

It should be possible to efficiently access an offset into an indexed table access.

For example, this query:

`SELECT * FROM tbl WHERE pk > 1234 LIMIT 4000 OFFSET 2000`

results in this plan:

```
+-----------------------------------+
| plan |
+-----------------------------------+
| Limit(4000) |
| └─ Offset(2000) |
| └─ IndexedTableAccess(tbl) |
| ├─ index: [tbl.pk] |
| ├─ filters: [{(1234, ∞)}]|
| └─ columns: [pk] |
+-----------------------------------+
```

This is a common pattern used in paginated results.

Currently, the engine implements this query by seeking to the beginning of the range, and then discarding the first 2000 values it pulls from the iterator. However, this we can do better: because every node in a Dolt prolly tree stores the total number of rows of each of it's children nodes (the "TreeCount"), it's possible to quickly advance the cursor by a given number of positions, by skipping entire tree nodes if none of the node's children are within range.

This is similar to, but distinct from https://github.com/dolthub/dolt/issues/8779. Both are optimizations leveraging the fact that every node stores size information for its children. However, since this structure isn't visible to GMS, Dolt needs to add its own analysis pass, or there otherwise needs to be an interface that the Dolt table can implement to make the optimization possible.

Contributor guide

No contributing guide indexed for this repository

Research direction

No files or tests are named. Start by tracing OFFSET handling for IndexedTableAccess and the prolly tree's TreeCount behavior, then compare the related work in issue #8779. Done means the example query can skip whole tree nodes while preserving the requested range and results.

Written by the indexing model from the issue text.

Assessment

Tech stack
go, sql
Domain
databases, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.