Re: What search algorithm does Oracle use?

Michael Horn wrote in message <34D6307D.CB07836D_at_uidaho.edu>...
>I am a student who is taking a DBA class and have been asked to do a
>presentaion on the search engine that Oracle uses.
>
>Would any of you have any verifiable information on the subject?
>
>(I am a CS major so I know the algorithms for search engines, I just
>dont know WHICH one Oracle uses)

AFAIK Oracle does not use a single search algorithm. The Cost Based Optimiser (CBO) uses its (sometimes weird) "logic" to decide how to process a query. For example, it may decide to use a hash join between a small and a large table, or a nested loop join between 2 large tables. It can also make use of a star join to join a large table with several smaller tables. It can make use of index range scans when doing parallel queries. Bitmap indexes also adds to this complexity.

Each of these different ways of processing data make use of different algorithms. I think that internally Oracle make use of b-tree structures for index processing - but that is just a small part in the overall processing of Oracle.

With Oracle Parallel Server it's even more complex. Parallel query (PQ) slaves are used to do work. The CBO may decide to split up a large full table scan into several "sub" processes and use the PQ slaves to scan and process x number of rows each from a table. The query coordinator manages this parallel processing. The PQ slaves also needs to sync with the query coordinator.

As you can see Oracle is a very complex db engine, and not one that can be described using a single search algorithm to process a query. In order to get an idea on how the Oracle CBO works, read the Oracle Server Tuning Manual - it contains a lot of information on how the different joins works, how hints such as first_row and all_row can be used to influence response times, etc.

regards,
Billy Received on Wed Feb 04 1998 - 00:00:00 CST