内存算法中的列存储与行存储

4

我熟悉使用列式存储和行式存储以将数据内部持久化到磁盘的方法。我的问题是,对于一个完全在内存中的数据集,并且没有存储到磁盘,行式存储和列式存储是否有很大的区别?

我能想到可能会有影响的因素是:

  • 对于小于8字节的字段,列式存储比行式存储涉及更少的内存访问。
  • 无论内存是否保存回存储器,压缩在列式存储上也更容易(如果不保存回存储器,似乎不太重要?在内存操作中压缩是否很重要?)
  • 可以矢量化操作。
  • 当然,在按行处理结构时,使用行式存储更加容易。

以上几点是否准确,并且还有没有其他因素?鉴于此,使用内存列式存储与行式存储相比,在只读数据集上是否会有显著的性能提高,还是仅有轻微的改进?


3
这完全取决于您对数据进行的操作。根据不同缓存层(Cache Lines/L1/L2/L3/TLB)的效果如何,可以预期差异在x1-x100左右。 - unddoch
如果你的数据集很大,并且在现代CPU上已经达到了内存带宽限制,那么压缩就非常重要。 - David Eisenstat
这个问题对我来说似乎有点太泛泛而谈,很难精确回答。如果您能提供更多关于所进行的分析类型字段数量字段类型(int?float?string?复杂对象?)以及大约有多少(5?50?5000?100万?)的信息,那就太好了。 - Jérôme Richard
对于这种分析,它也取决于您执行分析的方式。您是首先为所有结构执行X,然后执行Y,再执行Z,还是逐个结构执行X、Y和Z,然后为下一个结构执行相同的操作?这可能是一个微不足道的更改 - 或者需要对代码进行深层重构以提高效率。 - Hans Olsson
我假设你已经开始将代码对所需数据的访问抽象化,这样你就可以随意尝试布局并进行基准测试,对吧?特别是基准测试,那是唯一确定的方法,理论只能带你走到这里。 - John Bayko
2个回答

2
我熟悉使用列存储和行存储来将数据库数据持久化到磁盘。我的问题是,如果一个数据集完全在内存中,没有存储到磁盘,那么行与列的方向是否有很大的区别?
很多取决于数据集的大小,每行的内容是什么,你需要如何搜索它,是否要向数据集添加或删除项目等等。
还要考虑CPU和内存架构;你的缓存有多大,缓存行的大小是多少,你的CPU的预取器有多聪明。
对于小于8个字节的字段,列比行访问内存次数更少。
内存不是以寄存器为单位访问的,而是以缓存行为单位访问的。在大多数现代机器上,缓存行大小为64字节。
无论是否在内存中,压缩在列存储中也更容易。
并非完全如此。即使列没有按顺序存储在内存中,你仍然可以压缩/解压缩一列。但这可能会更快。
“压缩是否对内存操作有影响?”
这取决于情况。如果是内存操作,则压缩可能会降低性能,但另一方面,需要存储的数据量较小,因此您将能够将更多数据放入内存中。
“是否可能对操作进行向量化?”
只有在数据按行分组时,加载/存储到内存才可能变慢。
“当然,逐行处理结构体要容易得多。”
使用按行存储的指针很容易使用结构体,但是使用C++可以创建隐藏数据按列存储的类。这需要一些额外的工作,但一旦设置完成,就可能像按行一样容易。
此外,列存储通常用于实体-组件-系统模式(entity-component-system),并且有一些库(如EnTT)使得使用它非常容易。
“这两个都准确吗?还有没有其他的?鉴于此,如果在只读数据集上使用内存中的列存储与行存储相比,是否会有显著的性能提升,还是只有轻微的改进?”
再次强调,这在很大程度上取决于数据集的大小以及您想要如何访问它。如果您经常使用一行中的所有列,则首选逐行存储。如果您经常只使用一列,并且需要访问许多连续行的该列,则最好使用逐列存储。
此外,还有可能采用混合解决方案。您可以将一列单独存储,然后将所有其他列按行存储。
你如何在只读数据集中进行搜索非常重要。它是否会被排序,还是更像一个哈希表?如果是前者,您希望索引尽可能紧凑,并可能像B-tree一样排序,就像Alex Guteniev已经提到的那样。如果它将像哈希映射一样,那么您可能需要逐行查找。

0

对于内存数组,这被称为AoS vs SoA(结构体数组 vs 数组结构体)。

我认为在只读数据库中使用SoA的主要优点是搜索需要访问更小的内存范围。这更加缓存友好,不太容易出现页面错误。

改进的程度取决于您如何使用数据库。通过使用更有针对性的结构(排序数组、B树),可能会有一些更显着的改进。


SoA在只读数据库中的一个优点是搜索需要访问更少的内存,单属性搜索会比多属性搜索更容易估算权衡。 - greybeard

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接