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

• US 20020007363A1
• Filed: 05/21/2001
• Published: 01/17/2002
• Est. Priority Date: 05/25/2000
• Status: Active Grant

• Current Assignee: BeyondTrust Software, Inc. (BeyondTrust Corp.)
• Original Assignee: Lumigent Technologies, Inc. (BeyondTrust Corp.)
• Inventors: Vaitzblit, Lev
• Granted Patent: US 6,769,074 B2
• Time in Patent Office: Days
• US Class Current: 707/202
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

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.

Claims

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.