xqerl

%% -------------------------------------------------------------------
%%
%% xqerl - XQuery processor
%%
%% Copyright (c) 2018-2020 Zachary N. Dean  All Rights Reserved.
%%
%% This file is provided to you under the Apache License,
%% Version 2.0 (the "License"); you may not use this file
%% except in compliance with the License.  You may obtain
%% a copy of the License at
%%
%%   http://www.apache.org/licenses/LICENSE-2.0
%%
%% Unless required by applicable law or agreed to in writing,
%% software distributed under the License is distributed on an
%% "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
%% KIND, either express or implied.  See the License for the
%% specific language governing permissions and limitations
%% under the License.
%%
%% -------------------------------------------------------------------

%% @doc @todo Future home of xqldb_query_server.
%% server for compiling XPath statements to use indexes, etc.

-module(xqldb_query_server).

-behaviour(gen_server).

-export([
    init/1,
    handle_call/3,
    handle_cast/2,
    handle_info/2,
    terminate/2,
    code_change/3
]).

-define(STALE, 60000).

%% ====================================================================
%% API functions
%% ====================================================================
-export([
    start_link/0,
    sweep/1,
    get/4,
    put/5,
    delete/2
]).

start_link() ->
    {ok, Pid} = gen_server:start_link(?MODULE, [], []),
    sweep(Pid),
    {ok, Pid}.

%% do a sweep of the cache, clearing out old stuff
sweep(Server) ->
    Now = erlang:system_time(millisecond),
    gen_server:cast(Server, {sweep, Now}),
    timer:apply_after(?STALE, ?MODULE, ?FUNCTION_NAME, [Server]),
    ok.

% try to get the ets table id for this doc/query, return undefined if not there.
get(#{queries := Server}, DocId, InPathId, Steps) ->
    Key = {?MODULE, ?FUNCTION_NAME, Server, DocId, InPathId, Steps},
    case erlang:get(Key) of
        undefined ->
            Val = gen_server:call(Server, {get, DocId, InPathId, Steps}),
            _ = erlang:put(Key, Val),
            Val;
        V ->
            gen_server:cast(Server, {touch, DocId, InPathId, Steps}),
            V
    end.

put(#{queries := Server}, DocId, InPathId, Steps, Results) ->
    true = ets:give_away(Results, Server, ok),
    gen_server:call(Server, {put, DocId, InPathId, Steps, Results}).

delete(#{queries := Server}, DocId) ->
    gen_server:cast(Server, {delete, DocId}).

%% ====================================================================
%% Behavioural functions
%% ====================================================================

init([]) ->
    Tab = ets:new(?MODULE, [public]),
    {ok, #{tab => Tab}}.

handle_call({put, DocId, InPathId, Steps, Results}, _, #{tab := Tab} = State) ->
    Key = {DocId, InPathId, Steps},
    Now = expire(),
    _ = ets:insert(Tab, {Key, Results, Now}),
    %io:format("~p~n", [{?LINE, Now}]),
    {reply, ok, State};
handle_call({get, DocId, InPathId, Steps}, ReplyTo, #{tab := Tab} = State) ->
    Fun = fun() ->
        Key = {DocId, InPathId, Steps},
        Reply =
            case ets:lookup(Tab, Key) of
                [] ->
                    undefined;
                [{_, undefined, _}] ->
                    undefined;
                [{_, T, _}] ->
                    Now = expire(),
                    ets:update_element(Tab, Key, {3, Now}),
                    T
            end,
        gen_server:reply(ReplyTo, Reply)
    end,
    _ = erlang:spawn_link(Fun),
    {noreply, State};
handle_call(_Request, _From, State) ->
    Reply = ok,
    {reply, Reply, State}.

handle_cast({sweep, Then}, #{tab := Tab} = State) ->
    MS = [{{'$1', '$2', '$3'}, [{'<', '$3', Then}, {'=/=', '$3', undefined}], [{{'$1', '$2'}}]}],
    ToDel = ets:select(Tab, MS),
    Del = fun({K, T}) ->
        ets:delete(T),
        ets:insert(Tab, {K, undefined, undefined})
    end,
    ok = lists:foreach(Del, ToDel),
    {noreply, State};
handle_cast({delete, {Doc, Stmp}}, #{tab := Tab} = State) ->
    MS = [{{{{Doc, Stmp}, '$1', '$2'}, '$3', '_'}, [], [{{'$1', '$2', '$3'}}]}],
    ToDel = ets:select(Tab, MS),
    Del = fun
        ({K1, K2, undefined}) ->
            K = {{Doc, Stmp}, K1, K2},
            ets:delete(Tab, K);
        ({K1, K2, T}) ->
            ets:delete(T),
            K = {{Doc, Stmp}, K1, K2},
            ets:delete(Tab, K)
    end,
    ok = lists:foreach(Del, ToDel),
    {noreply, State};
handle_cast({touch, DocId, InPathId, Steps}, #{tab := Tab} = State) ->
    Now = expire(),
    Key = {DocId, InPathId, Steps},
    _ = ets:update_element(Tab, Key, {3, Now}),
    {noreply, State};
handle_cast(_Msg, State) ->
    {noreply, State}.

handle_info(_Info, State) ->
    {noreply, State}.

terminate(_Reason, _State) ->
    ok.

code_change(_OldVsn, State, _Extra) ->
    {ok, State}.

%% ====================================================================
%% Internal functions
%% ====================================================================

expire() ->
    erlang:system_time(millisecond) + ?STALE.

%% should be able to save queries similarly to RDBMS
% first time a query comes into a DB, it is analyzed and then cached somewhere.
% Then following queries for the cached statement use the cached version.
% think 'cursor' views in other DBs
% what is cached is a fun/1 that takes the context node.
% this should all make the analysis phase rather cheap for any given node.
% also, statistics can be updated, meaning that the cache is dropped and rebuilt
% the next time each statement is run. this adds some overhead after a
% statistics run, but also makes for a smaller cache and better plans later.

%%% XXX
%% path statements in `for` loops should cache results for all items in list
%% grouped by item id. then use a map to find the results for each id
% document has path []
%% predicates can function the same way. The predicate runs first, and filters
% the actual items that could match. A predicate should be smaller or the
% same size as the orignal list.
%% where statements act as predicates on the variable tuple. See if they
% can also be used as a predicate


%%% PATH from AXIS
%% ancestor          : all paths to root
%% ancestor-or-self  : all paths to root, plus self path
%% attribute         : current path , plus {att, Ns, Ln}
%% child             : current path plus one, can limit by node type
%% descendant        : all with prefix of current path
%% descendant-or-self: all with prefix of current path, plus self
%% following         : ALL document paths, except root! can maybe find by name
%% following-sibling : all with prefix of current path minus last, with same length
%% parent            : current path minus last
%% preceding         : ALL document paths, except root! can maybe find by name
%% preceding-sibling : all with prefix of current path minus last, with same length
%% self              : current path

%%% CARDINALITY-COST from AXIS
%% ancestor          : depth - 1
%% ancestor-or-self  : depth
%% attribute         : count
%% child             : count
%% descendant        : count
%% descendant-or-self: count
%% following         : all node count - id (last)
%% following-sibling : sibling
%% parent            : count
%% preceding         : id (last)
%% preceding-sibling : sibling
%% self              : 1

%%% NODEID from AXIS
%% ancestor          : split up of current ID
%% ancestor-or-self  : split up of current ID, plus self
%% attribute         : ID longer by one position and is attribute, element has att count in Bin
%% child             : ID longer by one position and is NOT attribute
%% descendant        : All IDs in Range self and self + 1 @ last position non-inclusive
%% descendant-or-self: descendant plus own ID
%% following         : ID greater than self, self not prefix, not ancestor
%% following-sibling : ID same length, same prefix(len - 1), less than ID
%% parent            : prefix(len - 1)
%% preceding         : ID less than self, not ancestor
%% preceding-sibling : ID same length, same prefix(len - 1), greater than ID
%% self              : ID

%% need to make decision on whether to use path of node id
%% known path from root, or descendant skips == use PATH because it is known
%% following/preceding NEVER path, but could be in filter when name known
%% PATH can be used in `lists:member` filter from node id

%% API
% paths statement should be list of {axis, node-kind, node-name, [filters (on built items)]}
% initial function is fn(Nodes, PathList)

%% think RDBMS cursor with binding varaibles

%%% PATH ANALYSIS
%% path analysis gives a list of path statments, each with reference to each other
% this can be used to find all path ids that will occur.
% each sub-selection becomes a fun that uses the prefix from the original node
% and the known path as a filter.
%% each fun can be created when the first nodes are selected, then passed around
% as variables when needed.
%% single attribute on unknown node can be select nodeid len + 1, where att
% multiple att for same node can all be selected at once


% scope     : database or document
% path      : known path to node
% rel_path  : partially known path to node -> causes unions
% node_value: value lookup to node
% doc_value : value lookup to node in document

% all axes can be done using the dewey id
% node name and value id can be in properties of a node record

% index levels : DB and DOC
% fields       : path, str_value, dbl_value, int_value (values are map val to string id)
%                string_id -> node/doc
%                nodes => node_id to node body/type/name/etc.
% node id == [DocId, Path, To, Node] upon build, DBId (Node/Num) prepended to Id

%% collection should return list of {node(), DBs}
%% at collection level, we need to find the documents that could answer the query,
%% then use the document ids in following queries

%% first focus on document level queries, adding DB layer on top is easy.
% makes each data access iterator do append joins in document-order

%% 1. get all path IDs that can point to the nodes, the count of paths might be high...
%% 2. do an iterator join on selection of every path, this gives node ids and paths

%% predicates with paths... multiple selections of node ids, joined at the returned node id
%% path is LHS, Path + Pred is RHS
%% /a/b/c[d] ==
%% {a,b,c} + {a,b,c,d} = all c from first where c == c from second (common prefix)

%% /a/b/c == [{_,a},{_,b},{_,c}]
%% /a//c  == [{_,a}|_] where lists:last() = c
%% /a//b/c  == [{_,a}|_] where ends with [{_,b},{_,c}]


%% logical query transformation == static-time full path resolution

% Path unknown == hard-way, path known == easy way  (path knowledge happens at static time)
% paths hidden in function are done the hard way unless can be easily found statically

% perhaps, build nodes after a flwor statement?? once all else is unknown
% they will most-likely be used in constructors anyway...

%% try to use the `return` portion as the driving factor with path expressions.

%% path on variable used in a for expression is grouped at the level of the for variable
%% predicates are grouped at level of the context item

% imagine a tree of functions, each calling callbacks with each tuple
% data access iterators can be handed to functions, each doing something
% and then calling other functions at the end, or returning....

% a `for` or `let` statement that is a path with no predicate is equal to just
% the path id for follow on expressions

% an unfiltered `for` with follow-on paths, means pull all at the follow-on
% paths, group by variable path depth
% caveate here is if there is a where filtering the `for` path statement
% this can mean pulling in a LOT of data when only a small portion is needed.
%  Maybe, for now, allow this to suck, and force the programmer to put this in
%  a predicate?

% truly need a FLWOR re-write of path statements to reverse lookups on
% filtered results

% TODO figure out how to put `where` statements in a predicate, if possible
% conditional statements in a where are split into two `let` statements.

% a filtered `for` with follow on paths, means pull all the ids for the loop
% make a function for each follow on that takes the ID as a parameter

% if nodes are collection, split all by DB, then doc
% function returned from each access by the query-server could start:
% 1. get node path from input node
% 2. check if path is cached for this db (if not get it)
% 3. add new path/s to this path
% 4. check cost for the statement
% 5. do which ever is cheapest (path -> structure, structure -> path, value -> path, etc.)
% 6. return node list as iterator, also put the returned nodes in record-format.
%
% ** calling process can shoot off as many calls it needs at once.
%     then loop all those calls to build the lists.

%% in-mem nodes also go through the fun-making process, only these functions
% take the node tree and return whatever is needed by traversing the tree.
% the functions made here are done in the calling process, not a server.


%% the calling process has to keep the path function for each call to the same DB, for the same path (caching)
% input may not be sorted, should be before first path statement
% these calls should be done in parallel accross different DBs
% a query should know if it is handling collection calls, then it can split the
% queries in static time, or add a DB split function when nodes are selected
% a query may also know that all nodes are coming from only one location, if
% that is the case, simplify everything.


% making dynamic funs is easy, use a map of all values and use the map as the
% match out.

% path analysis part, get all paths that can answer a query from all locations
%  example, all paths that when given a child with name N answer the query.
%  this list of all paths is put in a map and used in a fun as the match
% path 1,2,3 can answer .//x then #{1 => x, 2 => x, 3 => x}
% fun(Path) when is_map_key(Path, Map) -> NewPath; (_) -> [] end.
% could make this fun for all axes and names...




%%% NODEID from AXIS
%% ancestor          : split up of current ID
%% ancestor-or-self  : split up of current ID, plus self
%% attribute         : ID longer by one position and is attribute, element has att count in Bin
%% child             : ID longer by one position and is NOT attribute
%% descendant        : All IDs in Range self and self + 1 @ last position non-inclusive
%% descendant-or-self: descendant plus own ID
%% following         : ID greater than self, self not prefix
%% following-sibling : ID same length, same prefix(len - 1), less than ID
%% parent            : prefix(len - 1)
%% preceding         : ID less than self, not ancestor
%% preceding-sibling : ID same length, same prefix(len - 1), greater than ID
%% self              : ID




%% path statement using node id: find the 'highest' path expression
% meaning the closest to the root of the tree. Then go get all the nodes...
% use that list as the base for the following steps one-by-one
% this could suck, but that is likely the fault of crappy queries and not
% having crazy path rewrite optimizations...

% queries can use the structure index if the list of paths is small.
% also structure queries should only happen with simple forward axes (or maybe parent)
% where the base node-id can be filtered on.