Re: CYCLE and SEARCH [was Re: Common Table Expressions (WITH RECURSIVE) patch]

David Fetter <david(at)fetter(dot)org> writes:
> How hard would it be to add the infrastructure for CYCLE?

Personally I'm more interested in getting the recursive UNION (without
ALL) case to work.

I think that this might just be a matter of drawing on support that's
already there: have RecursiveUnion maintain a hash table of rows it's
already seen, and discard anything coming from either the non-recursive
term or the recursive term that is found to be already present in the
hash table.

Two objections to this are (a) it doesn't work for datatypes without
hash equality support, and (b) it would fail for recursion output
exceeding available memory. However, the alternative of using
sort-and-uniq to detect duplicates seems pretty horrid in this situation
--- you'd need a fresh sort and mergejoin-like scan for every iteration
of the recursive term. And it would become impractical to return rows
immediately after they're emitted by the subqueries. So I'd be willing
to live with only supporting the hash implementation.

If no objections, I'll look at that next week ...

regards, tom lane