在PostgreSQL中表示稀疏数据

Question

什么是在PostgreSQL中表示稀疏数据矩阵的最佳方法？我看到的两种明显的方法是：

1. 将数据存储在单个表中，每个可想象的特征都有一个单独的列（可能有数百万个），但未使用的特征具有默认值NULL。这在概念上非常简单，但是我知道，在大多数RDMS实现中，由于NULL值通常占用一些空间，因此通常效率很低。然而，我读过一篇文章（不幸的是找不到它的链接了），声称PG不会为NULL值占用数据，使其更适合存储稀疏数据。
2. 创建单独的“行”和“列”表，以及一个中间表来连接它们并在该行中存储该列的值。我认为这是更传统的RDMS解决方案，但与此相关的复杂性和开销更大。

我还发现PostgreDynamic，它声称更好地支持稀疏数据，但我不想为了这个功能而切换整个数据库服务器到PG分支。

还有其他解决方案吗？我应该使用哪一个？

- Cerin

Answer 1

我假设你想到的是从数学角度考虑的稀疏矩阵： http://en.wikipedia.org/wiki/Sparse_matrix（那里描述的存储技术是为了内存存储（快速算术运算），而不是持久性存储（低磁盘使用率）。）

由于通常在客户端而不是服务器端上对这些矩阵执行操作，因此 SQL-ARRAY[] 是最佳选择！

问题是如何利用矩阵的稀疏性？以下是一些调查结果。

设置：

- Postgres 8.4 - 具有400*400个双精度元素的矩阵-->每个矩阵的原始大小为1.28MiB - 33％的非零元素-->每个矩阵的有效大小为427kiB - 平均使用约1000个不同随机填充的矩阵

竞争方法：

- 依靠使用 SET STORAGE MAIN 或 EXTENDED 对列进行自动服务器端压缩。 - 只存储非零元素以及描述矩阵中非零元素位置的位图（bit varying(xx)）。 （一个双精度比一个位大64倍。理论上（忽略开销）如果<=98％为非零，则此方法应该是一种改进;-）。）激活了服务器端压缩。 - 用 NULL 替换 矩阵中的零。 （RDBMS 在存储 NULL 上非常有效。）激活了服务器端压缩。

（使用第二个索引-ARRAY[]对非零元素进行索引不太有前途，因此没有进行测试。）

结果：

- 自动压缩

• 无额外实现工作
• 未减少网络流量
• 最小化压缩开销
• 持久性存储 = 原始大小的39％

- 位图

• 可接受的实现工作
• 网络流量略有减少；取决于稀疏程度
• 持久性存储 = 原始大小的33.9％

- 用 NULL 替换零

• 需要一些实现工作（API 需要知道在构建 INSERT 查询时在 ARRAY[] 中设置 NULL 的位置和方式）
• 网络流量不变
• 持久性存储 = 原始大小的35％

结论：首先使用 EXTENDED/MAIN 存储参数。如果您有一些空闲时间，可以根据您的稀疏级别使用我的测试设置进行数据调查。但效果可能低于您的预期。

我建议始终使用矩阵序列化（例如行主序）加上两个整数列，用于矩阵尺寸 NxM。由于大多数 API 使用文本 SQL，因此您可以节省大量网络流量和客户端内存，而不必使用嵌套的 "ARRAY[ARRAY[..], ARRAY[..], ARRAY[..], ARRAY[..], ..]" ！！！

Tebas

CREATE TABLE _testschema.matrix_dense
(
  matdata double precision[]
);
ALTER TABLE _testschema.matrix_dense ALTER COLUMN matdata SET STORAGE EXTERN;


CREATE TABLE _testschema.matrix_sparse_autocompressed
(
  matdata double precision[]
);

CREATE TABLE _testschema.matrix_sparse_bitmap
(
  matdata double precision[]
  bitmap bit varying(8000000)
);

将相同的矩阵插入所有表格中。具体的数据取决于特定的表。

由于未使用但已分配的页面，请勿在服务器端更改数据。或者可以执行VACUUM操作。

SELECT 
pg_total_relation_size('_testschema.matrix_dense') AS dense, 
pg_total_relation_size('_testschema.matrix_sparse_autocompressed') AS autocompressed, 
pg_total_relation_size('_testschema.matrix_sparse_bitmap') AS bitmap;

- Tebas

Answer 2

几种解决方案可供选择：

1）将您的功能分成通常设置在一起的组，为每个组创建一个表，其具有与主数据的一对一外键关系，在查询时仅连接所需的表。

2）使用EAV反模式，创建一个“功能”表，其中包括主表的外键字段以及字段名和值列，并将功能作为该表中的行而不是主表中的属性进行存储。

3）类似于PostgreDynamic的方式，为主要表中的每个“列”创建一个表（它们使用单独的命名空间用于这些表），并创建函数来简化（以及有效地索引）访问和更新这些表中的数据。

4）在主数据中创建一个使用XML或VARCHAR的列，并在其中存储表示数据的一些结构化文本格式，使用功能性索引对数据进行索引，编写更新数据的函数（如果使用该格式则可以使用XML函数）。

5）使用contrib/hstore模块创建一个hstore类型的列，可容纳键值对，并且可以进行索引和更新。

6）接受大量空字段。

- MkV

---

你还可以创建一个“特征”类型，如featurename VARCHAR、featurevalue VARCHAR（或任何需要的值），并在主表中添加一个类型为feature[]的FEATURES字段。 - MkV

为什么你称EAV为“反模式”？谷歌搜索显示这是EAV的常见描述（通常用于贬低），但似乎没有人解释为什么。在许多情况下，数据库需要存储稀疏数据，例如医学领域，使EAV成为一种合适的“模式”。 - Cerin

它抛弃了数据库的所有优势，包括行级约束和引用完整性，使得很难为单个实体返回单个行。 - MkV

@Cerin：EAV是一种反模式。一开始看起来很迷人，但从长远来看，查询和维护会变成噩梦。我会选择列表中的选项5）或6）。 - user330315

也许这已经被列表解决了，但内置的Postgres JSON/JSONB支持可能已经足够了。 - Colin D

Answer 3

当值为NULL时，它不占用空间。在元组头中的位图中，它将占用一个位，但不管怎样位图都会存在。

然而，系统处理数百万列是无法处理的。理论上最大值略高于一千，但您真的不想走得那么远。

如果您确实需要在单个表中使用这么多列，则需要使用EAV方法，这基本上是您在（2）中所说的。

如果每个条目只有相对较少的键，则建议您查看“hstore”contrib模块，该模块可以非常高效地存储此类数据作为第三个选择。它在即将推出的9.0版本中进一步增强，因此，如果您离生产部署还有些距离，则可能直接查看该版本。但是，在8.4中也非常值得使用。它确实支持一些非常高效的基于索引的查找。绝对值得研究。

- Magnus Hagander

Answer 4

我知道这是一个旧的帖子，但是MadLib为Postgres提供了一种稀疏向量类型，以及几种机器学习和统计方法。

- Brian Dolan