Hi, Let me rephrase the problem with unsigned ints in a way that I personally find easier to understand.
Let's take a typical application that uses native Java types internally. For parquet-mr, these native types have to be converted to Parquet primitive types. The parquet-mr library supports low-level filtering of rows, pages or row groups by allowing the application to implement callbacks or build complex conditions using a set of predicates provided by parquet-mr. For this low-level filtering, conditions must be specified in terms of Parquet's primitive/logical types and not in terms of the native Java types that the application internally uses. The "primitive/logical" part of the last sentence is the actual change in question. This used to be "primitive" and now for the new statistics fields it should become "logical". Most logical types annotate binaries, which is a class (hierarchy) in parquet-mr. Making these logical-type-aware is more-or-less easily accomplished by providing a correct compareTo() implementation. The UINT logical types are an exception, however. For these, parquet-mr's internal primitive types are the regular native Java types, so there is no way to change their comparison behaviour. Even if we provide a correct Comparator, the application can simply specify filtering conditions like "value < 42", which will result in a signed comparison on unsigned fields. It makes it way too easy for developers to shoot themselves in the foot. Zoltan On Tue, Nov 14, 2017 at 12:29 PM Gabor Szadovszky < [email protected]> wrote: > Hi, > > During the development of this feature I’ve found out some scenarios which > would be really confusing for the clients. > For example: We have the new min-max statistics in the file and also have > dictionary encoding for binary elements. The client have filtering > implemented for the related column involving Gt. Which comparator shall we > use in the DictionaryFilter? If we use the new one based on the statistics > it might contradict to the UserDefinedPredicate implemented by the client > and might cause false negatives. If we use the current natural order of > Binary it would contradict to the one in statistics. Further more, we are > about the make the new comparators available to the client so the > implemented UserDefinedPredicate may not match to the DictionaryFilter or > the statistics anyway. > > I think, the following new proposal would solve the confusion issues and > even make the existing client code work properly with the new statistics. I > am not sure yet, but think that the implementation would be cleaner as well. > As far as I know the unsigned integer types (UINT_8 etc.) are not used > widely. I would skip creating min-max statistics for them or keep having > signed comparison. (BTW, don’t we want to deprecate them?) > By leaving the unsigned integers out of the picture only the Binary class > is left to support the different comparison logics. So, let’s refactor > Binary and create different implementations for the different logical > types. This way the natural ordering of Binary will always reflect the one > specified for the logical types and the Statistics implementations do not > need to be changed. > We do have a problem though and it is the current natural ordering of > Binary. It is implemented in a way that seems to be lexicographical but the > byte comparison is signed. I don’t think it is correct so I would drop this > implementation but it makes a bit hard to implement the handing of the > former min-max statistics. If I would like to be correct, I would not write > the former min-max statistics for Binary at all and would not use them at > read. (Or only use it if it was not written by parquet-mr.) I guess, this > issue was not identified because clients are rarely using characters where > unsigned/signed comparison matters. > What do you think? > > Regards, > Gabor > > > On 8 Nov 2017, at 18:02, Ryan Blue <[email protected]> wrote: > > > > Gabor, > > > > You're right that working with logical type data isn't really something > > that Parquet has done much in the past. We have the distinction between > > logical types and physical types to simplify what we need to support -- > we > > only have encodings for physical types -- but in this case, we can't do > > that, and will need to use comparators based on the logical types. For > now, > > we don't need to expose much to the layer above because all of the types > > have a defined sort order. In the future, we should be able to support > > other orders for UTF8 data, but we don't need to focus on that now. > > > > Zoltan, > > > > While it isn't ideal to have no control over the sort order, the only > thing > > we can do at the Parquet level is to handle data correctly when it does > > come in sorted. The concerns you're raising are good to think about, but > we > > need to solve them elsewhere. I think that the table format should have a > > way to specify the sort order it wants for incoming data and communicate > > that to the engine writing Parquet files. That's what we're working on > > adding to the data source v2 API in Spark. Tables should be able to > specify > > the expected clustering (for partitioning) and sort order for rows, then > > the query plan is automatically rewritten to make that happen. > > > > rb > > > > On Wed, Nov 8, 2017 at 7:47 AM, Zoltan Ivanfi <[email protected]> wrote: > > > >> Hi, > >> > >> I don't know the solution, just adding my thoughts. > >> > >> In my opinion the underlying problem is that min-max ranges have to be > >> small for the best filtering results. In order to achieve this, the data > >> has to be sorted, but calculating min-max statistics is the > responsibility > >> of the library, while sorting the data is a responsibility of the > >> application above the library. Without logical-type-based sorting rules, > >> the application may sort data using a different ordering than the one > used > >> for calculating/filtering on the min-max values. This results in too > broad > >> min-max ranges, that in theory could still function correctly, but are > not > >> optimal for filtering. (As an extra twist, even if we have > >> logical-type-based sorting rules, the application can still use a > different > >> ordering for sorting and even for comparisons. The results can range > from > >> overly broad min-max ranges to incorrectly discarded values.) > >> > >> From this point of view, dictionary entries and bloom filters are much > less > >> problematic, because sorting by *any* order will optimize these > structures, > >> as the only important thing is that equal values should end up next to > each > >> other to increase the chance of having a low number of values in a > single > >> page/row group. > >> > >> I think that trying to optimize min-max stats by sorting crosses the > layer > >> boundary between the library and the application and as such is much > better > >> suited to a full-stack implementation like Impala than the parquet-mr + > >> separate application stack. Neither relying on the application to > calculate > >> standards-compliant statistics nor forcing the application to use the > >> library's data types for sorting and comparison seems like a good > solution > >> to me. > >> > >> Please note that this problem inherently applies to columns statistics > as > >> well. > >> > >> Zoltan > >> > >> On Wed, Nov 8, 2017 at 3:41 PM, Gabor Szadovszky < > >> [email protected]> wrote: > >> > >>> Hi, > >>> > >>> I started working on the jira PARQUET-1025 <https://issues.apache.org/ > >>> jira/browse/PARQUET-1025>. It is about implementing the new min-max > >>> statistics specified in PARQUET-686 <https://issues.apache.org/ > >>> jira/browse/PARQUET-686>. > >>> > >>> After looking in the code deeper I think the spec of the new min-max > >> stats > >>> contradicts to the actual design of parquet-mr: > >>> The concept of parquet-mr is to use the raw types (representing the > >>> primitive types in the spec) and let the client of the API have them > >>> converted to rich objects (representing the logical types). For example > >>> parquet-mr have Binary for both UTF8 and DECIMAL (at least for one > >> specific > >>> representation) instead of returning String or BigDecimal anywhere. > >>> The new min-max stats requires to have separate comparison mechanisms > for > >>> the same primitives depending on the logical types. For example UTF8 > >>> requires unsigned (lexicographical) while DECIMAL requires signed > >>> comparisons for the same Binary class. > >>> The problem is that we are specifying sorting orders based on logical > >>> types while we are not providing specific java types for them. It means > >> the > >>> client can unintentionally use a different comparison logic than > >> parquet-mr > >>> in the min-max stats which can lead to discarding relevant values > during > >>> filtering. > >>> > >>> I can see two possible solutions however none of them seems to be good > >>> enough for me. > >>> > >>> 1. Implement specific comparison logics based on the logical types in > the > >>> related Statistics object > >>> The problem here is that we are still using the raw types therefore > >> client > >>> code in filters might implement different comparison logic than > specified > >>> and implemented in Statistics. For example in case of having UINT_32 > the > >>> min-max comparison in Statistics will use the proper unsigned > comparison > >>> logic while the client code in case of checking the elements (in the > >> column > >>> or in the dictionary) might implement somewhat simpler e.g. value > 7 > >> which > >>> may lead to different results. See UserDefinedPredicate.keep(T) > >>> It is highly confusing for the client that it has to re-implement the > >> same > >>> comparison logic in the client code for the raw types as it is > >> implemented > >>> for the statistics. > >>> > >>> 2. Return specific “rich” objects for the logical types instead of the > >> raw > >>> types > >>> This solution would solve the problems what the previous one has but > >> would > >>> introduce bigger problems. > >>> Breaks the actual design of parquet-mr > >>> Backward incompatible: existing client code would not work properly for > >>> several logical types > >>> > >>> (3.) Revert the specs of the new min-max statistics > >>> Let’s keep working on the raw types without having any additional > >>> comparison logic. Specify the existing comparison logic (e.g. signed > for > >>> all primitive types, (signed) lexicographical for binary) and expect > the > >>> client to use these if it want to have sorting implemented for the > values > >>> for better performance. > >>> > >>> > >>> What do you think, guys? Any suggestions on one of my solutions or for > a > >>> new one I did not recognise? > >>> > >>> Thanks a lot, > >>> Gabor > >>> > >> > > > > > > > > -- > > Ryan Blue > > Software Engineer > > Netflix > >
