tamnd / tamnd/firepanda

A filter under a sort under a limit should not build the frame in the middle

Open
#682 1 comment 0 reactions 0 assignees View on GitHub
area/plan performance
Dominant language
Mojo
Stars
1
Forks
0
PR merge metrics
PR metrics pending

Description

Found by the hand written and planner pair on ClickBench, #485, and it is the one gap that measurement turned up which is a missing optimization rather than the cost of having a planner.

q23 of the suite is the whole of it:

```sql
SELECT * FROM hits WHERE URL LIKE '%google%' ORDER BY EventTime LIMIT 10;
```

At 1M, ninety five rows out of a million survive the filter and ten of those are the answer. All 105 columns come back with them.

The plan filters, materializes 105 columns of the survivors into a frame, sorts that frame and then takes ten rows off the top. The hand written port in firepanda-bench calls `filter_sort_limit`, which never builds the middle frame at all: it carries positions through the filter and the sort and gathers once, at the end, for the ten rows that are actually returned. That is 4.8 ms against 35.8 ms, on the only query in the suite that asks for the table rather than for a reduction of it, and the width is why the gap is a factor of seven rather than a few percent.

The kernel exists and is used by hand. What is missing is the plan noticing that a filter under a sort under a limit does not need its middle frame.

## Why it is worth doing beyond one query

Filter, sort, limit is the shape of most of ClickBench and a good deal of everything else. It only pays this badly when the projection is wide, which is q23 alone in this suite, but the wide case is exactly the one a user hits with `SELECT *` against a table they did not choose the width of.

The saving is bounded by the width, so it does nothing for a query returning two columns, and the pass should be written knowing that rather than discovered to be pointless there.

## What lands

- [ ] A rule that recognises filter under sort under limit and lowers it to the one operator that carries positions
- [x] The same rule when there is no filter, since sort under limit is a top n and has the same middle frame
- [x] A decision, written down, about whether the rule applies at every width or above some number of columns, with the measurement behind it

## Done when

q23 through the planner is within a small factor of the hand written route, and the pair in #485 is remeasured with it.

Contributor guide

Open the contributing guide

Research direction

The issue points to the planner and the existing hand-written `filter_sort_limit` kernel; begin by tracing how q23's filter, sort, and limit plan is lowered and where the intermediate frame is materialized. Use q23 and pair #485 as the measurement cases, comparing them with the hand-written route. Done means the planner selects the position-carrying operator for the filtered shape, preserves the documented width decision, and q23 is within a small factor of the hand-written route.

Written by the indexing model from the issue text.

Assessment

Tech stack
sql
Domain
data-engineering, performance
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.