Skip to content

Memoize only the parser rules that are re-entered - #6

Closed
JelteF wants to merge 253 commits into
v2.0-cyanopterafrom
split-memoize
Closed

JelteF wants to merge 253 commits into
v2.0-cyanopterafrom
split-memoize

Conversation

@JelteF

@JelteF JelteF commented Sep 21, 2026

Copy link
Copy Markdown
Owner

Packrat memoization was enabled for twenty-two grammar rules. Counting every lookup and hit across the parser benchmarks, only three ever hit; the other nineteen account for 38.5 million of the 43.8 million lookups and return nothing. This drops those nineteen. Memoizing a rule only pays where more than one alternative can re-enter it at the same token, and fifteen of the nineteen are levels of the operator precedence hierarchy: Expression names LogicalOrExpression, which names LogicalAndExpression, and so on down to BaseExpression. Each level is named only by the level above it, so there is one way to reach it at a given token and a second lookup never happens.

This also adds three new qualification rules that do get re-entered: every identifier in an expression reaches them at the same token, because four of the five ColumnReference alternatives begin by matching name '.' there. Twenty-two memoized rules become six.

benchmark v2.0-cyanoptera this branch
ParserAoC 1.631s 1.497s -8.2%
ParserFlummi 2.569s 2.232s -13.1%
ParserGrammarConstruction 1.463s 1.465s +0.1%
ParserKeywordIdentifiers 0.793s 0.741s -6.5%
ParserMalformedSelect 0.546s 0.532s -2.6%
ParserNestedExpressions 1.317s 1.196s -9.1%
ParserStatements 1.135s 1.086s -4.4%
ParserStress * 11.216s 9.156s -18.4%
ParserTPCDS 2.523s 2.324s -7.9%
ParserTPCH 1.117s 1.042s -6.7%
ParserValuesList * 12.349s 11.101s -10.1%
ParserWideSelect 2.637s 2.405s -8.8%
geometric mean -8.1%

Rows marked * come from the benchmarks added by duckdb#26015

How this was measured

This repository's benchmark_runner, built BUILD_BENCHMARK=1 BUILD_JEMALLOC=1 make release (clang 21.1.8, plain release — no LTO, matching what the parser regression CI builds). This branch and v2.0-cyanoptera were built from the same worktree and alternated within each of three rounds so they share machine state; each figure is the median of three timed runs.

BUILD_BENCHMARK=1 make release
build/release/benchmark/benchmark_runner 'Parser.*'

AMD EPYC 9R14, 32 cores, no SMT, Ubuntu 24.04. The full suite passes on this branch.

These parser changes are being sent as separate branches, and they overlap — several remove work from the same expression matching — so if more than one lands, the second will measure smaller than quoted here.

Tishj and others added 30 commits September 4, 2026 13:44
…ile (duckdb#25573)

Files written by `v2.0.0` and later have `DEPRECATED_VERSION_NUMBER`
(999) as their main header version number with the real storage version
in the database headers. Older versions read that as an actual version
leading to a confusing error.

This PR improves the error message so that when the main header has the
`DEPRECATED_VERSION_NUMBER`, the version is read from the database
header instead.
RowGroupCollection::InitializeScan asserted that the collection has a root
segment. A DataTable with no committed row group has none: a table created in
the current transaction, a committed table that never had rows, or a table
whose rows are all still transaction-local in LocalStorage.

Starting a scan there is legitimate. The loop right below the assert already
handles a null root, and DataTable::InitializeScan continues into LocalStorage
afterwards, which is where the transaction-local rows are. Release builds
already behave this way; only assert-enabled builds threw
"Assertion triggered ... row_group_collection.cpp ... row_group".

The caller that trips it is the DuckLake extension:
DuckLakeServerSideCommit::ScanStagedTable reads its staged temp tables through
DataTable::InitializeScan inside the same transaction that created and filled
them, so every row is transaction-local.

Adds test/api/test_data_table_scan_without_row_groups.cpp, which drives
DataTable::InitializeScan and DataTable::Scan the same way for a
transaction-local table, a committed empty table, and a table with both
committed and transaction-local rows.
Review feedback: the removed assert needs no replacement comment; the null-tolerant loop below speaks for itself.
This PR updates Postgres, MySQL, SQLite and ODBC scanners in
`v1.5-variegata` branch.
…ow groups (duckdb#25668)

## What the assert is

`RowGroupCollection::InitializeScan`
(`src/storage/table/row_group_collection.cpp`) asserts that the
collection has a root segment:

```cpp
state.row_groups = GetRowGroups();
auto row_group = state.GetRootSegment();
D_ASSERT(row_group);                      // <- this one
state.max_row = state.row_groups->GetBaseRowId() + total_rows;
state.Initialize(context, GetTypes());
while (row_group && !row_group->GetNode().InitializeScan(state, *row_group)) {
	row_group = state.GetNextRowGroup(*row_group);
}
```

A `DataTable` with no committed row group has no root segment. That
happens for a table created in
the current transaction, for a committed table that never had rows, and
for a table whose rows are
all still transaction-local in `LocalStorage`.

## Who hits it

No SQL path inside DuckDB reaches it: `TableScanFunction` uses
`InitializeParallelScan`/`NextParallelScan`, and `RebuildIndexes` only
runs after a vacuum has
changed row ids. However, the DuckLake extension uses this path in 

`DuckLakeServerSideCommit::ScanStagedTable` (ducklake,
`src/storage/ducklake_server_side_commit.cpp`)
when it reads reads its staged temp tables with the internal API:

```cpp
storage.InitializeScan(context, duck_transaction, scan_state, column_ids);
while (true) {
	chunk.Reset();
	storage.Scan(duck_transaction, chunk, scan_state);
	...
}
```

`DuckLakeStagedCommit::Build` creates those staged temp tables
(`DuckLakeStagedTable::CreateAllSql`)
and fills them inside the same, still-open transaction that then runs
`SELECT * FROM ducklake_commit(<metadata schema>, <schema version>)`.
Every staged row is therefore
transaction-local and the collection has no root row group. The empty
staged tables - most of them
are empty in any given commit - have no root row group either, even
outside a transaction.

The PR removes the asserts and adds tests to test various scan types at
this lower level.


## Reproducing with an assertion-enabled DuckLake

In a `duckdb/ducklake` checkout, run:

```sh
ENABLE_QUACK=ON GEN=ninja make debug
python3 scripts/run_quack_tests.py --build-dir build/debug --no-install \
    test/sql/quack/server_side_commit_atomicity.test
```

which fails with :

```
[1/1] (100%): test/sql/quack/server_side_commit_atomicity.test
  ===============================================================================
  test cases: 1 | 1 failed
  assertions: 3 | 2 passed | 1 failed
  --- stderr ---

  1. test/sql/quack/server_side_commit_atomicity.test:19
  ================================================================================
  Query unexpectedly failed! (test/sql/quack/server_side_commit_atomicity.test:19)!
  ================================================================================
  INSERT INTO ducklake.test VALUES (1);
  ================================================================================
  TransactionContext Error: Failed to commit: Failed to invoke server-side ducklake_commit: Assertion triggered in file "/Users/boaz/src/md/ducklake/duckdb/src/storage/table/row_group_collection.cpp" on line 238: row_group

  Stack Trace:

  0        duckdb::Exception::ToJSON(duckdb::ExceptionType, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char>> const&) + 60
  1        duckdb::Exception::Exception(duckdb::ExceptionType, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char>> const&) + 52
  2        duckdb::InternalException::InternalException(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char>> const&) + 40
  3        duckdb::InternalException::InternalException(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char>> const&) + 36
  4        duckdb::InternalException::InternalException<char const*&, int&, char const*&>(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char>> const&, char const*&, int&, char const*&) + 80
  5        duckdb::DuckDBAssertInternal(bool, char const*, char const*, int) + 124
  6        duckdb::RowGroupCollection::InitializeScan(duckdb::QueryContext const&, duckdb::CollectionScanState&, duckdb::vector<duckdb::StorageIndex, true, std::__1::allocator<duckdb::StorageIndex>> const&, duckdb::optional_ptr<duckdb::TableFilterSet, true>) + 124
  7        duckdb::DataTable::InitializeScan(duckdb::ClientContext&, duckdb::DuckTransaction&, duckdb::TableScanState&, duckdb::vector<duckdb::StorageIndex, true, std::__1::allocator<duckdb::StorageIndex>> const&, duckdb::optional_ptr<duckdb::TableFilterSet, true>) + 216
  8        duckdb::DuckLakeServerSideCommit::ScanStagedTable(duckdb::DuckLakeStagedTableType) + 716
  9        duckdb::DuckLakeServerSideCommit::ReadColumnTypes() + 52
  10       duckdb::DuckLakeServerSideCommit::Run() + 64
  11       duckdb::DuckLakeCommitExecute(duckdb::ClientContext&, duckdb::TableFunctionInput&, duckdb::DataChunk&) + 184
```
Closes duckdb#23957
Closes duckdb#23956

I think there're two issues in the current parquet implementation:
- On write, we don't handle `TIME_NS` type, so it [fallbacks to
`VARCHAR`
type](https://github.com/duckdb/duckdb/blob/08cb7a49e91f14edc6dfa8b497268eabc6533f8d/extension/parquet/parquet_extension.cpp#L930-L932)
- On read, when `time.NANOS` set, we should convert into DuckDB
`TIME_NS` logical type
- (not related to parquet) We don't have cast impl for TIME && TIME_NS
When hive partitioning prunes down to a single file, aggregate optimization
can request statistics for partition columns that are not present in the
parquet file schema. Guard against out-of-bounds column indices instead of
asserting, and add a regression test for MAX on a hive date column.

Fixes duckdb#25629
Mytherin and others added 19 commits September 21, 2026 17:35
EnumToAnyCast invoked the inner ENUM->VARCHAR and VARCHAR->target casts
but discarded both boolean results, always reporting success. In the
TryCast path a failed conversion (e.g. 'sad'::mood -> UINTEGER) marked
the row NULL yet returned an engaged optional, so callers such as
duckdb_v2_value_get_uint read uninitialized storage and reported
DUCKDB_V2_ERROR_NONE with a garbage value.

Propagate the inner casts' return values so the failure surfaces as a
conversion error, matching every other composite cast.

Fixes duckdb#25633
Follow up to duckdb#25950

Sometimes you want to test for specific errors that rely on the target
to *not* support something.
If you define the support for a specific feature through setting an
environment variable, then it makes sense to require that environment
variable to not be defined at all.

`require-env-not <name>` requires the environment variable to not be
defined at all.
Moved duckdb#25806 to v2.0-cyanoptera.

> This PR changes batch_size_set_target to an optional_idx from idx_t.
Now you can call the callback without setting the target size.
Moved duckdb#25681 to v2.0-cyanoptera.

> This PR adds connection_progress_get to replace the 4 needed calls
before in the C API V2.
Small fix after duckdb#25865 that lets `ResultArrowArrayStreamWrapper` stream
again.
…uckdb#25983)

Currently query progress has a lot of gaps as it is not structurally
tested in the test suite. This PR starts to fix this by adding a
verification setting (`debug_verify_progress`) together with a test
config (`test/configs/verify_progress.json`) which runs the test suite
together with this verification. The verification tests a number of
failure modes of the progress bar:

* **UNSUPPORTED_SOURCE**: Source does not support progress
* **UNSUPPORTED_SINK**: the source reports valid progress, but the
sink's GetSinkProgress turns it invalid.
* **MALFORMED_SOURCE**: the raw source progress is NaN or infinite, or
has done < 0, total < 0 or done > total.
* **MALFORMED_SINK**: the same range and finiteness check on the
sink-adjusted pipeline progress
* **NON_MONOTONIC**: progress decreases between two samples of one run,
beyond a 1e-6 tolerance.
* **INCOMPLETE**: a pipeline that ran to completion ends below 100%
(0.1% tolerance).
* **STALLED**: progress stays the same for every sample of a run while
the source produces at least 16,384 rows. Being stuck at 100% doesn't
count.

`debug_verify_progress_ignore` takes a list of operators to ignore,
e.g.:

```sql
SET debug_verify_progress_ignore='INCOMPLETE:ORDER_BY,INCOMPLETE:SEQ_SCAN,...'
```

This allows the test config to pass right now. The goal is to fix these
bugs over time.

CC @rustyconover
The v2 C API surfaces StatementType under the same numeric values, but
core had no count sentinel, so a member appended in core could only be
caught by two runtime tests probing the values past the last known one.

STATEMENT_TYPE_COUNT makes that a static_assert: appending a member
shifts the count and fails to compile until the new type has an id in
the v2 spec. The two probe tests are no longer needed.
Add:
```
    {"DeltaKernel", "delta"}, {"DuckLakeMetadata", "ducklake"},         {"HTTPFSInfo", "httpfs"},
    {"Iceberg", "iceberg"},   {"PostgresQueryLog", "postgres_scanner"}, {"Quack", "quack"},
```
instead of only ducklake and iceberg ones.
… closed (duckdb#26002)

Follow up on duckdb#25989

Check for whether the Arrow stream ended before converting a batch in
`GetNext` to prevent an internal exception.
Originally, this PR removed `libduckdb-src.zip`, but that's not a good
idea, for now. I've removed those changes from this PR, so only the
codecov/osx changes remain.

Closes duckdblabs/duckdb-internal#10623.
The v2 C API surfaces StatementType under the same numeric values, but
core had no count sentinel, so a member appended in core could only be
caught by two runtime tests probing the values past the last known one.

STATEMENT_TYPE_COUNT makes that a static_assert: appending a member
shifts the count and fails to compile until the new type has an id in
the v2 spec. The two probe tests are no longer needed.

Originally first commit at duckdb#25990,
but as pointed out better reviewed independently.

Newer version of duckdb#25972
)

Example at
https://github.com/duckdb/duckdb/actions/runs/35599921257/job/106337553504?pr=25978#step:8:2552,
where result would be:
```
  python3 ./duckdb/scripts/ci/run_tests.py ./build/release/test/unittest *
  CI detected, enabling retry=2 per batch
  config: patterns=['*'], workers=12, retry=2, max_retries=4, batch_size=10, batch_timeout_seconds=300, fail_require_skip=False
  .................................................. [ 50%]
  .................................................. [100%]
  all tests passed in 160s (125 skipped tests)

  Skipped tests for the following reasons:
  mode skip unspecified: 10
  require icu: 8
  require postgres_scanner: 1
  require spatial: 1
  require tpch: 2
  require-env DUCKLAKE_CI: 1
  require-env LOCAL_EXTENSION_REPO: 1
  require-env S3_TEST_SERVER_AVAILABLE 1: 4
  require-env TEST_PERSISTENT_SECRETS_AVAILABLE: 1
  ran tests: 652 passed, 125 skipped in 160s
```
that is great, but 125 skipped an listing about 30 of them is not
informative.
@JelteF
JelteF force-pushed the split-memoize branch 6 times, most recently from 13ef9af to 4b03b0a Compare September 22, 2026 12:53
Packrat memoization was enabled for twenty-two grammar rules. Counting every lookup and hit
across the parser benchmarks, only three ever hit; the other nineteen account for 38.5
million of the 43.8 million lookups and return nothing. This drops those nineteen. Memoizing
a rule only pays where more than one alternative can re-enter it at the same token, and
fifteen of the nineteen are levels of the operator precedence hierarchy: `Expression` names
`LogicalOrExpression`, which names `LogicalAndExpression`, and so on down to
`BaseExpression`. Each level is named only by the level above it, so there is one way to
reach it at a given token and a second lookup never happens.

This also adds three new qualification rules that do get re-entered: every identifier in an
expression reaches them at the same token, because four of the five `ColumnReference`
alternatives begin by matching `name '.'` there. Twenty-two memoized rules become six.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.