> There is one database that I'm aware of that uses sentinels _and_
supports complex types with missing values: Kx's KDB+.
I read this and was pleased that KDB is being used as a reference. It is a
seriously good database: the gold-standard in many people's eyes.
> This has led to some seriously strange choices like the ASCII space
character being used as the sentinel value for strings.
But then I saw this. Surely if sentinels are good enough for KDB then isn't
that a sign that sentinels are not as bad as this group fears?
What about grouping and joining columns that contain NA? Here's an
example from R data.table :
> DT = data.table(x=c(1,3,3,NA,1,NA), v=1:6)
> DT
x v
<num> <int>
1: 1 1
2: 3 2
3: 3 3
4: NA 4
5: 1 5
6: NA 6
> DT[,sum(v),keyby=x]
x V1
<num> <int>
1: NA 10
2: 1 6
3: 3 5
The NAs are grouped as a distinct value and are not excluded for
statistical robustness reasons. This is very easy to achieve efficiently
internally; in fact there is no special code to deal with the NA values
because they are just another distinct value (the sentinel). In Arrow if a
bitmap is present, there would be more code needed to deal with the NAs
(either way: including the NA group or excluding the NA group), if I
understand correctly.
On Thu, Nov 8, 2018 at 3:18 PM Phillip Cloud <cpcl...@gmail.com> wrote:
> There is one database that I'm aware of that uses sentinels _and_ supports
> complex types with missing values: Kx's KDB+. This has led to some
> seriously strange choices like the ASCII space character being used as the
> sentinel value for strings. See
> https://code.kx.com/wiki/Reference/Datatypes for
> more details.
>
> On Thu, Nov 8, 2018 at 4:39 PM Wes McKinney <wesmck...@gmail.com> wrote:
>
> > hey Matt,
> >
> > Thanks for giving your perspective on the mailing list.
> >
> > My objective in writing about this recently
> > (http://wesmckinney.com/blog/bitmaps-vs-sentinel-values/, though I
> > need to update since the sentinel case can be done more efficiently
> > than what's there now) was to help dispel the notion that using a
> > separate value (bit or byte) to encode nullness is a performance
> > compromise to comply with the requirements of database systems. I too
> > prefer real world benchmarks to microbenchmarks, and probably null
> > checking is not going to be the main driver of aggregate system
> > performance. I had heard many people over the years object to bitmaps
> > on performance grounds but without analysis to back it up.
> >
> > Some context for other readers on the mailing list: A language like R
> > is not a database and has fewer built-in scalar types: int32, double,
> > string (interned), and boolean. Out of these, int32 and double can use
> > one bit pattern for NA (null) and not lose too much. A database system
> > generally can't make that kind of compromise, and most popular
> > databases can distinguish INT32_MIN (or any other value used as a
> > sentinel) and null. If you loaded data from an Avro or Parquet file
> > that contained one of those values, you'd have to decide what to do
> > with the data (though I understand there's integer64 add-on packages
> > for R now)
> >
> > Now back to Arrow -- we have 3 main kinds of data types:
> >
> > * Fixed size primitive
> > * Variable size primitive (binary, utf8)
> > * Nested (list, struct, union)
> >
> > Out of these, "fixed size primitive" is the only one that can
> > generally support O(1) in-place mutation / updates, though all of them
> > could support a O(1) "make null" operation (by zeroing a bit). In
> > general, when faced with designs we have preferred choices benefiting
> > use cases where datasets are treated as immutable or copy-on-write.
> >
> > If an application _does_ need to do mutation on primitive arrays, then
> > you could choose to always allocate the validity bitmap so that it can
> > be mutated without requiring allocations to happen arbitrarily in your
> > processing workflow. But, if you have data without nulls, it is a nice
> > feature to be able to ignore the bitmap or not allocate one at all. If
> > you constructed an array from data that you know to be non-nullable,
> > some implementations might wish to avoid the waste of creating a
> > bitmap with all 1's.
> >
> > For example, if we create an array::Array from a normal NumPy array of
> > integers (which cannot have nulls), we have
> >
> > In [6]: import pyarrow as pa
> > In [7]: import numpy as np
> > In [8]: arr = pa.array(np.array([1, 2, 3, 4]))
> >
> > In [9]: arr.buffers()
> > Out[9]: [None, <pyarrow.lib.Buffer at 0x7f34ecd3eea0>]
> >
> > In [10]: arr.null_count
> > Out[10]: 0
> >
> > Normally, the first buffer would be the validity bitmap memory, but
> > here it was not allocated because there are no nulls.
> >
> > Creating an open standard data representation is a difficult thing;
> > one cannot be "all things to all people" but the intent is to be a
> > suitable lingua franca for language agnostic data interchange and as a
> > runtime representation for analytical query engines (where most
> > operators are "pure"). If the Arrow community's goal were to create a
> > "mutable column store" then some things might be designed differently
> > (perhaps more like internals of https://kudu.apache.org/). It is
> > helpful to have an understanding of what compromises have been made
> > and how costly they are in real world applications.
> >
> > best
> > Wes
> > On Mon, Nov 5, 2018 at 8:27 PM Jacques Nadeau <jacq...@apache.org>
> wrote:
> > >
> > > On Mon, Nov 5, 2018 at 3:43 PM Matt Dowle <mattjdo...@gmail.com>
> wrote:
> > >
> > > > 1. I see. Good idea. Can we assume bitmap is always present in Arrow
> > then?
> > > > I thought I'd seen Wes argue that if there were no NAs, the bitmap
> > doesn't
> > > > need to be allocated. Indeed I wasn't worried about the extra
> storage,
> > > > although for 10,000 columns I wonder about the number of vectors.
> > > >
> > >
> > > I think different implementations handle this differently at the
> moment.
> > In
> > > the Java code, we allocate the validity buffer at initial allocation
> > > always. We're also looking to enhance the allocation strategy so the
> > fixed
> > > part of values are always allocated with validity (single allocation)
> to
> > > avoid any extra object housekeeping.
> > >
> > >
> > > > 2. It's only subjective until the code complexity is measured, then
> > it's
> > > > not subjective. I suppose after 20 years of using sentinels, I'm used
> > to it
> > > > and trust it. I'll keep an open mind on this.
> > > >
> > > Yup, fair enough.
> > >
> > >
> > > > 3. Since I criticized the scale of Wes' benchmark, I felt I should
> > show how
> > > > I do benchmarks myself to show where I'm coming from. Yes none-null,
> > > > some-null and all-null paths offer savings. But that's the same under
> > both
> > > > sentinel and bitmap approaches. Under both approaches, you just need
> to
> > > > know which case you're in. That involves storing the number of NAs in
> > the
> > > > header/summary which can be done under both approaches.
> > > >
> > >
> > > The item we appreciate is that you can do a single comparison every 64
> > > values to determine which of the three cases you are in (make this a
> > local
> > > decision). This means you don't have to do housekeeping ahead of time.
> It
> > > also means that the window of choice is narrow, minimizing the penalty
> in
> > > situations where you have rare invalid values (or rare valid values).
> >
>
