Apfelmaennchen (Mandelbrot set) and the WITH Clause

[trueqbit]

Apfelmaennchen (Mandelbrot set) and the WITH Clause

Hi @fn12c,

I have exciting news to announce and I think you will like it 😎!

See this output produced using sqlite_orm, driven by 'common table expressions':

                                    ....#
                                   ..#*..
                                 ..+####+.
                            .......+####....   +
                           ..##+*##########+.++++
                          .+.##################+.
              .............+###################+.+
              ..++..#.....*#####################+.
             ...+#######++#######################.
          ....+*################################.
 #############################################...
          ....+*################################.
             ...+#######++#######################.
              ..++..#.....*#####################+.
              .............+###################+.+
                          .+.##################+.
                           ..##+*##########+.++++
                            .......+####....   +
                                 ..+####+.
                                   ..#*..
                                    ....#
                                    +.

This is directly taken from the documentation of SQLite's WITH Clause.

I started implementing the WITH Clause along with common table expressions (CTEs) a few weeks ago. Not sure whether it's entirely feature-complete, but I think it's time to put out word and get feedback, and start a discussion prior to a draft pull request.

Currently, the feature exists in FireDaemon's CTE branch.

Please have a look at the 'common table expression' examples located in https://github.com/FireDaemon/sqlite_orm/blob/CTEs/examples/common_table_expressions.cpp to see how all this is used.
I especially like the neat ability to select all columns from an alias and the ability to back-reference mapped columns, as shown in the 'supervisor chain' example.

BTW, here's the Apfelmaennchen select 😺!

A high-level view of how this is working:

Some apriori concepts:

• the notion of a 'table' in the storage implementation has been abstracted to a 'mapper'.
• so-called "labels" or "label types" bind together regular storage->table->object mappings and abstracted cte expression storage->cte mapper->cte result object. They also allow sqlite_orm to look up the corresponding cte-related mappings, just like the object is used for lookup in the regular mappings.

---

For CTEs to function we need to build a temporary 'storage implementation' from the CTE's subselect. It shall purely exist during the lifetime of the actual select-statement.
So:

1. There's a dedicated API for creating CTEs and the WITH Clause.
2. storage_t methods, which operate on that with-clause expression, create the temporary 'cte expression storage'.
3. The subselect expression that shapes the CTE is captured, as well as the column results, effectively forming a dedicated data object, which will be mapped. The captured expressions allow for back-referencing at later points. Otherwise an index-based back-referencing mechanism is provided as well.
4. A dedicated cte expression storage->cte mapper->cte result object is chained together with the regular storage->table->object.
5. All CTEs, including the current, as well as the actual select-statement can then refer to the results in the CTE.

Some implementation details that I just mention here

• label-type to abstract storage->table->object mappings
• Ad-hoc storage impl for expressions
• Extended 'column pointer' concept (it proved very handy in abstracting the ability to reference columns in other result sets)
• Capture expressions that form a subselect's columns, and their result

Along the way, in order to make all CTE examples and my use cases work, I added additional features that would make useful additions even without the CTE features.

• Ability to select all from table alias [select(asterisk<alias_a<Object>>)]
• Ability to form column numbers/indices via numeric literal operator template (ref)
• Ability to order by column number [order_by(1_nth_col)]
• min(X, Y, ...), max(X, Y, ...)
• Extended using_ to accept column pointers
• Ability to dump an expression (as opposed to only dumping the prepared statement) (ref)
• Ability to capture pointer-to-members at compile-time (this is useful for back-referencing)
• Fixed a bug finding the column via a column pointer

Additionally I didn't hesitate to overhaul internal parts of the storage implemention lookup machinery.

• Hoisted storage impl type calculations out of member functions into type system see storage_lookup.h
  (i.e. obsoleted storage_impl<>::get_impl<>() and storage_t<>::get_impl<>`)
• Overhauled storage implementation access, which greatly simplifies things.
• Hoisted a bunch of table/column lookup function into free-standing functions, for improved encapsulation.
• I removed the friend declarations in storage_t - it was hard to understand how exactly it was needed. Now, because serializator_context_builder was given friend access, anyone could access storage_t anyway. The much better thing I have chosen is an ADL friend function that obtains const access to the storage implementation. This allows for much better traceability. Additionally, unless necessary the better choice is to use the new access function.
• Everything in turn also improves code readability.

Questions

• Currently C++17 due to a bunch of fold-expression mambo-jambo. I find it already hard to program with C++14, so we might keep it C++17?
• It would be definitely useful if @fnc12 or others could eyeball the code.

TODO

• Unit Tests (currently only static unit tests for 'column expression types').
• Thourough build test to ensure I didn't break anything (I didn't attempt to build all examples and unit tests yet).
• Improve documentation.
• There might be problems with Visual C++ 2017 (15.9); there's a nasty bug in regard to variadic template functions being passed only one template argument (currently it only affects the polyfill::as_template_base).

[fnc12]

Hi @trueqbit . Your work looks existing and marvelous! I'm impressed! You wrote a lot of useful text so I'll respond with a bunch of text also.

1. your branch doesn't compile on my machine (macOS Xcode 13 clang 13). Errors depend on C++ standard I choose (I tried 14, 17 and 20);
2. implementing CTE and WITH is a great challenge!
3. code like this

//WITH RECURSIVE
//    cnt(x) AS(VALUES(1) UNION ALL SELECT x + 1 FROM cnt WHERE x < 1000000)
//    SELECT x FROM cnt;
auto ast =
    with(cte<cte_1>("x")(
             union_all(select(from), select(column<cte_1>(0_col) + c(1), where(column<cte_1>(0_col) < end)))),
         select(column<cte_1>(0_col)));

looks impressive but it lacks WITH table name 'cnt'. I'd change cte_1 to custom alias just like it is implemented in sqlite_orm:

using als_c = alias_c<Employee>;
using als_d = alias_d<Department>;

This technique allows using custom aliases like this:

struct alias_cnt {
    static std::string_view get() {  // return type can be std::string, const char * and anything that has operator<< with std::ostream
        return "cnt";
    }
};
// and then:
auto ast =
    with(cte<alias_cnt>("x")(
             union_all(select(from), select(column<alias_cnt>(0_col) + c(1), where(column<alias_cnt>(0_col) < end)))),
         select(column<alias_cnt>(0_col)));

Why it is important? Cause one of sqlite_orm goals is to provide coverage for 100% cases of serialization. I mean if user wants to use 'cnt' as alias we must not skip giving him/her this opportunity;
4) also we need an option to provide or omit RECURSIVE keyword. Probably using with and with_recursive functions;
5) one more question: how to specify columns with names right after cta table name? Probably some users will want to create a struct for it for mapping. Of course we can leave it unimplemented just for now. I am just asking;
6) 0_col functionality looks great but WHERE org.boss = works_for_alice.n doesn't equal where(c(&Org::boss) == column<cte_1>(0_col))). To write this user will need to keep one extra mapping inside his/her head: SQL to sqlite_orm mapping like 'yeah I remember that I cannot specify CTE's column name so I need to count the index of the column and write n_col instead'. The perfect option is to allow user writing the same thing using existing columns and column aliases technique;
7) I don't understand the purpose of c_v<&Family::name>. Describe me please;
8) Let me describe how I see CTE API:

//WITH RECURSIVE
//    parent_of(name, parent) AS
//    (SELECT name, mom FROM family 
//     UNION 
//     SELECT name, dad FROM family),
//    ancestor_of_alice(name) AS
//    (SELECT parent FROM parent_of WHERE name = 'Alice'
//        UNION ALL
//        SELECT parent FROM parent_of JOIN ancestor_of_alice USING(name))
//    SELECT family.name FROM ancestor_of_alice, family
//    WHERE ancestor_of_alice.name = family.name
//    AND died IS NULL
//    ORDER BY born;

struct MyCte1 {
    std::string name;
    std::string parent;
};

struct MyCte2 {
    std::string name;
};

auto ast =
        with(make_tuple(cte<MyCte1>("parent_of", make_column("name", &MyCte1::name), make_column("parent", &MyCte1::parent))
                        (union_(select(columns(c_v<&Family::name>, &Family::mom)),
                                select(columns(&Family::name, &Family::dad)))),
                        cte<MyCte2>("ancestor_of_alice", make_column("name", &MyCte2::name))
                        (union_all(
                            select(&MyCte1::parent, where(column<MyCte1>(c_v<&Family::name>) == "Alice")),
                            select(&MyCte1::parent, join<MyCte2>(using_(column<MyCte1>(c_v<&Family::name>))))))),
             select(&Family::name,
                    where(is_equal(&MyCte2::name, &Family::name) && is_null(&Family::died)),
                    order_by(&Family::born)));

9. order_by(2_nth_col) can be replaced with order_by(2) already now. 2_nth_col is over-engineering;
10. cte_label is a nice solution but a) it has not comfortable string interface (I am saying about dividing string into chars as template arguments); b) there is already API for this: table aliases from the item 3;
11. this is incredible

auto ast = with(
        make_tuple(
            cte<cte_xaxis>("x")(
                union_all(select(-2.0),
                          select(column<cte_xaxis>(0_col) + c(0.05), where(column<cte_xaxis>(0_col) < 1.2)))),
            cte<cte_yaxis>("y")(
                union_all(select(-1.0),
                          select(column<cte_yaxis>(0_col) + c(0.1), where(column<cte_yaxis>(0_col) < 1.0)))),
            cte<cte_m>("iter", "cx", "cy", "x", "y")(
                union_all(select(columns(0, column<cte_xaxis>(0_col), column<cte_yaxis>(0_col), 0.0, 0.0)),
                          select(columns(column<cte_m>(0_col) + c(1),
                                         column<cte_m>(1_col),
                                         column<cte_m>(2_col),
                                         column<cte_m>(3_col) * c(column<cte_m>(3_col)) -
                                             column<cte_m>(4_col) * c(column<cte_m>(4_col)) + column<cte_m>(1_col),
                                         c(2.0) * column<cte_m>(3_col) * column<cte_m>(4_col) + column<cte_m>(2_col)),
                                 where((column<cte_m>(3_col) * c(column<cte_m>(3_col)) +
                                        column<cte_m>(4_col) * c(column<cte_m>(4_col))) < c(4.0) &&
                                       column<cte_m>(0_col) < 28)))),
            cte<cte_m2>("iter", "cx", "cy")(select(
                columns(max<>(column<cte_m>(0_col)), column<cte_m>(1_col), column<cte_m>(2_col)),
                group_by(column<cte_m>(1_col), column<cte_m>(2_col)))),
            cte<cte_a>("t")(select(group_concat(substr(" .+*#", 1 + min<>(column<cte_m2>(0_col) / c(7.0), 4.0), 1), ""),
                                   group_by(column<cte_m2>(2_col))))),
        select(group_concat(rtrim(column<cte_a>(0_col)), "\n")));

I am waiting when someone will encode a marriage offer inside sqlite_orm code just for fun 😀;
12) I don't understand what is 'the ability to back-reference mapped columns'. Describe me please;
13) 'Ability to select all from table alias [select(asterisk<alias_a>)]' - it is very nice. It would be better to merge it using a dedicated PR to make everything simpler;
14) 'Ability to form column numbers/indices via numeric literal operator template ' - as I said this feature already exists in ORDER BY in SQLite. Adding it for a common select may make API less readable cause not everybody remembers indexes of columns;
15) 'min(X, Y, ...), max(X, Y, ...)' - lol I was sure that scalar versions of min and max are implemented. Thanks. It also better be implemented within a dedicated PR;
16) 'Ability to dump an expression (as opposed to only dumping the prepared statement) (ref)' - what is the purpose of this for end users?
17) 'Fixed a bug finding the column via a column pointer' - describe it please. Probably it is better to merge it within a dedicated PR;
18) 'Hoisted storage impl type calculations out of member functions into type system see storage_lookup.h
(i.e. obsoleted storage_impl<>::get_impl<>() and storage_t<>::get_impl<>)' - yeah this sounds very nice cause storage_impl is a bunch of legacy and is a pain in the ass. I can share you my plans for storage_impl. I'd like to refactor it to std::tuple of tables to reduce custom inheritance which increases binary size. Looks like you moved the code closer to this goal!
19) 'Overhauled storage implementation access, which greatly simplifies things.' - one more nice thing! You are Santa!
20) 'Hoisted a bunch of table/column lookup function into free-standing functions, for improved encapsulation.' - sounds nice also. Improved encapsulation makes code clearer;
21) 'I removed the friend declarations in storage_t' - wow this is also pretty nice cause I also don't like friend feature (but it was added by me, shame to me);
22) 'Currently C++17 due to a bunch of fold-expression mambo-jambo. I find it already hard to program with C++14, so we might keep it C++17?' - are you asking about dropping C++14 support? I did not understand this question;
23) let me help you with TODOs and all other stuff in case you need my help if you wish. We can talk using some IM app like telegram or slack if it is more comfortable for you (or keep talking here).

[juandent]

I agree that we should continue working in C++17. At least in Visual Studio 2022 support even for C++20 is excellent so if possible lets move to C++17... I currently run all my sqlite_orm use in C++ latest features (which is even ahead of C++ 20)

[fnc12]

ok but we need to preserve support for C++14 builds as before. It doesn't mean that all new features must be available with C++14 though