Re: how does oracle manage hash maps?

From: Scott <oraracdba_at_yahoo.com>
Date: Thu, 12 Feb 2004 21:14:48 -0800 (PST)
Message-ID: <20040213051448.57700.qmail@web41510.mail.yahoo.com>

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_at_cox.net> 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_at_freelists.org > put 'unsubscribe' in the subject line. > -- > Archives are at > http://www.freelists.org/archives/oracle-l/ > FAQ is at > http://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_at_freelists.org put 'unsubscribe' in the subject line.

--
Archives are at http://www.freelists.org/archives/oracle-l/
FAQ is at http://www.freelists.org/help/fom-serve/cache/1.html
-----------------------------------------------------------------

Received on Thu Feb 12 2004 - 23:14:48 CST