veeso / wasm-dbms / 38079305667

95%

Build Type

push

github

Committed by web-flow

Commit Message

feat(dbms)!: execute joins with a hash join into JoinResultSet (#182)

The join engine compared every left row with every right row and cloned both rows for each match, so a join cost grew with the product of the two table sizes and 10,000 by 10,000 rows took over half a second for 10,000 output rows. On top of that the result repeated a JoinColumnDef with owned strings in every cell, which alone cost a quarter of the join time. Each join clause now builds a hash table over the right rows and probes it once per left row, intermediate rows are kept as row indices until filter, ordering, offset and limit have run, and select_join returns a JoinResultSet with the column list once and the rows as plain values. The left join keys are pushed down as an IN filter only when the right join column leads an index and the distinct key count fits the planner's 64-alternative limit; other inner and left joins scan non-null right keys once. DatabaseSchema::table_indexes exposes declared indexes. Filter gains a borrowing matches_joined_row_ref variant and the comparison benchmark gains a query/join_large case.

BREAKING CHANGE: Database::select_join and DatabaseSchema::select_join return DbmsResult<JoinResultSet> instead of DbmsResult<Vec<Vec<(JoinColumnDef, Value)>>>. Iterate the result with for row in &result and row.iter(), or resolve a column once with column_index and index result.rows. SqlResult::Rows is unchanged.

closes #181

Coverage Stats

771 of 787 new or added lines in 7 files covered. (97.97%)

1 existing line in 1 file now uncovered.

28953 of 30625 relevant lines covered (94.54%)

1709039.73 hits per line