morphismtech / squeal

Squeal, a deep embedding of SQL in Haskell
362 stars 32 forks source link

Use properly short-circuiting conditional for type-level merge sort #316

Closed Sciencei closed 2 years ago

Sciencei commented 2 years ago

Previously, the sort done for pretty printing used If. Because of how type families work, this doesn't short circuit like value-level if, and always evaluates both branches, which made sorting very slow and run out of memory with a larger schema like in (credit @wyao-simspace ). Sorting only happens in the case of an error, so this didn't come up in normal testing.

type Schema =
  '[ "public" ::: SomeTables
   ] :: Sq.SchemasType
type SomeTables =
  '[ "a" ::: 'Sq.Table SomeTable
   , "b" ::: 'Sq.Table SomeTable
   , "c" ::: 'Sq.Table SomeTable
   , "d" ::: 'Sq.Table SomeTable
   , "e" ::: 'Sq.Table SomeTable
   , "f" ::: 'Sq.Table SomeTable
   , "g" ::: 'Sq.Table SomeTable
   , "h" ::: 'Sq.Table SomeTable
   , "i" ::: 'Sq.Table SomeTable
   , "j" ::: 'Sq.Table SomeTable
   , "k" ::: 'Sq.Table SomeTable
   , "l" ::: 'Sq.Table SomeTable
   , "m" ::: 'Sq.Table SomeTable
   , "n" ::: 'Sq.Table SomeTable
   , "o" ::: 'Sq.Table SomeTable
   , "p" ::: 'Sq.Table SomeTable
   , "q" ::: 'Sq.Table SomeTable
   , "r" ::: 'Sq.Table SomeTable
   , "s" ::: 'Sq.Table SomeTable
   , "t" ::: 'Sq.Table SomeTable
   , "u" ::: 'Sq.Table SomeTable
   , "v" ::: 'Sq.Table SomeTable
   , "w" ::: 'Sq.Table SomeTable
   , "x" ::: 'Sq.Table SomeTable
   , "y" ::: 'Sq.Table SomeTable
   , "z" ::: 'Sq.Table SomeTable
   , "aa" ::: 'Sq.Table SomeTable
   , "bb" ::: 'Sq.Table SomeTable
   , "cc" ::: 'Sq.Table SomeTable
   , "dd" ::: 'Sq.Table SomeTable
   , "ee" ::: 'Sq.Table SomeTable
   , "ff" ::: 'Sq.Table SomeTable
   , "gg" ::: 'Sq.Table SomeTable
   , "hh" ::: 'Sq.Table SomeTable
   , "ii" ::: 'Sq.Table SomeTable
   , "jj" ::: 'Sq.Table SomeTable
   , "kk" ::: 'Sq.Table SomeTable
   , "ll" ::: 'Sq.Table SomeTable
   , "mm" ::: 'Sq.Table SomeTable
   , "nn" ::: 'Sq.Table SomeTable
   , "oo" ::: 'Sq.Table SomeTable
   , "pp" ::: 'Sq.Table SomeTable
   , "qq" ::: 'Sq.Table SomeTable
   , "rr" ::: 'Sq.Table SomeTable
   , "ss" ::: 'Sq.Table SomeTable
   , "tt" ::: 'Sq.Table SomeTable
   , "uu" ::: 'Sq.Table SomeTable
   ] :: Sq.SchemaType
type SomeTable = ('[] :=> SomeColumns) :: Sq.TableType
type SomeColumns =
  '[ "a" ::: 'Sq.NoDef :=> 'NotNull 'PGtext
   , "b" ::: 'Sq.NoDef :=> 'NotNull 'PGuuid
   ] :: Sq.ColumnsType
​
someQuery :: Sq.Query '[] '[] Schema '[] '[ "a" ::: 'NotNull 'PGtext ]
someQuery =
  Sq.select_
    (#table ! #a)
    (Sq.from (Sq.table #table))

This changes the sort logic to use a custom type family that does only evaluate one branch of the conditional. This improves the performance so that we can compile the above schema, up until it (as expected) reports a type error. Also tested was a schema with 250 entries, which also worked with -freduction-depth=0 set. I don't have the above added as a test, because it by design throws a type error.