24

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

  1. 将数据存储在一个表中,每个可能的功能(可能数百万)都有一个单独的列,但对于未使用的功能,默认值为 NULL。这在概念上非常简单,但我知道对于大多数 RDMS 实现来说,这通常是非常低效的,因为 NULL 值通常会占用一些空间。但是,我读了一篇文章(不幸的是找不到它的链接)声称 PG 不占用 NULL 值的数据,使其更适合存储稀疏数据。

  2. 创建单独的“行”和“列”表,以及一个中间表来链接它们并在该行存储列的值。我相信这是更传统的 RDMS 解决方案,但与之相关的复杂性和开销更大。

我还发现了 PostgreDynamic,它声称可以更好地支持稀疏数据,但我不想仅仅为了这个特性而将我的整个数据库服务器切换到 PG 分支。

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

4

4 回答 4

17

我假设您正在考虑数学上下文中的稀疏矩阵: http ://en.wikipedia.org/wiki/Sparse_matrix (那里描述的存储技术用于内存存储(快速算术运算),而不是持久存储(低磁盘用法)。)

因为通常在客户端而不是在服务器端对这个矩阵进行操作,所以 SQL-ARRAY[] 是最好的选择!

问题是如何利用矩阵的稀疏性?这里是一些调查的结果。

设置:

  • Postgres 8.4
  • 具有双精度(8 字节)的 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[..]、..]”节省了大量网络流量和客户端内存!!!

特巴斯


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)
);

将相同的矩阵插入所有表中。具体数据以某表为准。由于未使用但已分配的页面,请勿更改服务器端的数据。或者做一个真空。

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;
于 2011-04-28T11:50:30.297 回答
9

脑海中浮现出一些解决方案,

1)将您的特征分成通常设置在一起的组,为每个组创建一个与主数据具有一对一外键关系的表,仅在查询时加入您需要的表

2) 使用 EAV 反模式,使用主表中的外键字段以及字段名和值列创建“特征”表,并将特征作为行存储在该表中,而不是作为属性存储在主表中桌子

3)与 PostgreDynamic 的做法类似,为主表中的每个“列”创建一个表(它们为这些表使用单独的命名空间),并创建函数来简化(以及有效地索引)访问和更新数据那些桌子

4)使用 XML 或 VARCHAR 在您的主数据中创建一个列,并在其中存储一些结构化的文本格式来表示您的数据,使用功能索引在数据上创建索引,编写函数来更新数据(或者使用 XML 函数,如果你正在使用该格式)

5)使用contrib/hstore模块创建一个hstore类型的列,可以保存键值对,并且可以被索引和更新

6)生活在很多空旷的地方

于 2010-04-08T11:25:55.617 回答
3

NULL 值在为 NULL 时不会占用空间。它会在元组标头的位图中占用一位,但无论如何都会存在。

但是,系统无法处理数百万列,周期。IIRC 的理论最大值是一千多一点,但你真的不想走那么远。

如果你真的需要那么多,在一个表中,你需要使用 EAV 方法,这基本上就是你在 (2) 中所说的。

如果每个条目只有相对较少的键,我建议您查看“hstore”contrib 模块,它可以让您非常有效地存储此类数据,作为第三种选择。它在即将发布的 9.0 版本中得到了进一步增强,因此如果您离生产部署有点远,您可能想直接查看那个版本。但是,在 8.4 中也很值得。它确实支持一些非常有效的基于索引的查找。绝对值得研究。

于 2010-04-08T11:00:03.623 回答
2

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

于 2015-01-20T22:44:19.333 回答