Materialize: sql: make SQL queries linearizable

[mjibson]

SQL queries are currently not linearizable. We need to change them so that our timestamp selection never goes down so that if any sql session observes something, all others are guaranteed to also. One way of solving this is to keep a record of any chosen query timestamps and ensure that any other chosen timestamps are at least that. This has problems though because sometimes we choose timestamps that are 0 or max, or we have sources that don't create realtime timestamps, and we need a way to prevent the global "don't go down from this" timestamp from ever being max or something that would cause realtime queries to block indefinitely waiting to catch up.

This problem, though, is caused because we have various ways of creating timestamps, some with different meanings. Many things generate now-ish timestamps, which is fine. Debezium consistency topic sources, though, start at 1 and increase from there, and thus aren't even timestamps, just a counter.

6393 is a proposal to create things called timelines that would specify the meaning of these timestamp numbers and also prevent join data sources from two different timelines. We want to prevent that joining because:

1. The chosen timestamp could be so high it will never be reached, resulting in a user waiting forever instead of mz telling the user "nope, this will just wait forever".
2. Even if the user did wait forever, it is not correct to join data from two timelines that happen to have the same timestamp number because those timestamps mean different things. If we return data anyway, we are implying to the user that the data are meaningful and correct, when they are not.

Linearizability, then, should perhaps keep one number per timeline and ensure it always goes up. This would allow everything to 1) always go forward, 2) be correct and 3) never have a "wait forever" behavior.

[mjibson]

cc @awang @frankmcsherry. These are my current thoughts about why timelines and linearizability are related.

[awang]

Thanks! In general I really like the idea of allowing users to specify how they want a specific source or view to behave, as an alternative to "wait forever" behavior! However:

also prevent join data sources from two different timelines.

Does this imply creating a user limitation like it sounds like -- ie some sources will be unable to be joined? If so, which sources?

[mjibson]

allowing users to specify how they want a specific source or view to behave

No, the proposal is that materialize determines how they behave, not the user.

some sources will be unable to be joined? If so, which sources?

Correct. Sources from different timelines can't be joined.

I'm going to open a PR probably today with an updated timelines proposal which will go over all of these in detail, so maybe wait until that is open to ask more questions, since it might answer them. I wanted to use this issue only to document a high-level direction for linearizability and how timelines relate to it. Let's delay any discussion of timelines until I open a PR.