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(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/