Question: Complexity Class for a Wildcard MySQL Search


Complexity Class for a Wildcard MySQL Search

Answers 1
Added at 2017-11-30 17:11

I have two mysql tables. In one table is the actual data (of a product for example) and in another are tags. Each product can have an unlimited amount of tags. So there are two ways, to save the relationship of the tags to the product.

My way is to use a third table to store the relationship. Just Product_id and Tag_id. That's it. My colleague want to create a text column in the product Table and save comma separated IDs of the Tags in the field. And if some one is looking for products with a specific tag, he want to run a full text (wildcard) search. He says, that he need only one DB Query for the Data. Instead I need three.

My opinion is, that I need three queries. One in the complexity of O(n) = n log n for the search and two of the complexity of O(n) = 1 for the direct fetching of data. A wildcard full text search is much more expensive.

What's your opinion?

Answers to

Complexity Class for a Wildcard MySQL Search

nr: #1 dodano: 2017-11-30 18:11

Using a join table is in most cases the correct answer, although both would work. Using a join table you'd find products with a single query such as:

class Product < ApplicationRecord
  has_many :product_tags
  has_many :tags, through :product_tags

class ProductTag < ApplicationRecord
  belongs_to :product
  belongs_to :tag

class Tag < ApplicationRecord
  has_many :product_tags
  has_many :products, through: :product_tags

Product.joins(:tags).where(tags: { name: "SEARCHEDTAG" })

Generally, wildcard text queries are much slower than joins with indexes.

Source Show
◀ Wstecz