Implement history indexes

[bruth]

History applies to the valid time. Facts can be added to the database that apply to any point in time and therefore must be sorted and merged when being evaluated. The following command:

origins history mydomain --start=1492-01-01 --duration=1y --asof=1w

translates to the following query plan:

• Get all transactions in mydomain up to 1 week ago from now
• For each transaction
  • Find those that have at least one fact with a valid_time greater than or equal 1492-01-01 or less than 1493-01-01
  • Sort the facts by valid_time
  • Filter out facts not in the valid_time range
• Merge facts across transactions by valid_time

A few things to consider with this approach:

• Determining the set of applicable transactions is an O(n) operation
  • An interval tree index may be used here if necessary
• Transaction facts contain metadata including minValidTime and maxValidTime which are used to determine if the transaction is applicable. The filter function looks like this:

func filterTx(tx *Transaction, minT, maxT, minV, maxV int64) bool {
    // Not included
    if tx.TxTime < minT || tx.TxTime > maxT {
        return false
    }

    // At least one fact is known to be within the valid range.
    return tx.minValidTime >= minV || tx.maxValidTime <= maxV
}

• Filter and sort of each transaction can be done in parallel