Exponential planning time (100s of seconds) with UNION and ORDER BY queries

@berkaysynnada

Describe the bug

Our internal system generates queries that look like the following

select c1, null as c2, ... null as cn from t ORDER BY c1
   UNION ALL
 select null as c1, c2, ... null as cn from t ORDER BY c2
 ...
 select null as c1, null as c2, ... cn from t ORDER BY cn
  ORDER BY c1, c2 ... CN

When there are 10 columns this takes 22 ms (in release mode) to plan (which is still quite a while)

When there are 100 columns, it takes over 2 minutes (!!) to plan, which basically caused two production incidents

Here are some timings with numbers of columns (you can see the exponential growth):

Running with 10 columns...completed in 22.65575ms
Running with 20 columns...completed in 107.885ms
Running with 30 columns...completed in 481.31775ms
Running with 40 columns...completed in 1.656844042s
Running with 50 columns...completed in 4.560470708s
Running with 60 columns...completed in 10.54814975s
Running with 70 columns...completed in 21.993968458s
Running with 80 columns...completed in 41.614843209s
Running with 90 columns...completed in 73.642939542s
Running with 100 columns...completed in 123.150163417s

To Reproduce

With this data file (has 100 columns): data.csv

Create Table

CREATE EXTERNAL TABLE t STORED AS CSV LOCATION 'data.csv' WITH ORDER (c1)

Run query

40 column version (this takes over a second to plan in release mode)

(SELECT c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c0)
  UNION ALL
(SELECT null as c0, c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c1)
  UNION ALL
(SELECT null as c0, null as c1, c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c2)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c3)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c4)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c5)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c6)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c7)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c8)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c9)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c10)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c11)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c12)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c13)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c14)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c15)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c16)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c17)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c18)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c19)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c20)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c21)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c22)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c23)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c24)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c25)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c26)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c27)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c28)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c29)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c30)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c31)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c32)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, c33, null as c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c33)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, c34, null as c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c34)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, c35, null as c36, null as c37, null as c38, null as c39 FROM t ORDER BY c35)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, c36, null as c37, null as c38, null as c39 FROM t ORDER BY c36)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, c37, null as c38, null as c39 FROM t ORDER BY c37)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, c38, null as c39 FROM t ORDER BY c38)
  UNION ALL
(SELECT null as c0, null as c1, null as c2, null as c3, null as c4, null as c5, null as c6, null as c7, null as c8, null as c9, null as c10, null as c11, null as c12, null as c13, null as c14, null as c15, null as c16, null as c17, null as c18, null as c19, null as c20, null as c21, null as c22, null as c23, null as c24, null as c25, null as c26, null as c27, null as c28, null as c29, null as c30, null as c31, null as c32, null as c33, null as c34, null as c35, null as c36, null as c37, null as c38, c39 FROM t ORDER BY c39)
ORDER BY c0, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12, c13, c14, c15, c16, c17, c18, c19, c20, c21, c22, c23, c24, c25, c26, c27, c28, c29, c30, c31, c32, c33, c34, c35, c36, c37, c38, c39

Expected behavior

I expect that the query plans within a second with 100 columns

Additional context

The code spends an increasing amount of time in :

27.22 Gc  99.9%	-	                  datafusion_physical_expr::equivalence::properties::calculate_union::h9a6d0c834d33dfa8
27.20 Gc  99.9%	2.00 Mc	                   datafusion_physical_expr::equivalence::properties::UnionEquivalentOrderingBuilder::add_satisfied_orderings::haff5d34880826c26
27.20 Gc  99.8%	-	                    datafusion_physical_expr::equivalence::properties::EquivalenceProperties::ordering_satisfy_requirement::h7800d9c061e4551e
26.94 Gc  98.9%	2.00 Mc	                     datafusion_physical_expr::equivalence::properties::EquivalenceProperties::with_constants::h9b627573961f7ac1
26.72 Gc  98.1%	17.83 Mc	                      datafusion_physical_expr::equivalence::properties::EquivalenceProperties::discover_new_orderings::hdb50bd332b5dedd2
21.92 Gc  80.5%	3.85 Gc	                       datafusion_physical_expr::equivalence::ordering::OrderingEquivalenceClass::remove_redundant_entries::h3394f8a44ca387d2
2.52 Gc   9.2%	5.25 Mc	                       _$LT$alloc..vec..Vec$LT$T$GT$$u20$as$u20$alloc..vec..spec_from_iter..SpecFromIter$LT$T$C$I$GT$$GT$::from_iter::hb5d026af61b973ba
2.12 Gc   7.8%	2.03 Gc	                       _$LT$datafusion_physical_expr..expressions..column..Column$u20$as$u20$core..cmp..PartialEq$LT$dyn$u20$core..any..Any$GT$$GT$::eq::h7faccabfc76823d5

This particularly bad behavior was introduced in influxdata@577e4bb / #12562 (🤦 myself)

I think this is also what @berkaysynnada was warning us in #12446 (comment)

I tested this with various released versions:

`42.0.0`:

Worst case takes 7.5 seconds

Running with 10 columns...completed in 25.767125ms
Running with 20 columns...completed in 59.605292ms
Running with 30 columns...completed in 151.040583ms
Running with 40 columns...completed in 352.528417ms
Running with 50 columns...completed in 701.194625ms
Running with 60 columns...completed in 1.259548375s
Running with 70 columns...completed in 2.142141458s
Running with 80 columns...completed in 3.42683925s
Running with 90 columns...completed in 5.22279025s
Running with 100 columns...completed in 7.59148425s

`43.0.0`:

Same as reported above (123.150163417s)

`main`

I also tested with main as of now: 36a1361

It is better, but still quite a bit worse than 42

Running with 10 columns...completed in 35.857458ms
Running with 20 columns...completed in 102.454125ms
Running with 30 columns...completed in 429.636584ms
Running with 40 columns...completed in 1.403798625s
Running with 50 columns...completed in 3.770518708s
Running with 60 columns...completed in 8.758160834s
Running with 70 columns...completed in 18.022044708s
Running with 80 columns...completed in 34.337127625s
Running with 90 columns...completed in 60.926777084s
Running with 100 columns...completed in 101.470021875s

BTW here is the code I am using to generate those numbers (it is pretty grotty)

Details

// DataFusion spilling sort benchmark / exmaples
// Idea is to replicate a report from  https://discord.com/channels/885562378132000778/1166447479609376850/1276137008435298335
// where sort doesn't spill

// Related link: sorting strings

use std::fs::File;
use std::path::PathBuf;
use datafusion::arrow::array::{ArrayRef, Int32Array};
use datafusion::arrow::datatypes::{Field, Fields, Schema};
use datafusion::arrow::record_batch::RecordBatch;
use datafusion::error::Result;
use std::sync::Arc;
use datafusion::arrow;
use datafusion::prelude::SessionContext;

#[tokio::main]
async fn main() -> Result<()> {
    // initialize logging to see DataFusion's internal logging
    std::env::set_var("RUST_LOG", "info");
    env_logger::init();


    let ctx = SessionContext::new();
    let n = 100;
    make_table(n);
    ctx.sql(&format!("CREATE EXTERNAL TABLE t({})  STORED AS CSV LOCATION 'data.csv' WITH ORDER (c1)", column_list(100))).await?
        .show().await?;

    println!("10 columns");
    println!("{}", make_query(10));

    println!("40 columns");
    println!("{}", make_query(40));


    for n in [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] {
        let sql = make_query(n);
        print!("Running with {n} columns");
        let start = std::time::Instant::now();
        ctx.sql(&sql).await?.collect().await?;
        let elapsed = start.elapsed();
        println!("...completed in {:?}", elapsed);
    }
    Ok(())
}

fn column_list(n: usize) -> String {
    (0..n)
        .map(|i| format!("c{} int", i))
        .collect::<Vec<_>>()
        .join(", ")
}

/// Writes a table like this to CSV file
/// c1: int, c2: int, c3: int....cn:int
///
/// returns the filename
fn make_table(n: usize) -> PathBuf {
    let path = PathBuf::from("data.csv");
    let arrays = (0..n)
        .map(|i| {
            let i = i as i32;
            let n = n as i32;
            Arc::new(Int32Array::from(vec![i * n, 2 * i * n, 3 * i * n])) as ArrayRef
        })
        .collect::<Vec<_>>();

    let schema = Schema::new(Fields::from(
        arrays
            .iter()
            .enumerate()
            .map(|(i, arr)| Field::new(&format!("c{}", i), arr.data_type().clone(), false))
            .collect::<Vec<_>>(),
    ));

    let batch = RecordBatch::try_new(Arc::new(schema), arrays).unwrap();
    let file = File::create(&path).unwrap();
    let mut writer = arrow::csv::Writer::new(file);
    writer.write(&batch).unwrap();
    // flush on drop
    // writer.into_inner();
    path
}

/// return a query like
/// ```sql
/// select c1, null as c2, ... null as cn from t ORDER BY c1
///   UNION ALL
/// select null as c1, c2, ... null as cn from t ORDER BY c2
/// ...
/// select null as c1, null as c2, ... cn from t ORDER BY cn
///  ORDER BY c1, c2 ... CN
/// ```
fn make_query(n: usize) -> String {
    let mut query = String::new();
    for i in 0..n {
        if i != 0 {
            query.push_str("\n  UNION ALL \n");
        }
        let select_list = (0..n)
            .map(|j| {
                if i == j {
                    format!("c{j}")
                } else {
                    format!("null as c{j}")
                }
            })
            .collect::<Vec<_>>()
            .join(", ");
        query.push_str(&format!("(SELECT {} FROM t ORDER BY c{})", select_list, i));
    }
    query.push_str(&format!(
        "\nORDER BY {}",
        (0..n)
            .map(|i| format!("c{}", i))
            .collect::<Vec<_>>()
            .join(", ")
    ));
    query
}

Do you know where the time is being spent?
esp is this some plan property that's being recalculated in an expensive manner?

Do you know where the time is being spent? esp is this some plan property that's being recalculated in an expensive manner?

Yes the time is being spent normalizing equivalence orderings.

I just need to spend some time staring at the code and figuring out how it could be done better

Here is a flamegraph showing where the time is spent

I spent some time reviewing the flamegraph.

remove_redundant_entries is called / takes up 1/3 of the time
normalized_oeq_class requires 2/3 of the time

The high level observation is that continually recomputing normalized equivalence groups requires significaint amounts of time. What I am going to try is to make these implementations much more efficient (avoid allocation and recomputation) and

Sketch:

try and avoid calling normalized_oeq_class by ensuring that the oeq_class is always normalized
I think we could reduce remove_redundant_entries by storing it in an IndexSet rather than a Vec

FYI I am pretty sure I was seeing this with some of the sqlite test files, specifically https://github.com/Omega359/arrow-datafusion/blob/feature/sqllogictest_add_sqlite/datafusion/sqllogictest/test_files/sqlite/select4.slt

I will make this much better, but it will take me a while

I have big plans on how to fix this holistically, but I also want to be able to resolve the issue quickly if possible. I am going to see if I can find some way to work around this for now while I work on a better long term plan

FYI I am pretty sure I was seeing this with some of the sqlite test files, specifically https://github.com/Omega359/arrow-datafusion/blob/feature/sqllogictest_add_sqlite/datafusion/sqllogictest/test_files/sqlite/select4.slt

For anyone following along, we are tracking completing the sqllogictest work in

[EPIC] Run full sqllogic / sqlite test suite against DataFusion #13811

I have a few PRs open to make the fields non pub. I have also been studying the code -- my first POC will be to figure out how to avoid calling normalized_oeq_class() so much as that is expensive and gets called many times.

Update:
I spent some time trying to avoid calling OrderingEquivalenceClass::normalized_oeq_class as much. This helped but not enough to really fix the problem:

WIP: Reduce time spent normalizing #14049

I made a flamegraph with #14049 and it looks like almost all the time now is in "remove_reundant_entries"

(here is the raw flamegraph):

My next step will be to attempt to use some sort of Set rather than Vec for OrderingEquivalenceClass

I think I am close to actually making measurable progress

With some more flame graph profiling, I am convinced that the time is largely spent in

OrderingEquivalenceProperties::resolve_overlap (this shows up as OrderingEquivalenceProperties::remove_redundant_entries
normalize_sort_exprs

My next steps are to create a benchmark in the repository and then work on validating some optimizations (such as #14136)

Benchmark:

Add benchmark for planning sorted unions #14157

I am basically stalled with this code -- I have some ideas but we have a workaround downstream in InfluxData and a bunch of other priorities have come up since then

For anyone looking, I think this is the workaround Influx has for this issue.

For anyone looking, I think this is the workaround Influx has for this issue.

Indeed -- that basically disables the code in question. However, doing so leads to the Sanity Checker failing for certain queries with unions and constants 😢

So we also disable the sanity checker

@Omega359

Hi @Omega359 -- I am very interested in this and will be very happy to help review / push things along

@alamb

@alamb hello I wanted to help, and since it's marked as regression there must be some working version. So what about bisecting?

@DanielFrantes

@alamb hello I wanted to help, and since it's marked as regression there must be some working version. So what about bisecting?

Thanks @DanielFrantes

I think it came in via

Account for constant equivalence properties in union, tests #12562

So the real question is how to improve the performance - I think we need to change the algorithmic structure so it isn't super exponential

@ozankabak I think mentioned he had some work in progress to do this but I am not sure what the status currently is

@ozankabak I think mentioned he had some work in progress to do this but I am not sure what the status currently is

a few items were left, he’ll probably open the PR soon

@alamb

@alamb and what about memory consummation? If there are too many sequential operations on large memory chunks, it will run slowly.

@alamb

@alamb @ozankabak

I don't think this issue should have been closed. The performance now is definitely better than it was as provided in the description above however it's still quite slow.

I've updated the sql_planner benchmark to showcase that planning is still exponentially slow based on the number of columns and unions in the query. The output I see is below:

physical_sorted_union_order_by_10
                        time:   [12.089 ms 12.105 ms 12.125 ms]
                        change: [+6.4475% +6.6567% +6.8895%] (p = 0.00 < 0.05)
                        Performance has regressed.

physical_sorted_union_order_by_50
                        time:   [323.92 ms 324.75 ms 325.53 ms]
                        change: [+6.5657% +6.8547% +7.1319%] (p = 0.00 < 0.05)
                        Performance has regressed.

Benchmarking physical_sorted_union_order_by_100: Warming up for 30.000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 18.5s.
physical_sorted_union_order_by_100
                        time:   [1.7079 s 1.7143 s 1.7221 s]
                        change: [+6.5417% +6.9412% +7.5811%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 1 outliers among 10 measurements (10.00%)
  1 (10.00%) high mild

Benchmarking physical_sorted_union_order_by_200: Warming up for 30.000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 118.6s.
physical_sorted_union_order_by_200
                        time:   [10.271 s 10.321 s 10.400 s]
                        change: [+4.3930% +4.9196% +5.7641%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 3 outliers among 10 measurements (30.00%)
  2 (20.00%) low mild
  1 (10.00%) high severe

Benchmarking physical_sorted_union_order_by_500: Warming up for 30.000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 1350.0s.
physical_sorted_union_order_by_500
                        time:   [129.75 s 131.00 s 132.82 s]

@Omega359

Thank you @Omega359 -- I suggest we open a new ticket to describe the follow on work. If that is ok with you, I will do so (or I may be fishing to get you to do it ;) )

Ha, you got me :) I'll file a ticket tomorrow

Followup ticket #17261

Navigation Menu

Repository navigation

Exponential planning time (100s of seconds) with `UNION` and `ORDER BY` queries #13748

Describe the bug

To Reproduce

Create Table

Run query

Expected behavior

Additional context

`42.0.0`:

`43.0.0`:

`main`

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Exponential planning time (100s of seconds) with UNION and ORDER BY queries #13748

Description

Describe the bug

To Reproduce

Create Table

Run query

Expected behavior

Additional context

Activity

alamb commented on Dec 12, 2024

42.0.0:

43.0.0:

main

alamb commented on Dec 12, 2024

findepi commented on Dec 13, 2024

alamb commented on Dec 13, 2024

alamb commented on Dec 13, 2024

alamb commented on Dec 13, 2024

Omega359 commented on Dec 14, 2024

alamb commented on Dec 15, 2024

alamb commented on Dec 15, 2024

alamb commented on Dec 18, 2024

alamb commented on Jan 7, 2025

alamb commented on Jan 8, 2025

alamb commented on Jan 16, 2025

alamb commented on Jan 16, 2025

alamb commented on Feb 22, 2025

Omega359 commented on Feb 22, 2025

alamb commented on Feb 23, 2025

alamb commented on Feb 27, 2025

DanielFrantes commented on May 14, 2025

alamb commented on May 15, 2025

berkaysynnada commented on May 15, 2025

DanielFrantes commented on May 16, 2025

Omega359 commented on Aug 19, 2025

alamb commented on Aug 19, 2025

Omega359 commented on Aug 20, 2025

Omega359 commented on Aug 20, 2025

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

Exponential planning time (100s of seconds) with `UNION` and `ORDER BY` queries #13748

`42.0.0`:

`43.0.0`:

`main`