Re: Re: how does oracle manage hash maps?
- From: <ryan.gaffuri@xxxxxxx>
- To: oracle-l@xxxxxxxxxxxxx
- Date: Fri, 13 Feb 2004 8:57:40 -0500
I know how the LRU works with linked lists. I've written linked list code
before.
From your diagram I take it that, oracle builds the hash map in the pga. The
number of buckets is a prime number.
Its hard to read your diagram. I'm not quite sure how the hash map links to the
buffer chain. In basic hashing methodology each hash bucket points to a
specific value.
Jonathan lewis stated that in making the hash map oracle grabs the actually
values you want to return. However, those values don't go into the PGA with the
hash map do they? I thought all data elements went into the buffer cache?
>
> From: Scott <oraracdba@xxxxxxxxx>
> Date: 2004/02/13 Fri AM 12:14:48 EST
> To: oracle-l@xxxxxxxxxxxxx
> CC: ryan.gaffuri@xxxxxxx
> Subject: Re: how does oracle manage hash maps?
>
> I hope this diagram shows up. Yahoo is not the best
> for creating diagrams.
>
> This example applies to Oracle7 and Oracle8, although
> in reality there may be multiple LRU chains. In
> Oracle8i the LRU concept is replaced by a touch-count
> algorithm but the idea is the same.
>
> LRU Chain:
> Most Recent Doubly linked list Least Recent
> +------+------+------+ - - - -
> +------+------+------+------+------+
> | | | | | | PTR |
> | | |
> +------+------+------+ - - - -
> +------+------+------+------+------+
> Newly used buffers | We search for
> are placed at this end. | LRU just FREE buffers
> | points from this end
> LRUW Chain (Dirty List): | to of the LRU.
> +------+------+ - - +------+ | buffer Dirty
> buffers
> | | | | | | headers. are
> moved
> to
> +------+------+ - - +------+ | LRUW if
> there
> (Cleared by DBWR) | is room.
> |
> |
> Hashing is |
> based on DBA |
> modulo the |
> number of buckets. |
> A LATCH protects |
> each hash chain |
> |
> ,-------.
> --------------------------------/----------------------+
> Double
> | Hash |
> <------------------------------/---------------------+
> | linked
> | Bucket| ,--------. ,---------V----.
> ,--------. | | hash
> | 1 | ----->| Buffer |--->| Buffer
> |---->| Buffer |--+ | chain.
> `-------' <-----| Header |<---| Header
> |<----| Header |<---+
> | 40 | | 2 |
> | 999 |
> | | | |
> | |
> |--------| | |
> | |
> |Usr|Wait| | |
> | |
> `--------' `--------------'
> `--------'
> ,-------. | | |
> :
> |SO. |--------------' | |
>
> | | | |
>
> `-------' | |
>
> Buffer Handle | |
>
> state object | |
> | |
> (actual DB blocks)
> | |
> ,-------------------.
> ,-------. | |
> | 1 |
> | Hash | | |
> | |
> | Bucket| | |
> +-------------------+
> | 2 | -->... |
> `---------->| 2 |
> `-------' <--... |
> | |
> |
> +-------------------+
> |
> : :
> |
> +-------------------+
> :
> `-------------------------->| 40 Data Block |
> :
> | |
>
> +-------------------+
>
> : :
>
> +-------------------+
> ,-------.
> | 999 |
> | Hash |
> | |
> | Bucket|
> +-------------------+
> | N |
> | 1000 |
> `-------'
> | |
> There are a PRIME
> +-------------------+
> number of Hash buckets.
>
>
> --- Ryan <ryan.gaffuri@xxxxxxx> wrote:
> >
> >
> > When Oracle performs a hash-join it first creates a
> > hashmap. This hash map is placed in the PGA. Now,
> > Oracle uses linked lists to manage the buffer cache.
> > Traditional hashing uses an array for the hash, then
> > a linked list for the collisions. How does Oracle
> > manage this?
> >
> ----------------------------------------------------------------
> > Please see the official ORACLE-L FAQ:
> > http://www.orafaq.com
> >
> ----------------------------------------------------------------
> > To unsubscribe send email to:
> > oracle-l-request@xxxxxxxxxxxxx
> > put 'unsubscribe' in the subject line.
> > --
> > Archives are at
> > //www.freelists.org/archives/oracle-l/
> > FAQ is at
> > //www.freelists.org/help/fom-serve/cache/1.html
> >
> -----------------------------------------------------------------
>
>
> __________________________________
> Do you Yahoo!?
> Yahoo! Finance: Get your refund fast by filing online.
> http://taxes.yahoo.com/filing.html
> ----------------------------------------------------------------
> Please see the official ORACLE-L FAQ: http://www.orafaq.com
> ----------------------------------------------------------------
> To unsubscribe send email to: oracle-l-request@xxxxxxxxxxxxx
> put 'unsubscribe' in the subject line.
> --
> Archives are at //www.freelists.org/archives/oracle-l/
> FAQ is at //www.freelists.org/help/fom-serve/cache/1.html
> -----------------------------------------------------------------
>
----------------------------------------------------------------
Please see the official ORACLE-L FAQ: http://www.orafaq.com
----------------------------------------------------------------
To unsubscribe send email to: oracle-l-request@xxxxxxxxxxxxx
put 'unsubscribe' in the subject line.
--
Archives are at //www.freelists.org/archives/oracle-l/
FAQ is at //www.freelists.org/help/fom-serve/cache/1.html
-----------------------------------------------------------------
Other related posts:
