[
https://issues.apache.org/jira/browse/DRILL-5546?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16036141#comment-16036141
]
Paul Rogers edited comment on DRILL-5546 at 6/5/17 3:57 PM:
------------------------------------------------------------
I believe we are saying basically the same thing. To be certain, [watch out,
we're gonna try some theory|https://store.xkcd.com/products/try-science].
h3. Basics
We'll need some terminology, defined in the usual way:
* (a, b, c) is a set that contains a, b, c
* \{a:b} is a map from a to b
* \[a, b, c] is an ordered list of a, b, c, where each element has an index i =
0, 1, 2...
* empty = () or {} or \[] is the empty collection (of the proper type)
* null = SQL null: we don't know what the value is
* ∧ = Java, C, etc. null: we know the value, and it is nothing
Drill is, at its core, relational. A relation R can be defined as:
{{R = (S, T)}}
Where:
* S is the schema
* T is a set of tuples (t ~1~, t ~2~, t ~3~) (AKA a table)
{{S = (C, N)}}
Where:
* C is the list of column schemas:
{{C = \[ c ~0~, c ~1~, c ~2~, ...]}}
{{c = (name, type)}}
And:
* N is a map from name to column index:
{{N = \{name : i\} }} where i the index of column c ∈ C
Drill defines the idea of _compatible_ schemas. Two schemas are compatible if
we redefine the schema as a set of columns:
{{S’ = (C ~0~, C ~1~, …)}}
Two schemas are compatible iff the column sets are identical (same name and
type for each column). This is a bit more forgiving than the traditional
relational model which requires that the ordered list of column schemas be
identical. Let's assume this rule as we discuss schema below.
We'll also need the idea of _cardinality_:
{{\|S| = n}}
Says that the cardinality (number of items) in S is _n_. Later, well just use
_n_ to mean a schema (or relation or whatever) that has n items.
h3. Relations and Multi-Relations
A relation can be:
{{R : ∧}} (programming null) -- the relation simply does not exist.
{{ | (0,0)}} -- the trivial relation of no columns and (by
definition), no rows.
{{ | (s,0)}} -- a relation with some schema s, |s| ≠ 0, and no rows
{{ | (s,n)}} -- a "normal" relation with schema and n tuples (rows)
of data, \|s| ≠ 0, n ≠ 0
It is helpful to remember some basic relational algebra:
{{R(s,0) ⋃ R(s,n) = R(s,n)}}
{{R(s,n) ⋃ R(s,m) = R(s,n+m)}}
Drill works not just with relations R, but also "multi-relations" (to make up a
term). That is, each schema change in Drill introduces a new relation, so that
the whole result set from a query is a series of relations. Let's define a
"multi-reation" M using semi-BNF as:
{{M : ∧}} -- undefined result set
{{ | R(0,0)}} -- trivial result set
{{ | R(s,0)}} - empty result set, \|s| ≠ 0
{{ | R(s,n)}} -- normal, single result set, n ≠ 0
{{ | R ~1~(s ~1~,n), R ~1~(s ~2~,m), ...}} -- multi-relation if s
~i~ ≠ s ~j~
Normally when we say multi-relation, we mean the last case: two or more
relations with distinct schemas. The condition above says that to adjacent
relations R ~i~ and R ~j~ must have distinct schema (or by the rules above, two
relations with the same schema just collapse into a single relation with that
schema. A schema can repeat, but a different schema must occur between
repetitions.)
h3. Multi-Relations in Drill
Now let's get to Drill. Drill uses the term "schema change" to mean the
transition from s ~i~ to s ~j~, s ~i~ ≠ s ~j~.
The essence of the proposal here, as I understand it, is to update the
implementation to fully support the first three definitions of a multi-relation
(undefined, trivial and empty), assuming that Drill already supports the other
two definitions (single relation and multi-relation.)
In Drill, relations are broken into batches, which are, themselves, just
relations. Thus a batch, B, can be:
{{B : ∧}} -- undefined result set)
{{ | R(0,0)}} -- trivial batch
{{ | R(s,0)}} -- empty batch set, |s| ≠ 0
{{ | R(s,n)}} -- normal batch, |s| ≠ 0, n ≠ 0
And the whole result set D (for Drill) is an ordered list of batches:
{{D = \[B ~1~, B ~2~, ..., B ~n~]}}
Where
{{B ~i~ = (s ~i~, t ~i~)}}
As noted above, if adjacent batches have the same schema, then they are just
sub-relations within a single larger (logical) relation. But, if the schemas
differ, then the adjacent batches are the last and first of two distinct
relations within a larger (logical) multi-relation. Said another way:
{{D = R ~1~, R ~2~}}
{{R ~i~ = B ~i,1~, B ~i,2~, ...}}
To clarify, let’s visualize the schema changes as ∆~i~:
{{D = \[B ~0~(s ~0~,t), B ~1~(s ~0~,t), … ∆~1~, B ~i~(s ~1~,t), B ~i+1~(s
~1~,t), …]}}
The above sequence can describe any series of batches. As I understand the
proposal, we want to put some constraints on the sequence.
h3. Results of a Drill Query
Let’s start by defining how should present the multi-relation to the client.
The client also receives batches, but, following the rules in the proposal, we
want to constrain the output:
{{D ~e~ : B(0,0)}} -- Null result
{{ | B(s,0)}} -- Empty result
{{ | B(s,n)\+}} -- “Classic” O/JDBC result
{{ | (B(s ~i~,n)\+)\+}} -- Multi-relation result
(Here, the parenthesis take on their regex/BNF meaning of grouping.)
That is the output of a Drill query is:
* A single trivial batch (zero columns, zero rows)
* A single empty batch (schema, but no data)
* One or more non-empty batches
For the non-empty case, we end up with two cases:
* A single relation (O/JDBC compatible)
* A multi-relation
h3. Drill Internals
Internally, we might want to allow any pattern of batches (include empty or
null); Drill operators do the necessary conversion:
{{D ~i~ = \[B\+, (∆, B\+)\+]}}
We want to remove empty batches where possible to convert the internal
multi-relation to the external one. First, let’s define an empty batch:
{{empty-batch : ∧}} -- undefined result set
{{ | R(0,0)}} -- trivial result set
{{ | R(s,0)}} -- empty result set, |s| ≠ 0
We can define some harmless extensions to the normal rules for unions of
relations:
{{∧ ⋃ R = R}}, for any relation R
{{R(0,0) ⋃ R = R}}, for {{R ≠ ∧}}
{{R(c,0) ⋃ R = R}}, for {{R ≠ ∧, R(0,0)}}
These rules define a “hierarchy of emptiness” to deal with adjacent empty
batches. The result of the above rules are that we can remove empty batches
from a Drill result set as long as there are adjacent non-empty batches. But,
suppose the (internal to Drill) result set has only one empty batch, B ~1~,
then the external (visible to client) result set , D ~e~, is:
{{D ~e~ = R(0,0)}} if {{B ~1~ = ∧}} or {{B ~1~ = R(0,0)}}
{{D ~e~ = R(c,0)}} if {{B ~1~ = R(c,0)}}
Otherwise, according to what we said earlier, since the internal result set has
at least one non-empty batch, then the external result set will be non-empty.
This is true because we can (indeed, should) remove empt batches internal to
Drill using the rules noted above and explained in this proposal.
h3. The Drill Iterator Protocol
Finally, we can put all this together. The proposal focuses on Drill’s
Volcano-based iterator protocol. The iterator protocol labels batches with one
of three iterator outcomes, as defined by an enum E:
{{e(s,t) ∈ E}}
{{E : NONE(∧)}}
{{ | OK_NEW_SCHEMA(s,t)}}
{{ | OK(s,t)}}
That is, each iterator outcome labels a batch and so carries a schema and data
set. NONE is a special case as it carries an undefined batch. This definition
lets us map the iterator protocol directly to a slightly modified version of
the multi-relation sequence shown earlier:
{{D = \[∆ ~0~, B ~0~(s ~0~,t), B ~1~(s ~0~,t), … ∆ ~1~, B ~i~(s ~1~,t), B
~i+1~(s ~1~,t), … ∧]}}
{{OK_NEW_SCHEMA = \[∆, B]}}
{{OK = \[B]}}
{{NONE = ∧}}
Now we can define the iterator protocol:
{{protocol : (OK_NEW_SCHEMA OK\*)\* NONE}}
The “fast NONE” path is simply an empty sequence of {{(OK_NEW_SCHEMA OK\*)\*}}
terms.
h3. Conclusion
The proposal for this ticket says that operators should handle the empty
batches. The above suggests *why* the operators should handle them. The best
solution for *how* to handle them is so modify the "inner next" code that calls
a child operator; have that code "compress out" empty batches if followed by a
non-empty batch.
This note suggests that we look at empty batches (in all three forms) as a
natural part of Drill's multi-relation model. Rather than treating them as
special cases, empty batches should be defined as a normal part of Drill's
internal protocol.
A separate proposal (part of DRILL-5211) will suggest that the scanner use the
above rules to compress out empty batches that emerge from a variety of special
cases with readers.
was (Author: paul-rogers):
I believe we are saying basically the same thing. To be certain, [watch out,
we're gonna try some theory|https://store.xkcd.com/products/try-science].
h3. Basics
We'll need some terminology, defined in the usual way:
* (a, b, c) is a set that contains a, b, c
* \{a:b} is a map from a to b
* \[a, b, c] is an ordered list of a, b, c, where each element has an index i =
0, 1, 2...
* empty = () or {} or \[] is the empty collection (of the proper type)
* null = SQL null: we don't know what the value is
* ∧ = Java, C, etc. null: we know the value, and it is nothing
Drill is, at its core, relational. A relation R can be defined as:
{{R = (S, T)}}
Where:
* S is the schema
* T is a set of tuples (t ~1~, t ~2~, t ~3~) (AKA a table)
{{S = (C, N)}}
Where:
* C is the list of column schemas:
{{C = \[ c ~0~, c ~1~, c ~2~, ...]}}
{{c = (name, type)}}
And:
* N is a map from name to column index:
{{N = \{name : i\} }} where i the index of column c ∈ C
Drill defines the idea of _compatible_ schemas. Two schemas are compatible if
we redefine the schema as a set of columns:
{{S’ = (C ~0~, C ~1~, …)}}
Two schemas are compatible iff the column sets are identical (same name and
type for each column). This is a bit more forgiving than the traditional
relational model which requires that the ordered list of column schemas be
identical. Let's assume this rule as we discuss schema below.
We'll also need the idea of _cardinality_:
{{\|S| = n}}
Says that the cardinality (number of items) in S is _n_. Later, well just use
_n_ to mean a schema (or relation or whatever) that has n items.
h3. Relations and Multi-Relations
A relation can be:
{{R : ∧}} (programming null) -- the relation simply does not exist.
{{ | (0,0)}} -- the trivial relation of no columns and (by
definition), no rows.
{{ | (s,0)}} -- a relation with some schema s, |s| ≠ 0, and no rows
{{ | (s,n)}} -- a "normal" relation with schema and n tuples (rows)
of data, \|s| ≠ 0, n ≠ 0
It is helpful to remember some basic relational algebra:
{{R(s,0) ⋃ R(s,n) = R(s,n)}}
{{R(s,n) ⋃ R(s,m) = R(s,n+m)}}
Drill works not just with relations R, but also "multi-relations" M. That is, a
multi-relation (the entire result set from a single query) can defined (using
semi-BNF) as:
{{M : ∧}} -- undefined result set
{{ | R(0,0)}} -- trivial result set
{{ | R(s,0)}} - empty result set, \|s| ≠ 0
{{ | R(s,n)}} -- normal, single result set, n ≠ 0
{{ | R ~1~(s ~1~,n), R ~1~(s ~2~,m), ...}} -- multi-relation if s
~i~ ≠ s ~j~
Normally when we say multi-relation, we mean the last case: two or more
relations with distinct schemas. The condition above says that to adjacent
relations R ~i~ and R ~j~ must have distinct schema (or by the rules above, two
relations with the same schema just collapse into a single relation with that
schema. A schema can repeat, but a different schema must occur between
repetitions.)
h3. Multi-Relations in Drill
Now let's get to Drill. Drill uses the term "schema change" to mean the
transition from s ~i~ to s ~j~, s ~i~ ≠ s ~j~.
The essence of the proposal here, as I understand it, is to update the
implementation to fully support the first three definitions of a multi-relation
(undefined, trivial and empty), assuming that Drill already supports the other
two definitions (single relation and multi-relation.)
In Drill, relations are broken into batches, which are, themselves, just
relations. Thus a batch, B, can be:
{{B : ∧}} -- undefined result set)
{{ | R(0,0)}} -- trivial batch
{{ | R(s,0)}} -- empty batch set, |s| ≠ 0
{{ | R(s,n)}} -- normal batch, |s| ≠ 0, n ≠ 0
And the whole result set D (for Drill) is an ordered list of batches:
{{D = \[B ~1~, B ~2~, ..., B ~n~]}}
Where
{{B ~i~ = (s ~i~, t ~i~)}}
As noted above, if adjacent batches have the same schema, then they are just
sub-relations within a single larger (logical) relation. But, if the schemas
differ, then the adjacent batches are the last and first of two distinct
relations within a larger (logical) multi-relation. Said another way:
{{D = R ~1~, R ~2~}}
{{R ~i~ = B ~i,1~, B ~i,2~, ...}}
To clarify, let’s visualize the schema changes as ∆~i~:
{{D = \[B ~0~(s ~0~,t), B ~1~(s ~0~,t), … ∆~1~, B ~i~(s ~1~,t), B ~i+1~(s
~1~,t), …]}}
The above sequence can describe any series of batches. As I understand the
proposal, we want to put some constraints on the sequence.
h3. Results of a Drill Query
Let’s start by defining how should present the multi-relation to the client.
The client also receives batches, but, following the rules in the proposal, we
want to constrain the output:
{{D ~e~ : B(0,0)}} -- Null result
{{ | B(s,0)}} -- Empty result
{{ | B(s,n)\+}} -- “Classic” O/JDBC result
{{ | (B(s ~i~,n)\+)\+}} -- Multi-relation result
(Here, the parenthesis take on their regex/BNF meaning of grouping.)
That is the output of a Drill query is:
* A single trivial batch (zero columns, zero rows)
* A single empty batch (schema, but no data)
* One or more non-empty batches
For the non-empty case, we end up with two cases:
* A single relation (O/JDBC compatible)
* A multi-relation
h3. Drill Internals
Internally, we might want to allow any pattern of batches (include empty or
null); Drill operators do the necessary conversion:
{{D ~i~ = \[B\+, (∆, B\+)\+]}}
We want to remove empty batches where possible to convert the internal
multi-relation to the external one. First, let’s define an empty batch:
{{empty-batch : ∧}} -- undefined result set
{{ | R(0,0)}} -- trivial result set
{{ | R(s,0)}} -- empty result set, |s| ≠ 0
We can define some harmless extensions to the normal rules for unions of
relations:
{{∧ ⋃ R = R}}, for any relation R
{{R(0,0) ⋃ R = R}}, for {{R ≠ ∧}}
{{R(c,0) ⋃ R = R}}, for {{R ≠ ∧, R(0,0)}}
These rules define a “hierarchy of emptiness” to deal with adjacent empty
batches. The result of the above rules are that we can remove empty batches
from a Drill result set as long as there are adjacent non-empty batches. But,
suppose the (internal to Drill) result set has only one empty batch, B ~1~,
then the external (visible to client) result set , D ~e~, is:
{{D ~e~ = R(0,0)}} if {{B ~1~ = ∧}} or {{B ~1~ = R(0,0)}}
{{D ~e~ = R(c,0)}} if {{B ~1~ = R(c,0)}}
Otherwise, according to what we said earlier, since the internal result set has
at least one non-empty batch, then the external result set will be non-empty.
This is true because we can (indeed, should) remove empt batches internal to
Drill using the rules noted above and explained in this proposal.
h3. The Drill Iterator Protocol
Finally, we can put all this together. The proposal focuses on Drill’s
Volcano-based iterator protocol. The iterator protocol labels batches with one
of three iterator outcomes, as defined by an enum E:
{{e(s,t) ∈ E}}
{{E : NONE(∧)}}
{{ | OK_NEW_SCHEMA(s,t)}}
{{ | OK(s,t)}}
That is, each iterator outcome labels a batch and so carries a schema and data
set. NONE is a special case as it carries an undefined batch. This definition
lets us map the iterator protocol directly to a slightly modified version of
the multi-relation sequence shown earlier:
{{D = \[∆ ~0~, B ~0~(s ~0~,t), B ~1~(s ~0~,t), … ∆ ~1~, B ~i~(s ~1~,t), B
~i+1~(s ~1~,t), … ∧]}}
{{OK_NEW_SCHEMA = \[∆, B]}}
{{OK = \[B]}}
{{NONE = ∧}}
Now we can define the iterator protocol:
{{protocol : (OK_NEW_SCHEMA OK\*)\* NONE}}
The “fast NONE” path is simply an empty sequence of {{(OK_NEW_SCHEMA OK\*)\*}}
terms.
h3. Conclusion
The proposal for this ticket says that operators should handle the empty
batches. The above suggests *why* the operators should handle them. The best
solution for *how* to handle them is so modify the "inner next" code that calls
a child operator; have that code "compress out" empty batches if followed by a
non-empty batch.
This note suggests that we look at empty batches (in all three forms) as a
natural part of Drill's multi-relation model. Rather than treating them as
special cases, empty batches should be defined as a normal part of Drill's
internal protocol.
A separate proposal (part of DRILL-5211) will suggest that the scanner use the
above rules to compress out empty batches that emerge from a variety of special
cases with readers.
> Schema change problems caused by empty batch
> --------------------------------------------
>
> Key: DRILL-5546
> URL: https://issues.apache.org/jira/browse/DRILL-5546
> Project: Apache Drill
> Issue Type: Bug
> Reporter: Jinfeng Ni
> Assignee: Jinfeng Ni
>
> There have been a few JIRAs opened related to schema change failure caused by
> empty batch. This JIRA is opened as an umbrella for all those related JIRAS (
> such as DRILL-4686, DRILL-4734, DRILL4476, DRILL-4255, etc).
>
--
This message was sent by Atlassian JIRA
(v6.3.15#6346)
