System and method for transaction-selective rollback reconstruction of database objects

Abstract

Most commercial database systems provide a recovery mechanism that is used to restore data integrity in the event of a hardware or software failure. Many of these systems restore the database from the most recent backup file by rolling forward all transactions from the most recent undamaged transaction log. The present invention discloses a novel system and method for recovering data from user or application errors. Embodiments of the present invention selectively target and undo only those transactions that caused data corruption. In this way, the present invention is able to recover fine-grained database objects such as a table or a row within a table. The present invention has the further advantage of minimizing the number of transactions that are lost after recovery.

What is claimed is:  
     
       1. A method of constructing a rollback script used to modify data in a database comprising the steps of: 
       choosing at least one selection criterion for use in determining if a transaction in a transaction log should be rolled back;  
       determining an end of a time range for use in terminating searching of the transaction log,  
       searching the transaction log to find at least one log record that satisfies the at least one selection criterion, wherein the at least one log record contains an operation that is part of a committed transaction;  
       extracting the at least one log record from the transaction log;  
       computing a command for use in rolling back the operation contained in the at least one log record; and  
       writing the command to a rollback script.  
     
     
       2. The method of  claim 1 , wherein the at least one selection criterion is selected from the group consisting of SPID List, Table List, Activity Type, Time Range, and Logical Row Locator, wherein Logical Row Locator is a specific row within a table described by a standard SQL language. 
     
     
       3. The method of  claim 1 , wherein determining an end of a time range further comprises the steps of: 
       issuing a checkpoint command; and  
       reading a log sequence number of a last checkpoint command from a database boot record.  
     
     
       4. The method of  claim 2 , wherein determining an end of a time range further comprises the step of: 
       using the at least one selection criteria to determine the end of the time range.  
     
     
       5. The method of  claim 1 , comprising the step of: 
       accumulating changes needed to rollback each effected row of a table.  
     
     
       6. The method of  claim 5 , wherein the transaction is an Insert. 
     
     
       7. The method of  claim 6 , wherein the changes needed to rollback the transaction comprise the steps of: 
       determining if a row affected by the operation in an input log record was subsequently deleted in the database; and  
       determining that no change is needed to rollback the transaction if the row affected by the operation in the input log record was subsequently deleted in the database.  
     
     
       8. The method of  claim 6 , wherein the changes needed to rollback the transaction comprise the steps of: 
       determining if a row affected by the operation in an input log record was subsequently deleted in the database;  
       maintaining a temporary table that contains row images as they existed at various time points;  
       removing all rows from the table, except for rows of type “B,” whose Physical Row Id and Table Id match the input log record's Physical Row Id and Object Id;  
       reading a data row directly from a physical database page identified by the Physical Row Id in the input log record;  
       creating a new row in the table of type “D” and Physical Row Id equal to the input log record's Physical Row Id and DataRow equal to the data row read directly from the physical database page identified by the Physical Row Id in the input log record; and  
       creating a new row in the table of type “B”, and Physical Row Id equal to the input log record's Physical Row Id and DataRow equal to the data row read directly from the physical database page identified by the Physical Row Id in the input log record.  
     
     
       9. The method of  claim 5 , wherein the transaction is a Delete. 
     
     
       10. The method of  claim 9 , comprising the steps of: 
       removing all rows whose Physical Row Id and Table Id match the input log record's Physical Row Id and Object Id, except those of type “B”; and  
       creating a new row in the table of type “I” and Physical Row Id equal to a physical row id of the input log record and DataRow equal to a data row of the input log record.  
     
     
       11. The method of  claim 5 , wherein the transaction is a Modify. 
     
     
       12. The method of  claim 11 , comprising the steps of: 
       determining if the table contains a row with the same Row Id as an input log record; and  
       using the row with the same Row Id to perform the Modify transaction.  
     
     
       13. The method of  claim 1 , wherein the at least one selection criterion is Time Range and searching the transaction log comprises using binary search techniques. 
     
     
       14. The method of claims  1 ,  2 ,  3 ,  4 ,  5 ,  6 ,  7 ,  8 ,  9 ,  10 ,  11 ,  12  or  13 , wherein the database is a SQL Server database. 
     
     
       15. A method for determining the contents of a row in a database at any point in time comprising the steps of: 
       determining an LSN for the row;  
       searching a transaction log using the LSN in order to identify at least one log record that performed a transaction on the row; and  
       filtering the at least one log record to determine if the transaction was committed.  
     
     
       16. The method of  claim 15 , wherein the searching is performed in reverse chronological order. 
     
     
       17. The method of claims  15  or  16 , further comprising the step of: 
       determining if the row was relocated to a different physical page.  
     
     
       18. The method of  claim 17 , wherein determining if the row was relocated is done with a pseudo-delete mechanism. 
     
     
       19. The method of  claim 17 , wherein determining if the row was relocated is further comprised of the steps of: 
       analyzing an operation code in the at least one log record;  
       determining if the row has a clustered key;  
       saving the value of the clustered key; and  
       analyzing a set of log records to determine what modification each log record made and if a clustered key in each log record matches the saved clustered key.  
     
     
       20. The method of  claim 17 , wherein determining if the row was relocated is further comprised of the steps of: 
       analyzing an operation code in the at least one log record; and  
       determining if the row has a forward pointer.  
     
     
       21. The method of claims  15 ,  16 ,  18 ,  19 , or  20 , wherein the database is a SQL Server database. 
     
     
       22. The method of  claim 17 , wherein the database is a SQL Server database. 
     
     
       23. Computer-executable process steps stored on a computer-readable medium, the computer-executable process steps to construct a rollback script used to restore data in a database, the computer-executable process steps comprising: 
       code to choose at least one selection criterion for use in determining if a transaction in a transaction log should be rolled back;  
       code to determine an end of a time range for use in terminating searching of the transaction log,  
       code to search the transaction log to find at least one log record that satisfies the at least one selection criterion, wherein the at least one log record contains an operation that is part of a committed transaction;  
       code to extract the at least one log record from the transaction log;  
       code to compute a command for use in rolling back the operation contained in the at least one log record; and  
       code to write the command to a rollback script.  
     
     
       24. The computer executable process steps of  claim 23 , wherein the at least one selection criterion is selected from the group consisting of SPID List, Table List, Activity Type, Time Range, and Logical Row Locator, wherein Logical Row Locator is a specific row within a table described by a standard SQL language. 
     
     
       25. The computer executable process steps of  claim 23 , wherein determining an end of a time range further comprises: 
       code to issue a checkpoint command; and  
       code to read a log sequence number of a last checkpoint command from a database boot record.  
     
     
       26. The computer executable process steps of  claim 24 , wherein determining an end of a time range further comprises: 
       code to use the at least one selection criteria to determine the end of the time range.  
     
     
       27. The computer executable process steps of  claim 23 , comprising: 
       code to accumulate changes needed to rollback each effected row of a table.  
     
     
       28. The computer executable process steps of  claim 27 , wherein the transaction is an Insert. 
     
     
       29. The computer executable process steps of  claim 28 , wherein the changes needed to rollback the transaction comprise: 
       code to determine if a row affected by the operation in an input log record was subsequently deleted in the database; and  
       code to determine that no change is needed to rollback the transaction if the row affected by the operation in the input log record was subsequently deleted in the database.  
     
     
       30. The computer executable process steps of  claim 28 , wherein the changes needed to rollback the transaction comprise: 
       code to determine if a row affected by the operation in an input log record was subsequently deleted in the database;  
       code to maintain a temporary table that contains row images as they existed at various time points;  
       code to remove all rows from the table, except for rows of type “B,” whose Physical Row Id and Table Id match the input log record's Physical Row Id and Object Id;  
       code to read a data row directly from a physical database page identified by the Physical Row Id in the input log record;  
       code to create a new row in the table of type “D” and Physical Row Id equal to the input log record's Physical Row Id and DataRow equal to the data row read directly from the physical database page identified by the Physical Row Id in the input log record; and  
       code to create a new row in the table of type “B”, and Physical Row Id equal to the input log record's Physical Row Id and DataRow equal to the data row read directly from the physical database page identified by the Physical Row Id in the input log record.  
     
     
       31. The computer executable process steps of  claim 27 , wherein the transaction is a Delete. 
     
     
       32. The computer executable process steps of  claim 31 , further comprising: 
       code to remove all rows whose Physical Row Id and Table Id match the input log record's Physical Row Id and Object Id, except those of type “B”; and  
       code to create a new row in the table of type “I” and Physical Row Id equal to a physical row id of the input log record and DataRow equal to a data row of the input log record.  
     
     
       33. The computer executable process steps of  claim 27 , wherein the transaction is a Modify. 
     
     
       34. The computer executable process steps of  claim 33 , further comprising: 
       code to determine if the table contains a row with the same Row Id as an input log record; and  
       code to use the row with the same Row Id to perform the Modify transaction.  
     
     
       35. The computer executable process steps of  claim 23 , wherein the at least one selection criterion is Time Range and searching the transaction log comprises using binary search techniques. 
     
     
       36. The computer executable process steps of claims  23 ,  24 ,  25 ,  26 ,  27 ,  28 ,  29 ,  30 ,  31 ,  32 ,  33 ,  34 , or  35 , wherein the database is a SQL Server database. 
     
     
       37. Computer-executable process steps stored on a computer-readable medium, the computer-executable process steps to determine the contents of a row in a database at any point in time the computer-executable process steps comprising: 
       code to determine an LSN for the row;  
       code to search a transaction log using the LSN in order to identify at least one log record that performed a transaction on the row; and  
       code to filter the at least one log record to determine if the transaction was committed.  
     
     
       38. The computer-executable process steps of  claim 37 , wherein the searching is performed in reverse chronological order. 
     
     
       39. The computer-executable process steps of claims  37  or  38 , further comprising: 
       code to determine if the row was relocated to a different physical page.  
     
     
       40. The computer-executable process steps of  claim 39 , wherein determining if the row was relocated is done with a pseudo-delete mechanism. 
     
     
       41. The computer-executable process steps of  claim 39 , wherein determining if the row was relocated, further comprising: 
       code to analyze an operation code in the at least one log record;  
       code to determine if the row has a clustered key;  
       code to save the value of the clustered key; and  
       code to analyze a set of log records to determine what modification each log record made and if a clustered key in each log record matches the saved clustered key.  
     
     
       42. The computer-executable process steps of  claim 39 , wherein determining if the row was relocated further comprises: 
       code to analyze an operation code in the at least one log record; and  
       code to determine if the row has a forward pointer.  
     
     
       43. The computer-executable process steps of  claim 37 ,  38 ,  40 ,  41 , or  42 , wherein the database is a SQL Server database. 
     
     
       44. The computer-executable process steps of  claim 39 , wherein the database is a SQL Server database. 
     
     
       45. An apparatus for configuring a computerized database restoration system wherein the restoration is performed by executing a rollback script, apparatus comprising: 
       memory means which stores one or more computer-executable process steps; and  
       a processor which executes the process steps so as to:  
       choose at least one selection criterion for use in determining if a transaction in a transaction log should be rolled back;  
       determine an end of a time range for use in terminating searching of the transaction log,  
       search the transaction log to find at least one log record that satisfies the at least one selection criterion, wherein the at least one log record contains an operation that is part of a committed transaction;  
       extract the at least one log record from the transaction log;  
       compute a command for use in rolling back the operation contained in the at least one log record; and  
       write the command to a rollback script.  
     
     
       46. The apparatus of  claim 45 , wherein the at least one selection criterion is selected from the group consisting of SPID List, Table List, Activity Type, Time Range, and Logical Row Locator, wherein Logical Row Locator is a specific row within a table described by a standard SQL language. 
     
     
       47. The apparatus of  claim 45 , wherein the processor further executes steps so as to: 
       issue a checkpoint command; and  
       read a log sequence number of a last checkpoint command from a database boot record.  
     
     
       48. The apparatus of  claim 46 , wherein the processor further executes steps so as to: 
       use the at least one selection criteria to determine the end of the time range.  
     
     
       49. The apparatus of  claim 45 , wherein the processor further executes steps so as to: 
       accumulate changes needed to rollback each effected row of a table.  
     
     
       50. The apparatus of  claim 49 , wherein the processor further executes steps so that the transaction is an Insert. 
     
     
       51. The apparatus of  claim 50 , wherein the processor further executes steps so as to: 
       determine if a row affected by the operation in an input log record was subsequently deleted in the database; and  
       determine that no change is needed to rollback the transaction if the row affected by the operation in the input log record was subsequently deleted in the database.  
     
     
       52. The apparatus of  claim 50 , wherein the processor further executes steps so as to: 
       determine if a row affected by the operation in an input log record was subsequently deleted in the database;  
       maintain a temporary table that contains row images as they existed at various time points;  
       remove all rows from the table, except for rows of type “B,” whose Physical Row Id and Table Id match the input log record's Physical Row Id and Object Id;  
       read a data row directly from a physical database page identified by the Physical Row Id in the input log record;  
       create a new row in the table of type “D” and Physical Row Id equal to the input log record's Physical Row Id and DataRow equal to the data row read directly from the physical database page identified by the Physical Row Id in the input log record; and  
       create a new row in the table of type “B”, and Physical Row Id equal to the input log record's Physical Row Id and DataRow equal to the data row read directly from the physical database page identified by the Physical Row Id in the input log record.  
     
     
       53. The apparatus of  claim 49 , wherein the processor further executes steps so that the transaction is a Delete. 
     
     
       54. The apparatus of  claim 53 , wherein the processor further executes steps so as to: 
       remove all rows whose Physical Row Id and Table Id match the input log record's Physical Row Id and Object Id, except those of type “B”; and  
       create a new row in the table of type “I” and Physical Row Id equal to a physical row id of the input log record and DataRow equal to a data row of the input log record.  
     
     
       55. The apparatus of  claim 49 , wherein the processor further executes steps so that the transaction is a Modify. 
     
     
       56. The apparatus of  claim 55 , wherein the processor further executes steps so as to: 
       determine if the table contains a row with the same Row Id as an input log record; and  
       use the row with the same Row Id to perform the Modify transaction.  
     
     
       57. The apparatus of  claim 45 , wherein the at least one selection criterion is Time Range and searching the transaction log comprises using binary search techniques. 
     
     
       58. The apparatus of claims  45 ,  46 ,  47 ,  48 ,  49 ,  50 ,  51 ,  52 ,  53 ,  54 ,  55 ,  56 , or  57 , wherein the database is a SQL Server database. 
     
     
       59. An apparatus for determining the contents of a row in a database at any point in time wherein, apparatus comprising: 
       memory means which stores one or more computer-executable process steps; and  
       a processor which executes the process steps so as to:  
       determine an LSN for the row;  
       search a transaction log using the LSN in order to identify at least one log record that performed a transaction on the row; and  
       filter the at least one log record to determine if the transaction was committed.  
     
     
       60. The apparatus of  claim 59 , wherein the processor further executes steps so as to search in reverse chronological order. 
     
     
       61. The apparatus of  claim 59  or  60 , wherein the processor further executes steps so as to: 
       determine if the row was relocated to a different physical page.  
     
     
       62. The apparatus of  claim 61 , wherein the processor further executes steps so as to: 
       determine if the row was relocated with a pseudo-delete mechanism.  
     
     
       63. The apparatus of  claim 61 , wherein the processor further executes steps so as to: 
       analyze an operation code in the at least one log record;  
       determine if the row has a clustered key;  
       save the value of the clustered key; and  
       analyze a set of log records to determine what modification each log record made and if a clustered key in each log record matches the saved clustered key.  
     
     
       64. The apparatus of  claim 61 , wherein the processor further executes steps so as to: 
       analyze an operation code in the at least one log record; and  
       determine if the row has a forward pointer.  
     
     
       65. The apparatus of  claim 59 ,  60 ,  62 ,  63 , or  64 , wherein the database is a SQL Server database. 
     
     
       66. The apparatus of  claim 61 , wherein the database is a SQL Server database.