Field and document level security in Elasticsearch - Time & Space Complexity

Time Complexity: Field and document level security

O(n)

Understanding Time Complexity

When using field and document level security in Elasticsearch, it's important to know how the time to check permissions grows as data grows.

We want to understand how the cost of filtering fields and documents changes with more data.

Scenario Under Consideration

Analyze the time complexity of the following Elasticsearch query with field and document level security.

GET /my-index/_search
{
  "query": {
    "bool": {
      "filter": [
        { "term": { "user": "alice" } },
        { "range": { "age": { "gte": 30 } } }
      ]
    }
  },
  "_source": ["name", "email"]
}
    

This query filters documents by user and age, then returns only the "name" and "email" fields, enforcing field and document level security.

Identify Repeating Operations

Look at what repeats as data grows.

• Primary operation: Filtering documents by conditions and selecting specific fields.
• How many times: Each document is checked once against filters, and fields are selected per matching document.

How Execution Grows With Input

As the number of documents grows, the system checks more documents to see if they match the filters.

Input Size (n)	Approx. Operations
10	About 10 document checks and field selections
100	About 100 document checks and field selections
1000	About 1000 document checks and field selections

Pattern observation: The work grows roughly in direct proportion to the number of documents.

Final Time Complexity

Time Complexity: O(n)

This means the time to filter and select fields grows linearly with the number of documents.

Common Mistake

[X] Wrong: "Filtering by fields or documents happens instantly no matter how many documents there are."

[OK] Correct: Each document must be checked against the filters, so more documents mean more work and more time.

Interview Connect

Understanding how filtering and field selection scale helps you explain how Elasticsearch handles security efficiently as data grows.

Self-Check

What if we added nested queries or more complex filters? How would the time complexity change?