Subject: Re: New type and pg_operator.

From: [email-masked] (Paul M. Aoki)
Date: Fri, 15 Jul 94 05:34:41 -0700

the info needed to add new operators and stuff is in chapter 13 of
the user manual.

Wojtek Bogusz <[email-masked]> writes:
> surprising for me that for all operators connected with char/text types
> field oprprec (operator precedence) is equal 0. Why ?

doesn't work anyway.

>  Does exist some (simple :-) explanation what join strategies mean ?

sure, in any database textbook..

the nickle version:

nestloop join - compare everything in A to everything in B

sortmerge join - exploit sorted order to avoid scanning things in 
B known not to match the current element of A (too big, too small,
whatever).

hash join - join only those elements that fall into the same hash 
bucket (same idea - if it doesn't hash into the same bucket, it's 
not bitwise equal, so you don't have to look at it)

> And why hash join strategy is defined (oprcanhash = t) just for "=" ?

unless you use arcane order-preserving hash functions, hash join 
only makes sense for bitwise equality.

> And why
> merge-sort join strategy is not defined for all char/text operators ie. 
> oprrsortop and oprlsort are equal to 0 ?

i have no idea why not.
--
  Paul M. Aoki          |  University of California at Berkeley
  [email-masked]  |  Dept. of EECS, Computer Science Division (#1776) 
                        |  Berkeley, CA 94720-1776

==============================================================================
   To add/remove yourself to/from the POSTGRES mailing list: send mail with 
   the subject line ADD or DEL to "[email-masked]"

   If this fails, send mail to "[email-masked]" and
   a human will deal with it.  DO NOT post to the "postgres" mailing list.
==============================================================================

---

From: Wojtek Bogusz <[email-masked]>
Date: Fri, 15 Jul 1994 14:00:40 +0200 (MET DST)

Hello,

 I am trying to add a new type to postgres. It is a king of char, char2,
char4, ... and text type but for different language than english. I took a
look in to pg_operators to see how they where defined :-) It is a bit
surprising for me that for all operators connected with char/text types
field oprprec (operator precedence) is equal 0. Why ?

 Does exist some (simple :-) explanation what join strategies mean ? And
why hash join strategy is defined (oprcanhash = t) just for "=" ? And why
merge-sort join strategy is not defined for all char/text operators ie. 
oprrsortop and oprlsort are equal to 0 ?

 Thank You
 Wojtek Bogusz

---

From: Venkata Nagarjuna Rao Goli <[email-masked]>
Date: Fri, 15 Jul 1994 11:52:05 -0500 (CDT)

> unless you use arcane order-preserving hash functions, hash join 
		^^^^^^^^^^^^^^^^^^^^^^^^^^
> only makes sense for bitwise equality.
			^^^^^^^^^^^^^^^^
Please explain me

What are those order preserving hash functions?

and 

What do you mean by bitwise equality?

Thank you,
Goli Nagarjuna.

---

From: [email-masked] (Kai Petzke)
Date: Sat, 16 Jul 1994 11:45:58 +0200 (MET DST)

> > unless you use arcane order-preserving hash functions, hash join 

Hash functions calculate a short "checksum" from a datum.  Examples
are the CRC-32 used by many file transfer software or the "sum"
command of your operating system.  If your datums are long, the hash
might be much shorter, resulting in much faster index operations.

But because of the data reduction, it is in general impossible to
preserve the ordering of the data.  If you compare the two datums
"Miller, Cathlenn" and "Miller, Richard", Cathlenn comes first.  But
it is not said, that the hash of "Miller, Cathlenn" is smaller than
the hash of "Miller, Richard".

Another backdraw is, that two different datums may have the same
hash value.  So, even if two hashs are identical, you have to
check the datums as well.

So hashs make sense, where you have to index a string field, and
the only operation you are going to perform is exact string match.
For example, most modern shells use a hash table for system commands.

> What do you mean by bitwise equality?

That every bit of two values is identical.

---

From: [email-masked] (Paul M. Aoki)
Date: Fri, 12 Aug 94 01:35:13 -0700

[email-masked] (Kai Petzke) writes:
> > > unless you use arcane order-preserving hash functions,
> Hash functions calculate a short "checksum" from a datum.
> preserve the ordering of the data.

41. CONFERENCE PAPER
    Fox, E.A.; Qi Fan Chen; Daoud, A.M.; Heath, L.S.
      Order preserving minimal perfect hash functions and information
    retrieval.
    IN:  Proceedings of the 13th International Conference on Research and
    Development in Information Retrieval. (Proceedings of the 13th
    International Conference on Research and Development in Information
    Retrieval, Brussels, Belgium, 5-7 Sept. 1990). Edited by: Vidick, J.L. New
    York, NY, USA: ACM, 1989. p. 279-312.
      Pub type:  Practical; Theoretical or Mathematical.

Abstract: Rapid access to information is essential for a wide variety of
     retrieval systems and applications. Hashing has long been used when the
     fastest possible direct search is desired, but is generally not
     appropriate when sequential or range searches are also required. The paper
     describes a hashing method, developed for collections that are relatively
     static, that supports both direct and sequential access. Indeed, the
     algorithm described gives hash functions that are optimal in terms of time
     and hash table space utilization, and that preserve any a priori ordering
     desired. Furthermore, the resulting order preserving minimal perfect has
     functions (OPMPHFs) can be found using space and time that is on average
     linear in the number of keys involved.

i happened to run across this while searching for "linear hashing"
references.  whew.  i was thinking i was totally nuts for thinking
such a thing existed.  after some thought, i also dimly recall that
there were also some later papers on the subject from fox's group in
the ACM SIGIR Forum as well.

(which is not to say that anything else i have ever said, here or
anywhere else, is either right or sensible.)
--
  Paul M. Aoki          |  University of California at Berkeley
  [email-masked]  |  Dept. of EECS, Computer Science Division (#1776) 
                        |  Berkeley, CA 94720-1776