01-08-2012, 03:50 PM
Fast and Adaptive Browsing State Recovery for Multimedia Consumer Electronics Devices
[attachment=29918]
Abstract
Most multimedia consumer electronics (CE)
devices, such as smart phones, MP3 players, PMPs, and
digital cameras, allow users to search and browse multimedia
contents stored in the device. For multimedia CE devices,
there are two important requirements: (1) the search results
displayed in the browser screen must be restored when the
device is turned off and later turned back on, and (2) the
search results displayed in the browser screen must be
updated dynamically to reflect data changes made by other
applications. These two requirements have been handled in
rather ad-hoc and inefficient manners until now. In this paper,
we propose an efficient and systematic solution to meet the
two requirements. The proposed solution enables us to save
the current browsing state so that the search results displayed
in the browser screen can be restored instantly at a later time.
Furthermore, the proposed solution restores the browsing
state adaptively to reflect data changes made after saving.
Through performance evaluation in a real multimedia CE
device, we show that the proposed method provides excellent
performance compared to existing methods1.
Index Terms — Browsing State Recovery, Multimedia CE
Device, Query Processing, Embedded DBMS.
I. INTRODUCTION
Multimedia Consumer Electronics (CE) devices, such as
smart phones, MP3 players, PMPs, and digital cameras, are
electronic equipments that are daily used to create, store, and
play multimedia contents. Multimedia CE devices store a
large number of multimedia contents, and provide users with
the ability to search and browse multimedia contents stored in
the devices [1].
Multimedia CE devices typically provide metadata-based
browsing to search and browse multimedia contents stored in
the devices [2]. Fig. 1(a) shows an example of metadata-based
browsing. The metadata-based browsing is a more advanced
method than the traditional folder-based browsing, because it
enables users to reach the desired contents through various
routes. In metadata-based browsing, each multimedia content
is tagged with metadata (e.g., ID3 tags). A user then browses
multimedia contents by their metadata (e.g., genre, artist,
album, etc.).
1Seokjin Hong is with Samsung Electronics, Yongin, Gyeonggi-do 446-
712, Korea (e-mail: s.jin.hong[at]samsung.com).
Ki Yong Lee is with Sookmyung Women’s University, Seoul 140-742,
Korea (e-mail: kiyonglee[at]sookmyung.ac.kr) (Corresponding author).
Ki Yong Lee is with Samsung Electronics, Yongin, Gyeonggi-do 446-712,
Korea (e-mail: kiyong07.lee[at]samsung.com).
(a) Example of metadata-based browsing
SELECT Id, Title
FROM Music
WHERE Artist = “Beatles”
(b) Example of a browsing query
All Artists
“ABBA”
“Beatles”
“Chicago”
Genre
Artist
Album
Track
Title #210
Title #211
…
Title #219
All Albums
“Revolver”
“Help!”
“Let it be”
Title #1
Title #500
Fig. 1 Metadata-based browsing in multimedia CE devices
In order to facilitate the efficient browsing of multimedia
contents, embedded database management systems (DBMSs)
are widely used in multimedia CE devices. Once we store
metadata in the DBMS, we can retrieve the desired
multimedia contents efficiently by submitting a browsing
query to the DBMS. Fig. 1(b) shows an example of browsing
query, which retrieves all MP3 files whose artist is “Beatles”.
If a user selects “Artist”, “Beatles”, and then “All albums”
from the menu shown in Fig. 1(a), the query in Fig. 1(b) is
submitted to the DBMS. The DBMS then executes the query
and open a cursor on the result set of the query. A cursor is a
pointer to a record in the result set. Because multimedia CE
devices typically have limited screen size, the result set is split
into multiple pages. The user then browses the result set by
moving the cursor forward and backward.
For multimedia CE devices, there are two important and
common requirements as follows:
(1) Fast recovery of the browser screen on power-off and
on: Unlike PC or servers, multimedia CE devices are
frequently turned on and off. Because users want to continue
to see the last displayed screen even when the device is turned
off and later turned back on, the search results displayed in the
browser screen must be restored quickly when the device is
turned back on. For example, in Fig. 1(a), a user is browsing
from the 210th to the 219th title among all the 500 titles of the
Beatles. If the user turns off the device and later turns it back
on, those titles should be displayed in the browser screen
again without any user noticeable delay.
S. Hong et al.: Fast and Adaptive Browsing State Recovery for Multimedia Consumer Electronics Devices 165
To restore the search results displayed in the browser screen,
existing methods (1) re-execute the query, (2) move the cursor
from the beginning to its original position in the result set, and then
(3) retrieve the last displayed results again. This approach is very
simple, but it is inefficient when the result set is large and the
original cursor position is far from the beginning of the result set.
(2) Adaptive update of the browser screen on data changes:
During metadata-based browsing, multimedia contents can be
inserted, deleted, or updated by other applications. These
changes should be reflected to the browser screen immediately
in order to provide the user with up-to-date data. For example,
consider a user who is browsing the search results in Fig. 1(a).
If new MP3 files are added to the device by the insertion of a
memory card or through a wireless network, those MP3 files
should be reflected to the displayed results immediately.
To reflect data changes to the browser screen, existing
methods (1) stop the browsing query, (2) re-execute the query,
(3) move the cursor from the beginning to its original position
in the result set, and then (4) retrieve the updated results from
the updated data. However, this approach has the same
problem described above, because the cursor should be moved
to its original position. Moreover, the original cursor position
may be changed due to data changes. Existing methods,
however, do not address this problem.
Although these two requirements are very important and
common in multimedia CE devices, they have been handled in
rather ad-hoc and inefficient manners until now. In this paper,
we propose an efficient and systematic solution to meet the
two requirements, which is built into the DBMS. The
proposed solution enables us to save the current browsing
state so that the search results displayed in the browser screen
can be restored instantly at a later time. The proposed save
and restore processes take only a very short time, regardless of
the cursor position in the result set. Furthermore, the proposed
solution restores the browsing state adaptively to reflect data
changes made after the browsing state is saved. We present a
complete restore process that considers all possible cases of
data changes. Through performance evaluation in a real
multimedia CE device, we show that the proposed solution
provides excellent performance compared to existing methods.
The remainder of the paper is organized as follows: In
Section II, we review some preliminaries and related work.
Section III describes the problem in detail and Section IV
presents the proposed solution. In Section V, we discuss
further considerations. Section VI presents experimental
results and Section VII concludes the paper.
II. PRELIMINARIES AND RELATED WORK
In this section, we briefly describe query processing in
multimedia CE devices and introduce some related researches.
A. Query Processing
Generally, a DBMS translates a query into a query
evaluation plan, which is represented as a tree [3]. Fig. 2
shows an example of query evaluation plan. In a query
evaluation plan, each internal node represents an operator and
each leaf node represents a table. There are two approaches to
evaluate a query [3]:
? Music.id = Content.id
genre = ‘pop’
Music
Content
SortMusic.title
Fig. 2 An example of query evaluation plan
Materialization: Starting from the leaf nodes, each node
in the query evaluation plan is evaluated and its entire result is
stored in a temporary table. The parent nodes are evaluated
using the results of the child nodes stored in the temporary
tables. The result of the root node becomes the final result of
the query.
Pipelining: Each intermediate result of a node is delivered
to its parent immediately without being stored in a temporary
table. Whenever a parent node receives intermediate results
from the child nodes, it produces its own intermediate result
and delivers the result to its parent node.
In multimedia CE devices, a query is typically executed
using the pipelining approach, for the following reasons
[4][5][6]: First, the pipelining approach provides a faster
response time than the materialized approach, because it can
return a partial result without gathering all the results of the
descendant nodes. In practice, the response time of a CE
device is required not to exceed 100 ms, which is the
psychological boundary value for the average user not to
sense the delay [7][8][9]. Second, the pipelining approach
does not require a large amount of memory to store the
temporary results. Thus, it is more suitable for CE devices that
typically have limited memory.
B. Iterator Model
The pipelining approach described in Section II-A is
usually implemented using the iterator model. In the iterator
model, each node in a query evaluation plan is called an
iterator. Each iterator provides three functions: Open(), Next(),
and Close() [10]. Open() initializes the iterator. Next() returns
the next output record of the iterator. Close() tells the iterator
that no more output records are required. To get the results of
the query, the system makes repeated calls to Next() on the
root iterator. Each time an iterator receives a Next() call, it
recursively calls Next() on its child iterators. A leaf iterator
fetches a record from the table and returns it to the parent
iterator. On receiving input records from the child iterators,
the parent iterator performs its own operation, produces its
output record, and sends the output record to its parent iterator.
166 IEEE Transactions on Consumer Electronics, Vol. 57, No. 1, February 2011
Eventually, the root iterator returns the final output records
of the query.
In order to return the correct next output record on each
Next() call, each iterator maintains some information to
indicate its current record. The current record of the root
iterator corresponds to the current cursor position in the
result set. We will describe this information in more detail
in Section IV-A.
C. Related Work
There have been a few researches similar to our work.
[11] and [12] propose a framework for suspending and
resuming complex, long-running decision support queries.
They temporarily suspend the queries that require a lot of
resources (e.g., memory, CPU) and much time, and make
the resources be returned for short-running high-priority
queries. The suspended queries are resumed after the shortrunning
high-priority queries are executed using the
resources.
[11] and [12] are similar to our work from the point of
view that they propose a framework for suspending and
resuming a query. However, our work is different from
them for the following reasons: First, we focus on saving
and restoring the browsing state, which enables the user to
continue to see the last displayed search results. On the
other hand, [11] and [12] focus on suspending and
resuming the progress of a complex, long-running query
that occupies a lot of resources. Second, more importantly,
the proposed solution handles data changes made after the
browsing state is saved, which is a very important problem
in CE devices. [11] and [12], however, do not address this
problem.
III. PROBLEM DESCRIPTION
In this section, we describe the problem considered in this
paper in detail. We assume that a browsing query is executed
using the pipelining approach. With the pipelining approach, a
browsing query returns not all the result records at a time, but
returns only a single result record at a time. For example,
consider Fig. 3, where the browser screen can display 10
records in one page. Let Q be a browsing query. In order to
display the first result page of Q, the system calls Next() on
the root iterator 10 times, which returns the first 10 result
records of Q. Now the cursor is on the 10th record of the
result set. If the user moves to the next result page, the system
calls Next() on the root iterator another 10 times, which makes
the cursor move to the 20th record of the result set.
The first record The 10th record The 20th record The last record
The first page The second page
Cursor
Result set
Fig. 3 Cursor position
Now suppose that the device is turned off and later turned
back on. In order to restore the last browser screen, existing
methods re-execute Q and then call Next() on the root iterator
20 times to move the cursor from the beginning to its original
position in the result set. Then, the last 10 result records are
retrieved again. Therefore, the response time increases as the
original cursor position is far from the beginning of the result
set.
To solve this problem, we provides new functionalities that
enable us to save and restore the current browsing state. The
proposed solution provides the following two processes,
which can be built into any general purpose DBMS:
SaveBrowsingState(): saves the current browsing state,
which includes the current cursor position.
RestoreBrowsingState(): restores the browsing state from
the saved browsing state.
If we save the current browsing state by calling
SaveBrowsingState() before the device is turned off, we can
restore the original cursor position instantly by calling
RestoreBrowsingState() after the device is turned back on.
Because we do not need to call Next() on the root iterator
repeatedly, the response time is significantly reduced.
Furthermore, we can continue to browse the result set by
moving the cursor forward and backward.
The proposed solution also enables us to update the browser
screen efficiently to reflect data changes made by other
applications during browsing. Suppose that, in Fig. 3, a new
MP3 file is added to the device during browsing. If it
corresponds to the 15th record in the result set, it should appear
in the browser screen when the user moves to the second result
page. On the other hand, if the 18th record in the result set is
removed during browsing, it should not appear in the second
result page. However, these newly added or deleted records
cannot be reflected to the result set while the cursor is open.
This is because a lock is held on the table while the cursor is
open, so that the table cannot be updated by other applications
until the lock is released. In order to reflect these changes to the
result set, existing methods stop Q to close the cursor, update
the table, re-execute Q, and then call Next() on the root iterator
20 times to move the cursor from the beginning to its original
position in the result set. Therefore, also in this case, the
response time increases as the original cursor position is far
from the beginning of the result set.
If we save the current browsing state by calling
SaveBrowsingState() before stopping Q, we can restore the
original cursor position instantly at a later time by calling
RestoreBrowsingState(). Furthermore, RestoreBrowsingState()
restores the browsing state adaptively to reflect data changes
made after the browsing state is saved. Therefore, the cursor
position is always properly restored even when existing
records in the result set are removed or new records are added
to the result set. We will describe the proposed save and
restore processes in detail in the next section.
S. Hong et al.: Fast and Adaptive Browsing State Recovery for Multimedia Consumer Electronics Devices 167
IV. THE PROPOSED SOLUTION
A. Basic Concepts
Let Q be a browsing query. Let P be a query evaluation
plan for Q. We call each node in P an iterator. We classify
iterators into the following three categories:
Leaf iterator: A leaf iterator is an iterator for a leaf node
in the query evaluation plan. There are two kinds of leaf
iterators: table iterator and index iterator. A table iterator
sequentially fetches records from a table in the order of their
record identifiers (i.e., RID). An index iterator successively
fetches records from a table in the order of their index key
values (e.g., B+-tree).
Pipelined iterator: A pipelined iterator is an iterator for an
internal node in the query evaluation plan, which is executed
in a pipelined manner. Whenever receiving input records from
the child iterators, a pipelined iterator generates its own output
records, and then passes it immediately to its parent iterator.
Examples of pipelined iterators are select iterator, project
iterator, and join iterator, each of which performs selection,
project, and join operations [10], respectively.
Materialized iterator: A materialized iterator is an iterator
for an internal node in the query evaluation plan, which is
executed in a materialized manner. A materialized iterator
receives all input records from its child iterators, generates
and stores its entire results in a temporary table, and then
successively fetch records from the temporary table. Examples
of materialized iterators are sort iterator and aggregate
iterator, each of which performs sort and aggregate (groupby)
operations [10], respectively
Whenever Next() on the root iterator of P is called, the next
output record of Q is returned and the cursor moves to that
record. In order to return the correct next output record of Q
on each Next() call, each iterator in P maintains some
information.
Definition 1. Let n be an iterator of a query evaluation plan.
The current record of n, denoted by cr(n), is the most recent
output record of n.
Definition 2. Let n be an iterator of a query evaluation plan.
The state of n, denoted by state(n), is the internal information
of n used to indicate cr(n).
Depending on the kind of an iterator, the state of the iterator
is defined differently, as described below:
Leaf iterator: For a table iterator n, state(n) is defined as
RID, which is a record identifier that uniquely identifies a
record in the table. For an index iterator n, state(n) is defined
as (indexKey, RID), where indexKey is an index key value and
RID is a record identifier that uniquely identifies a record if
there are multiple records with the same indexKey.
Pipelined iterator: For a pipelined iterator n, state(n) is
defined as the set of the current records of its child iterators,
i.e., state(n) = {cr© | c is a child iterator of n}. For example,
a join iterator obtains its output record by joining the current
records of its child iterators.
Materialized iterator: For a sort iterator n, state(n) is
defined as (sortKey, RID), where sortKey is a sort key value,
and RID is a record identifier that uniquely identifies a record
in the temporary table if there are multiple records with the
same sortkey. For an aggregate iterator n, state(n) is defined as
GID, which is a grouping attribute(s) value.
Now we define the browsing state as follows:
Definition 3. Let P be a query evaluation plan. The
browsing state of P, denoted by BS(P), is defined as BS(P) =
{state(n) | n is an iterator of P}.
In other words, the browsing state of a query evaluation
plan is the set of the states of all iterators in the query
evaluation plan. Now we can formally describe the proposed
save and restore processes
SaveBrowsingState(): Given a query evaluation plan P,
this process saves BS(P) by serializing it to disk.
RestoreBrowsingState(): Given a query evaluation plan P
and a saved browsing state B, this process makes BS(P) equal
to B.
Save Serialize
BrowsingState()
Restore
BrowsingState()
Join
Table Index
Project
Key
Join
Table Index
Project
Key
Fig. 4 The concept of saving and restoring the browsing state
Fig. 4 illustrates the concept of saving and restoring the
browsing state. Note that the state of a pipelined iterator can
be restored solely from the current records of its child iterators.
Therefore, we do not need to store the states of pipelined
iterators, so we store only the states of leaf iterators and
168 IEEE Transactions on Consumer Electronics, Vol. 57, No. 1, February 2011
materialized iterators. We will describe the save and restore
processes in more detail in Section IV.
Finally, we define the current cursor position in the result
set as follows:
Definition 4. Let Q be a browsing query. Let P be a query
evaluation plan for Q. Let r be the root iterator of P. The
current cursor position in the result set of Q is equal to cr®.
B. Reflection of Data Changes
As we described in Section III, the tables involved in the
query can be changed after the browsing state is saved. As a
result, new records can be added to the result set, or existing
records can be removed from the result set. These changes
should be handled properly because the browsing state can be
changed.
The proposed solution automatically reflects these data
changes to the restored browsing state. The proposed solution
follows the following two rules when restoring the browsing
state:
Rule 1: If the record indicated by the state of an iterator
still exists, the state of the iterator is restored as the saved one.
Rule 2: If the record indicated by the state of an iterator is
disappeared due to data changes, the state of the iterator is
restored so as to indicate its next output record.
In Rule 2, the term "next" has different meanings for
different iterators. For example, for a table iterator, the next
output record is the record with the next highest RID. Fig. 5
shows an example of restoring the state of a table iterator.
Suppose that the current record of the table iterator was '300'
when the browsing state was saved, as shown in Fig. 5(a). If
there is no data change, the current record is restored as '300'.
If '200' is deleted and '600' is inserted into the table after the
browsing state is saved, the current record is restored as '300',
as shown in Fig. 5(b), because '300' still exists. However, if
'300' and '400' are deleted from table after the browsing state
is saved, the current record is restored as '500', as shown in
Fig. 5©, because '500' is the next output record of '300'.
RID
100
200
300
400
500
RID
100
300
400
500
600
RID
100
200
500
(a) Original position (b) If ‘200’ is deleted
and ‘600’ is inserted
© If ‘300’ and ‘400’
are deleted
Fig. 5 Restoring the state of a table iterator
According to the semantic of an iterator, the next output
record of the iterator is determined differently. We will
describe the complete restore process in Section IV-D.
C. The Save Process
In this section, we describe the SaveBrowsingState()
procedure in detail. Fig. 6 shows the SaveBrowsingState()
procedure. The SaveBrowsingState() procedure simply calls
the SaveInteratorState() procedure for the root iterator of the
query evaluation plan. The SaveIteratorState() procedure
saves the state of the input iterator and then recursively calls
itself on the child iterators.
If the input iterator is a leaf iterator or a materialized
iterator, the SaveIteratorState() function saves the state of the
iterator. If the input iterator is a materialized iterator, it
additionally stores the timestamp that indicates the time when
the temporary table is stored. The timestamp will be used in
the restore process to determine whether the tables below the
materialized iterator are changed after the temporary table is
stored. Note that we do not store the states of pipelined
iterators, because they can be restored from the states of the
child iterators.
Fig. 6 The procedure for saving the browsing state
D. The Restore Process
In this section, we describe the RestoreBrowsingState()
procedure in detail. Fig. 7 shows the RestoreBrowsingState()
procedure. The RestoreBrowsingState() procedure simply
calls the RestoreIteratorState() procedure for the root iterator
of the query evaluation plan. The RestoreIteratorState()
procedure restores the state of the input iterator and then
recursively calls itself on the child iterators.
Procedure SaveBrowsingState(P)
Input P: a query evaluation plan
1: Let r = the root iterator of P;
2: SaveIteratorState®;
End procedure
Procedure SaveIteratorState(N)
Input N: an iterator
1: if (N is a table iterator) then
2: Store RID to disk;
3: else if (N is an index iterator) then
4: Store (indexKey, RID) to disk;
5: else if (N is a sort iterator) then
6: Store (sortKey, RID, timestamp) to disk;
7: else if (N is an aggregate iterator) then
8: Store GID to disk;
9: else
10: for each child iterator C of N do
11: SaveIteratorState©;
12: end for
13: end if
S. Hong et al.: Fast and Adaptive Browsing State Recovery for Multimedia Consumer Electronics Devices 169
Fig. 7 The procedure for restoring the browsing state
Now we describe how the RestoreIteratorState() procedure
handles different types of iterators. If the input iterator is a
leaf iterator, RestoreIteratorState() restores the state of the
iterator as the saved state. If the record indicated by the state
of the iterator is disappeared due to data changes, the state of
the iterator is restored to indicate the next output record. For a
table iterator, the next output record is the record with the next
highest RID. For an index iterator, the next output record is
the record with the same indexKey but the next highest RID,
or the record with the next highest indexKey if there is no
record with the same indexKey.
If the input iterator is a materialized iterator,
RestoreIteratorState() restores the state of the iterator as the
saved state. If the timestamp of the materialized iterator is
older than the last update time of the tables below the
materialized iterator, the query evaluation plan rooted at the
materialized iterator is re-evaluated and the entire results are
stored in a temporary table again. Then, the state of the
iterator is restored as the saved state. If the record indicated by
the state of the iterator does not exist, the state of the iterator
is restored so as to indicate the next output record. For a sort
iterator, the next output record is the record with the same
sortKey but the next highest RID, or the record with the next
highest sortKey if there is no record with the same sortKey.
For an aggregate iterator, the next output record is the record
with the next highest GID.
Table
A B
1 10
2 20
2 30
2 40
3 50
Group-by
A COUNT(*)
1 1
2 3
3 1
Table
A B
1 10
2 15
2 40
3 50
Table
A B
1 10
3 50
Group-by
A COUNT(*)
1 1
3 1
(a) Original position (b) If (2, 20) and (2,30) are
deleted, and (2, 15) is
inserted
© If all the records whose
GID is 2 are deleted
Group-by
A COUNT(*)
1 1
2 2
3 1
Fig. 8 An example of restoring the state of an aggregate iterator
Fig. 8 shows an example of restoring the state of an
aggregate iterator, which is one of materialized iterators.
Suppose that the current record of the aggregate iterator was
(2, 3) when the browsing state was saved, as shown in Fig.
8(a). Note that the GID of (2, 3) is 2, because the value of the
grouping attribute A is 2. If there is no data change, the
current record is restored as (2, 3). If (2, 20) and (2, 30) are
deleted from the table and (2, 15) is inserted into the table, the
aggregate iterator is re-revaluated and the entire results are
stored in a temporary table again. In this case, the current
record of the aggregate iterator is restored as (2, 2), as shown
in Fig. 8(b), because (2, 2) is the record whose GID is 2. On
the other hand, if (2, 20), (2, 30), and (2, 40) are deleted from
the table, the current record of the aggregate iterator is
restored as (3, 1), as shown in Fig. 8©, because there is no
record whose GID is 2 and (3, 1) is the record with the next
highest GID.
If the input iterator is a pipelined iterator, the
RestoreIteratorState() procedure restores the state of the
iterator using the current records of its child iterators. The
state of a pipelined iterator is restored differently depending
on the type of the iterator.
Fig. 9 shows an example of restoring the state of a join
iterator. Assume that the join iterator is executed using the
indexed nested-loop join algorithm [10]. Suppose that the
current records of the two child iterators are (2, 30) and (2,
300), respectively. If the current records of both the child
iterators are not changed, the current record of the join iterator
is restored as (2, 30, 300), as shown in Fig. 9(a). If (2, 300) is
removed from the table Table2 after the browsing state is
saved, the current record of the right child iterator is restored
as (2, 400). Then, the current record of the join iterator is
determined by joining the current record of the left child
Procedure RestoreBrowsingState(P, B)
Input P: a query evaluation plan
B: the saved browsing state
1: Let r = the root iterator of P;
2: RestoreIteratorState(r, B);
End procedure
Procedure RestoreIteratorState(N, B)
Input N: an iterator
B: the saved browsing state
1: if (N is a table iterator) then
2: Load RID from B;
3: else if (N is an index iterator) then
4: Load (indexKey, RID) from B;
5: else if (N is a sort iterator) then
6: Load (sortKey, RID, timestamp) from B;
7: t = the last update time of the tables below N;
8: if (t > timestamp) then
9: Re-evaluate N and store the result to disk;
10: else if (N is an aggregate iterator) then
11: Load GID from B;
12: t = the last update time of the tables below N;
13: if (t > timestamp) then
14: Re-evaluate N and store the result to disk;
15: else // N is a pipelined iterator
16: for each child iterator C of N do
17: RestoreIteratorState(C, B);
18: end for
19: end if
20: Find the record indicated by the state of N;
21: if (the record is not found) then
22: Make the state indicate the next output record;
23: end if
170 IEEE Transactions on Consumer Electronics, Vol. 57, No. 1, February 2011
iterator (i.e., (2, 30)) with the new current record of the right
child iterator (i.e.., (2, 400)). As a result, the current record of
the join iterator is restored as (2, 30, 400). On the other hand,
if (2, 30) is removed from the table Table1 after the browsing
state is saved, the current record of the left child iterator is
restored as (2, 40). Then, the current record of the join iterator
is determined by joining the new current record of the left
child iterator (i.e., (2, 40)) with the first record in the table
Table2 whose join key value is the same as that of (2, 40) (i.e.,
(2, 200)). As a result, the current record of the join iterator is
restored as (2, 40, 200). In a similar way, the current record of
the other types of pipelined iterators can be restored using the
current records of their child iterators.
Table1
A B
1 10
2 20
2 30
2 40
3 50
Table2
A C
1 100
2 200
2 300
2 400
3 500
? Table1.A = Table2.A
A B C
…
2 30 200
2 30 300
2 30 400
…
Table1
A B
1 10
2 20
2 30
2 40
3 50
Table2
A C
1 100
2 200
2 400
3 500
? Table1.A = Table2.A
A B C
…
2 30 200
2 30 400
2 40 200
…
(a) Original position (b) If (2, 300) is deleted
from Table2
© If (2, 30) is deleted
from Table1
Table1
A B
1 10
2 20
2 40
3 50
? Table1.A = Table2.A
A B C
…
2 20 400
2 40 200
2 40 300
…
Table2
A C
1 100
2 200
2 300
2 400
3 500
Fig. 9 An example of restoring the state of a join iterator
V. FURTHER CONSIDERATIONS
In this section, we describe several additional considerations
for saving and restoring the browsing states.
A. Block-based Iterators
A block-based iterator is an iterator that performs in a
block-by-block way (e.g., block nested loop join iterator)
[10]. Until now, we have considered iterators whose state
includes the information about only a single record. On the
other hand, a block-based iterator maintains several buffers
internally to store a number of records, so they should be
included in the state of the iterator. Fig. 10 shows an
example of a block nested loop join iterator, which is one of
the block-based iterators. The block nested loop join iterator
maintains two buffers internally; the outer buffer for the
outer table and the inner buffer for the inner table. The block
nested loop join operation is executed on the basis of these
two buffers.
In the state of a block-based iterator, in addition to the
current record, we include the information about the first and
last records of each buffer. When the browsing state is saved,
these information are also saved. When the browsing state is
restored, the records between the first and last records of each
buffer are read from the child iterators to fill the buffer. If the
first record of a buffer is removed, the next available record
becomes the first record of the buffer. Similarly, if the last
record of a buffer is removed, the previous available record
becomes the last record of the buffer.
Note that we do not store the buffer itself, but only the
information about the first and last records of the buffer.
This is for the following two reasons: First, if the records in
the buffer are stored on disk, data changes cannot be
reflected to the buffer in the restore process. Second,
dumping the entire buffer takes a long time so that the save
process can be slow.
If the data are changed and the number of records
between the first and last records of a buffer becomes
larger than before, main memory may not be large enough
to keep all the records in the buffer. Furthermore, main
memory can be insufficient because the available memory
itself for the buffer can be varied. In this situation, some
records should be removed from the buffer and
maintained on disk not to break the execution order of the
block-based operations.
Outer buffer
Current
position
The first
record
Outer table Inner table
Current
position
Inner buffer
The first
record
The last
record
The last
record
Fig. 10 The state of a block nested loop join iterator
B. Subquery
The proposed solution can also be applied to subqueries. A
subquery can appear in the WHERE, HAVING, or FROM clause
of a SQL query. If a subquery appears in the WHERE or
HAVING clause, the subquery acts as a condition filter for
each record in the main query. Because all result records of
the subquery should be fetched for each record in the main
query, we don't need to keep track of the current record of the
subquery. Therefore, we do not save the state of the subquery.
If a subquery appears in the FROM clause, the subquery acts
as a table. Thus, in this case, the root iterator of the query
evaluation plan for the subquery is treated as a table iterator.
Therefore, in this case, we save the state of the subquery along
with the state of the main query.
C. Browser Applications
As already mentioned, the proposed solution can be used by
browser applications in multimedia CE devices. A browser
application saves and restores the browsing state to efficiently
handle power-off and data changes made by other applications.
Although the save process incurs additional overhead on the
S. Hong et al.: Fast and Adaptive Browsing State Recovery for Multimedia Consumer Electronics Devices 171
system, the save process takes only an extremely small time,
as will be shown in Section VI. Furthermore, the save process
does not have to be executed on every record fetch. It is
sufficient to execute the save process only in the following
cases:
When the browser screen is changed to a different result
page by the user's interaction.
When the device is turned off.
Because these cases occur only occasionally in practice, our
solution incurs little overhead on the system.
[attachment=29918]
Abstract
Most multimedia consumer electronics (CE)
devices, such as smart phones, MP3 players, PMPs, and
digital cameras, allow users to search and browse multimedia
contents stored in the device. For multimedia CE devices,
there are two important requirements: (1) the search results
displayed in the browser screen must be restored when the
device is turned off and later turned back on, and (2) the
search results displayed in the browser screen must be
updated dynamically to reflect data changes made by other
applications. These two requirements have been handled in
rather ad-hoc and inefficient manners until now. In this paper,
we propose an efficient and systematic solution to meet the
two requirements. The proposed solution enables us to save
the current browsing state so that the search results displayed
in the browser screen can be restored instantly at a later time.
Furthermore, the proposed solution restores the browsing
state adaptively to reflect data changes made after saving.
Through performance evaluation in a real multimedia CE
device, we show that the proposed method provides excellent
performance compared to existing methods1.
Index Terms — Browsing State Recovery, Multimedia CE
Device, Query Processing, Embedded DBMS.
I. INTRODUCTION
Multimedia Consumer Electronics (CE) devices, such as
smart phones, MP3 players, PMPs, and digital cameras, are
electronic equipments that are daily used to create, store, and
play multimedia contents. Multimedia CE devices store a
large number of multimedia contents, and provide users with
the ability to search and browse multimedia contents stored in
the devices [1].
Multimedia CE devices typically provide metadata-based
browsing to search and browse multimedia contents stored in
the devices [2]. Fig. 1(a) shows an example of metadata-based
browsing. The metadata-based browsing is a more advanced
method than the traditional folder-based browsing, because it
enables users to reach the desired contents through various
routes. In metadata-based browsing, each multimedia content
is tagged with metadata (e.g., ID3 tags). A user then browses
multimedia contents by their metadata (e.g., genre, artist,
album, etc.).
1Seokjin Hong is with Samsung Electronics, Yongin, Gyeonggi-do 446-
712, Korea (e-mail: s.jin.hong[at]samsung.com).
Ki Yong Lee is with Sookmyung Women’s University, Seoul 140-742,
Korea (e-mail: kiyonglee[at]sookmyung.ac.kr) (Corresponding author).
Ki Yong Lee is with Samsung Electronics, Yongin, Gyeonggi-do 446-712,
Korea (e-mail: kiyong07.lee[at]samsung.com).
(a) Example of metadata-based browsing
SELECT Id, Title
FROM Music
WHERE Artist = “Beatles”
(b) Example of a browsing query
All Artists
“ABBA”
“Beatles”
“Chicago”
Genre
Artist
Album
Track
Title #210
Title #211
…
Title #219
All Albums
“Revolver”
“Help!”
“Let it be”
Title #1
Title #500
Fig. 1 Metadata-based browsing in multimedia CE devices
In order to facilitate the efficient browsing of multimedia
contents, embedded database management systems (DBMSs)
are widely used in multimedia CE devices. Once we store
metadata in the DBMS, we can retrieve the desired
multimedia contents efficiently by submitting a browsing
query to the DBMS. Fig. 1(b) shows an example of browsing
query, which retrieves all MP3 files whose artist is “Beatles”.
If a user selects “Artist”, “Beatles”, and then “All albums”
from the menu shown in Fig. 1(a), the query in Fig. 1(b) is
submitted to the DBMS. The DBMS then executes the query
and open a cursor on the result set of the query. A cursor is a
pointer to a record in the result set. Because multimedia CE
devices typically have limited screen size, the result set is split
into multiple pages. The user then browses the result set by
moving the cursor forward and backward.
For multimedia CE devices, there are two important and
common requirements as follows:
(1) Fast recovery of the browser screen on power-off and
on: Unlike PC or servers, multimedia CE devices are
frequently turned on and off. Because users want to continue
to see the last displayed screen even when the device is turned
off and later turned back on, the search results displayed in the
browser screen must be restored quickly when the device is
turned back on. For example, in Fig. 1(a), a user is browsing
from the 210th to the 219th title among all the 500 titles of the
Beatles. If the user turns off the device and later turns it back
on, those titles should be displayed in the browser screen
again without any user noticeable delay.
S. Hong et al.: Fast and Adaptive Browsing State Recovery for Multimedia Consumer Electronics Devices 165
To restore the search results displayed in the browser screen,
existing methods (1) re-execute the query, (2) move the cursor
from the beginning to its original position in the result set, and then
(3) retrieve the last displayed results again. This approach is very
simple, but it is inefficient when the result set is large and the
original cursor position is far from the beginning of the result set.
(2) Adaptive update of the browser screen on data changes:
During metadata-based browsing, multimedia contents can be
inserted, deleted, or updated by other applications. These
changes should be reflected to the browser screen immediately
in order to provide the user with up-to-date data. For example,
consider a user who is browsing the search results in Fig. 1(a).
If new MP3 files are added to the device by the insertion of a
memory card or through a wireless network, those MP3 files
should be reflected to the displayed results immediately.
To reflect data changes to the browser screen, existing
methods (1) stop the browsing query, (2) re-execute the query,
(3) move the cursor from the beginning to its original position
in the result set, and then (4) retrieve the updated results from
the updated data. However, this approach has the same
problem described above, because the cursor should be moved
to its original position. Moreover, the original cursor position
may be changed due to data changes. Existing methods,
however, do not address this problem.
Although these two requirements are very important and
common in multimedia CE devices, they have been handled in
rather ad-hoc and inefficient manners until now. In this paper,
we propose an efficient and systematic solution to meet the
two requirements, which is built into the DBMS. The
proposed solution enables us to save the current browsing
state so that the search results displayed in the browser screen
can be restored instantly at a later time. The proposed save
and restore processes take only a very short time, regardless of
the cursor position in the result set. Furthermore, the proposed
solution restores the browsing state adaptively to reflect data
changes made after the browsing state is saved. We present a
complete restore process that considers all possible cases of
data changes. Through performance evaluation in a real
multimedia CE device, we show that the proposed solution
provides excellent performance compared to existing methods.
The remainder of the paper is organized as follows: In
Section II, we review some preliminaries and related work.
Section III describes the problem in detail and Section IV
presents the proposed solution. In Section V, we discuss
further considerations. Section VI presents experimental
results and Section VII concludes the paper.
II. PRELIMINARIES AND RELATED WORK
In this section, we briefly describe query processing in
multimedia CE devices and introduce some related researches.
A. Query Processing
Generally, a DBMS translates a query into a query
evaluation plan, which is represented as a tree [3]. Fig. 2
shows an example of query evaluation plan. In a query
evaluation plan, each internal node represents an operator and
each leaf node represents a table. There are two approaches to
evaluate a query [3]:
? Music.id = Content.id
genre = ‘pop’
Music
Content
SortMusic.title
Fig. 2 An example of query evaluation plan
Materialization: Starting from the leaf nodes, each node
in the query evaluation plan is evaluated and its entire result is
stored in a temporary table. The parent nodes are evaluated
using the results of the child nodes stored in the temporary
tables. The result of the root node becomes the final result of
the query.
Pipelining: Each intermediate result of a node is delivered
to its parent immediately without being stored in a temporary
table. Whenever a parent node receives intermediate results
from the child nodes, it produces its own intermediate result
and delivers the result to its parent node.
In multimedia CE devices, a query is typically executed
using the pipelining approach, for the following reasons
[4][5][6]: First, the pipelining approach provides a faster
response time than the materialized approach, because it can
return a partial result without gathering all the results of the
descendant nodes. In practice, the response time of a CE
device is required not to exceed 100 ms, which is the
psychological boundary value for the average user not to
sense the delay [7][8][9]. Second, the pipelining approach
does not require a large amount of memory to store the
temporary results. Thus, it is more suitable for CE devices that
typically have limited memory.
B. Iterator Model
The pipelining approach described in Section II-A is
usually implemented using the iterator model. In the iterator
model, each node in a query evaluation plan is called an
iterator. Each iterator provides three functions: Open(), Next(),
and Close() [10]. Open() initializes the iterator. Next() returns
the next output record of the iterator. Close() tells the iterator
that no more output records are required. To get the results of
the query, the system makes repeated calls to Next() on the
root iterator. Each time an iterator receives a Next() call, it
recursively calls Next() on its child iterators. A leaf iterator
fetches a record from the table and returns it to the parent
iterator. On receiving input records from the child iterators,
the parent iterator performs its own operation, produces its
output record, and sends the output record to its parent iterator.
166 IEEE Transactions on Consumer Electronics, Vol. 57, No. 1, February 2011
Eventually, the root iterator returns the final output records
of the query.
In order to return the correct next output record on each
Next() call, each iterator maintains some information to
indicate its current record. The current record of the root
iterator corresponds to the current cursor position in the
result set. We will describe this information in more detail
in Section IV-A.
C. Related Work
There have been a few researches similar to our work.
[11] and [12] propose a framework for suspending and
resuming complex, long-running decision support queries.
They temporarily suspend the queries that require a lot of
resources (e.g., memory, CPU) and much time, and make
the resources be returned for short-running high-priority
queries. The suspended queries are resumed after the shortrunning
high-priority queries are executed using the
resources.
[11] and [12] are similar to our work from the point of
view that they propose a framework for suspending and
resuming a query. However, our work is different from
them for the following reasons: First, we focus on saving
and restoring the browsing state, which enables the user to
continue to see the last displayed search results. On the
other hand, [11] and [12] focus on suspending and
resuming the progress of a complex, long-running query
that occupies a lot of resources. Second, more importantly,
the proposed solution handles data changes made after the
browsing state is saved, which is a very important problem
in CE devices. [11] and [12], however, do not address this
problem.
III. PROBLEM DESCRIPTION
In this section, we describe the problem considered in this
paper in detail. We assume that a browsing query is executed
using the pipelining approach. With the pipelining approach, a
browsing query returns not all the result records at a time, but
returns only a single result record at a time. For example,
consider Fig. 3, where the browser screen can display 10
records in one page. Let Q be a browsing query. In order to
display the first result page of Q, the system calls Next() on
the root iterator 10 times, which returns the first 10 result
records of Q. Now the cursor is on the 10th record of the
result set. If the user moves to the next result page, the system
calls Next() on the root iterator another 10 times, which makes
the cursor move to the 20th record of the result set.
The first record The 10th record The 20th record The last record
The first page The second page
Cursor
Result set
Fig. 3 Cursor position
Now suppose that the device is turned off and later turned
back on. In order to restore the last browser screen, existing
methods re-execute Q and then call Next() on the root iterator
20 times to move the cursor from the beginning to its original
position in the result set. Then, the last 10 result records are
retrieved again. Therefore, the response time increases as the
original cursor position is far from the beginning of the result
set.
To solve this problem, we provides new functionalities that
enable us to save and restore the current browsing state. The
proposed solution provides the following two processes,
which can be built into any general purpose DBMS:
SaveBrowsingState(): saves the current browsing state,
which includes the current cursor position.
RestoreBrowsingState(): restores the browsing state from
the saved browsing state.
If we save the current browsing state by calling
SaveBrowsingState() before the device is turned off, we can
restore the original cursor position instantly by calling
RestoreBrowsingState() after the device is turned back on.
Because we do not need to call Next() on the root iterator
repeatedly, the response time is significantly reduced.
Furthermore, we can continue to browse the result set by
moving the cursor forward and backward.
The proposed solution also enables us to update the browser
screen efficiently to reflect data changes made by other
applications during browsing. Suppose that, in Fig. 3, a new
MP3 file is added to the device during browsing. If it
corresponds to the 15th record in the result set, it should appear
in the browser screen when the user moves to the second result
page. On the other hand, if the 18th record in the result set is
removed during browsing, it should not appear in the second
result page. However, these newly added or deleted records
cannot be reflected to the result set while the cursor is open.
This is because a lock is held on the table while the cursor is
open, so that the table cannot be updated by other applications
until the lock is released. In order to reflect these changes to the
result set, existing methods stop Q to close the cursor, update
the table, re-execute Q, and then call Next() on the root iterator
20 times to move the cursor from the beginning to its original
position in the result set. Therefore, also in this case, the
response time increases as the original cursor position is far
from the beginning of the result set.
If we save the current browsing state by calling
SaveBrowsingState() before stopping Q, we can restore the
original cursor position instantly at a later time by calling
RestoreBrowsingState(). Furthermore, RestoreBrowsingState()
restores the browsing state adaptively to reflect data changes
made after the browsing state is saved. Therefore, the cursor
position is always properly restored even when existing
records in the result set are removed or new records are added
to the result set. We will describe the proposed save and
restore processes in detail in the next section.
S. Hong et al.: Fast and Adaptive Browsing State Recovery for Multimedia Consumer Electronics Devices 167
IV. THE PROPOSED SOLUTION
A. Basic Concepts
Let Q be a browsing query. Let P be a query evaluation
plan for Q. We call each node in P an iterator. We classify
iterators into the following three categories:
Leaf iterator: A leaf iterator is an iterator for a leaf node
in the query evaluation plan. There are two kinds of leaf
iterators: table iterator and index iterator. A table iterator
sequentially fetches records from a table in the order of their
record identifiers (i.e., RID). An index iterator successively
fetches records from a table in the order of their index key
values (e.g., B+-tree).
Pipelined iterator: A pipelined iterator is an iterator for an
internal node in the query evaluation plan, which is executed
in a pipelined manner. Whenever receiving input records from
the child iterators, a pipelined iterator generates its own output
records, and then passes it immediately to its parent iterator.
Examples of pipelined iterators are select iterator, project
iterator, and join iterator, each of which performs selection,
project, and join operations [10], respectively.
Materialized iterator: A materialized iterator is an iterator
for an internal node in the query evaluation plan, which is
executed in a materialized manner. A materialized iterator
receives all input records from its child iterators, generates
and stores its entire results in a temporary table, and then
successively fetch records from the temporary table. Examples
of materialized iterators are sort iterator and aggregate
iterator, each of which performs sort and aggregate (groupby)
operations [10], respectively
Whenever Next() on the root iterator of P is called, the next
output record of Q is returned and the cursor moves to that
record. In order to return the correct next output record of Q
on each Next() call, each iterator in P maintains some
information.
Definition 1. Let n be an iterator of a query evaluation plan.
The current record of n, denoted by cr(n), is the most recent
output record of n.
Definition 2. Let n be an iterator of a query evaluation plan.
The state of n, denoted by state(n), is the internal information
of n used to indicate cr(n).
Depending on the kind of an iterator, the state of the iterator
is defined differently, as described below:
Leaf iterator: For a table iterator n, state(n) is defined as
RID, which is a record identifier that uniquely identifies a
record in the table. For an index iterator n, state(n) is defined
as (indexKey, RID), where indexKey is an index key value and
RID is a record identifier that uniquely identifies a record if
there are multiple records with the same indexKey.
Pipelined iterator: For a pipelined iterator n, state(n) is
defined as the set of the current records of its child iterators,
i.e., state(n) = {cr© | c is a child iterator of n}. For example,
a join iterator obtains its output record by joining the current
records of its child iterators.
Materialized iterator: For a sort iterator n, state(n) is
defined as (sortKey, RID), where sortKey is a sort key value,
and RID is a record identifier that uniquely identifies a record
in the temporary table if there are multiple records with the
same sortkey. For an aggregate iterator n, state(n) is defined as
GID, which is a grouping attribute(s) value.
Now we define the browsing state as follows:
Definition 3. Let P be a query evaluation plan. The
browsing state of P, denoted by BS(P), is defined as BS(P) =
{state(n) | n is an iterator of P}.
In other words, the browsing state of a query evaluation
plan is the set of the states of all iterators in the query
evaluation plan. Now we can formally describe the proposed
save and restore processes
SaveBrowsingState(): Given a query evaluation plan P,
this process saves BS(P) by serializing it to disk.
RestoreBrowsingState(): Given a query evaluation plan P
and a saved browsing state B, this process makes BS(P) equal
to B.
Save Serialize
BrowsingState()
Restore
BrowsingState()
Join
Table Index
Project
Key
Join
Table Index
Project
Key
Fig. 4 The concept of saving and restoring the browsing state
Fig. 4 illustrates the concept of saving and restoring the
browsing state. Note that the state of a pipelined iterator can
be restored solely from the current records of its child iterators.
Therefore, we do not need to store the states of pipelined
iterators, so we store only the states of leaf iterators and
168 IEEE Transactions on Consumer Electronics, Vol. 57, No. 1, February 2011
materialized iterators. We will describe the save and restore
processes in more detail in Section IV.
Finally, we define the current cursor position in the result
set as follows:
Definition 4. Let Q be a browsing query. Let P be a query
evaluation plan for Q. Let r be the root iterator of P. The
current cursor position in the result set of Q is equal to cr®.
B. Reflection of Data Changes
As we described in Section III, the tables involved in the
query can be changed after the browsing state is saved. As a
result, new records can be added to the result set, or existing
records can be removed from the result set. These changes
should be handled properly because the browsing state can be
changed.
The proposed solution automatically reflects these data
changes to the restored browsing state. The proposed solution
follows the following two rules when restoring the browsing
state:
Rule 1: If the record indicated by the state of an iterator
still exists, the state of the iterator is restored as the saved one.
Rule 2: If the record indicated by the state of an iterator is
disappeared due to data changes, the state of the iterator is
restored so as to indicate its next output record.
In Rule 2, the term "next" has different meanings for
different iterators. For example, for a table iterator, the next
output record is the record with the next highest RID. Fig. 5
shows an example of restoring the state of a table iterator.
Suppose that the current record of the table iterator was '300'
when the browsing state was saved, as shown in Fig. 5(a). If
there is no data change, the current record is restored as '300'.
If '200' is deleted and '600' is inserted into the table after the
browsing state is saved, the current record is restored as '300',
as shown in Fig. 5(b), because '300' still exists. However, if
'300' and '400' are deleted from table after the browsing state
is saved, the current record is restored as '500', as shown in
Fig. 5©, because '500' is the next output record of '300'.
RID
100
200
300
400
500
RID
100
300
400
500
600
RID
100
200
500
(a) Original position (b) If ‘200’ is deleted
and ‘600’ is inserted
© If ‘300’ and ‘400’
are deleted
Fig. 5 Restoring the state of a table iterator
According to the semantic of an iterator, the next output
record of the iterator is determined differently. We will
describe the complete restore process in Section IV-D.
C. The Save Process
In this section, we describe the SaveBrowsingState()
procedure in detail. Fig. 6 shows the SaveBrowsingState()
procedure. The SaveBrowsingState() procedure simply calls
the SaveInteratorState() procedure for the root iterator of the
query evaluation plan. The SaveIteratorState() procedure
saves the state of the input iterator and then recursively calls
itself on the child iterators.
If the input iterator is a leaf iterator or a materialized
iterator, the SaveIteratorState() function saves the state of the
iterator. If the input iterator is a materialized iterator, it
additionally stores the timestamp that indicates the time when
the temporary table is stored. The timestamp will be used in
the restore process to determine whether the tables below the
materialized iterator are changed after the temporary table is
stored. Note that we do not store the states of pipelined
iterators, because they can be restored from the states of the
child iterators.
Fig. 6 The procedure for saving the browsing state
D. The Restore Process
In this section, we describe the RestoreBrowsingState()
procedure in detail. Fig. 7 shows the RestoreBrowsingState()
procedure. The RestoreBrowsingState() procedure simply
calls the RestoreIteratorState() procedure for the root iterator
of the query evaluation plan. The RestoreIteratorState()
procedure restores the state of the input iterator and then
recursively calls itself on the child iterators.
Procedure SaveBrowsingState(P)
Input P: a query evaluation plan
1: Let r = the root iterator of P;
2: SaveIteratorState®;
End procedure
Procedure SaveIteratorState(N)
Input N: an iterator
1: if (N is a table iterator) then
2: Store RID to disk;
3: else if (N is an index iterator) then
4: Store (indexKey, RID) to disk;
5: else if (N is a sort iterator) then
6: Store (sortKey, RID, timestamp) to disk;
7: else if (N is an aggregate iterator) then
8: Store GID to disk;
9: else
10: for each child iterator C of N do
11: SaveIteratorState©;
12: end for
13: end if
S. Hong et al.: Fast and Adaptive Browsing State Recovery for Multimedia Consumer Electronics Devices 169
Fig. 7 The procedure for restoring the browsing state
Now we describe how the RestoreIteratorState() procedure
handles different types of iterators. If the input iterator is a
leaf iterator, RestoreIteratorState() restores the state of the
iterator as the saved state. If the record indicated by the state
of the iterator is disappeared due to data changes, the state of
the iterator is restored to indicate the next output record. For a
table iterator, the next output record is the record with the next
highest RID. For an index iterator, the next output record is
the record with the same indexKey but the next highest RID,
or the record with the next highest indexKey if there is no
record with the same indexKey.
If the input iterator is a materialized iterator,
RestoreIteratorState() restores the state of the iterator as the
saved state. If the timestamp of the materialized iterator is
older than the last update time of the tables below the
materialized iterator, the query evaluation plan rooted at the
materialized iterator is re-evaluated and the entire results are
stored in a temporary table again. Then, the state of the
iterator is restored as the saved state. If the record indicated by
the state of the iterator does not exist, the state of the iterator
is restored so as to indicate the next output record. For a sort
iterator, the next output record is the record with the same
sortKey but the next highest RID, or the record with the next
highest sortKey if there is no record with the same sortKey.
For an aggregate iterator, the next output record is the record
with the next highest GID.
Table
A B
1 10
2 20
2 30
2 40
3 50
Group-by
A COUNT(*)
1 1
2 3
3 1
Table
A B
1 10
2 15
2 40
3 50
Table
A B
1 10
3 50
Group-by
A COUNT(*)
1 1
3 1
(a) Original position (b) If (2, 20) and (2,30) are
deleted, and (2, 15) is
inserted
© If all the records whose
GID is 2 are deleted
Group-by
A COUNT(*)
1 1
2 2
3 1
Fig. 8 An example of restoring the state of an aggregate iterator
Fig. 8 shows an example of restoring the state of an
aggregate iterator, which is one of materialized iterators.
Suppose that the current record of the aggregate iterator was
(2, 3) when the browsing state was saved, as shown in Fig.
8(a). Note that the GID of (2, 3) is 2, because the value of the
grouping attribute A is 2. If there is no data change, the
current record is restored as (2, 3). If (2, 20) and (2, 30) are
deleted from the table and (2, 15) is inserted into the table, the
aggregate iterator is re-revaluated and the entire results are
stored in a temporary table again. In this case, the current
record of the aggregate iterator is restored as (2, 2), as shown
in Fig. 8(b), because (2, 2) is the record whose GID is 2. On
the other hand, if (2, 20), (2, 30), and (2, 40) are deleted from
the table, the current record of the aggregate iterator is
restored as (3, 1), as shown in Fig. 8©, because there is no
record whose GID is 2 and (3, 1) is the record with the next
highest GID.
If the input iterator is a pipelined iterator, the
RestoreIteratorState() procedure restores the state of the
iterator using the current records of its child iterators. The
state of a pipelined iterator is restored differently depending
on the type of the iterator.
Fig. 9 shows an example of restoring the state of a join
iterator. Assume that the join iterator is executed using the
indexed nested-loop join algorithm [10]. Suppose that the
current records of the two child iterators are (2, 30) and (2,
300), respectively. If the current records of both the child
iterators are not changed, the current record of the join iterator
is restored as (2, 30, 300), as shown in Fig. 9(a). If (2, 300) is
removed from the table Table2 after the browsing state is
saved, the current record of the right child iterator is restored
as (2, 400). Then, the current record of the join iterator is
determined by joining the current record of the left child
Procedure RestoreBrowsingState(P, B)
Input P: a query evaluation plan
B: the saved browsing state
1: Let r = the root iterator of P;
2: RestoreIteratorState(r, B);
End procedure
Procedure RestoreIteratorState(N, B)
Input N: an iterator
B: the saved browsing state
1: if (N is a table iterator) then
2: Load RID from B;
3: else if (N is an index iterator) then
4: Load (indexKey, RID) from B;
5: else if (N is a sort iterator) then
6: Load (sortKey, RID, timestamp) from B;
7: t = the last update time of the tables below N;
8: if (t > timestamp) then
9: Re-evaluate N and store the result to disk;
10: else if (N is an aggregate iterator) then
11: Load GID from B;
12: t = the last update time of the tables below N;
13: if (t > timestamp) then
14: Re-evaluate N and store the result to disk;
15: else // N is a pipelined iterator
16: for each child iterator C of N do
17: RestoreIteratorState(C, B);
18: end for
19: end if
20: Find the record indicated by the state of N;
21: if (the record is not found) then
22: Make the state indicate the next output record;
23: end if
170 IEEE Transactions on Consumer Electronics, Vol. 57, No. 1, February 2011
iterator (i.e., (2, 30)) with the new current record of the right
child iterator (i.e.., (2, 400)). As a result, the current record of
the join iterator is restored as (2, 30, 400). On the other hand,
if (2, 30) is removed from the table Table1 after the browsing
state is saved, the current record of the left child iterator is
restored as (2, 40). Then, the current record of the join iterator
is determined by joining the new current record of the left
child iterator (i.e., (2, 40)) with the first record in the table
Table2 whose join key value is the same as that of (2, 40) (i.e.,
(2, 200)). As a result, the current record of the join iterator is
restored as (2, 40, 200). In a similar way, the current record of
the other types of pipelined iterators can be restored using the
current records of their child iterators.
Table1
A B
1 10
2 20
2 30
2 40
3 50
Table2
A C
1 100
2 200
2 300
2 400
3 500
? Table1.A = Table2.A
A B C
…
2 30 200
2 30 300
2 30 400
…
Table1
A B
1 10
2 20
2 30
2 40
3 50
Table2
A C
1 100
2 200
2 400
3 500
? Table1.A = Table2.A
A B C
…
2 30 200
2 30 400
2 40 200
…
(a) Original position (b) If (2, 300) is deleted
from Table2
© If (2, 30) is deleted
from Table1
Table1
A B
1 10
2 20
2 40
3 50
? Table1.A = Table2.A
A B C
…
2 20 400
2 40 200
2 40 300
…
Table2
A C
1 100
2 200
2 300
2 400
3 500
Fig. 9 An example of restoring the state of a join iterator
V. FURTHER CONSIDERATIONS
In this section, we describe several additional considerations
for saving and restoring the browsing states.
A. Block-based Iterators
A block-based iterator is an iterator that performs in a
block-by-block way (e.g., block nested loop join iterator)
[10]. Until now, we have considered iterators whose state
includes the information about only a single record. On the
other hand, a block-based iterator maintains several buffers
internally to store a number of records, so they should be
included in the state of the iterator. Fig. 10 shows an
example of a block nested loop join iterator, which is one of
the block-based iterators. The block nested loop join iterator
maintains two buffers internally; the outer buffer for the
outer table and the inner buffer for the inner table. The block
nested loop join operation is executed on the basis of these
two buffers.
In the state of a block-based iterator, in addition to the
current record, we include the information about the first and
last records of each buffer. When the browsing state is saved,
these information are also saved. When the browsing state is
restored, the records between the first and last records of each
buffer are read from the child iterators to fill the buffer. If the
first record of a buffer is removed, the next available record
becomes the first record of the buffer. Similarly, if the last
record of a buffer is removed, the previous available record
becomes the last record of the buffer.
Note that we do not store the buffer itself, but only the
information about the first and last records of the buffer.
This is for the following two reasons: First, if the records in
the buffer are stored on disk, data changes cannot be
reflected to the buffer in the restore process. Second,
dumping the entire buffer takes a long time so that the save
process can be slow.
If the data are changed and the number of records
between the first and last records of a buffer becomes
larger than before, main memory may not be large enough
to keep all the records in the buffer. Furthermore, main
memory can be insufficient because the available memory
itself for the buffer can be varied. In this situation, some
records should be removed from the buffer and
maintained on disk not to break the execution order of the
block-based operations.
Outer buffer
Current
position
The first
record
Outer table Inner table
Current
position
Inner buffer
The first
record
The last
record
The last
record
Fig. 10 The state of a block nested loop join iterator
B. Subquery
The proposed solution can also be applied to subqueries. A
subquery can appear in the WHERE, HAVING, or FROM clause
of a SQL query. If a subquery appears in the WHERE or
HAVING clause, the subquery acts as a condition filter for
each record in the main query. Because all result records of
the subquery should be fetched for each record in the main
query, we don't need to keep track of the current record of the
subquery. Therefore, we do not save the state of the subquery.
If a subquery appears in the FROM clause, the subquery acts
as a table. Thus, in this case, the root iterator of the query
evaluation plan for the subquery is treated as a table iterator.
Therefore, in this case, we save the state of the subquery along
with the state of the main query.
C. Browser Applications
As already mentioned, the proposed solution can be used by
browser applications in multimedia CE devices. A browser
application saves and restores the browsing state to efficiently
handle power-off and data changes made by other applications.
Although the save process incurs additional overhead on the
S. Hong et al.: Fast and Adaptive Browsing State Recovery for Multimedia Consumer Electronics Devices 171
system, the save process takes only an extremely small time,
as will be shown in Section VI. Furthermore, the save process
does not have to be executed on every record fetch. It is
sufficient to execute the save process only in the following
cases:
When the browser screen is changed to a different result
page by the user's interaction.
When the device is turned off.
Because these cases occur only occasionally in practice, our
solution incurs little overhead on the system.