Uploaded image for project: 'IMPALA'
  1. IMPALA
  2. IMPALA-4624

Add dictionary filtering to Parquet scanner

    Details

      Description

      To efficiently process a highly selective scan query, just using partition pruning is too coarse grain (due to the limit on the number of partitions). For selective scan, very often, Impala can simply check the values in the Parquet dictionary page and determine that the whole row group can be thrown out.

        Activity

        Hide
        joemcdonnell Joe McDonnell added a comment -

        commit 9b923a1a277d90d7056e9c64f97904a90d8f231b
        Author: Joe McDonnell <joemcdonnell@cloudera.com>
        Date: Thu Jan 26 18:07:46 2017 -0800

        IMPALA-4624: Implement Parquet dictionary filtering

        Here is a basic summary of the changes:
        Frontend looks for conjuncts that operate on a single slot and pass a
        map from slot id to the conjunct index through thrift to the backend.
        The conjunct indices are the indices into the normal PlanNode conjuncts list.
        The conjuncts need to satisfy certain conditions:
        1. They are bound on a single slot
        2. They are deterministic (no random functions)
        3. They evaluate to FALSE on a NULL input. This is because the dictionary
        does not include NULLs, so any condition that evaluates to TRUE on NULL
        cannot be evaluated by looking only at the dictionary.

        The backend converts the indices into ExprContexts. These are cloned in
        the scanner threads.

        The dictionary read codepath has been removed from ReadDataPage into its
        own function, InitDictionary. This has also been turned into its own step
        in row group initialization. ReadDataPage will not see any dictionary
        pages unless the parquet file is invalid.

        For dictionary filtering, we initialize dictionaries only as needed to evaluate
        the conjuncts. The Parquet scanner evaluates the dictionary filter conjuncts on the
        dictionary to see if any dictionary entry passes. If no entry passes, the row
        group is eliminated. If the row group passes the dictionary filtering, then we
        initialize all remaining dictionaries.

        Dictionary filtering is controlled by a new query option,
        parquet_dictionary_filtering, which is on by default.

        Since column chunks can have a mixture of encodings, dictionary filtering
        uses three tests to determine whether this is purely dictionary encoded:
        1. If the encoding_stats is in the parquet file, then use it to determine if
        there are only dictionary encoded pages (i.e. there are no data pages with
        an encoding other than PLAIN_DICTIONARY).
        OR
        2. If the encoding stats are not present, then look at the encodings. The column
        is purely dictionary encoded if:
        a) PLAIN_DICTIONARY is present
        AND
        b) Only PLAIN_DICTIONARY, RLE, or BIT_PACKED encodings are listed
        OR
        3. If this file was written by an older version of Impala, then we know that
        dictionary failover happens when the dictionary reaches 40,000 values.
        Dictionary filtering can proceed as long as the dictionary is smaller than
        that.

        parquet-mr writes the encoding list correctly in the current version in our
        environment (1.5.0). This means that check #2 works on some existing files
        (potentially most existing parquet-mr files).
        parquet-mr writes the encoding stats starting in 1.9.0. This is the version
        where check #1 will start working.

        Impala's parquet writer now implements both, so either check above will work.

        Change-Id: I3a7cc3bd0523fbf3c79bd924219e909ef671cfd7
        Reviewed-on: http://gerrit.cloudera.org:8080/5904
        Reviewed-by: Marcel Kornacker <marcel@cloudera.com>
        Tested-by: Impala Public Jenkins

        Show
        joemcdonnell Joe McDonnell added a comment - commit 9b923a1a277d90d7056e9c64f97904a90d8f231b Author: Joe McDonnell <joemcdonnell@cloudera.com> Date: Thu Jan 26 18:07:46 2017 -0800 IMPALA-4624 : Implement Parquet dictionary filtering Here is a basic summary of the changes: Frontend looks for conjuncts that operate on a single slot and pass a map from slot id to the conjunct index through thrift to the backend. The conjunct indices are the indices into the normal PlanNode conjuncts list. The conjuncts need to satisfy certain conditions: 1. They are bound on a single slot 2. They are deterministic (no random functions) 3. They evaluate to FALSE on a NULL input. This is because the dictionary does not include NULLs, so any condition that evaluates to TRUE on NULL cannot be evaluated by looking only at the dictionary. The backend converts the indices into ExprContexts. These are cloned in the scanner threads. The dictionary read codepath has been removed from ReadDataPage into its own function, InitDictionary. This has also been turned into its own step in row group initialization. ReadDataPage will not see any dictionary pages unless the parquet file is invalid. For dictionary filtering, we initialize dictionaries only as needed to evaluate the conjuncts. The Parquet scanner evaluates the dictionary filter conjuncts on the dictionary to see if any dictionary entry passes. If no entry passes, the row group is eliminated. If the row group passes the dictionary filtering, then we initialize all remaining dictionaries. Dictionary filtering is controlled by a new query option, parquet_dictionary_filtering, which is on by default. Since column chunks can have a mixture of encodings, dictionary filtering uses three tests to determine whether this is purely dictionary encoded: 1. If the encoding_stats is in the parquet file, then use it to determine if there are only dictionary encoded pages (i.e. there are no data pages with an encoding other than PLAIN_DICTIONARY). OR 2. If the encoding stats are not present, then look at the encodings. The column is purely dictionary encoded if: a) PLAIN_DICTIONARY is present AND b) Only PLAIN_DICTIONARY, RLE, or BIT_PACKED encodings are listed OR 3. If this file was written by an older version of Impala, then we know that dictionary failover happens when the dictionary reaches 40,000 values. Dictionary filtering can proceed as long as the dictionary is smaller than that. parquet-mr writes the encoding list correctly in the current version in our environment (1.5.0). This means that check #2 works on some existing files (potentially most existing parquet-mr files). parquet-mr writes the encoding stats starting in 1.9.0. This is the version where check #1 will start working. Impala's parquet writer now implements both, so either check above will work. Change-Id: I3a7cc3bd0523fbf3c79bd924219e909ef671cfd7 Reviewed-on: http://gerrit.cloudera.org:8080/5904 Reviewed-by: Marcel Kornacker <marcel@cloudera.com> Tested-by: Impala Public Jenkins

          People

          • Assignee:
            joemcdonnell Joe McDonnell
            Reporter:
            alan@cloudera.com Alan Choi
          • Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development