diff options
Diffstat (limited to '')
| -rw-r--r-- | src/query_planner.erl | 601 |
1 files changed, 0 insertions, 601 deletions
diff --git a/src/query_planner.erl b/src/query_planner.erl deleted file mode 100644 index d995f88..0000000 --- a/src/query_planner.erl +++ /dev/null @@ -1,601 +0,0 @@ -%%% @doc Query Planner and Prepared Statement Execution -%%% -%%% Provides a Lisp-inspired tuple-based DSL for constructing and executing -%%% relational algebra queries. Queries are represented as nested Erlang tuples -%%% that can be validated, optimized, and compiled into iterator pipelines. -%%% -%%% == Query DSL Syntax == -%%% -%%% The DSL uses nested tuples to represent relational operations: -%%% <pre> -%%% % Base relation (just use the relation name) -%%% employees -%%% -%%% % Selection (filter) -%%% {select, employees, fun(T) -> maps:get(age, T) > 30 end} -%%% -%%% % Projection -%%% {project, employees, [name, age]} -%%% -%%% % Equijoin (natural join on common attribute) -%%% {join, employees, departments, dept_id} -%%% -%%% % Theta join (join with arbitrary predicate) -%%% {theta_join, -%%% employees, -%%% departments, -%%% fun(L, R) -> maps:get(dept_id, L) =:= maps:get(id, R) end} -%%% -%%% % Sort -%%% {sort, employees, fun(A, B) -> maps:get(age, A) =< maps:get(age, B) end} -%%% -%%% % Take (limit) -%%% {take, employees, 10} -%%% -%%% % Rename attribute -%%% {rename, old_name, new_name, employees} -%%% -%%% % Composite query -%%% {project, -%%% {select, -%%% {join, employees, departments, dept_id}, -%%% fun(T) -> maps:get(age, T) > 30 end}, -%%% [name, dept_name]} -%%% </pre> -%%% -%%% == Usage == -%%% <pre> -%%% % Prepare a query plan -%%% Plan = query_planner:prepare({select, employees, -%%% fun(T) -> maps:get(age, T) > 30 end}). -%%% -%%% % Execute and get iterator -%%% Iter = query_planner:execute(DB, Plan). -%%% -%%% % Collect all results -%%% Results = query_planner:collect(DB, Plan). -%%% </pre> -%%% -%%% @author Nekoma Team -%%% @copyright 2025 - --module(query_planner). - --export([prepare/1, - execute/2, - collect/2, - explain/1]). - --include("operations.hrl"). - -%%% Types - --type query_plan() :: - atom() % Relation name - | {select, query_plan(), fun((map()) -> boolean())} % Filter - | {project, query_plan(), [atom()]} % Projection - | {join, query_plan(), query_plan(), atom()} % Equijoin - | {theta_join, query_plan(), query_plan(), - fun((map(), map()) -> boolean())} % Theta join - | {sort, query_plan(), fun((map(), map()) -> boolean())} % Sort - | {take, query_plan(), pos_integer()} % Limit - | {rename, atom(), atom(), query_plan()} % Rename attribute - | {materialize, query_plan()} % Materialize all - | {materialize, query_plan(), pos_integer()}. % Materialize N tuples - --export_type([query_plan/0]). - -%%% Public API - -%% @doc Prepare and validate a query plan. -%% -%% Takes a query plan tuple and validates its structure. Returns the -%% plan unchanged if valid, or throws an error if invalid. -%% -%% @param Plan The query plan to prepare -%% @returns The validated query plan -%% @throws {invalid_plan, Reason} --spec prepare(query_plan()) -> query_plan(). -prepare(Plan) -> - case validate_plan(Plan) of - ok -> Plan; - {error, Reason} -> error({invalid_plan, Reason}) - end. - -%% @doc Execute a prepared query plan against a database. -%% -%% Returns an ephemeral relation for top-level operations that can spawn -%% multiple independent iterators. The relation's generator creates fresh -%% iterator pipelines on demand, allowing reproducible results. -%% -%% @param DB The database state -%% @param Plan The prepared query plan -%% @returns Ephemeral relation record --spec execute(term(), query_plan()) -> #relation{}. -execute(DB, Plan) -> - create_ephemeral_relation(DB, Plan). - -%% @doc Execute a query plan and collect all results. -%% -%% Convenience function that executes the plan and collects all -%% tuples into a list. Uses the ephemeral relation to create an -%% iterator and automatically closes it. -%% -%% If the iterator times out (e.g., when sorting an infinite relation), -%% returns partial results with a warning. -%% -%% @param DB The database state -%% @param Plan The prepared query plan -%% @returns List of result tuples, or partial results on timeout --spec collect(term(), query_plan()) -> [map()]. -collect(DB, Plan) -> - EphemeralRelation = execute(DB, Plan), - Iter = (EphemeralRelation#relation.generator)(), - Results = operations:collect_all(Iter), - operations:close_iterator(Iter), - case Results of - {error, timeout, PartialResults} -> - io:format("~nWarning: Query timed out. Returning partial results (~b tuples).~n", - [length(PartialResults)]), - io:format("Tip: For infinite relations, use 'take' before operations like 'sort'.~n~n"), - PartialResults; - {error, Reason, PartialResults} -> - io:format("~nWarning: Query failed (~p). Returning partial results (~b tuples).~n~n", - [Reason, length(PartialResults)]), - PartialResults; - _ -> - Results - end. - -%% @doc Explain a query plan in human-readable form. -%% -%% Converts the query plan to a readable string representation -%% showing the operation tree. -%% -%% @param Plan The query plan to explain -%% @returns String representation of the plan --spec explain(query_plan()) -> string(). -explain(Plan) -> - explain_plan(Plan, 0). - -%%% Internal Functions - -%% @doc Create an ephemeral relation for the top-level query plan. -%% -%% Uses pure relational operators from relational_operators module to construct -%% the query result. Returns an ephemeral relation with a generator closure that -%% can spawn fresh iterators, allowing reproducible query results. -%% -%% @param DB The database state (for looking up base relations only) -%% @param Plan The query plan -%% @returns Ephemeral relation record --spec create_ephemeral_relation(term(), query_plan()) -> #relation{}. -create_ephemeral_relation(DB, Plan) -> - % Compile plan to ephemeral relation using pure operators - compile_to_relation(DB, Plan). - -%% @doc Compute the schema for a query plan. -%% -%% Recursively analyzes the query plan structure to determine the output schema. -%% The schema maps attribute names to their domain/type information. -%% -%% @param DB The database state -%% @param Plan The query plan -%% @returns Schema map --spec compute_schema(term(), query_plan()) -> map(). -compute_schema(DB, RelationName) when is_atom(RelationName) -> - case maps:get(RelationName, DB#database_state.relations, undefined) of - undefined -> - % Relation not found, return empty schema - #{}; - RelationHash -> - [Relation] = mnesia:dirty_read(relation, RelationHash), - Relation#relation.schema - end; - -compute_schema(DB, {select, SubPlan, _Predicate}) -> - % Select doesn't change schema, just filters tuples - compute_schema(DB, SubPlan); - -compute_schema(DB, {project, SubPlan, Attributes}) -> - % Project filters the schema to only include selected attributes - SubSchema = compute_schema(DB, SubPlan), - maps:with(Attributes, SubSchema); - -compute_schema(DB, {join, LeftPlan, RightPlan, _Attribute}) -> - % Join combines schemas from both sides, handling attribute conflicts - LeftSchema = compute_schema(DB, LeftPlan), - RightSchema = compute_schema(DB, RightPlan), - merge_join_schemas(LeftSchema, RightSchema); - -compute_schema(DB, {theta_join, LeftPlan, RightPlan, _Predicate}) -> - % Theta join also combines schemas from both sides, handling attribute conflicts - LeftSchema = compute_schema(DB, LeftPlan), - RightSchema = compute_schema(DB, RightPlan), - merge_join_schemas(LeftSchema, RightSchema); - -compute_schema(DB, {sort, SubPlan, _Comparator}) -> - % Sort doesn't change schema - compute_schema(DB, SubPlan); - -compute_schema(DB, {take, SubPlan, _N}) -> - % Take doesn't change schema, just limits tuples - compute_schema(DB, SubPlan); - -compute_schema(DB, {rename, OldAttr, NewAttr, SubPlan}) -> - % Rename changes one attribute name in the schema - SubSchema = compute_schema(DB, SubPlan), - case maps:is_key(OldAttr, SubSchema) of - true -> - AttrType = maps:get(OldAttr, SubSchema), - SubSchema1 = maps:remove(OldAttr, SubSchema), - maps:put(NewAttr, AttrType, SubSchema1); - false -> - % Attribute doesn't exist, return unchanged schema - SubSchema - end; - -compute_schema(DB, {materialize, SubPlan}) -> - % Materialize doesn't change schema - compute_schema(DB, SubPlan); - -compute_schema(DB, {materialize, SubPlan, _N}) -> - % Materialize with limit doesn't change schema - compute_schema(DB, SubPlan); - -compute_schema(_DB, _UnknownPlan) -> - % Unknown plan type, return empty schema - #{}. - -%% @doc Merge schemas for join operations, handling attribute conflicts elegantly. -%% -%% Instead of prefixing conflicting attribute names, this approach maintains -%% both provenances in the schema value. For attributes that exist in both -%% relations, the schema value becomes a list of the original values. -%% This is especially important for natural joins where the join attribute -%% logically represents the same entity from both sides. -%% -%% @param LeftSchema Schema from left relation -%% @param RightSchema Schema from right relation -%% @returns Merged schema map with provenance lists for conflicts --spec merge_join_schemas(map(), map()) -> map(). -merge_join_schemas(LeftSchema, RightSchema) -> - maps:fold( - fun(Key, RightValue, Acc) -> - case maps:get(Key, Acc, undefined) of - undefined -> - % No conflict, add the right attribute - maps:put(Key, RightValue, Acc); - LeftValue when LeftValue =:= RightValue -> - % Same type/domain, keep single value (common in natural joins) - maps:put(Key, LeftValue, Acc); - LeftValue when is_list(LeftValue) -> - % Left value is already a list, append if not already present - case lists:member(RightValue, LeftValue) of - true -> maps:put(Key, LeftValue, Acc); - false -> maps:put(Key, LeftValue ++ [RightValue], Acc) - end; - LeftValue -> - % Conflict with different types - create provenance list - maps:put(Key, [LeftValue, RightValue], Acc) - end - end, - LeftSchema, - RightSchema - ). - -%% @doc Compute provenance for a query plan. -%% -%% Recursively analyzes the query plan structure to determine the provenance, -%% following the provenance types defined in operations.hrl. -%% -%% @param Plan The query plan -%% @returns Provenance term --spec compute_provenance(query_plan()) -> term(). -compute_provenance(RelationName) when is_atom(RelationName) -> - {base, RelationName}; - -compute_provenance({select, SubPlan, _Predicate}) -> - % For select, we'd need to represent the predicate constraints - % For now, simplified without constraint details - SubProvenance = compute_provenance(SubPlan), - {select, SubProvenance, #{}}; - -compute_provenance({project, SubPlan, Attributes}) -> - SubProvenance = compute_provenance(SubPlan), - {project, SubProvenance, Attributes}; - -compute_provenance({join, LeftPlan, RightPlan, _Attribute}) -> - LeftProvenance = compute_provenance(LeftPlan), - RightProvenance = compute_provenance(RightPlan), - {join, LeftProvenance, RightProvenance}; - -compute_provenance({theta_join, LeftPlan, RightPlan, _Predicate}) -> - LeftProvenance = compute_provenance(LeftPlan), - RightProvenance = compute_provenance(RightPlan), - {join, LeftProvenance, RightProvenance}; - -compute_provenance({sort, SubPlan, _Comparator}) -> - % Sort doesn't change provenance - compute_provenance(SubPlan); - -compute_provenance({take, SubPlan, N}) -> - SubProvenance = compute_provenance(SubPlan), - {take, SubProvenance, N}; - -compute_provenance({rename, _OldAttr, _NewAttr, SubPlan}) -> - % Rename preserves underlying provenance - compute_provenance(SubPlan); - -compute_provenance({materialize, SubPlan}) -> - % Materialize doesn't change provenance - compute_provenance(SubPlan); - -compute_provenance({materialize, SubPlan, _N}) -> - % Materialize with limit doesn't change provenance - compute_provenance(SubPlan); - -compute_provenance(_UnknownPlan) -> - % Unknown plan type - undefined. - -%% Validate query plan structure --spec validate_plan(query_plan()) -> ok | {error, term()}. -validate_plan(Name) when is_atom(Name) -> - ok; -validate_plan({select, SubPlan, Pred}) when is_function(Pred, 1) -> - validate_plan(SubPlan); -validate_plan({project, SubPlan, Attrs}) when is_list(Attrs) -> - case lists:all(fun is_atom/1, Attrs) of - true -> validate_plan(SubPlan); - false -> {error, {invalid_attributes, Attrs}} - end; -validate_plan({join, Left, Right, Attr}) when is_atom(Attr) -> - case {validate_plan(Left), validate_plan(Right)} of - {ok, ok} -> ok; - {{error, _} = Error, _} -> Error; - {_, {error, _} = Error} -> Error - end; -validate_plan({theta_join, Left, Right, Pred}) when is_function(Pred, 2) -> - case {validate_plan(Left), validate_plan(Right)} of - {ok, ok} -> ok; - {{error, _} = Error, _} -> Error; - {_, {error, _} = Error} -> Error - end; -validate_plan({sort, SubPlan, Comp}) when is_function(Comp, 2) -> - validate_plan(SubPlan); -validate_plan({take, SubPlan, N}) when is_integer(N), N > 0 -> - validate_plan(SubPlan); -validate_plan({rename, OldAttr, NewAttr, SubPlan}) when is_atom(OldAttr), is_atom(NewAttr) -> - validate_plan(SubPlan); -validate_plan({materialize, SubPlan}) -> - validate_plan(SubPlan); -validate_plan({materialize, SubPlan, N}) when is_integer(N), N > 0 -> - validate_plan(SubPlan); -validate_plan(Plan) -> - {error, {unknown_operator, Plan}}. - -%% Compile query plan to iterator pipeline --spec compile_to_iterator(term(), query_plan()) -> pid(). -compile_to_iterator(DB, Name) when is_atom(Name) -> - operations:get_tuples_iterator(DB, Name); - -compile_to_iterator(DB, {select, SubPlan, Predicate}) -> - SubIter = compile_to_iterator(DB, SubPlan), - operations:select_iterator(SubIter, Predicate); - -compile_to_iterator(DB, {project, SubPlan, Attributes}) -> - SubIter = compile_to_iterator(DB, SubPlan), - operations:project_iterator(SubIter, Attributes); - -compile_to_iterator(DB, {join, LeftPlan, RightPlan, Attribute}) -> - LeftIter = compile_to_iterator(DB, LeftPlan), - RightIter = compile_to_iterator(DB, RightPlan), - operations:equijoin_iterator(LeftIter, RightIter, Attribute); - -compile_to_iterator(DB, {theta_join, LeftPlan, RightPlan, Predicate}) -> - LeftIter = compile_to_iterator(DB, LeftPlan), - RightIter = compile_to_iterator(DB, RightPlan), - operations:theta_join_iterator(LeftIter, RightIter, Predicate); - -compile_to_iterator(DB, {sort, SubPlan, Comparator}) -> - SubIter = compile_to_iterator(DB, SubPlan), - operations:sort_iterator(SubIter, Comparator); - -compile_to_iterator(DB, {take, SubPlan, N}) -> - %% For iterator-based compilation, use take_iterator - SubIter = compile_to_iterator(DB, SubPlan), - operations:take_iterator(SubIter, N); - -compile_to_iterator(DB, {rename, OldAttr, NewAttr, SubPlan}) -> - SubIter = compile_to_iterator(DB, SubPlan), - %% Inline simple rename - no need for separate function - spawn(fun() -> - rename_loop_inline(SubIter, OldAttr, NewAttr) - end); - -compile_to_iterator(DB, {materialize, SubPlan}) -> - % Materialize returns all tuples as a "static" iterator - SubIter = compile_to_iterator(DB, SubPlan), - Results = operations:collect_all(SubIter), - operations:close_iterator(SubIter), - static_iterator(Results); - -compile_to_iterator(DB, {materialize, SubPlan, Limit}) -> - % Materialize with limit - SubIter = compile_to_iterator(DB, SubPlan), - LimitedIter = operations:take_iterator(SubIter, Limit), - Results = operations:collect_all(LimitedIter), - operations:close_iterator(LimitedIter), - static_iterator(Results). - -%% Static iterator - serves pre-materialized tuples --spec static_iterator([map()]) -> pid(). -static_iterator(Tuples) -> - spawn(fun() -> static_loop(Tuples) end). - -static_loop(Tuples) -> - receive - {next, Caller} -> - case Tuples of - [] -> - Caller ! done, - static_loop([]); - [Tuple | Rest] -> - Caller ! {tuple, Tuple}, - static_loop(Rest) - end; - {close, Caller} -> - Caller ! ok - end. - -%% @private -%% Inline helper for compile_to_iterator rename case -rename_loop_inline(SourceIter, OldAttr, NewAttr) -> - receive - {next, Caller} -> - case operations:next_tuple(SourceIter) of - done -> - Caller ! done; - {ok, Tuple} -> - RenamedTuple = case maps:is_key(OldAttr, Tuple) of - true -> - Value = maps:get(OldAttr, Tuple), - Tuple1 = maps:remove(OldAttr, Tuple), - maps:put(NewAttr, Value, Tuple1); - false -> - Tuple - end, - Caller ! {tuple, RenamedTuple}, - rename_loop_inline(SourceIter, OldAttr, NewAttr) - end; - {close, Caller} -> - operations:close_iterator(SourceIter), - Caller ! ok - end. - -%% Pretty-print query plan --spec explain_plan(query_plan(), non_neg_integer()) -> string(). -explain_plan(Name, Indent) when is_atom(Name) -> - indent(Indent) ++ "Relation: " ++ atom_to_list(Name) ++ "\n"; - -explain_plan({select, SubPlan, _Pred}, Indent) -> - indent(Indent) ++ "Select (filter)\n" ++ - explain_plan(SubPlan, Indent + 2); - -explain_plan({project, SubPlan, Attrs}, Indent) -> - AttrStr = string:join([atom_to_list(A) || A <- Attrs], ", "), - indent(Indent) ++ "Project [" ++ AttrStr ++ "]\n" ++ - explain_plan(SubPlan, Indent + 2); - -explain_plan({join, LeftPlan, RightPlan, Attr}, Indent) -> - indent(Indent) ++ "Join on " ++ atom_to_list(Attr) ++ "\n" ++ - explain_plan(LeftPlan, Indent + 2) ++ - explain_plan(RightPlan, Indent + 2); - -explain_plan({theta_join, LeftPlan, RightPlan, _Pred}, Indent) -> - indent(Indent) ++ "Theta Join\n" ++ - explain_plan(LeftPlan, Indent + 2) ++ - explain_plan(RightPlan, Indent + 2); - -explain_plan({sort, SubPlan, _Comp}, Indent) -> - indent(Indent) ++ "Sort\n" ++ - explain_plan(SubPlan, Indent + 2); - -explain_plan({take, SubPlan, N}, Indent) -> - indent(Indent) ++ "Take " ++ integer_to_list(N) ++ "\n" ++ - explain_plan(SubPlan, Indent + 2); - -explain_plan({rename, OldAttr, NewAttr, SubPlan}, Indent) -> - indent(Indent) ++ "Rename " ++ atom_to_list(OldAttr) ++ " -> " ++ atom_to_list(NewAttr) ++ "\n" ++ - explain_plan(SubPlan, Indent + 2); - -explain_plan({materialize, SubPlan}, Indent) -> - indent(Indent) ++ "Materialize (all)\n" ++ - explain_plan(SubPlan, Indent + 2); - -explain_plan({materialize, SubPlan, N}, Indent) -> - indent(Indent) ++ "Materialize (" ++ integer_to_list(N) ++ " tuples)\n" ++ - explain_plan(SubPlan, Indent + 2). - -%% Helper: indent string --spec indent(non_neg_integer()) -> string(). -indent(N) -> lists:duplicate(N, $\s). - -%% Helper: get relation from database --spec get_relation_from_db(term(), atom()) -> #relation{}. -get_relation_from_db(DB, RelationName) -> - case maps:get(RelationName, DB#database_state.relations, undefined) of - undefined -> - erlang:error({relation_not_found, RelationName}); - RelationHash -> - [Relation] = mnesia:dirty_read(relation, RelationHash), - Relation - end. - -%% @doc Compile query plan to ephemeral relation using pure relational operators. -%% -%% This is the new approach: build a relation tree using pure operators, -%% then return the final ephemeral relation. No iterators are created until -%% the generator is called. --spec compile_to_relation(term(), query_plan()) -> #relation{}. -compile_to_relation(DB, RelationName) when is_atom(RelationName) -> - BaseRelation = get_relation_from_db(DB, RelationName), - GeneratorFun = fun() -> - operations:get_tuples_iterator(DB, RelationName) - end, - BaseRelation#relation{generator = GeneratorFun}; - -compile_to_relation(DB, {select, SubPlan, Predicate}) -> - SubRelation = compile_to_relation(DB, SubPlan), - relational_operators:select(SubRelation, Predicate); - -compile_to_relation(DB, {project, SubPlan, Attributes}) -> - SubRelation = compile_to_relation(DB, SubPlan), - relational_operators:project(SubRelation, Attributes); - -compile_to_relation(DB, {join, LeftPlan, RightPlan, Attribute}) -> - LeftRelation = compile_to_relation(DB, LeftPlan), - RightRelation = compile_to_relation(DB, RightPlan), - relational_operators:join(LeftRelation, RightRelation, Attribute); - -compile_to_relation(DB, {theta_join, LeftPlan, RightPlan, Predicate}) -> - LeftRelation = compile_to_relation(DB, LeftPlan), - RightRelation = compile_to_relation(DB, RightPlan), - relational_operators:theta_join(LeftRelation, RightRelation, Predicate); - -compile_to_relation(DB, {sort, SubPlan, Comparator}) -> - SubRelation = compile_to_relation(DB, SubPlan), - relational_operators:sort(SubRelation, Comparator); - -compile_to_relation(DB, {take, SubPlan, N}) -> - SubRelation = compile_to_relation(DB, SubPlan), - relational_operators:take(SubRelation, N); - -compile_to_relation(DB, {rename, OldAttr, NewAttr, SubPlan}) -> - SubRelation = compile_to_relation(DB, SubPlan), - relational_operators:rename(SubRelation, #{OldAttr => NewAttr}); - -compile_to_relation(DB, {materialize, SubPlan}) -> - GeneratorFun = fun() -> - compile_to_iterator(DB, SubPlan) - end, - EphemeralName = list_to_atom("materialized_" ++ integer_to_list(erlang:unique_integer([positive]))), - #relation{ - hash = crypto:hash(sha256, term_to_binary({materialize, SubPlan})), - name = EphemeralName, - tree = undefined, - schema = compute_schema(DB, SubPlan), - constraints = constraint:empty_constraints(), - cardinality = unknown, - generator = GeneratorFun, - membership_criteria = #{}, - provenance = compute_provenance(SubPlan) - }; - -compile_to_relation(DB, {materialize, SubPlan, N}) -> - % Materialize with limit - SubRelation = compile_to_relation(DB, SubPlan), - TakeRelation = relational_operators:take(SubRelation, N), - % Then wrap in a materialized form (for now just return take) - TakeRelation. |