Big-O cho SQL là gì, cho một bảng có n hàng và tôi muốn trả về kết quả m?Big-O cho SQL là gì?
Và Big-O cho hoạt động Update hoặc delete hoặc hoạt động Create là gì?
Tôi đang nói về mysql và sqlite nói chung.
Vì bạn không kiểm soát thuật toán được chọn, không có cách nào để biết trực tiếp. Tuy nhiên, không có chỉ mục SELECT nên là O (n) (một bảng quét phải kiểm tra mọi bản ghi có nghĩa là nó sẽ mở rộng với kích thước của bảng).
Với chỉ mục SELECT có thể là O (log (n)) (mặc dù nó sẽ phụ thuộc vào thuật toán được sử dụng để lập chỉ mục và các thuộc tính của dữ liệu nếu điều đó đúng với bất kỳ bảng thực nào). Để xác định kết quả của bạn cho bất kỳ bảng hoặc truy vấn nào bạn phải sử dụng để định cấu hình dữ liệu thế giới thực để chắc chắn.
INSERT không có chỉ mục phải rất nhanh (gần với O (1)) trong khi UPDATE cần tìm các bản ghi đầu tiên và vì vậy sẽ chậm hơn (hơi) so với CHỌN đưa bạn đến đó.
INSERT với chỉ mục có thể sẽ lại nằm trong ballpark của O (log (n^2)) khi cây chỉ mục cần được cân bằng lại, gần với O (log (n)) nếu không. Sự suy giảm tương tự sẽ xảy ra với một UPDATE nếu nó ảnh hưởng đến các hàng được lập chỉ mục, trên đầu trang của các chi phí SELECT.
Tất cả các phiên cược bị tắt khi bạn đang nói về JOIN trong hỗn hợp: bạn sẽ phải lập hồ sơ và sử dụng các công cụ ước tính truy vấn cơ sở dữ liệu của bạn để đọc trên đó. Cũng lưu ý rằng nếu truy vấn này là hiệu suất quan trọng, bạn nên lại tiểu sử theo thời gian vì thuật toán được trình tối ưu hóa truy vấn của bạn sử dụng sẽ thay đổi khi thay đổi tải dữ liệu.
Một điều khác cần lưu ý ... big-O không cho bạn biết về chi phí cố định cho mỗi giao dịch. Đối với các bảng nhỏ hơn có thể cao hơn chi phí công việc thực tế. Ví dụ: việc thiết lập, xé nhỏ và chi phí liên lạc của truy vấn mạng chéo cho một hàng duy nhất chắc chắn sẽ lớn hơn việc tìm kiếm bản ghi được lập chỉ mục trong một bảng nhỏ.
Vì lý do này, tôi thấy rằng việc có thể nhóm một nhóm truy vấn có liên quan trong một lô có thể có tác động lớn đến hiệu suất hơn bất kỳ tối ưu nào tôi đã làm cho cơ sở dữ liệu phù hợp.
Phù hợp với nhận xét về thứ tự của một lựa chọn có tham gia, lưu ý rằng một phép chọn với phép nối đôi vào một bảng có thể là n^2. Ví dụ; chọn * từ bảng trong đó id> (chọn avg (id) từ bảng) có thể phát triển hình vuông trên mỗi bản ghi, mà không sử dụng các chỉ mục. –
Tôi nghĩ câu trả lời thực chỉ có thể được xác định trên cơ sở từng trường hợp (cơ sở dữ liệu, thiết kế bảng, chỉ mục, v.v.).
Tuy nhiên, nếu bạn là người dùng MS SQL Server, bạn có thể tự làm quen với Kế hoạch thực hiện ước tính trong Query Analyzer (2000) hoặc Management Studio (2005+). Điều đó cung cấp cho bạn rất nhiều thông tin bạn có thể sử dụng để phân tích.
Tất cả phụ thuộc vào cách (tốt) bạn viết SQL của bạn và cơ sở dữ liệu của bạn được thiết kế như thế nào cho hoạt động bạn đang thực hiện. Hãy thử sử dụng hàm kế hoạch giải thích để xem mọi thứ sẽ được thực thi bởi db như thế nào. Các. Bạn có thể tính toán big-O
trùng lặp: http://stackoverflow.com/questions/727719/database-query-time-complexity –