Table time travel support

[gruuya]

Is your feature request related to a problem or challenge?

A lot of DBs and table formats (e.g. Delta Lake) rely on one form or another of MVCC, whererby writes to a given table will result in a new table version. Typically, writes will usually append new files to the table state (INSERT) and/or potentially remove some files from the state (UPDATE/DELETE).

A core feature of such systems is the ability to travel between different table versions, so that one can query some earlier (non-latest) table state. However, this is not currently officially supported by DataFusion, though it is doable in a hacky way (see below for details or here for an overview of how this works in seafowl right now).

Describe the solution you'd like

First part of the work would be in the sqlparser crate, which would need to support the standard temporal table specifier in the form of a AS OF clause (https://en.wikipedia.org/wiki/SQL:2011)

I think this should probably be captured in a new field in TableFactor::Table.

Over at DataFusion side, besides capturing the parsed version in the TableScan logical plan, I imagine the main (breaking) change would be to alter the signature of the SchemaProvider::table method to something like

async fn table(&self, name: &str, version: Option<TableVersion>) -> Option<Arc<dyn TableProvider>>;

with TableVersion being some kind of an enum covering time formats or literal version denotations for starters. That would enable the implementer of this trait to know which specific table version needs to be loaded (if any).

Describe alternatives you've considered

The alternative that seafowl uses atm is the following:

• abuse the existing table function syntax to smuggle the version information in a given sqlparser::ast::Statement[0]
• perform a walk over each incoming sqlparser::ast::Query, trying to see whether a table function syntax was used[1]
• if it was, rename the table to something unique, and register the TableProvider for the specific table version in a new session context/state[2]

[0] https://seafowl.io/docs/guides/querying-time-travel#querying-older-table-versions
[1] https://github.com/splitgraph/seafowl/blob/main/src/version.rs#L58-L91
[2] https://github.com/splitgraph/seafowl/blob/main/src/context.rs#L542-L565

Additional context

If this is something that is deemed to be sufficiently important for/compatible with DataFusion I'd be happy to take on the work needed to implement this.

[gruuya]

Over at DataFusion side, besides capturing the parsed version in the TableScan logical plan

Actually, looking at this a bit more in-depth, TableScan would not need to be changed. Instead prior to creating that node we'd need to parse the table version during table reference resolution (resolve_table_references) inside statement_to_plan, which would in turn mean extending the sqlparser Visitor to go through TableFactors.

Then, while pre-populating the table providers for the referenced tables in the SessionContextProvider, we'd register the TableProvider for the specific table version provided. This also means that SessionContextProvider would need to track both the table name and the version too, since a given query could involve multiple versions of the same table, so something like

struct SessionContextProvider<'a> {
    state: &'a SessionState,
    tables: HashMap<(String, Option<TableVersion>), Arc<dyn TableSource>>,
}

[alamb]

It seems like another possibility might be to add another argument to the TableProvider::scan argument. That way it would parallel other options that get pushed down like limit and filtering 🤔

https://docs.rs/datafusion/latest/datafusion/datasource/provider/trait.TableProvider.html#tymethod.scan

(if we are going to update the scan method, we might want to think about making a ScanOptions type struct and leave some backwards compatibility pieces around)

[gruuya]

another possibility might be to add another argument to the TableProvider::scan

True, but the main reason deferring the version resolution to the scan itself may be less favorable is that schemas can also evolve over different versions, and then we'd need to extend the TableProvider::schema method (and probably TableProvider::statistics or others). This means we'd also need to make any callers of these methods aware of what was the original version used in the query, which would mean a lot of new arguments all over the place.

Hence, why having a separate TableProvider per version is better I think (and registering those ahead of time, when populating the SessionContextProvider for a given query).

[alamb]

Hence, why having a separate TableProvider per version is better I think (and registering those ahead of time, when populating the SessionContextProvider for a given query)

That makes sense 👍

[gruuya]

Thanks; if there's a consensus on whether this would be worthwhile for DataFusion at all let me know, as I would love to contribute it.

[alamb]

Maybe it would be worth sending a note to dev@arrow.apache.org to get a wider distribution.

For example https://lists.apache.org/thread/837ghhjh9gd1kvg0qqnmxqs0rm62x0xt

[gruuya]

Great, will do that, thanks!

[alamb]

While reviewing apache/datafusion-sqlparser-rs#951 I found the following reference from BigQuery about "time decorators" that might be able to support this feature without any datafusion changes:

https://cloud.google.com/bigquery/docs/table-decorators#time_decorators

❯ create table foo (x int);
0 rows in set. Query took 0.001 seconds.

❯ select * from foo@1234;
Error during planning: table 'datafusion.public.foo@1234' not found

The downside is that the integer syntax to calculate is pretty bad, Adding real SQL support is likely a nicer option

[gruuya]

Oh that's a nice find, I haven't seen that. Indeed it seems it could provide time travel support without DF changes, albeit in a hacky way, by smuggling the version in the table name itself.

The downside is that the integer syntax to calculate is pretty bad, Adding real SQL support is likely a nicer option

Agreed; real SQL support would be more expressive and explicit.

[liukun4515]

I think we need more response from the community and review it.
It's a big feature and changes

[gruuya]

I think we need more response from the community and review it. It's a big feature and changes

Yup, makes sense. Happy to leave this open (or close it) until definitive consensus is achieved.

Just the sqlparser PR on it's own would go a long way in terms of easing the implementation of table time travel in DataFusion derived systems.

[alamb]

Just the apache/datafusion-sqlparser-rs#951 on it's own would go a long way in terms of easing the implementation of table time travel in DataFusion derived systems.

That has been merge and released, so hopefully that helps

[gruuya]

Closing this, as I think the sqlparser changes and extensions will suffice for now, thanks!