[WIP] Native SQLite Database reader (works at CTFE)

[Chris Wright via Digitalmars-d]

On Sun, 21 Feb 2016 18:12:27 +0000, Stefan Koch wrote:

> On Sunday, 21 February 2016 at 18:08:30 UTC, Chris Wright wrote:
>> That means never using an index.
> How so ?

Or rather, parsing a query to use an index becomes exponential unless you 
parse X86 instructions.

D doesn't let you access the contents of a lambda expression. (C# does.) 
So in order to evaluate the lambda, you have to invoke it.

You can't override <= separately from <. You only have an opCmp 
invocation and return value. So with a query filter like:

query.where!("age", (age) => age >= 18);

You know it's being compared to 10, but you don't know what comparison. 
So the first time, you have opCmp return -1, and the lambda yields false. 
Try again, have opCmp return 0, and the lambda yields true. Try a third 
time, have opCmp return 1, and it yields true.

That's three invocations for one variable. What about two variables?

query.where!("age,parental_supervision",
  (age, parentalSupervision) => age >= 18 || parentalSupervision == true);

Now I have to try three different values for the 'age' expression and two 
for the 'parentalSupervision' variable, and there's a combinatorial 
expansion.

That yields a giant truth table, and that's probably good enough. You 
look at which columns have an index and, of those, which have the best 
correlation with the lambda's result. That even lets you reduce the 
amount of memory you use -- you don't need to hold the whole truth table, 
just a series of counters. But you're still dealing with O(2**n) 
evaluations of the lambda.