New Setting to enable successive time range queries over a large overall time range

[knudtty]

Company or project name

ClickStack @ ClickHouse

Use case

Ability to short circuit non read_in_order top N queries and pseudo-streaming of aggregation functions.

Describe the solution you'd like

A setting(s) that allows specifying a time bucketing column and varying time buckets to execute multiple queries. Example usage would be time_range_identifier='Timestamp', time_range_buckets='1m,15m,1h,6h,6h,12h,24h'. In the case where the time range queried exceeds the sum total of the time range buckets, the final time bucket is used for further time bucket queries. For the example of settings I've given applied to a 4 day range query, the subqueries are issued in succession with time ranges of 1m, 15m, 1h, 6h, 6h, 12h, 24h, 24h, and 22h44m. For Top N queries with an ORDER BY and LIMIT, the query can be short circuited once the LIMIT is hit. For Aggregation queries that are grouping by the time_range_identifier, results can be streamed back to the client upon each successive query.

Describe alternatives you've considered

Application level logic (explained in the Additional context). However, each application that seeks these benefits must implement them on their own, and there is an opportunity for a db level feature so that each application can benefit.

Recursive CTEs almost get you there, but I don't believe you can short circuit them. Also, they're pretty ugly.

The read_in_order optimization is the only short circuit mechanism that I know of, but it isn't always feasible. Additionally, read_in_order isn't applicable to aggregation queries like I outlined.

Additional context

In ClickStack, we are constantly trying to optimize performant queries and user experience. Some time ago, we saw on large datasets that Top N and aggregation queries over large time ranges will often take several seconds, and the users were not satisfied with watching loading spinners for many seconds. We implemented some application level logic to issue successive queries over increasingly large time ranges.

For a top N query example, imagine we want to display 200 rows over a time range in descending order where the overall time range is 24 hours. First the application breaks up the time range into several "windows" over a 1 minute time range with a limit. The returned rows are evaluated. If the limit was met, no further queries are sent. If the limit was not met, a successive query is issued from the application over the next 15 minutes in the time range with an adjusted limit based on how many rows were returned from the first query. This pattern is repeated with increasingly large time ranges (1m -> 15m -> 1h -> 6h -> 6h -> 12h -> 24h), until either the limit is reached or the search over the entire time range has been executed.

For an aggregation query example, imagine we have a line chart displaying a sum aggregation of some Value column over a time range. Aggregated sum values are grouped by some time bucketing transformation (eg. toStartOfMinute(Timestamp)). The application issues a queries successively over the entire time range following the same bucket sizing (1m -> 15m -> 1h -> 6h -> 6h -> 12h -> 24h) and displays results as they arrive.

[ylw510]

Hi @knudtty. Can you take a look at this issue? Do you think it is necessary to implement it at the kernel level?
#111447

[UnamedRus]

Related #17941

[rschu1ze]

For my understanding @knudtty - your application logic currently does this:

SELECT [...] WHERE <time_range_identifier_column> = now - INTERVAL 1 MINUTE;

--- if a result is returned early out, otherwise:
SELECT [...] WHERE <time_range_identifier_column> = now - INTERVAL 15 MINUTE;

--- if a result is returned early out, otherwise:
SELECT [...] WHERE <time_range_identifier_column> = now - INTERVAL 1 HOUR;

etc.

(the ticket also mentions read-in-order and <time_range_identifier_column> being a GROUP-BY key but this is all orthogonal if I understand correctly)

You want to run this:

SELECT [...] SETTINGS time_range_identifier='Timestamp', time_range_buckets='1m,15m,1h,6h,6h,12h,24h';

and you expect the database to do this internally:

SELECT [...] WHERE <time_range_identifier_column> = now - INTERVAL 1 MINUTE;
<ELSE>
SELECT [...] WHERE <time_range_identifier_column> = now - INTERVAL 1 MINUTE;
<ELSE>
SELECT [...] WHERE <time_range_identifier_column> = now - INTERVAL 1 MINUTE;
<ELSE>
[...]

where <ELSE> is some operator that doesn't exist today (I think the logic cannot be expressed elegantly using CTEs and UNION statements).

For a top N query example, imagine we want to display 200 rows over a time range in descending order where the overall time range is 24 hours. First the application breaks up the time range into several "windows" over a 1 minute time range with a limit. The returned rows are evaluated. If the limit was met, no further queries are sent. If the limit was not met, a successive query is issued from the application over the next 15 minutes in the time range with an adjusted limit based on how many rows were returned from the first query. This pattern is repeated with increasingly large time ranges (1m -> 15m -> 1h -> 6h -> 6h -> 12h -> 24h), until either the limit is reached or the search over the entire time range has been executed.

In other words, the UI runs ORDER BY <col> LIMIT <N> queries and the application logic is trying to outsmart the database 😄. We actually optimized such queries recently: #89835 (TODOs are left). The query shape is recently also supported by the query condition cache: #104478 #110507

There is a more specialized optimization for queries with matching GROUP-BY, ORDER BY and sort key: #104859

So if I'd have a choice I'd prefer if you could run a single query over the whole time range

SELECT [...] WHERE <time_range_identifier_column> = now - INTERVAL 24 HOUR;

and let the optimizations do their magic.

[UnamedRus]

So if I'd have a choice I'd prefer if you could run a single query over the whole time range

Well, I think it wouldn't harm if we have setting to execute UNION ALL not in parallel (how it works RN), but sequential.

Still, of course CH should be smart enough to slice ORDER BY range by number of non intersecting ranges (simple is by partition border, more complex to do it by ORDER BY partial ranges) and execute them sequentially (may be with some limited concurrency) Something like staged ConcatTransform

[knudtty]

Hmm more like the application currently does this

SELECT [...] WHERE <time_range_identifier_column> BETWEEN now AND now - INTERVAL 1 MINUTE;

--- if a result is returned early out, otherwise:
SELECT [...] WHERE <time_range_identifier_column> BETWEEN now - INTERVAL 1 MINUTE AND now - INTERVAL 16 MINUTE;

--- if a result is returned early out, otherwise:
SELECT [...] WHERE <time_range_identifier_column> BETWEEN now - INTERVAL 16 MINUTE AND now - INTERVAL 16 MINUTE - INTERVAL 1 HOUR;

where none of the underlying time ranges are overlapping. I'd like the db to do that internally

the application logic is trying to outsmart the database 😄
Yeah that's accurate. We support a large range of query shapes, but many optimizations that would help usually require the ORDER BY to match (usually a subset) of the PK, but often times changing the PK and migrating is so painful that it never happens. There's 2 types of queries here that I have in mind.

The Top N query in particular benefits when the ORDER BY does not match the PK. #89835 does look interesting, but I don't see use_skip_indexes_for_top_n as a session setting in the docs?

Aggregation queries would be pseudo-streamable, which is not currently possible (correct me if I'm wrong). Then users aren't stuck looking at a loading spinner if looking at charts over a 7 day period (pretty common, and with 30 day retention that could be 23% of their overall data). Like @UnamedRus mentioned, a sequential UNION ALL query that streams results back to the client as each branch finishes could solve this, since we intend to query the entire range anyways, but that still puts the requirement on each application to structure their queries into non-overlapping time range branches.

[UnamedRus]

Aggregation queries would be pseudo-streamable, which is not currently possible (correct me if I'm wrong).

No, why wouldn't they?

We already have a bit too silly optimize agg independent partitions.
Again, splitting data in non intersecting ranges (either for ORDER BY or GROUP BY, only complication for agg is that we need to validate than not only range of values is non intersecting, but function on top of them monotonic and result of it non intersecting) can unblock sequential execution or streaming of results to client, and basically work without any client extra knowledge.

TopN is not particularly good answer to that problem, because it still forces us to do index analysis/touch older partitions, which we very likely don't need to look into at all.

[rschu1ze]

SELECT [...] WHERE <time_range_identifier_column> BETWEEN now AND now - INTERVAL 1 MINUTE;

--- if a result is returned early out, otherwise:
SELECT [...] WHERE <time_range_identifier_column> BETWEEN now - INTERVAL 1 MINUTE AND now - INTERVAL 16 MINUTE;

--- if a result is returned early out, otherwise:
SELECT [...] WHERE <time_range_identifier_column> BETWEEN now - INTERVAL 16 MINUTE AND now - INTERVAL 16 MINUTE - INTERVAL 1 HOUR;

Ah, okay. The queries scan disjoint logical time ranges, and if <time_range_identifier_column> is the table sorting key also disjoint physical time ranges. In the latter case (which I assume is true in your scenario), the queries scan non-overlapping data. This means that even if the database gains the proposed special syntax which runs all sub-queries within one query, the database will have no opportunity for additional pruning or caching tricks to begin with, as far as I understand.