Elasticsearch vs relational databases - Performance Comparison

Time Complexity: Elasticsearch vs relational databases

O(log n)

Understanding Time Complexity

When comparing Elasticsearch and relational databases, it's important to understand how their query times grow as data size increases.

We want to see how the cost of searching or retrieving data changes with bigger datasets.

Scenario Under Consideration

Analyze the time complexity of a simple search query in Elasticsearch and a SQL SELECT query in a relational database.

    // Elasticsearch query example
    GET /products/_search
    {
      "query": {
        "match": { "name": "laptop" }
      }
    }

    -- Equivalent SQL query
    SELECT * FROM products WHERE name LIKE '%laptop%';
    

This code searches for products with "laptop" in their name using Elasticsearch and a relational database.

Identify Repeating Operations

Both queries scan through data to find matches.

• Primary operation: Searching through indexed data or table rows.
• How many times: Depends on the number of documents or rows (n).

How Execution Grows With Input

As the number of items grows, the search time changes differently in each system.

Input Size (n)	Elasticsearch Approx. Operations	Relational DB Approx. Operations
10	Quick, near constant time due to inverted index	May scan many rows, slower
100	Still fast, index helps find matches quickly	Slower, more rows to check
1000	Search time grows slowly, index efficient	Search time grows roughly linearly with rows

Pattern observation: Elasticsearch uses indexes to keep search time low even as data grows, while relational DBs without indexes scan more data and slow down more.

Final Time Complexity

Time Complexity: O(log n) for Elasticsearch with indexes, O(n) for relational DB without indexes

This means Elasticsearch searches grow slowly with data size, while relational DB searches can grow directly with data size if not indexed.

Common Mistake

[X] Wrong: "All database searches take the same time no matter the system."

[OK] Correct: Different systems use different ways to find data. Elasticsearch uses special indexes that make searching faster as data grows, unlike some relational databases without proper indexes.

Interview Connect

Understanding how search time changes with data size helps you explain why certain databases fit different needs. This skill shows you can think about performance, not just code.

Self-Check

"What if the relational database had proper indexes on the searched column? How would the time complexity change?"