Search configuration and languages in PostgreSQL - Time & Space Complexity

Time Complexity: Search configuration and languages

O(n)

Understanding Time Complexity

When using search configurations and languages in PostgreSQL, it is important to understand how the search process scales as the amount of data grows.

We want to know how the time to find matches changes when we have more text or more documents to search.

Scenario Under Consideration

Analyze the time complexity of the following PostgreSQL full-text search query using a specific search configuration.

SELECT *
FROM documents
WHERE to_tsvector('english', content) @@ to_tsquery('english', 'database & search');
    

This query searches the "content" column of the "documents" table for entries matching the words "database" and "search" using the English search configuration.

Identify Repeating Operations

Look for repeated work done by the query.

• Primary operation: The database processes each document's text to create a searchable vector and then compares it to the search query.
• How many times: This happens once for each document in the table.

How Execution Grows With Input

As the number of documents grows, the search work grows roughly in proportion.

Input Size (n)	Approx. Operations
10	About 10 vector creations and comparisons
100	About 100 vector creations and comparisons
1000	About 1000 vector creations and comparisons

Pattern observation: The work grows linearly with the number of documents because each one is checked.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the search grows directly in proportion to the number of documents being searched.

Common Mistake

[X] Wrong: "Using a search configuration makes the search instant no matter how many documents there are."

[OK] Correct: The search configuration helps interpret the text but does not reduce the number of documents to check unless indexes are used.

Interview Connect

Understanding how search configurations affect query time helps you explain how databases handle text search efficiently and how to scale searches as data grows.

Self-Check

"What if we add a full-text index on the content column? How would the time complexity change?"

Practice

1. What is the main purpose of a search configuration in PostgreSQL?

easy

A. To define how text is processed for full-text search in a specific language

B. To store user login information securely

C. To manage database connections and pooling

D. To backup and restore database data

Solution

1. Step 1: Understand search configuration role

   Search configurations tell PostgreSQL how to handle text for searching, especially for different languages.

2. Step 2: Compare options

   Options A, C, and D relate to security, connections, and backups, not text processing.

3. Final Answer:

   To define how text is processed for full-text search in a specific language -> Option A

4. Quick Check:

   Search configuration = text processing [OK]

Hint: Search configs define text processing rules for languages [OK]

Common Mistakes:

• Confusing search configuration with user or connection settings
• Thinking it manages backups or security
• Assuming it stores data instead of processing text

2. Which of the following is the correct syntax to create a new text search configuration named my_config based on the built-in english configuration?

easy

A. CREATE TEXT SEARCH CONFIGURATION my_config AS english;

B. CREATE TEXT SEARCH CONFIGURATION my_config FROM english;

C. CREATE TEXT SEARCH CONFIGURATION my_config ( COPY = english );

D. CREATE TEXT SEARCH CONFIGURATION my_config LIKE english;

Solution

1. Step 1: Recall correct CREATE syntax

   PostgreSQL uses CREATE TEXT SEARCH CONFIGURATION name ( COPY = existing_config ) to copy an existing config.

2. Step 2: Check options

   Only CREATE TEXT SEARCH CONFIGURATION my_config ( COPY = english ); uses the correct syntax with COPY = english. Others use invalid keywords.

3. Final Answer:

   CREATE TEXT SEARCH CONFIGURATION my_config ( COPY = english ); -> Option C

4. Quick Check:

   Use COPY = for cloning configs [OK]

Hint: Use COPY = existing_config to clone search configs [OK]

Common Mistakes:

• Using FROM or AS instead of COPY =
• Omitting parentheses around COPY clause
• Confusing syntax with table creation

3. Given the following SQL commands:

CREATE TEXT SEARCH CONFIGURATION my_english ( COPY = english );
ALTER TEXT SEARCH CONFIGURATION my_english
  ALTER MAPPING FOR asciiword, asciihword, hword_asciipart
  WITH simple;
SELECT to_tsvector('my_english', 'PostgreSQL is great!');

What is the output of the SELECT statement?

medium

A. 'postgresql':1 'great':3 'is':2 'simple':5

B. 'postgresql':1 'great':3 'is':2

C. 'postgresql':1 'great':3

D. Syntax error due to ALTER MAPPING

Solution

1. Step 1: Understand ALTER MAPPING effect

   The ALTER MAPPING changes how asciiword and related tokens are processed, using the simple dictionary which does not remove stop words.

2. Step 2: Analyze to_tsvector output

   The text 'PostgreSQL is great!' produces tokens: 'PostgreSQL' (pos 1, asciiword) -> 'postgresql':1; 'is' (pos 2, asciiword) -> 'is':2; 'great' (pos 3, asciiword) -> 'great':3. Simple indexes all without dropping stopwords. Matches 'postgresql':1 'great':3 'is':2.

3. Final Answer:

   'postgresql':1 'great':3 'is':2 -> Option B

4. Quick Check:

   Alter mapping changes dictionary used [OK]

Hint: ALTER MAPPING changes dictionary for word processing [OK]

Common Mistakes:

• Assuming stop words are always removed
• Confusing dictionary effects on stemming and stop words
• Expecting syntax error from ALTER MAPPING

4. You run the following command:

ALTER TEXT SEARCH CONFIGURATION my_config
  ALTER MAPPING FOR word WITH english_stem;

But you get an error: ERROR: dictionary "english_stem" does not exist
What is the most likely cause?

medium

A. The configuration name is reserved and cannot be changed

B. ALTER MAPPING cannot be used on existing configurations

C. You must drop the configuration before altering it

D. The dictionary name is misspelled or not created

Solution

1. Step 1: Analyze error message

   The error says the dictionary "english_stem" does not exist, indicating PostgreSQL cannot find that dictionary.

2. Step 2: Identify cause

   Most likely, the dictionary name is misspelled or the dictionary was never created in the database.

3. Final Answer:

   The dictionary name is misspelled or not created -> Option D

4. Quick Check:

   Dictionary must exist before use [OK]

Hint: Check dictionary exists before ALTER MAPPING [OK]

Common Mistakes:

• Assuming ALTER MAPPING is disallowed on configs
• Trying to drop config unnecessarily
• Ignoring dictionary creation step

5. You want to create a search configuration for French that uses the built-in french configuration but replaces the stopword dictionary with a custom dictionary named my_french_stop. Which sequence of commands correctly achieves this?

hard

A. CREATE TEXT SEARCH CONFIGURATION my_french ( COPY = french );
ALTER TEXT SEARCH CONFIGURATION my_french
ALTER MAPPING FOR stopword WITH my_french_stop;

B. CREATE TEXT SEARCH CONFIGURATION my_french ( COPY = french );
ALTER TEXT SEARCH CONFIGURATION my_french
ALTER MAPPING FOR word WITH my_french_stop;

C. CREATE TEXT SEARCH CONFIGURATION my_french AS french;
ALTER TEXT SEARCH CONFIGURATION my_french
ALTER MAPPING FOR stopword WITH my_french_stop;

D. CREATE TEXT SEARCH CONFIGURATION my_french ( COPY = french );
ALTER TEXT SEARCH CONFIGURATION my_french
ALTER MAPPING FOR stopword WITH french;

Solution

1. Step 1: Create configuration by copying french

   Use CREATE TEXT SEARCH CONFIGURATION my_french ( COPY = french ); to clone the built-in french config.

2. Step 2: Alter mapping for stopword dictionary

   Use ALTER MAPPING FOR stopword WITH my_french_stop; to replace the stopword dictionary with the custom one.

3. Final Answer:

   CREATE TEXT SEARCH CONFIGURATION my_french ( COPY = french ); ALTER TEXT SEARCH CONFIGURATION my_french ALTER MAPPING FOR stopword WITH my_french_stop; -> Option A

4. Quick Check:

   Copy config then alter stopword mapping [OK]

Hint: Copy config then ALTER MAPPING for custom dictionaries [OK]

Common Mistakes:

• Using AS instead of COPY = for creation
• Altering wrong token types like word instead of stopword
• Assigning built-in dictionary instead of custom one