RangeTypes

来自 PostgreSQL wiki
跳转到导航跳转到搜索

简介

注意：这是一个正在进行的草稿。

从数学角度上说，Range 类型是一种间隔类型，也就是说，它们具有绝对的开始和结束，并表示一组点。例如，间隔 [10, 20) 可能表示 10 到 19（方括号表示“包含在内”，圆括号表示“不包含在内”）的所有整数。这些范围类型对许多用途很重要，其中之一是对时间数据进行建模。

当然，范围也可以用两列表示。然而，使用单一数据类型有许多重要的好处

  • 能够使用“包含”或“重叠”之类的谓词执行索引搜索
  • 能够利用排除约束
  • 端点的包含/不包含没有歧义
  • 更容易编写易于理解的查询
  • 更容易处理端点的包含/不包含（仅限于离散范围，见下文），更容易在不改变磁盘上表示的情况下以不同的方式显示

范围和未来工作

还有其他一些有趣的话题稍微超出了该项目的范围（至少在第一轮迭代中）。其中之一是“成组的集合”（http://scottrbailey.wordpress.com/2009/10/06/timespan_sets/），这对于允许对两个不邻接或重叠的范围进行并集非常有用。这增加了复杂性并引入了新的行为和表示，所以为了使此轮项目易于管理，暂时会将其排除在外。

离散与连续范围

这些概念可能有更好的名称。从概念上讲，离散范围是指在某个给定值之后存在“下一个值”概念的类型的范围（例如 INTEGER 范围）。连续范围是指无法定义某个给定值之后“下一个值”的类型的范围（例如 NUMERIC）。

连续范围

连续范围仅要求在其基础类型上有一个全序

连续范围通常在遵循某一惯例时效果最佳，例如“将所有范围表示为闭合-开放”。这对许多应用程序很有用，但灵活性较差

  • 如果你的惯例是闭合-闭合，则你可以表示仅包含一个点的范围，但无法表示相邻的两个范围。
  • 如果你的惯例是其他任何形式，则无法表示仅包含一个点的范围。
  • 如果在一个应用程序中混合惯例，那么最终可能会产生所有四个惯例，而保持一致性也可能是一个挑战。

对于离散类型的连续范围存在一个特别的危险。例如，如果你尝试使 DATE 范围连续，那么将无法确定 DATE 范围[2009-01-01, 2009-01-03]和[2009-01-01, 2009-01-04)是相等的——这肯定会造成混乱和不一致。理论上，这是所有离散类型的一个问题，但在实践中可能不会对某些问题造成影响（例如 FLOAT8 在技术上是离散的，但将其视为连续的可能不会构成实际问题）。

离散范围

离散范围要求全序，并且要求基础类型具有一些“下一个”和“前一个”函数。例如，INTEGER 可以用作离散范围，因为“+1”和“-1”分别是“下一个”和“前一个”函数。

通过指定一个颗粒度，可以使 NUMERIC 等类型用作离散范围。例如，指定一个 1.0 的颗粒度将使数字范围等价于整数范围（但领域更大，没有 32 或 64 位限制）。除了下一个和前一个函数外，还有用于存储和操作颗粒度的加法、减法、乘法和除法函数，这也是很有用的。

浮点类型（包括浮点时间戳）会导致离散范围出现问题，因为颗粒度是可变宽度的。从理论上讲，浮点时间戳是离散的，并且有一个定义明确的“下一个”和“前一个”函数；但是没有任何有用的函数来确定在两个浮点数之间存在多少个离散点。此外，通常更容易产生混乱。

任何离散范围都可以采用任何可能的惯例来显示：闭合-闭合、闭合-开放、开放-闭合或开放-开放。这很有用，但也提出了“默认输出应该是什么？”的问题。

此外，很多时序数据库文献仅讨论离散范围[1]。

总结

我认为我们无法避开对离散范围和连续范围的支持。仅支持其中一种可能产生的问题似乎太多。

话虽如此，我们可能需要一种方法来引导用户避开这些陷阱，并使用明智的类型定义。此处表达了一些此类方面的担忧

概念

Date、Darwen 和 Lorentzos 合著的“时序数据和关系模型”一书为很多此类概念提供了基础。

分量类型

在构建范围时，有若干相关类型

  • RTYPE 这是范围本身的类型，例如，“PERIOD”可能是 TIMESTAMP 的范围。
  • STYPE 这是构成范围的类型。对于“PERIOD”范围类型，STYPE 是 TIMESTAMP。
  • DTYPE 这是表示 STYPE 的相对值的类型，即减去 STYPE 类型两个值时得到的结果类型。对于“PERIOD”范围类型，DTYPE 为 INTERVAL。

特殊值

范围可能为 NULL，就像任何其他值一样；范围的分量也可能为 NULL。范围分量为 NULL 的语义留给读者作为练习（暂时）。

范围分量也可能是特殊值“+/- 无穷大”。

范围还可能为空，这意味着它根本不包含任何点。空范围用字符串“EMPTY”表示。此外，你可以通过对起止点使用相同的值，并将包含性指定为“[)”或“()”，来构建空范围。所有空范围都是相等的，例如“[10, 10)”等于“(20, 20]”。

一些 STYPE，例如TIMESTAMP，允许“无穷大”等值。范围类型不会专门处理这些值，它们的行为与子类型中的相同。但是，TIMESTAMP 类型中的“无穷大”将小于特殊范围边界“+ 无穷大”。

通用 API

函数

empty(RTYPE) -> BOOL                       -- Is the range empty?
lower_bound(RTYPE) -> STYPE                -- Lower bound of range
upper_bound(RTYPE) -> STYPE                -- Upper bound of range
lb_null(RTYPE) -> BOOL                     -- Is the lower bound null?
ub_null(RTYPE) -> BOOL                     -- Is the upper bound null?
lb_inf(RTYPE) -> BOOL                      -- Is the lower bound negative infinity?
ub_inf(RTYPE) -> BOOL                      -- Is the upper bound infinity?

length(RTYPE) -> DTYPE                     -- Size of the range.
range_offset(STYPE, RTYPE) -> DTYPE        -- Offset of LHS within the range on the RHS; error if empty.
range_offset(RTYPE, STYPE) -> DTYPE        -- Offset of RHS within the range on the LHS; error if empty.



contains(RTYPE, STYPE) -> BOOL             -- Contains?
contained_by(RTYPE, STYPE) -> BOOL         -- Contained by?

distance(RTYPE, RTYPE) -> DTYPE            -- If RHS is strictly after the LHS, then the distance between end of LHS and
                                              start of RHS. If LHS is strictly after the RHS, then the distance between
                                              the end of RHS and the start of LHS. Otherwise, an exception is raised.
                                              Error if either are empty.

equals(RTYPE, RTYPE) -> BOOL               -- Equals? All empty intervals are equal.
nequals(RTYPE, RTYPE) -> BOOL              -- Not equals?
contains(RTYPE, RTYPE) -> BOOL             -- Contains?
contained_by(RTYPE, RTYPE) -> BOOL         -- Contained by?
before(RTYPE, RTYPE) -> BOOL               -- Strictly left of? Error if either are empty.
after(RTYPE, RTYPE) -> BOOL                -- Strictly right of? Error if either are empty.
adjacent(RTYPE, RTYPE) -> BOOL             -- Adjacent? That is, are they touching but not overlapping, e.g. "[10, 20)"
                                              and "[20, 21)"? Error if either are empty.
overlaps(RTYPE, RTYPE) -> BOOL             -- Overlaps?
overleft(RTYPE, RTYPE) -> BOOL             -- Over-left? (LHS's end point is less than or equal to RHS's end point). Error if either are empty.
overright(RTYPE, RTYPE) -> BOOL            -- Over-right? (LHS's start point is greater that or equal to RHS's start point). Error if either are empty.

range_union(RTYPE, RTYPE) -> RTYPE         -- Union of two ranges. Error if the ranges are neither adjacent nor overlapping.
range_intersect(RTYPE, RTYPE) -> RTYPE     -- Intersection of two ranges.
minus(RTYPE, RTYPE) -> RTYPE               -- Difference of two ranges. Error if the result is not a single range.

运算符

?  (RTYPE) -> BOOL          -- empty

=   (RTYPE, RTYPE) -> BOOL  -- equals
!=  (RTYPE, RTYPE) -> BOOL  -- nequals
<>  (RTYPE, RTYPE) -> BOOL  -- nequals
&&  (RTYPE, RTYPE) -> BOOL  -- overlaps
@>  (RTYPE, RTYPE) -> BOOL  -- contains
<@  (RTYPE, RTYPE) -> BOOL  -- contained_by
<<  (RTYPE, RTYPE) -> BOOL  -- before
>>  (RTYPE, RTYPE) -> BOOL  -- after
&<  (RTYPE, RTYPE) -> BOOL  -- overleft
&>  (RTYPE, RTYPE) -> BOOL  -- overright
-|- (RTYPE, RTYPE) -> BOOL  -- adjacent

@>  (RTYPE, STYPE) -> BOOL  -- contains
<@  (STYPE, RTYPE) -> BOOL  -- contained_by

#   (RTYPE) -> DTYPE        -- length

<-> (RTPYE, RTYPE) -> DTYPE -- distance

&   (RTYPE, RTYPE) -> RTYPE -- rintersect
|   (RTYPE, RTYPE) -> RTYPE -- runion
*   (RTYPE, RTYPE) -> RTYPE -- rintersect
+   (RTYPE, RTYPE) -> RTYPE -- runion
-   (RTYPE, RTYPE) -> RTYPE -- minus

GiST 索引策略

GiST opclass 将使用范围类型本身作为 GiST 谓词。picksplit 函数可以与“seg”contrib 模块中的函数相同。

定义范围类型

对于定义新范围类型和关联 DDL，有两种可能的范围类型框架实现。我们需要选择一种方法。

方法 1

这是最直接的方法。其目的是让 PostgreSQL 管理输入、输出和表示形式；并理解离散范围和连续范围之间的区别。

例如，对于离散范围类型，你需要指定类似内容

 CREATE TYPE <name> AS RANGE
 (
   SUBTYPE = <stype>,
   DTYPE   = <dtype>,
   GRANULE = <granule>,
   CMPFUNC = <cmpfunc>,
   ADDFUNC = <addfunc>,
   SUBFUNC = <subfunc>,
   MULFUNC = <mulfunc>,
   DIVFUNC = <divfunc>
 );

使用“下一个”和“上一个”功能代替“颗粒”，可以达到相同的效果。如果使用表示中的颗粒，例如<start, num_granules>，则仅需要乘法和除法。如果使用开始和结束点，则乘法和除法是非必须的。

可以像这样指定连续范围

 CREATE TYPE <name> AS RANGE
 (
   SUBTYPE = <stype>,
   DTYPE   = <dtype>,
   CMPFUNC = <cmpfunc>,
   ADDFUNC = <addfunc>,
   SUBFUNC = <subfunc>
 );

表示

方法 2

此方法更接近于类型接口，表示自身更封装，且对 PostgreSQL 隐藏。这样 PostgreSQL 就能够提供前述的通用 API（包括 GiST opclass），并且还能够了解范围类型以及对它们的操作方式（可以将其用于语法糖等）。

在此方法中，用户指定范围的输入、输出和表示方式。然后 API 只需要知道如何访问下限、上限、包容性/排他性，并且需要一个比较器来比较基本类型。例如

 CREATE TYPE <name> AS RANGE
 (
   STYPE       = <stype>,
   DTYPE       = <dtype>,
   CONSTRUCTOR = <constructor_func>,
   LBOUND      = <get_lbound_func>,
   UBOUND      = <get_ubound_func>,
   MIN         = <get_min_func>,
   MAX         = <get_max_func>,
   FLAGS       = <get_flags>,        -- null/inf bounds
   STYPE_CMP   = <stype_cmp_func>,
   WIDTH       = <get_width_func>,   -- for GiST penalty function
   [INPUT]     = <input_func>,
   [OUTPUT]    = <output_func>
 );

优点是它避免了 PostgreSQL 理解离散范围和连续范围之间的差别的复杂性。

缺点是在编译时稍微难以检查是否正常，并且在定义类型时会给用户带来更大的负担。

参考

  • Date、Darwen、Lorentzos：《时间数据和关系模型》第 344-47 页。
取自“https://wiki.postgresql.ac.cn/index.php?title=RangeTypes&oldid=16545”