facetnav-mr.js

// facetnav-mr.js
//
// Jon Rangel
// August 2013
//
// MongoDB Map-Reduce code to pre-compute faceted search navigation 
// meta-data from a product catalog.
//
// Documents in the collection on which this code operates (the product 
// catalog) should have the following schema:
//
// {
//     "_id" : 123,
//     "facets" : {
//         "<facet1_name>" : [
//             "<facet1_val1>",
//             "<facet1_val2>",
//             ...
//         ],
//         "<facet2_name>" : [
//             "<facet2_val1>",
//             ...
//         ],
//         ...
//     },
//     ...
// }
//
// Documents in output collection generated by this code will have the 
// following schema:
//
// {
//     "_id" : "<facet_filter_string>",
//     "value" : {
//         "count" : 12,
//         "facets" : {
//             "<facet1_name>" : {
//                 "<facet1_val1>" : 8,
//                 "<facet1_val2>" : 12,
//                 ...
//             },
//             "<facet2_name>" : {
//                 "<facet2_val1>" : 5,
//                 ...
//             },
//             ...
//         }
//     }
// }
//
// where <facet_filter_string> is either the empty string (for the document
// representing the root of the faceted navigation) or one or more of
// "|<facet_name>:<facet_filter_val>|" concatenated together.



var mapFn = function() {

    function emitFn(key, other_facets) {
        var value = { "count" : 1 };

        if (other_facets != null) {
            for (var i = 0; i < other_facets.length; i++) {
                var fname = other_facets[i][0];
                var tag_array = other_facets[i][1];

                for (var j = 0; j < tag_array.length; j++) {
                    var tag = tag_array[j];

                    if (!("facets" in value)) {
                        value["facets"] = {};
                    }
                    if (!(fname in value["facets"])) {
                        value["facets"][fname]  = {};
                    }

                    value["facets"][fname][tag] = 1;
                }
            }
        }

        emit(key, value);
    }

    function updateFacetFilters(filter_facets, other_facets) {

        // Return the cartesian product of one or more intput arrays.
        // e.g. cartesianProduct([[1,2],[3,4]]) returns [[1,3],[1,4],[2,3],[2,4]]
        function cartesianProduct(input_arrays) {
            return Array.prototype.reduce.call(input_arrays, function(a, b) {
                var ret = [];
                a.forEach(function(a) {
                    b.forEach(function(b) {
                        ret.push(a.concat([b]));
                    });
                });
                return ret;
            }, [[]]);
        }

        if (filter_facets == null) {
            // Special case for handling the 'root' of the faceted navigation
            // i.e. no filters applied
            emitFn("", other_facets);
        } else {
            // Massage the function input into an array of facet names
            // and an array containing an array of facet values for each facet.
            var filter_facets_n = [];
            var filter_facets_v = [];
            for (var i = 0; i < filter_facets.length; i++) {
                filter_facets_n.push(filter_facets[i][0]);
                filter_facets_v.push(filter_facets[i][1]);
            }

            var product = cartesianProduct(filter_facets_v);
            for (var i = 0; i < product.length; i++) {
                var filter_combo = product[i];
                assert(filter_combo.length == filter_facets_n.length);

                // Build the key for this particular combination of facet
                // filter values, and pass the key and other facets into
                // the emit function.
                var key = "|";
                for (var j = 0; j < filter_combo.length; j++) {
                    key += filter_facets_n[j] + ":" + filter_combo[j] + "|";
                }
                emitFn(key, other_facets);
            }
        }
    }

    // @@@ TODO:  The rest of the code in this function could be made more
    // generic i.e. have some generic code to do the combinatorics
    // instead of hard-coding an array of all the combinations.
    // Not too much of a big deal though if the number of facets is small
    // and changes rarely.

    // Collate all the facet values for this item.
    var facets = [["subject"],
                  ["publisher"],
                  ["language"]];

    for (var i = 0; i < facets.length; i++) {
        if (facets[i][0] in this["facets"]) {
            facets[i][1] = this["facets"][facets[i][0]];
        } else {
            facets[i][1] = [];
        }
    }

    var subject_facet = facets[0];
    var publisher_facet = facets[1];
    var language_facet = facets[2];

    // Array of facet filter combinations.
    // Each element in the array is as follows:
    // [[<filter facets>],[<other remaining facets>]]
    // Each ordered combination follows the canonical ordering
    // Subject, Publisher, Language.
    facet_filter_combinations = [
        // Root
        [null, [subject_facet, publisher_facet, language_facet]],

        // Subject facet filters
        [[subject_facet], [publisher_facet, language_facet]],
        // Publisher facet filters
        [[publisher_facet], [subject_facet, language_facet]],
        // Language facet filters
        [[language_facet], [subject_facet, publisher_facet]],

        // (Subject, Publisher) facet filters
        [[subject_facet, publisher_facet], [language_facet]],
        // (Subject, Language) facet filters
        [[subject_facet, language_facet], [publisher_facet]],
        // (Publisher, Language) facet filters
        [[publisher_facet, language_facet], [subject_facet]],

        // (Subject, Publisher, Language) facet filters
        [[subject_facet, publisher_facet, language_facet], null]
    ];

    // Now update the facetnav for all combinations of filters.
    for (var i = 0; i < facet_filter_combinations.length; i++) {
        updateFacetFilters(facet_filter_combinations[i][0],
                           facet_filter_combinations[i][1]);
    }
}


var reduceFn = function(key, values) {
    var res = { "count": 0 };

    // Iterate over each of the values to reduce.
    for (var i = 0; i < values.length; i++) {
        var value = values[i];

        // Sum the counts together.
        res["count"] += value.count;

        // Now process the facet values.
        // First check if we have any facets to process.
        if ("facets" in value) {
            if (!("facets" in res)) {
                res["facets"] = {};
            }

            // For each facet, add the facet values to a set
            // and merge the per-facet-value counts.
            for (var fname in value["facets"]) {
                // 'tags' is a document mapping tag name to count
                var tags = value["facets"][fname]

                if (!(fname in res["facets"])) {
                    res["facets"][fname] = {};
                }

                for (var tag in tags) {
                    if (!(tag in res["facets"][fname])) {
                        res["facets"][fname][tag] = 0;
                    }

                    res["facets"][fname][tag] += tags[tag];
                }
            }
        }
    }

    return res;
}