Chỉ mục thời gian không đổi cho cột chuỗi trên cơ sở dữ liệu Oracle

Các cụm băm có thể cung cấp thời gian truy cập O (1), nhưng không cung cấp thời gian thực thi ràng buộc O (1). Tuy nhiên, trong thực tế, thời gian truy cập không đổi của một cụm băm kém hơn thời gian truy cập O (log N) của một chỉ mục cây b thông thường. Ngoài ra, các cụm khó định cấu hình hơn và không mở rộng quy mô tốt cho một số hoạt động.

Tạo cụm băm

drop table orders_cluster;
drop cluster cluster1;

create cluster cluster1
(
    MerchantID number,
    TransactionID varchar2(20)
)
single table hashkeys 10000; --This number is important, choose wisely!

create table orders_cluster
(
    id number,
    MerchantID number,
    TransactionID varchar2(20)
) cluster cluster1(merchantid, transactionid);

--Add 1 million rows.  20 seconds.
begin
    for i in 1 .. 10 loop
        insert into orders_cluster
        select rownum + i * 100000, mod(level, 100)+ i * 100000, level
        from dual connect by level <= 100000;
        commit;
    end loop;
end;
/

create unique index orders_cluster_idx on orders_cluster(merchantid, transactionid);

begin
    dbms_stats.gather_table_stats(user, 'ORDERS_CLUSTER');
end;
/

Tạo Bảng Thông thường (Để So sánh)

drop table orders_table;

create table orders_table
(
    id number,
    MerchantID number,
    TransactionID varchar2(20)
) nologging;

--Add 1 million rows.  2 seconds.
begin
    for i in 1 .. 10 loop
        insert into orders_table
        select rownum + i * 100000, mod(level, 100)+ i * 100000, level
        from dual connect by level <= 100000;
        commit;
    end loop;
end;
/

create unique index orders_table_idx on orders_table(merchantid, transactionid);

begin
    dbms_stats.gather_table_stats(user, 'ORDERS_TABLE');
end;
/

Ví dụ về dấu vết

SQL * Plus Autotrace là một cách nhanh chóng để tìm kế hoạch giải thích và theo dõi hoạt động I / O trên mỗi câu lệnh. Số lượng yêu cầu I / O được gắn nhãn là "nhất quán được" và là một cách tốt để đo lường khối lượng công việc đã hoàn thành. Mã này trình bày cách các số được tạo cho các phần khác. Các truy vấn thường cần được chạy nhiều lần để làm nóng mọi thứ.

SQL> set autotrace on;
SQL> select * from orders_cluster where merchantid = 100001 and transactionid = '2';

no rows selected


Execution Plan
----------------------------------------------------------
Plan hash value: 621801084

------------------------------------------------------------------------------------
| Id  | Operation         | Name           | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |                |     1 |    16 |     1   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS HASH| ORDERS_CLUSTER |     1 |    16 |     1   (0)| 00:00:01 |
------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - access("MERCHANTID"=100001 AND "TRANSACTIONID"='2')


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

SQL>

Tìm Hashkey tối ưu, Đánh đổi

Để có hiệu suất đọc tối ưu, tất cả các xung đột băm phải nằm gọn trong một khối (tất cả Oracle I / O được thực hiện trên mỗi khối, thường là 8K). Để có được quyền lưu trữ lý tưởng rất khó và đòi hỏi bạn phải biết thuật toán băm, kích thước lưu trữ (không giống với kích thước khối) và số lượng khóa băm (nhóm). Oracle có một thuật toán và kích thước mặc định nên có thể chỉ tập trung vào một thuộc tính là số lượng khóa băm.

Nhiều khóa băm hơn dẫn đến ít va chạm hơn. Điều này tốt cho hiệu suất TABLE ACCESS HASH vì chỉ có một khối để đọc. Dưới đây là số lượng nhất quán cho các kích thước khóa băm khác nhau. Để so sánh, một quyền truy cập chỉ mục cũng được bao gồm. Với đủ số băm, số khối giảm xuống còn số tối ưu, 1.

Method          Consistent Gets (for transactionid = 1, 20, 300, 4000, and 50000)
Index           4,  3,  3,  3,  3
Hashkeys 100    1, 31, 31, 31, 31
Hashkeys 1000   1,  3,  4,  4,  4
Hashkeys 10000  1,  1,  1,  1,  1

Nhiều khóa băm hơn cũng dẫn đến nhiều nhóm hơn, nhiều dung lượng bị lãng phí hơn và hoạt động ĐẦY ĐỦ TRUY CẬP BẢNG chậm hơn.

Table type      Space in MB
HeapTable       24MB
Hashkeys 100    26MB
hashkeys 1000   30MB
hashkeys 10000  81MB

Để tạo lại kết quả của tôi, hãy sử dụng một truy vấn mẫu như select * from orders_cluster where merchantid = 100001 and transactionid = '1'; và thay đổi giá trị cuối cùng thành 1, 20, 300, 4000 và 50000.

So sánh hiệu suất

Mức độ nhất quán có thể dự đoán và dễ dàng đo lường, nhưng vào cuối ngày, chỉ có thời gian trên đồng hồ treo tường là quan trọng. Đáng ngạc nhiên, quyền truy cập chỉ mục với mức độ nhất quán gấp 4 lần vẫn nhanh hơn so với kịch bản cụm băm tối ưu.

--3.5 seconds for b-tree access.
declare
    v_count number;
begin
    for i in 1 .. 100000 loop
        select count(*)
        into v_count
        from orders_table
        where merchantid = 100000 and transactionid = '1';
    end loop;
end;
/

--3.8 seconds for hash cluster access.
declare
    v_count number;
begin
    for i in 1 .. 100000 loop
        select count(*)
        into v_count
        from orders_cluster
        where merchantid = 100000 and transactionid = '1';
    end loop;
end;
/

Tôi cũng đã thử kiểm tra với các vị từ biến nhưng kết quả tương tự.

Nó có mở rộng quy mô không?

Không, các cụm băm không chia tỷ lệ. Bất chấp độ phức tạp thời gian O (1) của TABLE ACCESS HASH và độ phức tạp thời gian O (log n) của INDEX UNIQUE SCAN, các cụm băm dường như không bao giờ tốt hơn chỉ mục b-tree.

Tôi đã thử mã mẫu ở trên với 10 triệu hàng. Cụm băm tải rất chậm và vẫn hoạt động kém chỉ mục về hiệu suất SELECT. Tôi đã cố gắng mở rộng quy mô nó lên đến 100 triệu hàng nhưng quá trình chèn sẽ mất 11 ngày.

Tin tốt là cây b * mở rộng quy mô tốt. Việc thêm 100 triệu hàng vào ví dụ trên chỉ yêu cầu 3 cấp trong chỉ mục. Tôi đã xem tất cả DBA_INDEXES đối với một môi trường cơ sở dữ liệu lớn (hàng trăm cơ sở dữ liệu và một petabyte dữ liệu) - chỉ số tồi tệ nhất chỉ có 7 cấp. Và đó là chỉ số bệnh lý trên VARCHAR2(4000) cột. Trong hầu hết các trường hợp, các chỉ mục b-tree của bạn sẽ luôn nông bất kể kích thước bảng.

Trong trường hợp này, O (log n) đánh bại O (1).

Nhưng TẠI SAO?

Hiệu suất cụm băm kém có lẽ là nạn nhân của nỗ lực của Oracle nhằm đơn giản hóa mọi thứ và ẩn các loại chi tiết cần thiết để làm cho một cụm băm hoạt động tốt. Các cụm rất khó để thiết lập và sử dụng đúng cách và dù sao cũng hiếm khi mang lại lợi ích đáng kể. Oracle đã không nỗ lực nhiều trong vài thập kỷ qua.

Những người bình luận đúng rằng một chỉ mục b-cây đơn giản là tốt nhất. Nhưng không rõ tại sao điều đó lại đúng và thật tốt khi nghĩ về các thuật toán được sử dụng trong cơ sở dữ liệu.