[Feature request] Add LTTB downsampling as a built-in table function for the Table Model #18532

Activity

1. DaZuiZui commented on Aug 27, 2026

   

   DaZuiZui

   on Aug 27, 2026

   Contributor

   More actions

   i work it
2. JackieTien97

   assigned

   DaZuiZui

   on Aug 27, 2026
3. DaZuiZui commented on Aug 27, 2026

   

   DaZuiZui

   on Aug 27, 2026

   Contributor

   More actions

   Proposed functional definition

   I suggest defining LTTB as a built-in Table Model table function, with parameter conventions aligned with the existing M4 table function.

   1. SQL syntax

   SELECT *
   FROM LTTB(
     DATA    => TABLE(<query>),
     TIMECOL => DESCRIPTOR(<time_column>),
     N       => <target_count>
   );

   or:

   SELECT *
   FROM LTTB(
     DATA    => TABLE(<query>),
     TIMECOL => DESCRIPTOR(<time_column>),
     SIZE    => <window_size>,
     SLIDE   => <window_step>,
     ORIGIN  => <time_origin>
   );

   DATA and TIMECOL are required. Exactly one execution mode must be selected:

   • Target-count mode: specify N; N is mutually exclusive with SIZE, SLIDE, and ORIGIN.
   • Window/bucket mode: specify SIZE; SLIDE defaults to SIZE, and ORIGIN is valid only for time-based windows.

   2. Parameter semantics

   • DATA: the input table, using the same table-argument semantics as M4.
   • TIMECOL: a descriptor identifying exactly one input time column. The column must have type TIMESTAMP. Input rows must be ordered by this column in ascending order within each partition; the function should enforce or establish this ordering before sampling.
   • N: a positive integer target number of points for each partition and each participant column. The minimum valid value is 3, because LTTB keeps the first point, the last point, and at least one intermediate point.
   • SIZE: the bucket/window size. A duration value selects time-window mode; an integer value selects count-window mode.
   • SLIDE: the window step, defaulting to SIZE. It is valid only with SIZE.
   • ORIGIN: the origin of a time window. It is valid only with duration-based SIZE, not with count windows.

   No explicit COL parameter is needed. As with M4, participant columns should be inferred from the input table: every supported numeric column other than the time column and partition columns is processed independently. Partition columns are preserved and define independent series.

   3. Supported data types

   For the first implementation, participant columns should support INT32, INT64, FLOAT, and DOUBLE. The time column must be TIMESTAMP. Partition columns may retain the data types already supported by Table Model grouping.

   BOOLEAN, TEXT/STRING, binary types, and complex types should be rejected as participant columns in the first version, because triangle-area calculation requires an ordered numeric value. They can be added later if a well-defined conversion policy is agreed.

   4. Target-count mode

   For each partition and participant column:

   1. Build the ordered sequence of eligible (timestamp, value) points.
   2. Ignore rows where that participant value is NULL; NULL rows must not be converted to zero and must not affect averages or triangle areas.
   3. If the number of eligible points is less than or equal to N, return all eligible points without interpolation.
   4. Otherwise apply the standard LTTB algorithm and return exactly N points.
   5. Always preserve the first and last eligible points and return the selected points in ascending timestamp order.

   LTTB is applied independently to every participant column. Consequently, different columns may select different timestamps. The target-count output should follow the count-window shape used by M4:

   window_index, <partition_columns>,
   <column_1>_time, <column_1>,
   <column_2>_time, <column_2>, ...
   

   For target-count mode, window_index is fixed to 0. Selected values are aligned by output position; if columns have different numbers of eligible points, shorter sequences are padded with NULL. Therefore each partition produces at most N rows (and exactly N rows when every participant column has more than N eligible points).

   5. Window/bucket mode

   Window construction must follow the same boundary, inclusiveness, timestamp-origin, and count-window rules as M4.

   For each bucket and participant column, select one representative point using the LTTB triangle:

   • A: the previously selected point (the anchor);
   • B: each non-NULL candidate point in the current bucket;
   • C: the average point of the next bucket (average timestamp and average numeric value over eligible points).

   Select the candidate with the largest triangle area. Ties should be resolved deterministically, for example by the earliest timestamp. Empty buckets produce no participant point. The implementation should define how the first bucket is anchored (the first eligible point in the partition is the initial anchor) and how the final bucket is handled when no next bucket exists (the last eligible point should be retained).

   The output schema follows M4:

   • Time-window mode:

     window_start, window_end, <partition_columns>,
     <column_1>_time, <column_1>,
     <column_2>_time, <column_2>, ...
     

   • Count-window mode:

     window_index, <partition_columns>,
     <column_1>_time, <column_1>,
     <column_2>_time, <column_2>, ...
     

   With SLIDE < SIZE, overlapping windows are expected to follow M4's set semantics. LTTB state must be computed per partition/window; results must not depend on fragment-local input boundaries.

   6. NULL and edge-case behavior

   • NULL participant values are ignored independently per column.
   • A partition with no eligible points for a participant column returns NULL for that column.
   • A partition with one eligible point returns that point; a partition with two eligible points returns both points. This short-series behavior applies even though N >= 3 is required for downsampling.
   • Duplicate timestamps should be handled consistently with the rest of the Table Model (prefer stable input order after sorting); implementations should document this behavior.
   • Numeric overflow in average/area calculations must be avoided by using a sufficiently wide intermediate type, for example DOUBLE.

   7. Validation errors

   The function should reject at least:

   • neither N nor SIZE is specified;
   • both N and SIZE are specified;
   • N < 3 or a non-positive/non-integer N;
   • N combined with SLIDE or ORIGIN;
   • SLIDE or ORIGIN without SIZE;
   • ORIGIN with count-window mode;
   • invalid or non-TIMESTAMP TIMECOL;
   • zero/negative/invalid SIZE or SLIDE;
   • unsupported participant data types.

   Example:

   SELECT *
   FROM LTTB(
     DATA => TABLE(sensor_data),
     TIMECOL => DESCRIPTOR(time),
     N => 500,
     SIZE => 1m
   );

   This must fail because N and SIZE select mutually exclusive modes.

   8. Execution and distributed semantics

   The function should have set semantics, consistent with M4. In target-count mode, bucket boundaries depend on the total number of eligible points, so the implementation may need to buffer each partition, with memory accounting and spill support where required. Window mode can use bounded state by retaining the previous selected point plus current and next buckets.

   LTTB is not generally mergeable. In distributed execution, all rows for a partition must be gathered and ordered before sampling; fragment-local LTTB results cannot simply be concatenated or merged into a globally correct result.

   9. Examples

   Target-count mode:

   SELECT *
   FROM LTTB(
     DATA => TABLE(
       SELECT time, temperature, pressure
       FROM sensor_data
       WHERE device_id = 'd1'
     ),
     TIMECOL => DESCRIPTOR(time),
     N => 500
   );

   Count-window mode:

   SELECT *
   FROM LTTB(
     DATA => TABLE(SELECT time, temperature, pressure FROM sensor_data),
     TIMECOL => DESCRIPTOR(time),
     SIZE => 100,
     SLIDE => 100
   );

   Time-window mode:

   SELECT *
   FROM LTTB(
     DATA => TABLE(SELECT time, temperature, pressure FROM sensor_data),
     TIMECOL => DESCRIPTOR(time),
     SIZE => 1m,
     SLIDE => 1m,
     ORIGIN => TIMESTAMP '2026-01-01 00:00:00'
   );

   10. Suggested tests

   Tests should cover:

   • deterministic output for a known LTTB data set;
   • preservation of first/last points;
   • exactly N points when input has more than N eligible points;
   • returning all points when input has no more than N points;
   • fixed window_index = 0 in target-count mode;
   • multiple participant columns selecting different timestamps;
   • different NULL distributions and empty participant series;
   • partitioned input;
   • count-based and time-based SIZE;
   • default and explicit SLIDE;
   • ORIGIN alignment;
   • overlapping windows;
   • invalid parameter combinations and unsupported types;
   • consistent standalone and distributed results.

   11. Scope for the first version

   The first version should keep the behavior deterministic and aligned with M4, while explicitly documenting the final-bucket/short-series rules and the treatment of overlapping windows. Follow-up work can add more participant types or alternative output layouts if there is a concrete use case.
4. DaZuiZui commented on Aug 27, 2026

   

   DaZuiZui

   on Aug 27, 2026

   Contributor

   More actions

   功能定义建议

   建议将 LTTB 定义为 Table Model 的内置表函数，参数约定与现有 M4 表函数保持一致。

   1. SQL 语法

   SELECT *
   FROM LTTB(
     DATA    => TABLE(<query>),
     TIMECOL => DESCRIPTOR(<time_column>),
     N       => <target_count>
   );

   或：

   SELECT *
   FROM LTTB(
     DATA    => TABLE(<query>),
     TIMECOL => DESCRIPTOR(<time_column>),
     SIZE    => <window_size>,
     SLIDE   => <window_step>,
     ORIGIN  => <time_origin>
   );

   DATA 和 TIMECOL 为必选参数。两种执行模式必须二选一：

   • 目标点数模式：指定 N；N 与 SIZE、SLIDE、ORIGIN 互斥。
   • 窗口/桶模式：指定 SIZE；SLIDE 默认为 SIZE，ORIGIN 仅适用于时间窗口。

   2. 参数含义

   • DATA：输入表，采用与 M4 相同的表参数语义。
   • TIMECOL：唯一时间列的 descriptor。该列必须为 TIMESTAMP 类型。函数应保证每个 partition 内的数据按该列升序排列后再采样。
   • N：每个 partition、每个 participant column 的目标点数。必须为正整数，最小值为 3，因为 LTTB 至少保留首点、尾点和一个中间点。
   • SIZE：桶/窗口大小。duration 值表示时间窗口，整数值表示按行数的窗口。
   • SLIDE：窗口步长，默认等于 SIZE；只有指定 SIZE 时才有效。
   • ORIGIN：时间窗口的起始基准；只适用于 duration 类型的 SIZE，不能用于计数窗口。

   不需要显式的 COL 参数。与 M4 一样，函数应自动识别 participant columns：除时间列和 partition columns 外，所有支持的数值列分别独立处理。partition columns 原样保留，并定义相互独立的时间序列。

   3. 支持的数据类型

   首版 participant columns 建议支持 INT32、INT64、FLOAT、DOUBLE；时间列必须为 TIMESTAMP。partition columns 沿用 Table Model 分组已支持的数据类型。

   BOOLEAN、TEXT/STRING、二进制类型和复杂类型首版应拒绝，因为三角形面积计算需要有序的数值。后续如有明确的转换规则，再扩展其他类型。

   4. 目标点数模式

   对每个 partition、每个 participant column：

   1. 构造按时间升序排列的 (timestamp, value) 点序列。
   2. 独立忽略该列 value 为 NULL 的行；NULL 不能当作 0，也不能参与平均值或三角形面积计算。
   3. 有效点数小于等于 N 时，直接返回全部有效点，不做插值。
   4. 有效点数大于 N 时，执行标准 LTTB，并准确返回 N 个点。
   5. 始终保留首个和最后一个有效点，输出按时间升序排列。

   每个 participant column 独立执行 LTTB，因此不同列可以选择不同的时间戳。目标点数模式的输出结构建议沿用 M4 的计数窗口：

   window_index, <partition_columns>,
   <column_1>_time, <column_1>,
   <column_2>_time, <column_2>, ...
   

   目标点数模式下 window_index 固定为 0。各列按输出位置对齐；若由于 NULL 分布不同导致某列序列较短，则用 NULL 补齐。因此每个 partition 最多输出 N 行；当所有 participant columns 的有效点数都大于 N 时，输出正好为 N 行。

   5. 窗口/桶模式

   窗口构造应遵循 M4 的边界、开闭区间、时间 origin 和计数窗口规则。

   对每个桶、每个 participant column，使用以下 LTTB 三角形选择一个代表点：

   • A：此前已选中的点（锚点）；
   • B：当前桶中的每个非 NULL 候选点；
   • C：下一个桶的平均点（对有效点计算平均时间和平均数值）。

   选择三角形面积最大的候选点；并用确定性的规则处理并列（例如选择时间最早的点）。空桶不产生该 participant column 的点。需要明确首桶的锚点规则（建议使用 partition 中第一个有效点），以及没有下一个桶时的末桶规则（建议保留最后一个有效点）。

   输出结构与 M4 一致：

   • 时间窗口模式：

     window_start, window_end, <partition_columns>,
     <column_1>_time, <column_1>,
     <column_2>_time, <column_2>, ...
     

   • 计数窗口模式：

     window_index, <partition_columns>,
     <column_1>_time, <column_1>,
     <column_2>_time, <column_2>, ...
     

   当 SLIDE < SIZE 时，重叠窗口应遵循 M4 的 set semantics。LTTB 状态必须按 partition/window 计算，不能依赖 fragment 的局部边界。

   6. NULL 与边界行为

   • 每个 participant column 独立忽略 NULL。
   • 某 partition 的某列没有有效点时，该列输出 NULL。
   • 只有一个有效点时返回该点；只有两个有效点时返回两个点。虽然下采样要求 N >= 3，但短序列仍应按此规则返回。
   • 重复时间戳的处理应与 Table Model 其余部分保持一致，建议排序后保持稳定输入顺序，并在文档中明确。
   • 平均值和面积计算使用足够宽的中间类型（例如 DOUBLE），避免数值溢出。

   7. 参数校验

   至少应拒绝以下情况：

   • N 和 SIZE 均未指定；
   • N 和 SIZE 同时指定；
   • N < 3，或 N 不是正整数；
   • N 与 SLIDE 或 ORIGIN 同时使用；
   • 未指定 SIZE 却指定 SLIDE 或 ORIGIN；
   • 计数窗口模式指定 ORIGIN；
   • TIMECOL 无效或不是 TIMESTAMP；
   • SIZE 或 SLIDE 为 0、负数或非法值；
   • participant column 使用不支持的数据类型。

   非法示例：

   SELECT *
   FROM LTTB(
     DATA => TABLE(sensor_data),
     TIMECOL => DESCRIPTOR(time),
     N => 500,
     SIZE => 1m
   );

   该调用应失败，因为 N 和 SIZE 选择了互斥的执行模式。

   8. 执行与分布式语义

   函数应具有与 M4 一致的 set semantics。目标点数模式需要先知道每个 partition 的有效点总数才能确定桶边界，因此可能需要缓存 partition 数据，并配合内存计费及必要的 spill 机制。窗口模式可通过保留前一个已选点以及当前、下一个桶来控制状态规模。

   LTTB 通常不可直接合并。在分布式执行中，必须先收集同一 partition 的全部数据并完成排序，再执行采样；不能简单拼接各 fragment 的局部 LTTB 结果来得到全局正确结果。

   9. 使用示例

   目标点数模式：

   SELECT *
   FROM LTTB(
     DATA => TABLE(
       SELECT time, temperature, pressure
       FROM sensor_data
       WHERE device_id = 'd1'
     ),
     TIMECOL => DESCRIPTOR(time),
     N => 500
   );

   计数窗口模式：

   SELECT *
   FROM LTTB(
     DATA => TABLE(SELECT time, temperature, pressure FROM sensor_data),
     TIMECOL => DESCRIPTOR(time),
     SIZE => 100,
     SLIDE => 100
   );

   时间窗口模式：

   SELECT *
   FROM LTTB(
     DATA => TABLE(SELECT time, temperature, pressure FROM sensor_data),
     TIMECOL => DESCRIPTOR(time),
     SIZE => 1m,
     SLIDE => 1m,
     ORIGIN => TIMESTAMP '2026-01-01 00:00:00'
   );

   10. 建议测试

   建议覆盖：

   • 已知 LTTB 数据集的确定性结果；
   • 首点、尾点保留；
   • 输入有效点多于 N 时准确返回 N 个点；
   • 输入有效点不多于 N 时返回全部点；
   • 目标点数模式下 window_index 固定为 0；
   • 多个 participant columns 选择不同时间戳；
   • 不同 NULL 分布、空序列；
   • partition 输入；
   • 基于计数和基于时间的 SIZE；
   • 默认及显式 SLIDE；
   • ORIGIN 对齐；
   • 重叠窗口；
   • 非法参数组合和不支持的数据类型；
   • 单机与分布式执行结果一致。

   11. 首版范围

   首版应优先保证确定性，并与 M4 的窗口语义保持一致，同时明确末桶、短序列和重叠窗口的处理规则。后续可根据实际用例扩展 participant 数据类型或其他输出布局。
5. DaZuiZui commented on Sep 9, 2026

   

   DaZuiZui

   on Sep 9, 2026

   Contributor

   More actions

   补充说明：为保证方案可实现、可测试，LTTB 需要明确以下规则。

   排序责任：planner 负责在 table function 执行前建立每个 partition 内按 TIMECOL 升序的全局顺序；分布式执行必须先汇聚同一 partition 的全部数据再排序和采样，不能合并 fragment-local 结果；相同 timestamp 保持稳定输入顺序。

   目标点数模式：M<=N 时返回全部有效点；否则保留首尾点，将中间 M-2 个点划分为 N-2 个 bucket，bucket i 使用 [floor(i*(M-2)/(N-2))+1, floor((i+1)*(M-2)/(N-2))+1)；A 为前一 bucket 选中点，B 为当前候选，C 为下一 bucket 平均点，末 bucket 的 C 使用最后一点；面积计算使用 DOUBLE，面积相同时按最早 timestamp、再按稳定输入顺序。

   窗口模式：每个 SIZE 窗口独立执行，采用 M4 的半开区间 [start,start+SIZE)；首 bucket anchor 是该窗口首个有效点，后续 anchor 是前一 bucket 选中点，末 bucket 使用窗口最后有效点作为 C，空 bucket 不改变 anchor。SLIDE<SIZE 时重叠窗口不共享 anchor 或状态，每个窗口重新初始化。

   全 NULL participant 列：NULL 不参与平均和面积；该列无有效值时仍保留 partition/window 输出，该列全部输出 NULL；即使所有 participant 列均为 NULL，也保留窗口/采样行。

   TIMECOL 解析：复用 M4 的 DESCRIPTOR 语法和 analyzer 路径；必须解析为唯一存在的 TIMESTAMP 列，不得是表达式或常量，并从 participant columns 中排除。以上规则用于消除实现歧义。
6. DaZuiZui commented on Sep 9, 2026

   

   DaZuiZui

   on Sep 9, 2026

   Contributor

   More actions

   Follow-up clarification for implementation and testing:

   Ordering: the planner must establish a globally ascending TIMECOL order within each partition before LTTB runs. In distributed execution, gather a partition to one node before sorting and sampling; fragment-local results cannot be merged. Sorting is stable for duplicate timestamps.

   Target-count mode: when M <= N, return all eligible points. Otherwise retain the first and last points and divide the M - 2 intermediate points into N - 2 buckets. Bucket i uses [floor(i*(M-2)/(N-2))+1, floor((i+1)*(M-2)/(N-2))+1). A is the previous selected point, B is a candidate in the current bucket, and C is the average point of the next bucket. For the final bucket, C is the last point. Use DOUBLE for averages and area calculations; break ties by earliest timestamp, then stable input order.

   Window mode: process each SIZE window independently with M4 half-open boundaries [start, start+SIZE). The first anchor is the first eligible point in that window; each following anchor is the previous selection; the final bucket uses the window’s last eligible point as C. Empty buckets do not change the anchor. Overlapping windows (SLIDE < SIZE) must not share anchors or state.

   All-NULL participant columns: ignore NULL values in averages and area calculations. Preserve the partition/window output and emit NULL for a participant column with no eligible values, including when all participant columns are NULL.

   TIMECOL parsing: reuse M4’s DESCRIPTOR syntax and analyzer path. It must resolve to exactly one existing TIMESTAMP column, cannot be an expression or constant, and must be excluded from participant columns.
7. DaZuiZui commented on Sep 24, 2026

   

   DaZuiZui

   on Sep 24, 2026

   Contributor

   More actions

   Implementation PR: #18725