Re: [GENERAL] intarray internals

Hi!

Sorry for delay, I hadn't access to Internet.
> [3]> Again, in g_int_decompress(), I couldn't figure out the functionality of> below lines:

gist__int_ops use rangeset compression technique, read about in "THE RD-TREE: AN 
INDEX STRUCTURE FOR SETS", Joseph M. Hellerstein,
http://www.sai.msu.su/~megera/postgres/gist/papers/rd-tree.ps


About your patches:
* intarray_contains.patch.0 - applied

* intarray_union.patch.0 - doesn't applied, but make small optimization to 
reduce number non-unique values. I don't believe that one pass through array 
with a lot of ifs will be faster than two pass with simple ifs. Did you some tests?

* intarray_same.patch.0 - move SORT as you suggest, but don't touch algorithm. 1) if (A[0] == B[0] && A[1] == B[1] &&
...)
 2) if (A[0] == B[0] && A[  N] == B[  N] &&    A[1] == B[1] && A[N-1] == B[N-1] &&    ...)
  Why are you sure that second a much faster? Did you make tests? Number of 
comparisons is the same...

* intarray_sort.patch.0 - doesn't applied. isort() is very often called for 
already sorted and unique arrays (which comes from index), so it should be fast 
as possible for sorted arrays. As I remember ordered array is a worst case for 
qsort(). May be, it will be better choice to use mergesort.




-- 
Teodor Sigaev                                   E-mail: teodor@sigaev.ru
  WWW: http://www.sigaev.ru/