Dremel

Question

阅读 Interactive Analysis of Web-Scale Datasets 论文，我碰到了重复和定义级别的概念。
虽然我理解这两个的必要性，但为了能够消除歧义，它为每个值附加了一个重复和定义级别。

我不清楚他们是如何计算水平的...

如图所示：

上面写着：

Consider ﬁeld Code in Figure 2. It occurs three times in r1. Occurrences ‘en-us’ and ‘en’ are inside the ﬁrst Name, while ’en-gb’ is in the third Name. To disambiguate these occurrences, we attach a repetition level to each value. It tells us at what repeated ﬁeld in the ﬁeld’s path the value has repeated.

The ﬁeld path Name.Language.Code contains two repeated ﬁelds, Name and Language. Hence, the repetition level of Code ranges between 0 and 2; level 0 denotes the start of a new record. Now suppose we are scanning record r1 top down. When we encounter ‘en-us’, we have not seen any repeated ﬁelds, i.e., the repetition level is 0. When we see ‘en’, ﬁeld Language has repeated, so the repetitionlevelis2.

我实在想不通，r1 中的 Name.Language.Code 有 en-us 和 en 值。而第一个 r = 0 和第二个 r = 2 是因为重复了两个定义吗？（语言和代码）？

如果是：

Name
    Language
       Code: en-us
Name 
    Language
        Code: en
Name
    Language
        Code: en-gb

会是吗？

0 2
1 2
2 2

Deﬁnition levels. Each value of a ﬁeld with path p, esp. every NULL, has a deﬁnition level specifying how many ﬁelds in p that could be undeﬁned (because they are optional or repeated) are actually present in record.

那为什么清晰度是2级呢？路径 Name.Language 不是包含两个字段 Code 和 Country 其中只有 1 是 optional\repeated 吗？

Answer 1

Dremel 条带化算法绝非易事。

回答你的第一个问题：

en-us 的重复级别为 0，因为它是记录中第一次出现 name.language.code 路径。
en 的重复级别为 2，因为重复发生在级别 2（语言标记）。

回答你的第二个问题，记录如下，

DocId: 20
Name
  Language
    Code: en-us
Name 
  Language
    Code: en
Name
  Language
    Code: en-gb

name.language.code 的条目将是

en-us 0 2
en    1 2
en-gb 1 2

解释：

定义级别始终为二级，因为存在两个可选标签 name 和 language。
en-us 的重复级别为零，因为它是记录中的第一个 name.language.code。
en 和 en-gb 的重复级别为 1，因为重复发生在 name 标记（级别 1）。

Answer 2

Adelin asked for some more random examples to make things clearer. To expand on user152468的回答：

DocId: 20
Name
  Language
    Code: en-us
Name 
  Language
    Code: en
Name
  Language
    Code: en-gb
  Language
    Code: zh
Name
  url: 'https://A'

将是：

Code	Repetition	Definition
en-us	0	2
en	1	2
en-gb	1	2
zh	2	2
NULL	1	1

对于zh，定义层级与前三码一样为2，但其重复层级为2。重复级别不是一个项目被重复的次数，它是树中被重复的级别。重复级别为 2，因为 Name.Language 重复（深度为 2）。 en 和 en-gb 的重复级别为 1，因为正在重复 Name（而不是 Name.Language）。

table中最后的NULL指的是https://AName中缺失的Name.Language.Code。重复级别为 1，因为 Name 是重复级别。定义级别为 1 因为只定义了 1 个可选级别 (Name).

定义级别

在尝试理解定义级别时，了解字段是必填还是可选（可为空或重复）很重要。在 Dremel 论文示例中，Code 是必需的，Country 可以为空。我为这个例子苦苦挣扎了一段时间：

DocId: 20
Name
  Language
    Code: en-us
    Country: us

Code	Repetition	Definition
en-us	0	2

Country	Repetition	Definition
us	0	3

en-us 的定义级别为 2，因为定义了 2 个 optional 字段：Name 和 Language。代码本身是必需的，因此不计入定义级别。

us定义级别为3，因为路径中有3个可选字段：Name、Language、Country.

所以回答原来的问题：

Why is then the definition level is 2? Isn't the path Name.Language contain two fields Code and Country where only 1 is optional\repeated?

定义级别不表示 Language 记录中有多少个可选字段。它传达了在 path 中定义了多少个可选字段。当一切都被定义时似乎没有必要，但当有 NULL 值时它很有用。

如果语言记录有更多可选字段（国家、方向和脚本）：

DocId: 20
Name
  Language
    Code (required): en-us
    Country (nullable): us
    Direction (nullable): right_to_left
    Script (nullable): Latin

Code和Country的定义级别不会改变：

Path	Value	Definition
`Name.Language.Code`	en-us	2
`Name.Language.Country`	us	3
`Name.Language.Direction`	right_to_left	3
`Name.Language.Script`	Latin	3

Dremel - 重复和清晰度级别

Dremel - repetition and definition level

algorithm

data-structures

dataset

parquet

定义级别