Uploaded image for project: 'Spark'
  1. Spark
  2. SPARK-21657

Spark has exponential time complexity to explode(array of structs)

    XMLWordPrintableJSON

Details

    Description

      It can take up to half a day to explode a modest-sized nested collection (0.5m).
      On a recent Xeon processors.

      See attached pyspark script that reproduces this problem.

      cached_df = sqlc.sql('select individ, hholdid, explode(amft) from ' + table_name).cache()
print sqlc.count()

      This script generate a number of tables, with the same total number of records across all nested collection (see `scaling` variable in loops). `scaling` variable scales up how many nested elements in each record, but by the same factor scales down number of records in the table. So total number of records stays the same.

      Time grows exponentially (notice log-10 vertical axis scale):

      At scaling of 50,000 (see attached pyspark script), it took 7 hours to explode the nested collections (!) of 8k records.

      After 1000 elements in nested collection, time grows exponentially.

      Attachments

        1. nested-data-generator-and-test.py
          3 kB
          Ruslan Dautkhanov
        2. ExponentialTimeGrowth.PNG
          54 kB
          Ruslan Dautkhanov

        Issue Links

          is related to

          Improvement - An improvement or enhancement to an existing feature or task. SPARK-4502 Spark SQL reads unneccesary nested fields from Parquet

          • Critical - Crashes, loss of data, severe memory leak.
          • Resolved
          relates to

          Bug - A problem which impairs or prevents the functions of the product. SPARK-16998 select($"column1", explode($"column2")) is extremely slow

          • Major - Major loss of function.
          • Resolved

          Bug - A problem which impairs or prevents the functions of the product. SPARK-22330 Linear containsKey operation for serialized maps.

          • Major - Major loss of function.
          • Resolved

          Improvement - An improvement or enhancement to an existing feature or task. SPARK-15214 Implement code generation for Generate

          • Major - Major loss of function.
          • Resolved

          Improvement - An improvement or enhancement to an existing feature or task. SPARK-22385 MapObjects should not access list element by index

          • Major - Major loss of function.
          • Resolved
          links to

          Pull request #19683 [Github] Pull Request #19683 (uzadude)

          Activity

            People

              uzadude Ohad Raviv
              Tagar Ruslan Dautkhanov
              Votes:
              4 Vote for this issue
              Watchers:
              16 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved: