Implement subqueries

[kashav]

Introduce subqueries to be used in condition statements, example:

"SELECT name FROM foo WHERE name NOT IN (SELECT name FROM ../bar WHERE date < ...)"

This shouldn't be too hard to implement.

First step is to introduce an IN operator for strings/numbers. The operator will return true if current the value is in the provided list.

The subquery should be evaluated individually. It returns a []Result for all files that passed the query (a Result struct holds each of the applicable attributes for a single file). Now we can apply IN to this result list.

Idea from https://news.ycombinator.com/item?id=14344493.

[kashav]

Work for this has begun on feature/subquery.

[kjhoerr]

Will this feature include the ability to reference values in superqueries? For instance,

"SELECT * FROM /foo AS foo WHERE name NOT IN (
  SELECT name FROM /bar AS bar WHERE foo.size < bar.size
)"

[kashav]

@kjhoerr Just want to clarify that I've understood this correctly.

Since we traverse each "source" directory provided to the FROM clause, the reference will point to each file and/or subdirectory of the source that we're currently traversing.

Using the example that you provided, if the directory structure was:

.
├── foo
│   └── bar
│       └── baz
├── bar
│   └── baz.txt

The query would run the subquery three times, first with foo referring to ./foo, then with foo referring to ./foo/bar, and then with foo referring to ./foo/bar/baz.

And each subquery would traverse each file of ./bar and compare the size of said file (which'll be referred to as bar) with that of foo.

If this is indeed what you're suggesting, I like it and I don't mind including the feature (sounds like a fun implementation), but based on my initial ideas, this may be very expensive to run. That being said, there might be a better implementation that I haven't thought of yet.

[kjhoerr]

Yes, such that it's quite like the implementation of subqueries in other SQL languages. The subquery is run against each entry of the superquery, so naturally it's very expensive to run. Then you could run queries that could for instance check if any given file appears in all the given directories.

Here's a mockup of the query, since I'm not sure how you could reference the parent folder:

# check for files that appear in all user's directories - target random but specific user
SELECT *
  FROM /home/user1 AS u1
  WHERE NOT EXISTS (
    FROM /home/. AS u2 WHERE NOT EXISTS ( 
      FROM `u2`/* WHERE u1.name = u2.name
    )
  )

Where EXISTS just returns true or false depending on whether or not any rows are returned from the subquery. Logically, it checks if a home exists that does not contain that file - if so, the file isn't included in the query. (No homes that do not contain the file can exist.)

In that case, since it has to know each name of each file before running the subquery to check against other directories, and it does so for each file. So, yes, enourmously expensive 🤕 I'm not sure if there's any cheaper way to write this sort of query, though.

[kashav]

This was partially implemented in #27.

Basic subqueries are working as expected (see README.md#subqueries), e.g.

>>> SELECT all FROM . WHERE name IN (SELECT name FROM ../foo)

However, there's no support for referencing values between queries yet. The boilerplate is implemented though, I hope to invest more time in completing this in the coming days.