时间戳

首页 > 解决方案 > 具有排序属性的 KDB 表的插入操作复杂度

database - 具有排序属性的 KDB 表的插入操作复杂度

问题描述

假设有一个包含 A、B 和 C 列的 KDB 表，并且它在 A 列上排序。我想了解将记录插入该表的复杂性（假设它必须保持表在 A 上排序）。

  1. 如果保证对该表的插入按 A 的排序顺序进行，它会有所帮助（就复杂性而言）。这意味着在任何时候 t2>t1, A(t2)>A(t1) ？
  2. 有没有办法可以利用上述事实 (t2>t1 => A(t2)>A(t1)) 并优化查询，甚至无需在 A 上应用排序属性？
  3. 我知道有一种方法可以对列执行二进制搜索，但我主要想知道是否有一种方法可以告诉查询计划程序“假设”列已排序（实际上没有排序属性，因为我想避免与之相关的插入复杂性）并相应地执行查询？

标签： databaseoptimizationkdbinsertion

解决方案

我的想法（其中一些只是意见，因为我们无法确切地看到 kdb 在幕后做了什么）：

A. 澄清一下 - kdb 本身不会“保持表格排序”。无论如何，Kdb 都会插入数据，由用户来确保表格保持排序。

B. 我认为您不应该担心 kdb 插入的开销/复杂性 - 我估计这insert是所有 kdb 中最优化的操作之一

C. 无论该列是否具有属性，kdb 都会以任何一种方式进行插入，并且可能只有在插入之后才会检查该属性是否保留。这将是一个高度优化的检查。s#将在非排序插入时丢失。u#将在非唯一插入上丢失。p#任何插入都会丢失，因为它通常用于静态/磁盘数据。

D. 唯一会产生不可忽略的插入成本/复杂性的情况是在维护分组属性的情况下，因为g#始终保留在插入时，并且存在更新隐藏哈希表的开销。但即便如此，这种开销也不会影响在一天内有数十亿次插入的大容量 RDB。

这些都不是实际的硬数字或大 O/复杂性信息，但根据我的经验，大 O/复杂性与查找具有属性的数据更相关，而不是属性/数据的插入/维护。根据我的经验，插入从来不是一个问题。

要回答您的实际问题：

  1. 正如我在 (A) 中所避免的那样，如果您想要一个已排序的属性并且想要保留它，那么您必须确保数据按排序顺序插入

  2. 如果没有属性，那么 kdb 会像对待任何其他向量一样对待列/向量——它每次都会扫描整个向量，因为没有标志/属性告诉它使用优化。唯一的例外是 as-of 连接（或窗口连接）aj/wj，其中ajon say`sym`time假设时间在 sym 中排序，而没有明确s#的时间属性。

  3. 除了aj/wj上面的例外，不，如果你想利用数据的排序特性来加速查询，那么你需要一个s#属性。当然，除非您使用不同的属性，例如p#我前面提到的有自己的警告

推荐阅读