Oracles MAX फ़ंक्शन का बड़ा ओ क्या है?

Question

क्या तालिका में पंक्तियों की संख्या के संबंध में ओरेकल MAX फ़ंक्शन ओ (1), ओ (लॉग एन) या ओ (एन) का time complexity है?

Answer 1

यदि आपके पास कॉलम पर बी-पेड़ इंडेक्स है तो अधिकतम मान ढूंढना ओ (लॉग (एन)) है क्योंकि उत्तर इंडेक्स की अंतिम (या पहली) पंक्ति होगी। मूल्य बी-पेड़ के गहरे नोड्स में संग्रहीत होते हैं जिनमें ऊंचाई ओ (लॉग (एन)) होती है।

किसी सूचकांक के बिना यह ओ (एन) है क्योंकि अधिकतम पंक्ति निर्धारित करने के लिए सभी पंक्तियां पढ़ी जानी चाहिए।

---

नोट: हे (एन) अंकन स्थिरांक पर ध्यान नहीं देता लेकिन असली दुनिया में इन स्थिरांक को नजरअंदाज नहीं किया जा सकता है। डिस्क से पढ़ने और स्मृति से पढ़ने के बीच अंतर परिमाण के कई आदेश है। इंडेक्स के पहले मूल्य तक पहुंचने की संभावना ज्यादातर रैम में की जा सकती है, जबकि एक विशाल टेबल के पूर्ण टेबल स्कैन को डिस्क से ज्यादातर पढ़ने की आवश्यकता होगी।

Answer 2

असल में, एक क्वेरी, एक टेबल परिभाषा, और एक क्वेरी योजना निर्दिष्ट किए बिना कहना मुश्किल है।

यदि आपके पास ऐसी तालिका है जिसमें कॉलम पर कोई अनुक्रमणिका नहीं है, तो आप MAX पर कंप्यूटिंग कर रहे हैं, ओरेकल को एक पूर्ण टेबल स्कैन करना होगा। यह ओ (एन) होने जा रहा है क्योंकि आपको तालिका में हर ब्लॉक को स्कैन करना होगा। आप क्वेरी प्लान को देखकर देख सकते हैं।

हम 100,000 पंक्तियों के साथ एक मेज पैदा करते हैं और यह सुनिश्चित करें कि पंक्तियों यथोचित बड़े हैं एक CHAR(1000) स्तंभ

SQL> create table foo(col1 number, col2 char(1000)); 

Table created. 

SQL> insert into foo 
    2 select level, lpad('a',1000) 
    3  from dual 
    4 connect by level <= 100000; 

100000 rows created. 

अभी सेवा का उपयोग करता हूँ, हम बुनियादी MAX ऑपरेशन के लिए योजना देख सकते हैं। आप स्तंभ आप की MAX कंप्यूटिंग रहे हैं पर एक सूचकांक बनाते हैं यह एक पूर्ण तालिका स्कैन (एक हे (एन) आपरेशन)

SQL> set autotrace on; 
SQL> select max(col1) 
    2 from foo; 

MAX(COL1) 
---------- 
    100000 


Execution Plan 
---------------------------------------------------------- 
Plan hash value: 1342139204 

--------------------------------------------------------------------------- 
| Id | Operation   | Name | Rows | Bytes | Cost (%CPU)| Time  | 
--------------------------------------------------------------------------- 
| 0 | SELECT STATEMENT |  |  1 | 13 | 4127 (1)| 00:00:50 | 
| 1 | SORT AGGREGATE |  |  1 | 13 |   |   | 
| 2 | TABLE ACCESS FULL| FOO | 106K| 1350K| 4127 (1)| 00:00:50 | 
--------------------------------------------------------------------------- 

Note 
----- 
    - dynamic sampling used for this statement (level=2) 


Statistics 
---------------------------------------------------------- 
     29 recursive calls 
      1 db block gets 
     14686 consistent gets 
      0 physical reads 
     176 redo size 
     527 bytes sent via SQL*Net to client 
     523 bytes received via SQL*Net from client 
      2 SQL*Net roundtrips to/from client 
      0 sorts (memory) 
      0 sorts (disk) 
      1 rows processed 

कर रही है, ओरेकल सूचकांक पर एक MIN/MAX scan कर सकते हैं। यह एक ओ (लॉग एन) ऑपरेशन है यदि वह ऑप्टिमाइज़र चुनने की योजना है। बेशक, एक व्यावहारिक मामले के रूप में, यह कार्यात्मक रूप से ओ (1) ऑपरेशन है क्योंकि एक सूचकांक की ऊंचाई कभी वास्तविक रूप से 4 या 5 से अधिक नहीं जा रही है - यहां निरंतर शर्तों पर हावी होने जा रहे हैं।

SQL> create index idx_foo_col1 
    2  on foo(col1); 

Index created. 

SQL> select max(col1) 
    2 from foo; 

MAX(COL1) 
---------- 
    100000 


Execution Plan 
---------------------------------------------------------- 
Plan hash value: 817909383 

------------------------------------------------------------------------------------------- 
| Id | Operation     | Name   | Rows | Bytes | Cost (%CPU)| Time  | 
------------------------------------------------------------------------------------------- 
| 0 | SELECT STATEMENT   |    |  1 | 13 |  2 (0)| 00:00:01 | 
| 1 | SORT AGGREGATE   |    |  1 | 13 |   |   | 
| 2 | INDEX FULL SCAN (MIN/MAX)| IDX_FOO_COL1 |  1 | 13 |  2 (0)| 00:00:01 | 
------------------------------------------------------------------------------------------- 

Note 
----- 
    - dynamic sampling used for this statement (level=2) 

Statistics 
---------------------------------------------------------- 
      5 recursive calls 
      0 db block gets 
     83 consistent gets 
      1 physical reads 
      0 redo size 
     527 bytes sent via SQL*Net to client 
     523 bytes received via SQL*Net from client 
      2 SQL*Net roundtrips to/from client 
      0 sorts (memory) 
      0 sorts (disk) 
      1 rows processed 

लेकिन फिर चीजें कठिन हो जाती हैं। MIN और MAX दोनों में एक ही ओ (लॉग एन) व्यवहार अलग-अलग है। लेकिन यदि आपके पास एक ही प्रश्न में MIN और MAX दोनों हैं, तो अचानक आप ओ (एन) ऑपरेशन पर वापस आ गए हैं। ओरेकल (11.2) के रूप में एक विकल्प हड़पने दोनों पहले खंड और एक सूचकांक

SQL> ed 
Wrote file afiedt.buf 

    1 select min(col1), max(col1) 
    2* from foo 
SQL>/

MIN(COL1) MAX(COL1) 
---------- ---------- 
     1  100000 


Execution Plan 
---------------------------------------------------------- 
Plan hash value: 1342139204 

--------------------------------------------------------------------------- 
| Id | Operation   | Name | Rows | Bytes | Cost (%CPU)| Time  | 
--------------------------------------------------------------------------- 
| 0 | SELECT STATEMENT |  |  1 | 13 | 4127 (1)| 00:00:50 | 
| 1 | SORT AGGREGATE |  |  1 | 13 |   |   | 
| 2 | TABLE ACCESS FULL| FOO | 106K| 1350K| 4127 (1)| 00:00:50 | 
--------------------------------------------------------------------------- 

Note 
----- 
    - dynamic sampling used for this statement (level=2) 


Statistics 
---------------------------------------------------------- 
      4 recursive calls 
      0 db block gets 
     14542 consistent gets 
      0 physical reads 
      0 redo size 
     601 bytes sent via SQL*Net to client 
     523 bytes received via SQL*Net from client 
      2 SQL*Net roundtrips to/from client 
      0 sorts (memory) 
      0 sorts (disk) 
      1 rows processed 

बेशक

के अंतिम खंड को लागू नहीं किया, ओरेकल के बाद के संस्करणों में, इस अनुकूलन लागू किया जा सकता है और इस के लिए वापस जाना होगा एक ओ (लॉग एन) ऑपरेशन होने के लिए। बेशक, आप एक अलग क्वेरी प्लान प्राप्त करने के लिए क्वेरी को फिर से लिख सकते हैं जो ओ (लॉग एन)

SQL> ed 
Wrote file afiedt.buf 

    1 select (select min(col1) from foo) min, 
    2   (select max(col1) from foo) max 
    3* from dual 
SQL> 
SQL>/

     MIN  MAX 
---------- ---------- 
     1  100000 


Execution Plan 
---------------------------------------------------------- 
Plan hash value: 3561244922 

------------------------------------------------------------------------------------------- 
| Id | Operation     | Name   | Rows | Bytes | Cost (%CPU)| Time  | 
------------------------------------------------------------------------------------------- 
| 0 | SELECT STATEMENT   |    |  1 |  |  2 (0)| 00:00:01 | 
| 1 | SORT AGGREGATE   |    |  1 | 13 |   |   | 
| 2 | INDEX FULL SCAN (MIN/MAX)| IDX_FOO_COL1 |  1 | 13 |  2 (0)| 00:00:01 | 
| 3 | SORT AGGREGATE   |    |  1 | 13 |   |   | 
| 4 | INDEX FULL SCAN (MIN/MAX)| IDX_FOO_COL1 |  1 | 13 |  2 (0)| 00:00:01 | 
| 5 | FAST DUAL     |    |  1 |  |  2 (0)| 00:00:01 | 
------------------------------------------------------------------------------------------- 


Note 
----- 
    - dynamic sampling used for this statement (level=2) 


Statistics 
---------------------------------------------------------- 
      7 recursive calls 
      0 db block gets 
     166 consistent gets 
      0 physical reads 
      0 redo size 
     589 bytes sent via SQL*Net to client 
     523 bytes received via SQL*Net from client 
      2 SQL*Net roundtrips to/from client 
      0 sorts (memory) 
      0 sorts (disk) 
      1 rows processed