agora inbox for postgres@postgres.berkeley.edu
help / color / mirror / Atom feedRe: New type and pg_operator.
4+ messages / 4 participants
[nested] [flat]
* Re: New type and pg_operator.
@ 1994-07-15 12:34 Paul M. Aoki <aoki@CS.Berkeley.EDU>
0 siblings, 1 reply; 4+ messages in thread
From: Paul M. Aoki @ 1994-07-15 12:34 UTC (permalink / raw)
To: Wojtek Bogusz <Wojtek.Bogusz@fuw.edu.pl>; +Cc: legacy
the info needed to add new operators and stuff is in chapter 13 of
the user manual.
Wojtek Bogusz <Wojtek.Bogusz@fuw.edu.pl> 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
aoki@CS.Berkeley.EDU | 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 "postgres-request@postgres.Berkeley.EDU"
If this fails, send mail to "post_questions@postgres.Berkeley.EDU" and
a human will deal with it. DO NOT post to the "postgres" mailing list.
==============================================================================
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: New type and pg_operator.
@ 1994-07-15 16:52 Venkata Nagarjuna Rao Goli <goli@plains.NoDak.edu>
parent: Paul M. Aoki <aoki@CS.Berkeley.EDU>
0 siblings, 1 reply; 4+ messages in thread
From: Venkata Nagarjuna Rao Goli @ 1994-07-15 16:52 UTC (permalink / raw)
To: Paul M. Aoki <aoki@CS.Berkeley.EDU>; +Cc: legacy
>
> 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.
==============================================================================
To add/remove yourself to/from the POSTGRES mailing list: send mail with
the subject line ADD or DEL to "postgres-request@postgres.Berkeley.EDU"
If this fails, send mail to "post_questions@postgres.Berkeley.EDU" and
a human will deal with it. DO NOT post to the "postgres" mailing list.
==============================================================================
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: New type and pg_operator.
@ 1994-07-16 09:45 Kai Petzke <wpp@marie.physik.tu-berlin.de>
parent: Venkata Nagarjuna Rao Goli <goli@plains.NoDak.edu>
0 siblings, 1 reply; 4+ messages in thread
From: Kai Petzke @ 1994-07-16 09:45 UTC (permalink / raw)
To: goli@plains.NoDak.edu; +Cc: legacy
>
>
> >
> > 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?
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.
> and
>
> What do you mean by bitwise equality?
That every bit of two values is identical.
==============================================================================
To add/remove yourself to/from the POSTGRES mailing list: send mail with
the subject line ADD or DEL to "postgres-request@postgres.Berkeley.EDU"
If this fails, send mail to "post_questions@postgres.Berkeley.EDU" and
a human will deal with it. DO NOT post to the "postgres" mailing list.
==============================================================================
^ permalink raw reply [nested|flat] 4+ messages in thread
* hash functions [was: New type and pg_operator.]
@ 1994-08-12 08:35 Paul M. Aoki <aoki@cs.Berkeley.EDU>
parent: Kai Petzke <wpp@marie.physik.tu-berlin.de>
0 siblings, 0 replies; 4+ messages in thread
From: Paul M. Aoki @ 1994-08-12 08:35 UTC (permalink / raw)
To: Kai Petzke <wpp@marie.physik.tu-berlin.de>; +Cc: goli@plains.NoDak.edu; legacy
wpp@marie.physik.tu-berlin.de (Kai Petzke) writes:
> > > unless you use arcane order-preserving hash functions,
> > What are those order preserving hash functions?
> Hash functions calculate a short "checksum" from a datum.
> But because of the data reduction, it is in general impossible to
> 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
aoki@CS.Berkeley.EDU | 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 "postgres-request@postgres.Berkeley.EDU"
If this fails, send mail to "post_questions@postgres.Berkeley.EDU" and
a human will deal with it. DO NOT post to the "postgres" mailing list.
==============================================================================
^ permalink raw reply [nested|flat] 4+ messages in thread
end of thread, other threads:[~1994-08-12 08:35 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
1994-07-15 12:34 Re: New type and pg_operator. Paul M. Aoki <aoki@CS.Berkeley.EDU>
1994-07-15 16:52 ` Venkata Nagarjuna Rao Goli <goli@plains.NoDak.edu>
1994-07-16 09:45 ` Kai Petzke <wpp@marie.physik.tu-berlin.de>
1994-08-12 08:35 ` hash functions [was: New type and pg_operator.] Paul M. Aoki <aoki@cs.Berkeley.EDU>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox