主页 / dba / 问题 / 300992
Accepted
tinlyx
Asked: 2021-10-13 01:45:56 +0800 CST

TOAST 存储中的 PostgreSQL 阵列是否具有随机访问时间？

  • 772

这个问题与 PostgreSQL TOAST 存储和 GIS.SE 问题有关：是否应该为 PostGIS 禁用 TOAST 压缩？

基本上，我想知道对于数组元素的随机访问是否有恒定时间复杂度（O（1））的保证？

也就是说，要获得arr[n]，最坏情况下的步数是需要一个常数（即O(1)）还是其他东西（O(log n)等等）？

我问是因为在某些数据形式（如 PostGIS 线或栅格）中，主要数据在逻辑上是一个（坐标）数组。众所周知，一旦数据量超过一定的限制（如 500 个点），此类数据的访问时间可能会非常长。一个可能的原因是这种大小的数据被传输到 TOAST 存储，并且可能会压缩数据（例如使用main存储）。目前尚不清楚 PostgreSQL 如何预测元素的大致位置并仍然提供随机访问时间。

大多数编程语言中数组的访问时间是恒定的（O(1)）。这就是使用数组的意义所在。只是出于好奇：

PostgreSQL 数组是否具有恒定的访问时间？（什么时候什么时候不？）

postgresql array

2 个回答

  1. Best Answer

    它取决于数组元素的数据类型。

    如果是像integeror这样的等宽数据类型uuid，那么通过简单的乘法就可以计算出到数组中的偏移量，复杂度为 O(1)。

    对于可变宽度数据类型，如、text或，每个数组元素都有不同的长度，访问数组中的第 n 个元素意味着跳过前 n-1 个元素，因此复杂度为 O(n)。varcharcharjsonb

    查看src/backend/utils/adt/arrayfuncs.c源代码中的函数。

    typlen您可以通过查看 中的列来判断数据类型是否具有固定长度pg_type。如果为 -1，则类型具有可变长度。

    • 2

  2. 作为记录，从 Postgres 13 开始，由于这种改进，可以访问 TOAST 值的前导字节。引用Postgres 13 的发行说明：

    改进对TOAST值的前导字节的检索（Binguo Bao，Andrey Borodin）

    以前，即使知道只需要一些前导字节，压缩的外联 TOAST 值也会被完全提取。现在，只获取足以产生结果的数据。

    这是有问题的功能：

    https://commitfest.postgresql.org/23/2135/

    但似乎不能应用于数组访问（还）。见劳伦兹的评论。

    • 1

相关问题