-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Gregory Stark wrote:
> But that requires a) dealing with the problem of the parent table which has no
> constraints and b) an efficient way to prove that constraints don't overlap
> and order them properly. The latter looks like an O(n^2) problem to me, though
> it's a planning problem which might be worth making slow in exchange for even
> a small speedup at run-time.
Is it really worthwile to optimize away the heap access by thinking about what the
child tables hold? If the tables are read using IO, I think the complete plan would
turn out to be IO-bound, and the heap is of no interest. If the tables reside in
memory, the heap still only slows the process down by O(log(<number of tables>)) which
usually won't be that much imho.
Nonetheless, in the case of range partitioning, a sort on the lower ends of the ranges
and a linear test of neighbouring ranges for "overlap", skipping emtpy ranges,
should work in O(n log(n)).
Jens-W. Schicke
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
iD8DBQFHRu2xzhchXT4RR5ARAu//AKCZWZj680RhnbivbU/UqLBvsigBggCgq0Tw
GB+OYl0VOidmzVcK6ckhFBw=
=gbt7
-----END PGP SIGNATURE-----
