orc-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Owen O'Malley" <owen.omal...@gmail.com>
Subject Re: Orc v2 Ideas
Date Sat, 06 Oct 2018 18:42:05 GMT
On Mon, Oct 1, 2018 at 3:56 PM Dain Sundstrom <dain@iq80.com> wrote:

>
> Interesting idea.  This could help some processors of the data.  Also, if
> the format has this, it would be good to support "clustered" and "unique"
> as flags for data that isn’t strictly sorted, but has all of the same
> values clustered together.  Then again, this seems like a property for the
> table/partition.
>

Clustered and unique are easy to measure while we are in dictionary mode,
but very hard while in direct mode. What are you thinking?


> >>
> >>  *   Stripe Footer Location
> >>
> >> Today stripe footers are stored at the end of each stripe. This design
> >> probably come from the Hive world where the implementation tries to
> align
> >> Orc stripe with an HDFS block. It would make sense when you only need to
> >> read one HDFS block for both the data and the footer. But the alignment
> >> assumption doesn’t hold in other systems that leverage Orc as a columnar
> >> data format. Besides even for Hive, often time it’s hard to make sure
> good
> >> alignment due to various reasons - for example, when memory pressure is
> >> high stripe needs to be flushed to disk earlier. With this in mind, it
> will
> >> make sense to support saving stripe footer at the end of the file,
> together
> >> with all the other file meta. This would be easier for one sequential
> IO to
> >> load all the meta, and is easier to cache them all together. And we can
> >> make this configurable through writer options.
> >>
> >
> > Some of the systems like S3 and Wasabi have a strong preference for
> reading
> > forward in files, so I think it is reasonable to put the stripe "footer"
> > first in the file, followed by the indexes, and finally the data. Putting
> > the "footer" first isn't hard for the implementation since it has to
> buffer
> > the entire stripe before anything is
>
> On a per-stripe basis, the footer, data and index could be in any order,
> because any implementation will need to completely buffer the stripe
> somewhere (it is just a reality of columnar writing).  Across the whole
> file, that is a completely different story.
>

I misread the original proposal. Stripes being co-located is a feature, not
a problem. So -1 to having the stripe footer at the bottom of the file.


> > One of the ideas that I've been playing with is to make "stripelets"
> where
> > each one contains 128k rows and flush the streams at that point. That
> would
> > enable you to read the first stripelet and start processing while you
> read
> > the next stripelet.
>
> What is the advantage of a "stripelet" over just flushing the stripe every
> 128k rows?
>

After thinking about it more, I agree. There were some advantages, but the
complexity is probably too high to justify it.


> >>  *   File Level Dictionary
> >>
> >> Currently Orc builds dictionary at stripe level. Each stripe has its own
> >> dictionary. But in most cases, data across stripes share a lot of
> >> similarities. Building one file level dictionary is probably more
> efficient
> >> than having one dictionary each stripe. We can reduce storage footprint
> and
> >> also improve read performance since we only have one dictionary per
> column
> >> per file. One challenge with this design is how to do file merge. Two
> files
> >> can have two different dictionary, and we need to be able to merge them
> >> without rewriting all the data. To solve this problem, we will need to
> >> support multiple dictionaries identified by uuid. Each stripe records
> the
> >> dictionary ID that identifies the dictionary it uses. And the reader
> loads
> >> the particular dictionary based on the ID when it loads a stripe. When
> you
> >> merge two files, dictionary data doesn’t need to be changed, but just to
> >> save the dictionaries from both files in the new merged file.
> >>
> >
> > I haven't seen the dictionary duplication being a problem. On the other
> > hand, having cross-block reads, which a global dictionary would require,
> > are painful. As you point out, stripe merging become much more
> complicated
> > in this case. (You don't need UUID schemes, because the writer would
> always
> > know the mapping of which stripes & columns are using which dictionary.)
>
> To be honest, I rarely see cross stripe/block reads.  In Presto, people
> normally want to be as a parallel as possible, so effectively every strip
> is read by a different threads/machines.  Of course there are corner cases,
> where a writer went crazy and wrote tiny stripes, but these are the
> exception.
>

Agreed.

We do need to do better about giving better guidance and default values for
wide schemas. There are many cases where the default behavior ends up with
20k rows per a stripe, which is really really bad for read performance.


> >>  *   Breaking Compression Block and RLE Runs at Row Group Boundary
> >>
> >> Owen has mentioned this in previous discussion. We did a prototype and
> are
> >> able to show that there’s only a slight increase of file size (< 1%)
> with
> >> the change. But the benefit is obvious - all the seek to row group
> >> operation will not involve unnecessary decoding/decompression, making it
> >> really efficient. And this is critical in scenarios such as predicate
> >> pushdown or range scan using clustered index (see my first bullet
> point).
> >> The other benefit is doing so will greatly simply the index
> implementation
> >> we have today. We will only need to record a file offset for row group
> >> index.
> >>
> >
> > Yeah, this is the alternative to the stripelets that I discussed above.
> >
> >>  *   Encoding and Compression
> >>
> >> The encoding today doesn’t have a lot of flexibility. Sometimes we would
> >> need to configure and fine tune encoding when it’s needed. For example,
> in
> >> previous discussions Gang brought up, we found LEB128 causes zStd to
> >> perform really bad. We would end up with much better result by just
> >> disabling LEB128 under zstd compression. We don’t have flexibility for
> >> these kind of things today. And we will need additional meta fields for
> >> that.
> >>
> >
> > I certainly have had requests for custom encodings, but I've tended to
> push
> > back because it makes it hard to ensure the files are readable on all of
> > the platforms. I did just add the option to turn off dictionary encoding
> > for particular columns.
>
> Yep. As someone that maintains a reader/writer implementation, I would
> prefer to keep the variety of encodings down for the same reason :)
>
> As for flexibility, the dictionary encoding flag you mentioned wouldn’t
> effect the format, so it seems like a reasonable change to me.  One format
> level flexibility change, I’d like to see is the ability to not sort
> dictionaries, because no one is taking advantage of it, and it make it
> impossible to predict the output size of the stipe (sorting can make
> compression better or worse).
>

Absolutely. We probably should make that the default for ORC v2.


> I guess that "breaking the compression" at row group boundaries could be
> done without format changes, but I’d prefer to see it required as it makes
> skipping a pain.
>
> > With respect to zstd, we need to test it under different data sets and
> > build up an understanding of when it works and when it doesn't. It sounds
> > like zstd with the options that you were using were a bad fit for what we
> > need. I would guess that longer windows and pre-loaded dictionaries may
> > help. We need more work to figure out what the right parameters are in
> > general by looking at more data sets.
>
> Totally agree.  My guess is it works good for thinks like timestamps and
> dates, but not great for varchar and binary.  Then again, if you are
> writing a lot of data, you could use the data from the previous stripes to
> speed up compression for later stripes.  My guess is that would be really
> complex to implement.
>
> If we decided we may want to pursue this path in the future, we could
> profile a "dictionary" section in the stream information.
>
> -dain

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message