Re: Array intersection

On Wed, Oct 17, 2007 at 10:37:23AM -0500, Josh Trutwin wrote:
> On Wed, 17 Oct 2007 10:19:43 -0500
> Josh Trutwin <josh(at)trutwins(dot)homeip(dot)net> wrote:
>
> > Hi,
> >
> > Is it possible to find the intersection of two array values?
> >
> > a = '{1,2,3}'
> > b = '{2,3,4}'
> >
> > a intersect b = '{2,3}'
> >
> > Assume I need to write a pl/pgsql function to do this.
>
> nm - I just wrote a function - though curious if this is the most
> effecient way:
>
>
> CREATE OR REPLACE FUNCTION array_has_intersect (array1 INTEGER[],
> array2 INTEGER[]) RETURNS BOOLEAN
> AS $$
> BEGIN
> IF array1 IS NULL OR array2 IS NULL THEN
> RETURN FALSE;
> END IF;
>
> FOR i IN ARRAY_LOWER(array1,1) .. ARRAY_UPPER(array1,1) LOOP
> FOR j IN ARRAY_LOWER(array2,1) .. ARRAY_UPPER(array2,1) LOOP
> IF (array1[i] = array2[j]) THEN
> RETURN TRUE;
> END IF;
> END LOOP;
> END LOOP;
>
> RETURN FALSE;
> END;
> $$ LANGUAGE PLPGSQL;

This is only going to work for one-dimensional arrays (I'm not sure how
you would ever fix that with the support postgres has for arrays) but
the (computational) complexity of having an embedded FOR loops looks bad
for performance. As you can already use '=ANY' syntax to search inside
an array, you may as well use that---it's probably a bit more faster
than the plpgsql work-alike. Leading to the following implementation of
intersect:

CREATE OR REPLACE FUNCTION array_intersect (array1 INTEGER[],array2 INTEGER[]) RETURNS INTEGER[]
AS $$
DECLARE
out INTEGER[];
BEGIN
IF array1 IS NULL OR array2 IS NULL THEN
RETURN '[]';
END IF;
FOR i IN ARRAY_LOWER(array1,1) .. ARRAY_UPPER(array1,1) LOOP
IF (array1[i] =ANY (array2)) THEN
out := array_append(out,array1[i]);
END IF;
END LOOP;
RETURN out;
END;
$$ LANGUAGE PLPGSQL;

It seems to work for me, but as a side effect will leave the array sorted
in the same order as the first parameter and with any duplicates it has.
Even more annoyingly if there is no intersection it will return NULL
instead of an empty array, how do I fix this?

Sam

p.s. plpgsql is badly in need of parametric polymorphism, the silly
anyarray/anyelement it's got at the moment means it's impossible to
declare an array of the same type as the type of its parameters.