Re: [RFC] ASOF Join
On 11/23/21 10:41, Isaac Morland wrote: > Umm, it's definitely negative: > > odyssey=> select '1 month -31 days +12:00:00'::interval < '0 > months'::interval; > -- > t Well, what you've shown here is that it's "negative" according to an arbitrary total ordering imposed in interval_cmp_value for the purpose of making it indexable in a btree ... > It's just that due to the complexities of our calendar/time systems, adding > it to a timestamp can move the timestamp in either direction: ... and this is just another way of saying that said arbitrary choice of btree ordering can't be used to tell you whether the interval is semantically positive or negative. (Of course, for a great many intervals, the two answers will be the same, but they're still answers to different questions.) > I'm working on a patch to add abs(interval) so I noticed this. There are > lots of oddities, including lots of intervals which compare equal to 0 but > which can change a timestamp when added to it, but as presently designed, > this particular interval compares as negative. It's no use—it's oddities all the way down. You can shove them off to one side of the desk or the other depending on your intentions of the moment, but they're always there. If you want to put intervals in a btree, you can define a total ordering where all days are 24 hours and all months are 30 days, and then there are no oddities in your btree, they're just everywhere else. Or you can compare your unknown interval to a known one like '0 months' and say you know whether it's "negative", you just don't know whether it moves a real date forward or back. Or you can see what it does to a real date, but not know whether it would precede or follow some other interval in a btree. Regards, -Chap
Re: [RFC] ASOF Join
On Tue, 23 Nov 2021 at 09:44, Chapman Flack wrote: > On 11/23/21 02:29, Ilya Anfimov wrote: > > (*We > > strangely don't have an absolute value operator on interval, but > > I think you've got the point*). > > Although tangential to the topic, that might be because a PG interval > is a triple of independently-signed months/days/seconds components. > An interval like '1 month -31 days +12:00:00' is positive or negative > depending on the absolute date you apply it to, so what its absolute > value should be isn't clear in isolation. > Umm, it's definitely negative: odyssey=> select '1 month -31 days +12:00:00'::interval < '0 months'::interval; ?column? -- t (1 row) It's just that due to the complexities of our calendar/time systems, adding it to a timestamp can move the timestamp in either direction: odyssey=> select '2021-02-01'::timestamp + '1 month -31 days +12:00:00'::interval; ?column? - 2021-01-29 12:00:00 (1 row) odyssey=> select '2021-03-01'::timestamp + '1 month -31 days +12:00:00'::interval; ?column? - 2021-03-01 12:00:00 (1 row) I'm working on a patch to add abs(interval) so I noticed this. There are lots of oddities, including lots of intervals which compare equal to 0 but which can change a timestamp when added to it, but as presently designed, this particular interval compares as negative.
Re: [RFC] ASOF Join
On 11/23/21 02:29, Ilya Anfimov wrote: > (*We > strangely don't have an absolute value operator on interval, but > I think you've got the point*). Although tangential to the topic, that might be because a PG interval is a triple of independently-signed months/days/seconds components. An interval like '1 month -31 days +12:00:00' is positive or negative depending on the absolute date you apply it to, so what its absolute value should be isn't clear in isolation. That's also why there's no everywhere-defined conversion from PG interval to XML xs:duration or to java.time.Duration, etc. Regards, -Chap
Re: [RFC] ASOF Join
On Mon, Nov 22, 2021 at 03:44:37PM +0300, Alexander Kuzmenkov wrote: > On 21.11.2021 07:53, Ilya Anfimov wrote: > > DISCLAIMER: I am both seeing this first time and I don't have a > > good understanding of the PosgreSQL development practices. > > > pure evil > > ridiculous > No worries, at least you got the etiquette just right. > > > There are two points in your mail that I'd like to discuss. > First, the ASOF grammar being bad because it's implicit. I do > agree on the general idea that explicit is better UX than implic- > it, especially when we're talking about SQL where you spend half > the time battling the query planner already. However, in the > grammar I proposed it's unambiguous which conditions are ASOF and > which are not -- all inequalities are ASOF, all equalities are I see at least two operators in postgres that implement ordering while they are not being <= ( ~<=~ -- for text compare byte-by- byte, and *<= for internal record compare) and four cases that are literally <= , but don't implement or- dering -- box, lseg, path and circle are compared by length and fuzzy floating-point comparision. Are you sure an implementor and a programmer will easily decide what is just a boolean test, and what is an order? What's worse, preference of values doesn't have a lot in common with filters you want on them. Let's get your example of a time matching: another reasonable business case is to match the near- est time point in any direction, within a reasonable time limit. Like timea BETWEEN timeb - '1s' AND timeb + '1s' , and to choose something like min(@(timea-timeb)) among them (*We strangely don't have an absolute value operator on interval, but I think you've got the point*). > not, and there can be no other kinds of conditions for this type > of join. It can also support any number of ASOF conditions. Which > grammar exactly do you suggest? Maybe something like this: > > asks JOIN bids ON asks.instrument = bids.instrument ASOF asks.timestamp <= > bids.timestamp I suggest JOIN bids ORDER BY asks.timestamp DESC LIMIT 1 ON asks.instrument = bids.instrument AND asks.timestamp <= bids.timestamp LIMIT 1 could also be implied.
Re: [RFC] ASOF Join
On 21.11.2021 07:53, Ilya Anfimov wrote: DISCLAIMER: I am both seeing this first time and I don't have a good understanding of the PosgreSQL development practices. pure evil ridiculous No worries, at least you got the etiquette just right. There are two points in your mail that I'd like to discuss. First, the ASOF grammar being bad because it's implicit. I do agree on the general idea that explicit is better UX than implicit, especially when we're talking about SQL where you spend half the time battling the query planner already. However, in the grammar I proposed it's unambiguous which conditions are ASOF and which are not -- all inequalities are ASOF, all equalities are not, and there can be no other kinds of conditions for this type of join. It can also support any number of ASOF conditions. Which grammar exactly do you suggest? Maybe something like this: asks JOIN bids ON asks.instrument = bids.instrument ASOF asks.timestamp <= bids.timestamp This still does require a keyword. Second, you say that we must first optimize the corresponding LATERAL. I was thinking about this as well, but _that_ is what's not explicit. I'm not sure if this optimization would have any value outside of optimizing ASOF joins. We might give better UX if we embrace the fact that we're doing an ASOF join and allow the user to state this explicitly and get an efficient and predictable plan, or an error, instead of trying to guess this from the rewritten queries and silently falling back to an inefficient plan for cryptic reasons. -- Alexander Kuzmenkov Timescale
Re: [RFC] ASOF Join
>But anyways this looks like just a syntactic sugar. LATERAL >JOINS should logically work just fine. Any optimisation should >deal with the LATERAL syntax style anyway. Agreed. However, if a rewrite is implemented, it then becomes encoded into PostgreSQL code what ASOF maps to. Anyone who wants to use ASOF can use it, and anyone who wants to directly use LATERAL can do so also. On Sun, 21 Nov 2021 at 15:54, Ilya Anfimov wrote: > On Thu, Nov 18, 2021 at 05:11:16PM +0300, Alexander Kuzmenkov wrote: > > Hi hackers, > > > > There was some interest in implementing ASOF joins in Postgres, see > > e.g. this prototype patch by Konstantin Knizhnik: > > > https://www.postgresql.org/message-id/flat/bc494762-26bd-b100-e1f9-a97901ddad57%40postgrespro.ru > > I't like to discuss the possible ways of implementation, if there is > > still any interest in that. > > > > > > Introduction > > > > ASOF join is often used to work with time series data such as stock > > quotes or IoT sensors. It is an interpolation where we want to relate > > two different time series measured at different points in time. For > > each value of the first time series, we take the most recent value of > > the second. > > DISCLAIMER: I am both seeing this first time and I don't have a > good understanding of the PosgreSQL development practices. > > But at a first glance the syntax looks like pure evil. I see > that this is somewhat common as of now (clickhouse, your refer- > enced questdb, quasar db) -- but it's bad anyway. And not really > a standard. > > This introduces a new keyword to the ridiculous list of key- > words. > The syntax loosely defines what preference it wants, by extract- > ing some vague set of ordering operators from the join condition. > Also, only one asof value is allowed (there may be more of it > sometimes). > > Perhaps, if we've got to some syntax -- than something like > ORDER BY ... LIMIT > in joins, just before the ON join_condition or USING() could be > much better. > This allows to >1) Easily separate just conditions from the likehood ones. No > deep analysis of a condition expression necessary. No need to > have another list of all the possible ranking functions and oper- > ators. >2) Have ordering preference for many ranking conditions. Like > ORDER BY secondary_field IS NOT NULL DESC, time_difference, reli- > ability >3) Have more than one row returned for a joined table. > > > But anyways this looks like just a syntactic sugar. LATERAL > JOINS should logically work just fine. Any optimisation should > deal with the LATERAL syntax style anyway. > > > > > > Besides an inequality condition on timestamp, such join can also have > > equality conditions on other columns. For example, this query joins > > two tables that contain bids and asks, finding the most recent task > > for each bid for given financial instrument: > > > > ```sql > > SELECT bids.ts timebid, bid, ask > > FROM bids > > ASOF JOIN asks ON bid.instrument = ask.instrument > > AND ask.ts <= bid.ts; > > ``` > > > > Semantically, this is equivalent to the following correlated subquery: > > ```sql > > SELECT bids.ts timebid, bid, ask > > FROM bids, > > LATERAL (select * from asks > > WHERE asks.instrument = bids.instrument AND asks.ts <= bids.ts > > ORDER BY ts DESC LIMIT 1) t; > > ``` > > This form is useful to think about which optimizations we can perform > > with an ASOF join, how it behaves with respect to other joins, and so > > on. > > > > QuestDB has some good docs on this with more examples: > > https://questdb.io/docs/reference/sql/join/#asof-join > > > > > > What Conditions Work with ASOF Join > > > > Conditions for an ASOF join consist of one inequality condition (>= > > etc), and optionally a number of equality conditions. All these > > conditions must be "mergejoinable" in PG terms -- they must belong to > > a btree operator family, which means there is a sorting operator that > > corresponds to the condition, which means we can perform a merge join. > > They also must support hashing because we'll probably need both > > sorting and hashing for implementation (see below). This holds for the > > usual data types like numeric. It is natural to think of the > > inequality column as "time", but technically it can be any column, > > even a string one, w/o changing the algorithm. > > > > > > Join variants > > > > The purpose of ASOF join is interpolation of one time series to match > > another, so it is natural to think of it as an INNER join. The outer > > variants might be less useful. Technically, it is easy to extend it to > > LEFT ASOF JOIN, where we would output nulls for the right hand columns > > if we haven???t yet seen a match. RIGHT and FULL variants also make > > sense, but the implementation may be impossible, depending on the > > algorithm -- merge and hash joins can support these variants, but the > > nested loop cannot. > > > > > > Use in Combination
Re: [RFC] ASOF Join
On Thu, Nov 18, 2021 at 05:11:16PM +0300, Alexander Kuzmenkov wrote: > Hi hackers, > > There was some interest in implementing ASOF joins in Postgres, see > e.g. this prototype patch by Konstantin Knizhnik: > https://www.postgresql.org/message-id/flat/bc494762-26bd-b100-e1f9-a97901ddad57%40postgrespro.ru > I't like to discuss the possible ways of implementation, if there is > still any interest in that. > > > Introduction > > ASOF join is often used to work with time series data such as stock > quotes or IoT sensors. It is an interpolation where we want to relate > two different time series measured at different points in time. For > each value of the first time series, we take the most recent value of > the second. DISCLAIMER: I am both seeing this first time and I don't have a good understanding of the PosgreSQL development practices. But at a first glance the syntax looks like pure evil. I see that this is somewhat common as of now (clickhouse, your refer- enced questdb, quasar db) -- but it's bad anyway. And not really a standard. This introduces a new keyword to the ridiculous list of key- words. The syntax loosely defines what preference it wants, by extract- ing some vague set of ordering operators from the join condition. Also, only one asof value is allowed (there may be more of it sometimes). Perhaps, if we've got to some syntax -- than something like ORDER BY ... LIMIT in joins, just before the ON join_condition or USING() could be much better. This allows to 1) Easily separate just conditions from the likehood ones. No deep analysis of a condition expression necessary. No need to have another list of all the possible ranking functions and oper- ators. 2) Have ordering preference for many ranking conditions. Like ORDER BY secondary_field IS NOT NULL DESC, time_difference, reli- ability 3) Have more than one row returned for a joined table. But anyways this looks like just a syntactic sugar. LATERAL JOINS should logically work just fine. Any optimisation should deal with the LATERAL syntax style anyway. > > Besides an inequality condition on timestamp, such join can also have > equality conditions on other columns. For example, this query joins > two tables that contain bids and asks, finding the most recent task > for each bid for given financial instrument: > > ```sql > SELECT bids.ts timebid, bid, ask > FROM bids > ASOF JOIN asks ON bid.instrument = ask.instrument > AND ask.ts <= bid.ts; > ``` > > Semantically, this is equivalent to the following correlated subquery: > ```sql > SELECT bids.ts timebid, bid, ask > FROM bids, > LATERAL (select * from asks > WHERE asks.instrument = bids.instrument AND asks.ts <= bids.ts > ORDER BY ts DESC LIMIT 1) t; > ``` > This form is useful to think about which optimizations we can perform > with an ASOF join, how it behaves with respect to other joins, and so > on. > > QuestDB has some good docs on this with more examples: > https://questdb.io/docs/reference/sql/join/#asof-join > > > What Conditions Work with ASOF Join > > Conditions for an ASOF join consist of one inequality condition (>= > etc), and optionally a number of equality conditions. All these > conditions must be "mergejoinable" in PG terms -- they must belong to > a btree operator family, which means there is a sorting operator that > corresponds to the condition, which means we can perform a merge join. > They also must support hashing because we'll probably need both > sorting and hashing for implementation (see below). This holds for the > usual data types like numeric. It is natural to think of the > inequality column as "time", but technically it can be any column, > even a string one, w/o changing the algorithm. > > > Join variants > > The purpose of ASOF join is interpolation of one time series to match > another, so it is natural to think of it as an INNER join. The outer > variants might be less useful. Technically, it is easy to extend it to > LEFT ASOF JOIN, where we would output nulls for the right hand columns > if we haven???t yet seen a match. RIGHT and FULL variants also make > sense, but the implementation may be impossible, depending on the > algorithm -- merge and hash joins can support these variants, but the > nested loop cannot. > > > Use in Combination with Normal Joins > > The difference of ASOF join from normal join is that for the > inequality condition, it does not output all the rows that match it, > but only the most recent one. We can think of it as first performing a > normal join and then applying a filter that selects the latest right > hand row. Which row is the "latest" depends on the entire set of rows > that match the join conditions (same as with LIMIT). This means that > the result of ASOF join may depend on the place in the join tree where > it is evaluated, because other joins may remove some rows. Similar to > outer joins, we must respect the user-specified jo
[RFC] ASOF Join
Hi hackers, There was some interest in implementing ASOF joins in Postgres, see e.g. this prototype patch by Konstantin Knizhnik: https://www.postgresql.org/message-id/flat/bc494762-26bd-b100-e1f9-a97901ddad57%40postgrespro.ru I't like to discuss the possible ways of implementation, if there is still any interest in that. Introduction ASOF join is often used to work with time series data such as stock quotes or IoT sensors. It is an interpolation where we want to relate two different time series measured at different points in time. For each value of the first time series, we take the most recent value of the second. Besides an inequality condition on timestamp, such join can also have equality conditions on other columns. For example, this query joins two tables that contain bids and asks, finding the most recent task for each bid for given financial instrument: ```sql SELECT bids.ts timebid, bid, ask FROM bids ASOF JOIN asks ON bid.instrument = ask.instrument AND ask.ts <= bid.ts; ``` Semantically, this is equivalent to the following correlated subquery: ```sql SELECT bids.ts timebid, bid, ask FROM bids, LATERAL (select * from asks WHERE asks.instrument = bids.instrument AND asks.ts <= bids.ts ORDER BY ts DESC LIMIT 1) t; ``` This form is useful to think about which optimizations we can perform with an ASOF join, how it behaves with respect to other joins, and so on. QuestDB has some good docs on this with more examples: https://questdb.io/docs/reference/sql/join/#asof-join What Conditions Work with ASOF Join Conditions for an ASOF join consist of one inequality condition (>= etc), and optionally a number of equality conditions. All these conditions must be "mergejoinable" in PG terms -- they must belong to a btree operator family, which means there is a sorting operator that corresponds to the condition, which means we can perform a merge join. They also must support hashing because we'll probably need both sorting and hashing for implementation (see below). This holds for the usual data types like numeric. It is natural to think of the inequality column as "time", but technically it can be any column, even a string one, w/o changing the algorithm. Join variants The purpose of ASOF join is interpolation of one time series to match another, so it is natural to think of it as an INNER join. The outer variants might be less useful. Technically, it is easy to extend it to LEFT ASOF JOIN, where we would output nulls for the right hand columns if we haven’t yet seen a match. RIGHT and FULL variants also make sense, but the implementation may be impossible, depending on the algorithm -- merge and hash joins can support these variants, but the nested loop cannot. Use in Combination with Normal Joins The difference of ASOF join from normal join is that for the inequality condition, it does not output all the rows that match it, but only the most recent one. We can think of it as first performing a normal join and then applying a filter that selects the latest right hand row. Which row is the "latest" depends on the entire set of rows that match the join conditions (same as with LIMIT). This means that the result of ASOF join may depend on the place in the join tree where it is evaluated, because other joins may remove some rows. Similar to outer joins, we must respect the user-specified join order for an ASOF join. It is useful to think about pushing another join below an ASOF join as pushing a join below a correlated subquery with LIMIT (see above). This transformation might be correct in some cases, so we might later think about adding some optimization for join order for ASOF join. Proposed Syntax ASOF join is semantically distinct from a normal join on the same conditions, so it requires separate grammar. ASOF modifier + listing all the conditions in the ON section, looks like a good baseline: `bids ASOF JOIN asks ON asks.timestamp <= bids.timestamp AND asks.instrument = bids.instrument` Algorithms Let's see which algorithm we can use to perform an ASOF join if we have a "<=" condition on timestamp and several "=" conditions on other columns (equi-columns). 1. Hash on Equi-keys This is what ClickHouse uses. It builds a hash table on equi columns, then for each equi-key builds an array of timestamps, sorted on demand. This requires bringing the entire right hand table into memory, so not feasible for large tables. 2. Merge Join on (equi-keys, timestamp) Sorting This is a natural extension of the merge join algorithm, but instead of returning all keys for the timestamp column, it returns only the latest one. A drawback of this algorithm is that the data must be sorted on timestamp last, so we can't reuse the natural ordering of the time series data encoded by a (timestamp) index. We will have to sort both tables entirely in different order, which is prohibitively costly for large tables. Another way is to create an index on (equi-keys, timestamp). This would allo
