Most efficient way to search for something: query database or loop through ArrayList?

[Wrichik Basu]

This is actually for my new Android app. But everything is written in Java and SQL; there is almost nothing that is specific to Android.

I have a database, and the following three tables are of interest here:

• itemEntity with columns:
  • itemID: integer primary key
  • itemName: String; indexed to be unique.
• categoryListEntity, with columns:
  • categoryID: integer primary key
  • categoryName: String; indexed to be unique.
• itemCategoryEntity, with columns (Composite primary key)
  • itemID (with a Foreign key to itemEntity)
  • categoryID (with a Foreign key to categoryListEntity)

I have to display the item name and its categories (along with some other details of each item) to the user. I have created a class that holds the necessary data for each item. The class looks somewhat like this:

public class ItemData {

    private final String itemName;
    private final ArrayList<String> categories;
    private final ArrayList<Long> packSizes, quantityStock, quantityInUse;

    public ItemData(@NonNull String itemName, @Nullable ArrayList<String> categories,
                                     @Nullable ArrayList<Long> packSizes, @Nullable ArrayList<Long> quantityStock,
                                     @Nullable ArrayList<Long> quantityInUse) {
        this.itemName = itemName;
        this.categories = categories;
        this.packSizes = packSizes;
        this.quantityStock = quantityStock;
        this.quantityInUse = quantityInUse;
    }
   
    // Getters omitted for simplicity
   
}

As you can see, each instance of this class is for one item. I haven't included the itemID and categoryIDs, because they won't be displayed to the user. In addition, one item can have more than one category. The class instances are created by reading data from the database; there is an ArrayList<ItemData> itemDataList that contains all such objects. In Android, this list is used to display the items to the user. Also, assume that this list has a large number of items.

I want to carry out some search queries. For example, I may want to find all the items that have a certain category, or I may want to find all items that start with some specific characters. Note that in order to display the filtered items to the user, I have to pass an itemDataList with only those filtered items. I have two options for doing this:

1. Loop through the old itemDataList, find the items which have that particular category or start with some specific letters, put them into a new list, and pass that to Android.
2. Directly search the database, create a new (or recreate the old) itemDataList, and pass that to Android.

I want to show search results as soon as the user is typing. So, with each letter the user types, the results will change.

1. If I choose option 1, I will have to use loops. Sometimes I will have to use more than one loops (for example, when I want to search the list of categories for each item). This is often considered inefficient.
2. Database queries are often resource-consuming (and preferably should be done in child threads and not the UI thread), because I will have to read from the internal storage. For small databases, it doesn't matter, but for a sufficiently large database, it will consume a lot of system resources if I continuously query the database for each letter the user types. Plus, I am not retrieving one column; I am retrieving a total of four columns each time I query.

So, which will be faster, and which is efficient? Can speed and efficiency be combined?

 

[pbuk]

I assume you are using Android's builtin SQLlite implementation: this obviously is specific to Android and the answers will differ for other implementations.

Generally speaking, queries that use an appropriately indexed database are faster and consume less resources than userspace code. This will almost certainly be the case for

I may want to find all the items that have a certain category

but

, or I may want to find all items that start with some specific characters.

introduces issues of UTF-8 character equivalence and other complications so YMMV.

1. Loop through the old itemDataList, find the items which have that particular category or start with some specific letters, put them into a new list, and pass that to Android.
2. Directly search the database, create a new (or recreate the old) itemDataList, and pass that to Android.

What do you mean 'pass that to Android'? Is this actually a client-server webapp not an Android app? If that is the case then your performance will be entirely dependent on network latency and all other considerations are irrelevant.

 

[Wrichik Basu]

I assume you are using Android's builtin SQLlite implementation

To be exact, I am using Room to connect to and query the database. Room is a layer of abstraction over SQLite so that the developer does not have to directly deal with Cursor (which is very prone to NullPointerException).

What do you mean 'pass that to Android'? Is this actually a client-server webapp not an Android app?

No, not client-server app. Actually I will pass that ArrayList to an adapter that extends Android RecyclerView.Adapter class. The adapter is, in turn, responsible for setting the view by reading the ArrayList.

 

[pbuk]

OK, so in that case the answer is 'it depends'. It is obiously going to be quicker to eliminate one entry from a list of 1,000,000 entries in a Java array than to query the 999,999 remaining ones anew, conversely it is going to be quicker to retrieve 1 entry from an abstraction over a well indexed SQLlite table than to sequentially search for 1 entry in a 1,000,000 entry Java array. Somewhere in the middle there will be no difference, and this will vary depending on the hardware and what else is running on it at the time.

 

[pbuk]

IME this question does not arise in practice because you don't cache the full query results in an array, you are working with a LIMITed set with something like the following pseudocode:

inputHandler(event)
  // Don't query until we have meaningful input.
  if event.data.length < 3 return
  query = "SELECT id, name FROM categories WHERE name SOUNDS LIKE ? LIMIT 5"
  try
    // Query the DB asynchronously.
    result = wait for
      execute query with event.data
    // Display up to 5 query results to the user.
  catch err
    // Handle exception.

// Let the user finish typing before firing the handler.
bind debounce(inputHandler, ONE_SECOND) to userInput

 

[bhobba]

I have done both - even a hybrid one. Here is how the hybrid worked. I initially searched the database and the program was returned by the computer operation staff as running too long. So what I did was keep pointers and put them at the end of an array as I went along. It reduced running time considerably. So my advice is to try searching the database, but if that takes too long use a buffer you search first.

Thanks
Bill