Method and apparatus for transmission of row differences

• US 6,112,197 A
• Filed: 05/29/1998
• Issued: 08/29/2000
• Est. Priority Date: 05/29/1998
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Gollapudi, Sreenivas, Chatterjee, Debashish
• Primary Examiner(s): Vu, Kim Yen
• Assistant Examiner(s): ALAM, SHAHID AL
• Application Number:
  US09/086,753
• Time in Patent Office: 823 Days
• Field of Search: 707/2-5, 707/10, 707/102, 707/101, 707/201, 711/103, 711/112
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

A method and apparatus for is provided for efficiently transmitting multiple rows of data to a client station. The client station generates a query that is transmitted to a remotely located server, which in turn generates a query result. The server transmits the first row of data from the query result to the client. The remaining rows of data are transmitted by first calculating the difference between successive rows of data. Next, the server sends only the unique rows resulting from the calculated row difference to the client. The server also send an indication of the number of non-repeated value columns detected in order to allow reconstruction of the query result by the client station.

Claims

1. A method for transmitting multiple rows of data to a client station based on a query result generated by a remote server, the method comprising the steps:

receiving a query from a client station;

generating the query result based on the received query;

transmitting a first row of data from the query result to the client station;

calculating row differences between successive rows of data contained in the query result; and

transmitting the calculated row differences to the client station, thereby allowing the client station to reconstruct the query result based on the received first row of data and the received row differences.

2. The method of claim 1 wherein the step of calculating the row differences between successive rows of data includes the step of detecting the number of repeated value columns between the successive rows of data.

3. The method of claim 2 wherein the step of transmitting the calculated row differences includes the step of indicating the number of repeated value columns detected by the remote server.

4. The method of claim 1 wherein the step of calculating the row differences between successive rows of data comprises the steps:

scanning a currently active row of data from the query result;

scanning a previous row of data from the query result; and

comparing the content of each column in the currently active row of data to the content of each corresponding column in the previous row of data.

5. The method of claim 4 further comprising the steps:

if the content of a compared column in the currently active row of data is equal to the content of a corresponding column in the previous row of data, then incrementing the value of a counter that indicates the number of repeated value columns detected in the currently active row of data; and

if the content of a compared column in the currently active row of data does not equal the content of a corresponding column of the previous row of data, then performing the step of transmitting the calculated row differences.

6. The method of claim 5 wherein the step of transmitting the calculated row differences includes the steps:

transmitting the counter to the client station;

transmitting a current column in the currently active row of data to the client station; and

transmitting all subsequent columns in the currently active row of data to the client station.

7. The method of claim 4 wherein the step of transmitting the calculated row differences further includes the steps:

determining if the content of all columns in the currently active row of data equal the content of all corresponding columns in the previous row of data; and

if all columns in the currently active row of data are equal, then transmitting a flag to the client station to indicate that all columns in the currently active row are common to the columns in the previous row of data.

8. The method of claim 1 wherein the step of calculating a row difference between successive rows of data comprises the steps:

scanning a currently active row of data from the query result;

scanning a previous row of data from the query result; and

generating a bit vector containing a plurality of entries corresponding to the number of columns in the currently active row of data.

9. The method of claim 8 further comprising the steps:

comparing the content of each column in the currently active row of data to the content of each corresponding column in the previous row of data stored in the previous row buffer;

if the content of a compared column in the currently active row of data is equal to the content of a corresponding column in the previous row of data, then storing a first value in the corresponding entry of the bit vector; and

if the content of a compared column in the currently active row of data does not equal the content of the corresponding column of the previous row of data, then storing a second value in the corresponding entry of the bit vector.

10. The method of claim 9 wherein the step of transmitting the calculated row differences comprises the steps:

transmitting the bit vector to the client station; and

transmitting, to the client station, columns from the currently active row of data that are not equal to corresponding columns in the row of data.

11. A method for receiving multiple rows of data from a remote server comprising the steps:

generating a query by a client station;

transmitting the query to the server;

receiving a first row of data from a query result generated by the server based on the transmitted query;

receiving calculated row differences from the server; and

reconstructing the query result generated by the server, based on the received first row of data and the received row differences.

12. The method of claim 11 wherein the step of receiving calculated row differences includes the steps:

receiving a counter that indicates the number of repeated value columns detected in a currently active row of data;

receiving a current column from the currently active row of data; and

receiving all subsequent columns from the currently active row of data.

13. The method of claim 12 wherein the step of reconstructing further comprises the steps:

copying a plurality of columns, equal to the value of the received counter, from the received row of data to a buffer; and

appending the received subsequent columns to the plurality of columns stored in the buffer in order to reconstruct the currently active row of data in the query result.

14. The method of claim 11 wherein the step of receiving calculated row differences further includes a step of receiving a flag that indicates that all columns in a currently active row are common to columns in a previous row of data.

15. The method of claim 11 wherein the step of receiving calculated row differences includes the steps:

receiving a bit vector containing a plurality of entries corresponding to the number of columns in a currently active row of data, each entry storing a value that indicates whether a content of the currently active row of data is equal to the content of a corresponding column in a previously received row of data; and

receiving columns from the currently active row of data that are not equal to corresponding columns in the previously received row of data.

16. The method of claim 15 wherein the step of reconstructing comprises the steps:

examining the content of each entry of the received bit vector;

if an examined entry contains a first value then performing the steps;

retrieving a value stored in a corresponding column of the previously received row of data, and storing the retrieved value in a column of a buffer; and

if an examined entry contains a second value then performing the steps;

retrieving a value stored in a corresponding column of the received row difference, and

storing the retrieved value in a column of the buffer.

17. A computer-readable medium carrying one or more sequences of instructions for transmitting multiple rows of data to a client station based on a query result generated by a remote server, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

transmitting a first row of data of the query result from the remote server to the client station;

calculating row differences between successive rows of data contained in the query result; and

transmitting the calculated row differences to the client station;

thereby allowing the client station to reconstruct the query result based on the received first row of data and the received row differences.

18. The computer readable medium of claim 17 wherein the step of calculating the row differences between successive rows of data includes the step of detecting the number of repeated value columns between the successive rows of data.

26. The computer readable medium of claim 17 wherein the step of calculating row differences between successive rows of data comprises the steps:

scanning a currently active row of data from the query result;

scanning a previous row of data from the query result; and

generating a bit vector containing a plurality of entries corresponding to the number of columns in the currently active row of data.

27. The computer readable medium of claim 26 further comprising the steps:

comparing the content of each column in the currently active row of data to the content of each corresponding column in the previous row of data;

if the content of a compared column in the currently active row of data is equal to the content of a corresponding column in the previous row of data, then storing a first value in the corresponding entry of the bit vector; and

if the content of a compared column in the currently active row of data does not equal the content of the corresponding column of the previous row of data, then storing a second value in the corresponding entry of the bit vector.

28. The computer readable medium of claim 27 wherein the step of transmitting the calculated row differences comprises the steps:

transmitting the bit vector to the client station; and

transmitting to the client station columns from the currently active row of data that are not equal to corresponding columns in the previous row of data.

29. The computer readable medium of claim 28 wherein the step of reconstructing comprises the steps:

examining the content of each entry of the received bit vector;

if an examined entry contains a first value then performing the steps;

retrieving a value stored in a corresponding column of a previously received row of data, and

storing the retrieved value in a column of a receive buffer; and

if an examined entry contains a second value then performing the steps;

retrieving a value stored in a corresponding column of the received row difference, and

storing the retrieved value in a column of a receive buffer.

19. The computer readable medium 18 wherein the step of transmitting the calculated row differences includes the step of indicating the number of repeated value columns detected by the remote server.

20. The computer readable medium of claim 19 wherein the step of calculating row differences between successive rows of data comprises the steps:

scanning a currently active row of data from the query result;

scanning a previous row of data from the query result; and

comparing the content of each column in the currently active row of data to the content of each corresponding column in the previous row of data.

21. The computer readable medium of claim 20 wherein:

the previous row of data is stored into a first buffer; and

the currently active row of data is stored into a second buffer.

22. The computer readable medium of claim 20 further comprising the steps:

if the content of a compared column in the currently active row of data is equal to the content of a corresponding column in the previous row of data, then incrementing the value of a counter that indicates the number of repeated value columns detected in the currently active row of data; and

if the content of a compared column in the currently active row of data does not equal the content of a corresponding column of the previous row of data, then performing the step of transmitting the calculated row differences.

23. The computer readable medium of claim 22 wherein the step of transmitting the calculated row differences includes the steps:

transmitting the counter to the client station;

transmitting a current column in the currently active row of data to the client station; and

transmitting all subsequent columns in the currently active row of data to the client station.

24. The computer readable medium of claim 23 wherein the step of reconstructing further comprises the steps:

copying a plurality of columns, equal to the value of the received counter, from the received row of data to a buffer; and

appending the received subsequent columns to the plurality of columns stored in the buffer in order to reconstruct the currently active row of the query result.

25. The computer readable medium of claim 20 wherein the step of transmitting the calculated row differences further includes the steps:

determining if the content of all columns in the currently active row of data equal the content of all corresponding columns in the previous row of data; and

if all columns in the currently active row of data are equal, then transmitting a flag to the client station to indicate that all columns in the currently active row are common to the columns in the previous row of data.

30. A system for transmitting at least one row of data based on a query result comprising:

a client station configured to generate a query and transmit the query to said client station; and

a remotely located server for receiving the query generated by the client station, said server being configured to;

generate a query result having at least one row of data, based on the received query,

transmit a first row of data of the query result to said client station,

calculate row differences between successive rows of data contained in the query result, and

transmit the calculated row differences to said client station;

said client station being further configured to reconstruct the query result based on the received row of data and the received row differences.

31. The system of claim 30 wherein said server is further configured to calculate the row differences between successive rows of data contained in the query result by performing the steps:

scanning a currently active row of data from the query result;

scanning a previous row of data from the query result;

comparing the content of each column in the currently active row of data to the content of each corresponding column in the first row of data;

if the content of a compared column in the currently active row of data is equal to the content of the corresponding column of the previous row of data, then incrementing the value of a counter that indicates the number of repeated value columns detected in the currently active row of data; and

if the content of a compared column in the currently active row of data does not equal the content of the corresponding column of the previous row of data, then performing the step of transmitting the calculated row differences.

32. The system of claim 31 wherein said server is further configured to transmit the calculated row differences by performing the steps:

determining if the content of all columns in the currently active row of data equal the content of all corresponding columns in the previous row of data; and

if all the columns are equal, then transmitting a flag value to the client station to indicate that all columns in the currently active row are common to the columns in the previous row of data.

33. The system of claim 31 wherein said server is further configured transmit the calculated row differences by performing the steps:

transmitting the counter to said client station;

transmitting the current column to the client station; and

transmitting all subsequent columns in the currently active row of data to the client station.

34. The system of claim 33 wherein said client station is further configured to reconstruct the query result by performing the steps:

copying a plurality of columns, equal to the value of the received counter, from a previously received row of data to a buffer; and

appending the received subsequent columns to the plurality of columns stored in the buffer in order to reconstruct the currently active row of the query result.

35. The system of claim 30 wherein said server is further configured to calculate the row differences between successive rows of data contained in the query result by performing the steps:

scanning a currently active row of data from the query result;

scanning a previous row of data from the query result;

generating a bit vector containing a plurality of entries corresponding to the number of columns in the currently active row of data;

comparing the content of each column in the currently active row of data to the content of each corresponding column in the previous row of data;

if the content of a compared column in the currently active row of data is equal to the content of a corresponding column in the previous row of data, then storing a first value in the corresponding entry of the bit vector; and

if the content of a compared column in the currently active row of data does not equal the content of the corresponding column of the previous row of data, then storing a second value in the corresponding entry of the bit vector.

36. The system of claim 35 wherein said server is further configured to transmit the calculated row differences by performing the steps:

transmitting the bit vector to the client station; and

transmitting columns from the currently active row of data that are not equal to corresponding columns in the previous row of data to the client station.

37. The system of claim 36 wherein said client station is further configured to reconstruct the query result by performing the steps:

examining the content of each entry of the received bit vector;

if an examined entry contains a first value then performing the steps;

retrieving a value stored in a corresponding column of the previously received row of data, and

storing the retrieved value in a column of a buffer; and

if an examined entry contains a second value then performing the steps;

retrieving a value stored in a corresponding column of the received row difference, and

storing the retrieved value in a column of a buffer.