Does ORDER BY work?

[bradjc]

I'm trying this:

#include "../../dbparser/dbparser.h"

#define BYTES_LEN 400

int main(void)
{

    char          memseg[BYTES_LEN];
    db_query_mm_t mm;
    db_op_base_t* root;
    db_tuple_t    tuple;

    init_query_mm(&mm, memseg, BYTES_LEN);
    parse("CREATE TABLE sensors (id int, temp int);", &mm);

    init_query_mm(&mm, memseg, BYTES_LEN);
    parse("INSERT INTO sensors VALUES (1, 221);", &mm);
    init_query_mm(&mm, memseg, BYTES_LEN);
    parse("INSERT INTO sensors VALUES (2, 89884);", &mm);
    init_query_mm(&mm, memseg, BYTES_LEN);
    parse("INSERT INTO sensors VALUES (3, 112);", &mm);
    init_query_mm(&mm, memseg, BYTES_LEN);
    parse("INSERT INTO sensors VALUES (4, 455);", &mm);
    init_query_mm(&mm, memseg, BYTES_LEN);
    parse("INSERT INTO sensors VALUES (5, 3313);", &mm);
    init_query_mm(&mm, memseg, BYTES_LEN);
    parse("INSERT INTO sensors VALUES (6, 11);", &mm);
    init_query_mm(&mm, memseg, BYTES_LEN);
    parse("INSERT INTO sensors VALUES (7, 99996);", &mm);
    init_query_mm(&mm, memseg, BYTES_LEN);
    parse("INSERT INTO sensors VALUES (8, 6565);", &mm);
    init_query_mm(&mm, memseg, BYTES_LEN);
    parse("INSERT INTO sensors VALUES (9, 6565);", &mm);

    init_query_mm(&mm, memseg, BYTES_LEN);
    root = parse("SELECT * FROM sensors ORDER BY id DESC;", &mm);
    if (root == NULL) {
        printf("NULL root\n");
    } else {
        init_tuple(&tuple, root->header->tuple_size, root->header->num_attr, &mm);

        while (next(root, &tuple, &mm) == 1) {
            int id = getintbyname(&tuple, "id", root->header);
            int sensor_val = getintbyname(&tuple, "temp", root->header);;
            printf("sensor val: %i (%i)\n", sensor_val, id);
        }
    }

    return 0;
}

and getting:

sensor val: 221 (1)
sensor val: 89884 (2)
sensor val: 112 (3)
sensor val: 455 (4)
sensor val: 3313 (5)
sensor val: 11 (6)
sensor val: 99996 (7)
sensor val: 6565 (8)
sensor val: 6565 (9)

But I am expecting the results in the opposite order.

[graemedouglas]

Not at present. There is support for a sorting-based operator that has not been worked into the parser. You basically get SELECT-FROM-WHERE for now if SQL is the way you go.

One way you could hack this is to look here. In particular, focus on some of the later unit tests that construct the queries by hand like test_sort_11 and test_sort_12. I know its a little ugly, but you could stack the sort on top of the returned query (you would pass root as the child to sort).

Aggregation and grouping is not yet supported, before you ask about that too. ;)

[pfalcon]

The main question here is whether LittleD supports indexes and can use them to fetch ordered results (or each sorting operation is expensive).

[pfalcon]

Ok, so there's https://github.com/graemedouglas/LittleD/tree/master/src/dbindex , and source even appears to have a function to read index. But there's no code for updating index, which effectively means there're no indexes. But then sorting anyhow efficiently means keeping in memory at least some value for each row in queryset (if not entire rows themselves). Of course, no Arduino can do that even for minuscule 1000-row database. But then there's another way to "sort" - for each row, linearly scan entire queryset to find "next in sorted order" row. And shiver me timbers if it's not what LittleD does.

That makes it O(n^2) operation, and to sort minuscule 1000-row database, there will be a million rows read. What a perfect way to burn joules in the sensor nodes!

So, thanks, but no. Perhaps, the idea to slim down sqlite is much more viable than dreaming that someone can just sit and write it all unbloated from scratch.

[graemedouglas]

Indexes have very, very rudimentary support in LittleD. The only index that is supported is one that assumes the tuples are already stored in sorted order for the attribute specified. Admittedly not ideal, which is part of the motivation behind why we built IonDB, to be the indexing/storage engine of LittleD eventually. That just hasn't happened yet.

Right now, LittleD's sort operation is in fact a terrible O(n^2) sort. I think that claiming this is entirely useless is unfair, since there would be cases where your tables are small (less than say 50 rows) where sorting is totally viable for queries not run often. For larger tables, you would definitely want to use an index though, which is again a planned feature.

I looked at trimming down SQLite, but thats a task much easier said than done. The majority of the complexity of these systems come from the query translation system, and SQLite uses traditional generated parsing/lexing techniques, which are non-starters for many applications. Also, SQLite can be made to work with no less than 300KiB ROM, 4KiB stack memory, and 100KiB heap out of the box, whereas LittleD uses far less (for most expected queries, well under 1KB). Of course, if your device could use SQLite and application code allow for it, it is the ideal choice, but this is a luxury many devices do not have.

If you had ideas of how to slim down SQLite, I would love to be proven wrong about the difficulty of the task. :)

[pfalcon]

Thanks for the response.

I think that claiming this is entirely useless

That's certainly not what I say. And the best argument you can give is that indexing is optimization, and before optimizing particular cases, there should be a general implementation which works for any case, and that's what you have. And it's hard to disagree with that. But it's also hard to disagree that real-world usability of databases, more so of databases using general relational model, depends on indexes. So, indexes not being part of the core design is pretty sad. LittleD of course has its use already and its pretty cool, it's just hard to see it as a general-purpose SQL database. In that regard, if it instead e.g. supported sorting by just one criteria, but used index, it would be more hopeful (adding inefficient generic algorithm is always easier ;-) ).

I looked at trimming down SQLite, but thats a task much easier said than done.

I know, I know, that's why I'm rather lurking around seeing what people do, rather than go for that myself purely out of aesthetic feelings ;-).

for most expected queries, well under 1KB

That's very cool, and I like that much. But then it does too little real-world useful to treat that as an ultimate win ;-).

If you had ideas of how to slim down SQLite, I would love to be proven wrong about the difficulty of the task. :)

Yep, sqlite is clearly not modular and decoupled enough, as e.g. attempt to integrate LMDB with it shows: https://gitlab.com/mdb/sqlightning.git . But sqlite4 (in pseudo-dormant development since 2011) makes it easier by clearly separating underlying key-value storage engine (which marks a full circle, as sqlite1 used gdbm as underlying storage engine; and btw, taking sqlite1 for embedded use may be not that bad idea either).