Advanced Transaction: Savepoint And Prepared Transaction

Hope you found my two previous posts on transaction interesting and useful. Based on some of readers request, I would cover few advanced transaction topic in my subsequent posts. In this post, I am going to cover following advanced variant of traditional transaction:

     1. Savepoint

     2. Prepared Transaction

Savepoint

In order to understand its usage, imagine one of your customer work-load as below:

            START TRANSACTION;

            Perform operation-1

            Perform operation-2

            Perform operation-3

Perform operation-4

            COMMIT;

As per the business logic it is likely that operation-3 and operation-4 are going to fail and also failure of these operations does not impact operation-1 and operation-2. Now as per transaction properties (recall the Basic of Transaction), whole of operation will be roll backed in-case of any of the four operation fails. So in the given business scenario though operation-1 and operation-2 should not be rollbacked but still it will be. 

In order to avoid this behavior  and control the main transaction life span, savepoint is being introduced.

Savepoint can be created only inside a transaction block. It creates a saving point for overall transaction i.e in-case if any commands results in error inside a transaction block, then instead of rollback whole transaction, it allows to rollback till the point where savepoint was created. E.g. Consider following example:
        CREATE TABLE TBL(ID INT, ID2 INT);
        CREATE UNIQUE INDEX IDX ON TBL(ID);

        START TRANSACTION
        INSERT INTO TBL VALUES(100, 100);
        INSERT INTO TBL VALUES(200, 200);
        SAVEPOINT first_save;
        INSERT INTO TBL VALUES(200, 300); <=== This will fail because of unique index.

Related Comamnds

1. SAVEPOINT savepoint_name: This command create a new savepoint inside a transaction block as shown in above example. There can be nested savepoint also i.e. savepoint can be created with-in already created savepoint.

2. ROLLBACK TO [SAVEPOINT ] savepoint_name: This command rollback all operation done from the point savepoint was created as shown in above example. Rollback to savepoint does not destroy the given savepoint but it destroys any savepoint nested with-in the given savepoint. E.g.

        START TRANSACTION

        INSERT INTO TBL VALUES(100, 100);

        INSERT INTO TBL VALUES(200, 200);

        SAVEPOINT first_save;

        INSERT INTO TBL VALUES(300, 300);

        SAVEPOINT second_save;

        INSERT INTO TBL VALUES(400, 400);

        ROLLBACK TO SAVEPOINT first_save;   <=== Will destroy second_save but first_save will remain active.

3. RELEASE [SAVEPOINT] savepoint_name: As the name suggest, it just removes/destroys the savepoint created. It does not have any impact on any other command executed after this savepoint. Similar to ROLLBACK TO SAVEPOINT, this command also destroy all savepoint nested with-in the savepoint getting released.

        START TRANSACTION

        INSERT INTO TBL VALUES(100, 100);

        INSERT INTO TBL VALUES(200, 200);

        SAVEPOINT first_save;

        INSERT INTO TBL VALUES(300, 300);

        SAVEPOINT second_save;

        INSERT INTO TBL VALUES(400, 400);

        RELEASE SAVEPOINT first_save; <=== Destroy both savepoints but no impact on records inserted.

        INSERT INTO TBL VALUES(400, 500); <=== As no savepoint active, so whole transaction gets rollbacked.

NOTE: There is no command like COMMIT TO SAVEPOINT as there is no meaning to commit only part of transaction (As it will be against transaction basic properties).

Prepare Transaction

Before jumping to define this variation, it is important to understand two-phase commit. As the name suggest it does commit of any transaction in two steps.

1.     First step is to verify all condition which needs to be satisfied in order to commit this transaction. This is called prepare stage.

2.    Second step is the actual commit, which is almost same as traditional commit.

This is more useful for a cluster based database or any similar variations, where in various nodes (databases) are responsible to run a part of bigger operation. So it is important that each node does either COMMIT or ROLLBACK at the same time in order to maintain overall transaction property. Many cluster solution achieve this using a dedicated transaction manager or just coordinator, whose tasks are:

1. Step-1: will probe all nodes to check if commit can be done and in turns all nodes will respond with either positive or negative acknowledgment.
2. Step-2: Once coordinator or transaction manager gets response from all nodes, it will issue COMMIT or ROLLBACK to all nodes.

I will cover more detailed two-phase commit in my future blogs.

So now coming back to understand Prepare Transaction, it actually prepares a normal current running transaction for two-phase commit. Once a transaction is prepared, it dissociates from current session and its gets stored on disk. Since its state gets stored on disk, it is almost certain that this transaction can be committed successfully even in-case of any database crash happened before explicit issue of commit.

Prepare transaction is given a unique identifier, which is used later to commit or rollback this transaction. Once prepare transaction is done, transaction gets dissociated from current session. Subsequently this transaction can be committed or rollbacked from any session using the name given during prepare.

Like traditional transaction, unless prepared transaction gets committed or rollbacked, impact of any operation done will not be visible by any session including the session which has performed this transaction.

This is not recommended to be used by application or any interactive sessions. Rather it should be used where there is need of any external transaction manager, which performs some validation or has some other dependency before actual commit.

Related Comamnds

1. PREPARE TRANSACTION name: Prepares the current transaction and immediately dissociates from the current session. A unique name is given to this prepared transaction, so that later it can be committed/rollbacked using the same name.
2. COMMIT PREPARED name: Commit the already prepared transaction. It’s like performing second phase of two phase commit protocol.
3. ROLLBACK PREPARE name: Rollback the already prepared transaction.

       Example:

        START TRANSACTION

        INSERT INTO TBL VALUES(100, 100);

        INSERT INTO TBL VALUES(200, 200);

        PREPARE TRANSACTION 'first_prepare';

        SELLECT * FROM TBL  <=== This will return zero record, as transaction is not yet committed

        COMMIT PREPARED 'first_prepare';

        SELLECT * FROM TBL  <=== This will return both records.

        START TRANSACTION

        INSERT INTO TBL VALUES(100, 100);

        INSERT INTO TBL VALUES(200, 200);

        PREPARE TRANSACTION 'first_prepare';

        ROLLBACK PREPARED 'first_prepare';

        SELLECT * FROM TBL  <=== This will return zero records as transaction rollbacked.

It is highly recommended to take PostgreSQL package from https://www.postgresql.org/download/ and try all of the commands described. 

Subscribe to my blog to stay informed about my new upcoming post.  

Please feel free to drop your query/suggestion/comments.

PostgreSQL Transaction Internal Code Flow

This post is in continuation of my previous post. Here I would explain main transaction working from code flow perspective. Sub-transaction, MVCC and other related details will be covered in subsequent posts. Request to see my previous post Basic of Transaction in order to get better understanding. 

Internally each transaction is represented as unique number in increasing order with an exception in-case of overflow. Also whole of transaction flow is tracked using various state as explained below:

Command Execution:

Usually each command execution has 3 steps as:

• StartTransactionCommand
• Do the operation specific to command
• CommitTransactionCommmand

As mentioned in my earlier post, if transaction is not started explicitly then it will be started internally for any command execution. So this forms two way of startign the transaction. Below it explain both of the case and corresponding state transition involved. 

Meaning  of below nomenclature

                    X ====action====>Y

Current state is X, in this it does operation "action" and gets transferred to state "Y". In-case there is no action mentioned, means in current state it does not do any operation, it directly moves to state "Y".

There are mainly 3 actions mentioned below, the purpose of each actions are as below:

• StartTransaction: Assign resources in terms of memory, initializes the guc variable specific, initialize the transaction properties like read-only transaction or read-write, create a new resource owner etc.
• CommitTransaction: Undo all initialization done by StartTransaction. Execute any pending triggers, handle all on commit action if any. Generate a COMMIT WAL record and insert same in WAL buffer, Update commit TS data. Then depending on synchronous commit or asynchronous commit configured, wait for response from standby node or directly flush the transaction to CLOG respectively.
• AbortTransaction: Almost similar to CommitTransaction except it writes an ABORT WAL, marks the transaction as ABORTED.

State transition mentioned in subsequent section are states from client queries perspective. In addition to these state, there are few states from server perspective also, these are:

• TRANS_DEFAULT: Idle, its default state.
• TRANS_START: This is the state in which transaction initialization happens (StartTransaction)
• TRANS_INPROGRESS: Means transaction has been started.
• TRANS_COMMIT: This state shows transaction commit is in progress (CommitTransaction)
• TRANS_ABORT:This state shows transaction abort is in progress (AbortTransaction)

Case-1: Explicit Start of Transaction:

Execution of START TRANSACTION command:

• StartTransactionCommand (TBLOCK_DEFAULT)====StartTransaction====>TBLOCK_STARTED
• Processing this command:  BeginTransactionBlock(TBLOCK_STARTED) =====> TBLOCK_BEGIN. 
• CommitTransactionCommmand(TBLOCK_BEGIN) ====> TBLOCK_INPROGRESS

Execution of a normal command:

• StartTransactionCommand (TBLOCK_INPROGRESS): Nothing to do.
• Processing this command: Till this point no transaction ID has been assigned, as was not sure if any command requiring transaction id going to be executed. So now call the function AssignTransactionId to assign a new transaction id. Current number of transaction is maintained in a shared variable ShmemVariableCache->nextXid; So the current value of this variable is taken as transaction id for current transaction. Then value of ShmemVariableCache->nextXid is incremented (taking care of overflow case). 

        Also each transaction information needs to be made durable (its one of the properties), for which it maintains:

1. Commit log for each transaction (Called CLOG stored in clog page)
2. Each transaction commit timestamp (call CommitTs stores in separate page)

        If current XID is going to be stored in a new page (either because its first transaction in the system or existing page is full), then it needs reset whole content of new page with zero. This should be done for all pages used for storing these information.

        Finally it should:

1. Also each session maintains MyPgXact, which maintains transaction information in memory. This is used by all other session for taking various decision. So assign this transaction to MyPgXact.
2. The new transaction id is stored in the each tuple being created (more on this in coming post related to MVCC).
3. Stores the current command id in each tuple being created.
4. Then continue with normal command operation.

• CommitTransactionCommmand(TBLOCK_INPROGRESS): Does command counter increment (CommandCounterIncrement) i.e. increments the command id so that if multiple commands running in same transaction then next command can see the operation done by previous command. No state transition.

Executing again a command:

• StartTransactionCommand (TBLOCK_INPROGRESS): Nothing to do.
• Processing this command: Since already transaction assigned nothing to do. Just continue with command execution.
• CommitTransactionCommmand(TBLOCK_INPROGRESS): Does command counter increment (CommandCounterIncrement) i.e. increments the command id so that if multiple commands running in same transaction then next command can see the operation done by previous command. No state transition.

Executing COMMIT/END command:

• StartTransactionCommand (TBLOCK_INPROGRESS): Nothing to do.
• Processing this command: EndTransactionBlock(TBLOCK_INPROGRESS) ====> TBLOCK_END
• CommitTransactionCommmand(TBLOCK_END)====CommitTransaction====> TBLOCK_DEFAULT

Executing ROLLBACK command:

• StartTransactionCommand (TBLOCK_INPROGRESS): Nothing to do.
• Processing this command: UserAbortTransactionBlock(TBLOCK_INPROGRESS) ====> TBLOCK_ABORT_PENDING
• CommitTransactionCommmand(TBLOCK_ABORT_PENDING)====AbortTransaction====> TBLOCK_DEFAULT

Case-2: Implicit Start of Transaction:

Transaction is started automatically in-case a transaction block start command was not executed. This transaction is valid only for the current command and it gets committed or aborted automatically once command gets executed successfully or gets fail respectively

Command Execution- Success:

• StartTransactionCommand (TBLOCK_DEFAULT)====StartTransaction====>TBLOCK_STARTED
• Do the actual operation
• CommitTransactionCommmand(TBLOCK_STARTED)====CommitTransaction====> TBLOCK_DEFAULT

Command Execution - Fail:

• StartTransactionCommand (TBLOCK_DEFAULT)====StartTransaction====>TBLOCK_STARTED
• Do the actual operation
• AbortCurrentTransaction(TBLOCK_STARTED) ====AbortTransaction====> TBLOCK_DEFAULT

In my subsequent post, I would cover some more details about transaction and their implementation details.

Any comment/query/suggestion welcome.

Basic of Transaction

Have you ever though about how below classic example works:

           You swipe your credit card in a shop and money gets debited from account but overall billing fails. In that case your money gets credited back to your account instantly.

If you can already relate this to one of the key property of Database called Transaction, then you already have some head start for this topic. If not then no need to worry, I will take you from very basic of Transactions.

Background

Transactions are one of the most fundamental key concept for any database including PostgreSQL. It enables multiple step actions to be grouped together in such a way that either all step executions are accepted or all are rejected. If all of step executions are success then as a group whole actions will be considered as success. If any of the step execution fails in between, then it will make sure to nullify the effect of all other previous successful steps. 

Consider an example of bank fund transfer, where in there is table consisting of customer name, their balance etc. There is a customer 'A' who wants to transfer 1000Rs to customer 'B'. In terms of SQL it will look like:

            UPDATE accounts SET balance = balance - 1000 where cust_name='A';

            UPDATE accounts SET balance = balance + 1000 where cust_name='B';

There are two steps involved in overall fund transfer activity and as per the above definition of transaction, either both of them should succeed i.e. once 1000Rs debited from A's account it must be credited to B's account or there should not be even debit from A's account. Also there should not be case where debit from A's account failed but B's account got credited with 1000Rs, in which case bank will not be happy.

Just explained property of relation is called as "Atomicity", there are other 3 additional properties of each transaction explained below:

Properties

There are four mandatory properties of each transaction:

Atomicity: 

This property make sure that all changes to data are performed as if they are a single operation. That is, all the changes are performed, or none of them. This is already explained above with example.

Consistency: 

This property ensures that database is in consistent state when transaction state and when it ends i.e. it just bring the database from one valid state to another. In above example balance data will remain in consistent state when transaction ends.

Isolation: 

This property insures that the intermediate state of a transaction is invisible to other concurrent running transactions. As a result, transactions that run concurrently appear to be serialized. In above example, if there is any concurrent transaction executing the below SQL command:

               SELECT sum(balance) FROM account;

Then it should always show the same amount i.e. it should not be able to see intermediate stage where 1000Rs has been debited from A's account but not credited to B's account.

Durability: 

This property related to action after transaction has completed and it ensures that once a transaction completes changes to data persists and are not undone even in event of system failure. In above example, once 1000Rs debited from A's account, even on system restart changed balance will be shown for A's account.

Major Commands

Below are the major commands related to transaction:

1. START TRANSACTION / BEGIN: This command start a new transaction. 

2. COMMIT: This command ends already running transaction.

3. ROLLBACK: This command is used to undo all changes done by the statements running in the current transaction. Some depending on your business logic you might need to execute this command.

In order to execute multiple statements in a single transaction, then before writing any statement, first command-1 needs to be executed and then after all statements are executed, command -2 or command -3 should be executed.

e.g..

START TRANSACTION

SQL-STMT-1

SQL-STMT-2

..

..

SQL-STMT-3

COMMIT/ROLLBACK.

Note: If an explicit START TRANSACTION/BEGIN command is not given before a SQL-statement then explicitly BEGIN command will be executed for that SQL-statement and once this statement finishes, an explicit COMMIT command will be executed.

I hope by now you understand how swiping credit card example works. Here debiting of money from your card, generation of bill all happens in the same transaction. So even if first step of debiting money success but final billing failed then whole transaction will be rollbacked and hence debited money will be credited back.

Do visit my next post to see how transaction works in PostgreSQL from code flow perspective.

Any comment/query/suggestion welcome.

Native Compilation Part-2 @ PGDay Asia 2016 Conference

Finally first PGDay Asia held in Singapore has successfully finished. I am also one of the organizer of this conference. It took months of hard work by many specially Sameer Kumar to achieve this.

I had also opportunity to present my paper on Native Compilation part-2, it was subsequent to my paper presented in last PGCon 2015 (Procedure compilation is additional).

Summary of this talk (For detail talk visit Native Compilation at PGDay Asia 2016):

Why Native Compilation Required:

Seeing the current hardware trend, I/O is no more bottleneck for the executor mainly because of below reasons:

1. Increase in RAM Size

2. Prevalence of High speed SSD

At the same time, though lot of work has happened in hardware but there is no focus on improving the CPU efficiency. Because of this, current executor biggest bottleneck is CPU usage efficiency not I/O. So in order to tackle CPU bottleneck without compromising on any feature, we need mechanism to execute lesser number of instruction and still getting all functionality.

What is Native Compilation:

Native Compilation is a methodology to reduce CPU instructions by executing only instruction specific to given query/objects unlike interpreted execution. Steps are:

 1. Generate C-code specific to objects/query.

 2. Compile C-code to generate DLL and load with server executable.

 3. Call specialized function instead of generalized function.

Native compilation can be applied to any entity which are inefficient in terms of CPU e.g.:

 1. Table

 2. Procedure

 3. Query

Table Native Compilation (Aka Schema Binding):

Since most of the properties of a particular table remains same once it is created, so its data gets stored and accessed in the similar pattern irrespective of any data. So instead of accessing tuples for same relation in generic way, we create a specialized access function for the particular relation during its creation and the same gets used for further query containing that table. This approach eliminates the need for various comparison (e.g. data-type check, length check, number of attribute check) during the access of tuple. More the deforming of tuples contribute to total run of query, more performance will be observed. Generation of code can be done in 3-ways, details of each of them is available in presentation.

Fig-1: Table compilation

Once a create table command is issued, a C-file with all specialized access function is generated, which is in turns gets loaded as DLL. These loaded functions are used by all SQL query accessing the compiled table.

Performance Improvement:

Below is the performance improvement observed on standard TPC-H benchmark.

The system configuration is as below:

SUSE Linux Enterprise Server 11 (x86_64), 2 Cores, 10 sockets per core

TPC-H Configuration: Default

Graph-1: TPC-H Performance

Table-1: TPC-H Performance 

With the above performance result, we observed that there is more than 70% reduction in CPU instruction and upto 36% performance improvement on TPC-H queries.

Procedure Compilation:

There are two parts in any of the procedure:

 1. SQL Query statements

 2. Non-SQL statement (e.g. loop, conditional, simple expression etc).

In this presentation, we focused only on 2nd part. As part of this whenever we create the procedure, we compile the Pl/Pgsql function into corresponding normal C-function. While compiling:

 1. Transform the Pl/Pgsql procedure signature to normal C-function signature.

 2. Transform all variable declaration as C-variable declaration.

 3. Transform all other non-SQL statement in corresponding normal C-statement.

 4. All SQL statements are transformed in the format SPI_xxx as below:

if (plan == NULL)

{

stmt = SPI_prepare(modified_query, number_of_variables, type_of_variable used);

SPI_keepplan(stmt);

plan = stmt;

}

SPI_execute_plan(plan, value,  isnull,  false, row_count);

 5. Finally compile the generated C-function using a traditional compiler to generate DLL and link  the same with SERVER executable.

 6. So on subsequent execution, directly C-function will be called instead of Pl/Pgsql function.

Fig-2: Procedure Compilation

Fig-3: Compiled Procedure invocation

Fig-2 highlights at what step and how procedure will be compiled.  Once the parsing of procedure is done, we will have all information about the procedure in PLpgSQL_function pointer, which we can traverse as planner does and for each statement corresponding C-code can be generated.

Fig-3 explain, how compiled function will be invoked.

How number of instruction reduced:

Consider a statment as x=2+y in Pl/Pgsql procedure. This statement will be executed as a traditional SELECT command as "SELECT 2+y;". So everytime this procedure gets executed, this query will be executed as if it was normal SQL query and hence many CPU instruction are executed.

But if we convert this to C-based statment, it execution will be directly as 2+y and hence will execute very few instruction comapred to original one.

Performance Improvement:

Below is the performance improvement observed on standard TPC-C benchmark:

The system configuration is as below:

SUSE Linux Enterprise Server 11 (x86_64), 2 Cores, 10 sockets per core

TPC-C Configuration: runMins=0, runTxnsPerTerminal=200000

Checkpoint_segment = 100

Graph-2: TPC-C Performance

Table-2: TPC-C Performance

With some basic compilation of procedure, we are able to get around 23% performance improvement.

Query Compilation:

Though this was not part of my presentation but would like to give some details to do this.

Unlike above two compilation, in order to compile query we need to use LLVM as the compilation time is very important while executing the query.

LLVM is open source compilation framework for very efficient and fast compilation. The LLVM compiler can only understand the IR (Internal representation something similar to assembly code). So before compilation using LLVM, we need to generate IR form of the code, which can be either of the two ways:

1. Generate C-code and generate IR for this using Clang (a tool built for C-code)

2. Or just use the IR-Builder interface function provided by LLVM to generate code directly in IR format.

The steps to compile query is as below:

1. Generate the Query plan as it is.

2. Choose the plan node to be compiled (if whole query to be compiled, then all nodes), generate a specific code corresponding to the node. This can be done in either of the ways explained above.

3. Compile the generated code using LLVM.

4. The code compiled using LLVM will return an object handler, which can be attached to the corresponding node.

5. So while executing that node, we can call compiled stored object if the compilation object stored for the corresponding node.

The most of the benefit is expected out of this query compilation. Once query compilation is done, even the SQL query statement of procedure also can be compiled in the same way (perhaps nothing explicit will be required for this...).

Conclusion:

Seeing the industry trend, we have implemented two way of specialization, which resulted in up to 36% and 23% of performance improvement on standard benchmark TPC-H and TPC-C respectively.

Any feedback/comments/queries are welcome.

Presented paper in PGCon 2015 on Native Compilation Technology

I am back from the PGCon 2015 and was fortunate enough to present my first paper on "Native Compilation" technology. Also got opportunity to meet most creamy  folks of PostgreSQL community, found everyone to be very polite and easy to go.

As part of this Native Compilation technology, I mostly focused on the Native Compilation of Relation, which we call it as Schema Binding.

Some of the details from presentation are as below (For complete presentation please visit Go Faster With Native Compilation):

Native Compilation:
Native Compilation is a methodology to reduce CPU instructions by executing only instruction specific to given query/objects unlike interpreted execution. Steps are:

• Generate C-code specific to objects/query.
• Compile C-code to generate DLL and load with server executable.
• Call specialized function instead of generalized function.

Schema Binding:

Native Compilation of relation is called the Schema Binding. Since most of the properties of a particular remains same once it is created, so its data gets stored and accessed in the similar patter irrespective of any data. So instead of accessing tuples for same relation in generic way, we create a specialized access function for the relation during its creation and the same gets used for further query containing that table.

It gives performance improvement of upto 30% on standard TPC-H benchmark.

Optimizer Hint @ Indian PGDay, Bangalore (11th April 2015)

I recently just got back from Indian PGDay conference 2015. It was an interesting, motivating and lot of knowledge sharing in terms of both attending and speaking at the conference.

I spoke about the various kind of "Optimizer Hint" provided by many database engines and also a new idea of "Hint", which can be provided to Optimizer. Some of the speakers shared their work on PostgreSQL as User.
Also it was interesting to know that many companies are evaluating migration or are in process of migrating from other DBs to PostgreSQL. This is really encouraging for all PostgreSQL experts.

Some of the details from presentation are as below (For complete presentation please visit Full Optimizer Hint)

Statistics Hint:

Statistics Hint is used to provide any kind of possible statistics related to query, which can be used by optimizer to yield the even better plan compare to what it would have done otherwise.
Since most of the databases stores statistics for a particular column or relation but doesn't store statistics related to join of column or relation. Rather these databases just multiply the statistics of individual column/relation to get the statistics of join, which may not be always correct.

Example:
Lets say there is query as
SELECT * FROM EMPLOYEE WHERE GRADE>5 AND SALARY > 10000;

If we calculate independent stats for a and b.
suppose sel(GRADE) = .2 and sel(SALARY) = .2;

then sel (GRADE and SALARY) =
sel(GRADE) * sel (SALARY) = .04.
 
In all practical cases if we see, these two components will be highly dependent i.e. if first column satisfy,second column will also satisfy. Then in that case sel (GRADE and SALARY) should be .2 not .04. But current optimizer will be incorrect in this case and may give wrong plan.

Data Hint:

This kind of hints provides the information about the relationship/ dependency among relations or column to influence the plan instead of directly hinting to provide desired plan or direct selectivity value. Optimizer can consider dependency information to derive the actual selectivity.

Example:
Lets say there is a query as
SELECT * FROM TBL  WHERE ID1 = 5 AND ID2=NULL;
SELECT * FROM TBL  WHERE ID1 = 5 AND ID2!=NULL;

Now here if we specify that the dependency as
“If TBL.ID1 = 5 then TBL.ID2 is NULL”
then the optimizer will always consider this dependency pattern and accordingly combined statistics for these two columns can be choosen.

Note: This feature is not yet available in PG.

Conclusion:
Unlike other DB, we can provide some actual statistics information to optimizer to come out with the most optimal plan instead of directly telling planner to choose one specific plan.

Index Scan Optimization for ">" condition

In PostgreSQL 9.5, we can see improved performance  for Index Scan on ">" condition.

In order to explain this optimization, consider the below schema:

create table tbl2(id1 int, id2 varchar(10), id3 int);

create index idx2 on tbl2(id2, id3);

Query as:

                select count(*) from tbl2 where id2>'a' and id3>990000;

As per design prior to this patch, Above query used following steps to retrieve index tuples:

• Find the scan start position by searching first position in BTree as per the first key condition i.e. as per id2>'a'
• Then it fetches each tuples from position found in step-1.
• For each tuple, it matches all scan key condition, in our example it matches both scan key condition.
• If condition match, it returns the tuple otherwise scan stops.

Now problem is here that already first scan key condition is matched to find the scan start position (Step-1), so it is obvious that any further tuple also will match the first scan key condition (as records are sorted).

So comparison on first scan key condition again in step-3 seems to be redundant.

So we have made the changes in BTree scan algorithm to avoid the redundant check i.e. remove the first key comparison for each tuple as it is guaranteed to be always true.

Performance result summary:

I would like to thanks Simon Riggs for verifying and committing this patch. Simon Riggs also confirmed improvement of 5% in both short and long index, on the least beneficial data-type and considered to be very positive win overall. 

Overview of PostgreSQL Engine Internals

POSTGRESQL is an open-source, full-featured relational database. This blog gives an overview of how POSTGRESQL engine processes queries received from the user.

Typical simplified flow of PostgreSQL engine is:

SQL Engine Flow

As part of this blog, I am going to cover all modules marked in yellow colour.

Parser:

Parser module is responsible for syntactical analysis of the query. It constitute two sub-modules:

1. Lexical scanner

2. Bison rules/actions

Lexical Scanner:

Lexical scanner reads each character from the given query and return the appropriate token based on the matching rules. E.g. rules can be as follows:

   

    Name given in the <> is the state name, in the above example <xc> is the state name for the comment start. So once it sees the comment starting character, comment body token will be read in the <xc> state only.

Bison:

Bison reads token returned from scanner and matches the same  against the given rule for a particular query and performs the associated actions. E.g. the bison rule for SELECT statement is:

       

So each returned token is matched with the rule mentioned above in left-right order, if at any time it does not find matching rule, then either it goes to next possible matching rule or throws an error.

Analyzer:

Analyzer module is responsible for doing semantic analysis of the given query.  Each raw information about the query received from the Parser module is transformed to database internal object form to get the corresponding object id. E.g. relation name "tbl" get replaces with its object id.

Output of analyzer module is Query tree, structure of same can be seen in the structure "Query" of file src/include/nodes/parsenodes.h

Optimizer:

Optimizer module also consider to be brain of SQL engine is responsible for choosing the best path for execution of the query. Best path for a query is selected based on the cost of the path. The path with least cost is considered to be a winner path.

Based on the winner path, plan is created which is used by executor to execute the query.

Some of the important decision points are taken in terms of below methods:

1. Scan Method
• Sequential scan: Simply read the heap file start to end so it is considered to be very slow if many records to be fetched.
• Index scan: Use a secondary data structure to quickly find the records that satisfy a certain predicate and then corresponding to that it looks for other part of the record in Heap. So it involves extra cost of random page access.
2. Join Method
• Nested Loop Join: In this join approach, each record of outer table is matched with each record of inner table. The simple algorithm for the same is:

               For a NL join between Outer and Inner on Outer:k = Inner:k:

                                     for each tuple r in outer:

                                             for each tuple s in Inner with s.k = r.k:

                                                        emit output tuple (r,s)

                            Equivalently: Outer is left, Inner is right.

                                        

                                  

• Merge Join: This join is suitable only sorted record of each participating table and only for "=" join clause. The simple algorithm for this join is:

                     For both r in Outer, s in Inner:

                                          if r.k = s.k:

                                                emit output tuple (r,s)

                                                Advance Outer & Inner

                                           if r.k < s.k

                                                Advance Outer

                                           else

                                                Advance Inner

                         

                              

                                   

• Hash Join: This join does not require records to be sorted but this is also used only for "=" join clause.

                       For a HJ between Inner and Outer on Inner:k = Outer:k:

                               -- build phase

                              for each tuple r in Inner:

                                   insert r into hash table T with key r.k

                              -- probe phase

                             for each tuple s in Outer:

                                   for each tuple r in bucket T[s.k]:

                                   if s.k = r.k:

                                        emit output tuple (T[s.k], s)

                              

                                  

3. Join Order: It is mechanism to decide the order in which table has to be joined.

 Typical output of the plan is:

  postgres=# explain select firstname from friend where age=33      order by firstname;

                          QUERY PLAN

--------------------------------------------------------------

 Sort  (cost=1.06..1.06 rows=1 width=101)

   Sort Key: firstname

   ->  Seq Scan on friend  (cost=0.00..1.05 rows=1 width=101)

         Filter: (age = 33)

(4 rows)

Executor:

Executor is the module, which takes output of planner as input and transform each node of plan to state tree node. Then in turn each node gets executed to perform the corresponding operation. 

The state tree nodes execution starts from root and to get the input, it keep going to child node till it reaches the leaf node. So finally leaf node executed to pass the input to upper node. Out of two leaf nodes, first outer node (i.e. left node) gets evaluated.

         At this point it uses the interface from storage module to retrieve the actual data.

Typically execution process can be divided as:

• Executor Start: Prepares the plan for execution. It process each node of plan recursively and generate corresponding state tree node. Also it initializes memory to hold projection list, qualification expression and slot for holding the resultant tuple. 
• Executor Run: Recursively process each state tree node and each resultant tuple is send to front-end using the register destination function.
• Executor Finish: Free all the allocated resources.

One of the typical flow of execution is as below:

So in above flow, Execution starts from Merge Join but it needs input to process, so it flow towards first left child node, take one tuple using index scan and then it request for input tuple from right child node. Right child node is Sort node, so it request for tuple from its child, which in turn does the sequence scan. So once all tuple is received at Sort node and tuples are shorted, then it passes the first tuple to its parent node.

Reference:

Older papers from PostgreSQL.